Aurora招新赛——关于mod

Crypto

Word count: 1.3kReading time: 6 min

 2020/03/20   Share

这道题充分反应了我的密码学是白学的，总共花的时间肯定24h+。
先看题目脚本

#second.py
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
from Crypto.Random.random import *
from flag import flag


Au = getStrongPrime(1024)
AuAu = getStrongPrime(1024)
AuAuAu = getStrongPrime(1024)


def AuAuAuAu(Au, AuAu):
    while AuAu: Au, AuAu = AuAu, Au % AuAu
    return Au


def AuAuAuAuAu(Au, AuAu, AuAuAu):
    AuAuAuAu = 1
    while AuAu != 0:
        if (AuAu & 1) == 1:
            AuAuAuAu = (AuAuAuAu * Au) % AuAuAu
        AuAu >>= 1
        Au = (Au * Au) % AuAuAu
    return AuAuAuAu


AuAuAuAuAuAuAuAu = AuAuAuAuAu(AuAuAu, Au, AuAu)
while True:
    AuAuAuAuAuAuAuAuAu = randint(1, 2 ** 512)
    if AuAuAuAu(AuAuAuAuAuAuAuAuAu, AuAu - 1) == 1:
        break
AuAuAuAuAuAu = bytes_to_long("AuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAu")
AuAuAuAuAuAuAuAuAuAu = AuAuAuAuAu(AuAuAu, AuAuAuAuAuAuAuAuAu, AuAu)
AuAuAuAuAuAuAuAuAuAuAu = (AuAuAuAuAuAu * AuAuAuAuAu(AuAuAuAuAuAuAuAu, AuAuAuAuAuAuAuAuAu, AuAu)) % AuAu
AuAuAuAuAuAuAu = bytes_to_long(flag)
AuAuAuAuAuAuAuAuAuAuAuAu = (AuAuAuAuAuAuAu * AuAuAuAuAu(AuAuAuAuAuAuAuAu, AuAuAuAuAuAuAuAuAu, AuAu)) % AuAu
with open('cipher_second.txt', 'w') as f:
    f.write("AuAuAuAuAuAuAuAuAuAu = " + str(AuAuAuAuAuAuAuAuAuAu) + "\n")
    f.write("AuAuAu = " + str(AuAuAu) + "\n")
    f.write("AuAuAuAuAuAuAuAuAuAuAu = " + str(AuAuAuAuAuAuAuAuAuAuAu) + "\n")
    f.write("AuAu = " + str(AuAu) + "\n")
    f.write("AuAuAuAuAuAuAuAuAuAuAuAu = " + str(AuAuAuAuAuAuAuAuAuAuAuAu) + "\n")
    
其中cipher_second.txt：
AuAuAuAuAuAuAuAuAuAu = 24060165536084067979813052960543411990367073733053765644699769988102126301607236684736234516917540119724097667932884475795898871957309932809071146014543460692909352480408824618517714722984771049822684175641847290185361834032033919030884844384627328802352161436308308068681230733830014160613566516126913599679
AuAuAu = 168230812504917132822031239630078220399074310356381999181653517650324353404279211761461822712544278210131581579847841070580950397484038230733404459908782058900591709322993519389006100884788751465393449665892538579778559870105753578478869369578539551683426350885553541430608204655262429792813559526327112757307
AuAuAuAuAuAuAuAuAuAuAu = 6176793597133333153104561382047091578706459334173172854358730376866346466693739263599908820647251113062601080198894369117388276661115933812633716068890695100939879884301897876409847467119800293136643838117806130141030659269692031448283847911409126502025196469087884093076807854121717604528435136002415867083
AuAu = 167908172755079385864716897695513030660553919301934409681210763749727536722398027958629268482499100608025554396933773154683645615083120905283181619647906045358631174674237455242955211996165382972055067541620477170429863892848862127083204138236540038524086429614874555987063767766002782758903781175206444000363
AuAuAuAuAuAuAuAuAuAuAuAu = 105084272748264545777918765251804955981747011423695761842563445096939882269112639284807907661779031158819140579730636212690913001865142790989296999645422093830570725060828634302857073362387686345561952108096388797147863938775327062182858148523836274897976493706637533409419483577687121544409394830323932412378

可以看到一堆密密麻麻的Au，我们要想怎么把这堆碍眼的Au换成简洁的表现形式。

#首先是AuAuAuAu，白学之一，我没有看出是gcd
def AuAuAuAu(Au, AuAu):
    while AuAu: Au, AuAu = AuAu, Au % AuAu
    return Au
    
#如果看出是gcd，那就解决了AuAuAuAu，
def gcd(Au, AuAu):
    while AuAu: Au, AuAu = AuAu, Au % AuAu
    return Au

#然后是AuAuAuAuAu,白学之二，没有看出是pow
def AuAuAuAuAu(Au, AuAu, AuAuAu):
    AuAuAuAu = 1
    while AuAu != 0:
        if (AuAu & 1) == 1:
            AuAuAuAu = (AuAuAuAu * Au) % AuAuAu
        AuAu >>= 1
        Au = (Au * Au) % AuAuAu
    return AuAuAuAu
关键在于AuAuAuAu = (AuAuAuAu * Au) % AuAuAu
AuAu是指数项，在while循环中不断右移一位，每右移一位Au就自乘一次，最后AuAu等于1，也就是累乘完了，进入if语句， 模上AuAuAu

#所以如果看出是pow。那就解决了AuAuAuAuAu
def pow(Au, AuAu, AuAuAu):
    AuAuAuAu = 1
    while AuAu != 0:
        if (AuAu & 1) == 1:
            AuAuAuAu = (AuAuAuAu * Au) % AuAuAu
        AuAu >>= 1
        Au = (Au * Au) % AuAuAu
    return AuAuAuAu

那题中的代码怎么简约化呢？
大概是照着rsa的思路，pow的元素用p(q、m、c)、e、n的元素替换
在这里用p

# -*- coding: utf-8 -*-
from Crypto.Util.number import *
from Crypto.Random.random import *
flag = b"flag{test}"


e0 = getStrongPrime(1024)
n = getStrongPrime(1024)
p = getStrongPrime(1024)


def gcd(Au, AuAu):
    while AuAu: Au, AuAu = AuAu, Au % AuAu
    return Au


def _pow(Au, AuAu, AuAuAu):
    AuAuAuAu = 1
    while AuAu != 0:
        if (AuAu & 1) == 1:
            AuAuAuAu = (AuAuAuAu * Au) % AuAuAu
        AuAu >>= 1
        Au = (Au * Au) % AuAuAu
    return AuAuAuAu


tmp = _pow(p, e0, n)
while True:
    e1 = randint(1, 2 ** 512)
    if gcd(e1, n - 1) == 1:
        break
y = bytes_to_long("AuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAu")
print (y)
r2 = _pow(p, e1, n)
r0 = (y * _pow(tmp, e1, n)) % n
x = bytes_to_long(flag)
r1 = (x * _pow(tmp, e1, n)) % n
with open('cipher_second.txt', 'w') as f:
    f.write("r2 = " + str(r2) + "\n")
    f.write("p = " + str(p) + "\n")
    f.write("r0 = " + str(r0) + "\n")
    f.write("n = " + str(n) + "\n")
    f.write("r1 = " + str(r1) + "\n")

看到关键的几行代码

y = bytes_to_long("AuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAu")
print (y)
r2 = _pow(p, e1, n)
r0 = (y * _pow(tmp, e1, n)) % n
x = bytes_to_long(flag)
r1 = (x * _pow(tmp, e1, n)) % n

也就是可以得到y、r2、p、r0、n、r1的值，通过这些值算出x，也就是flag
我们把_pow(tmp, e1, n)看成一个整体，令他为m，则

y = bytes_to_long("AuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAuAu")
print (y)
r2 = _pow(p, e1, n)
r0 = (y * m) % n
x = bytes_to_long(flag)
r1 = (x * m) % n

对于r0 = (y * m) % n
由于我们知道r0，y，n的值，先通过求y模n的乘法逆元，然后可以求得m

$y*y^{-1} mod\ n \equiv 1$ $r0 = (y * m) mod \ n$

两边同乘$y^{-1}$
修改：乍的一看应该是下面的形式

$r0*y^{-1}=m$

其实正确的换算应该是

$m= (r0*y^{-1}) mod\ n$

也就是最关键的两个式子

$ (a+b) mod\ n =t $
$ a= (t-b)mod\ n $

$(ab) mod\ n=t$
$ a=(tb^{-1})mod\ n$

def inverse(u, v):
    """The inverse of :data:`u` *mod* :data:`v`."""

    u3, v3 = u, v
    u1, v1 = 1, 0
    while v3 > 0:
        q = u3 // v3
        u1, v1 = v1, u1 - v1*q
        u3, v3 = v3, u3 - v3*q
    while u1<0:
        u1 = u1 + v
    return u1
r0=6176793597133333153104561382047091578706459334173172854358730376866346466693739263599908820647251113062601080198894369117388276661115933812633716068890695100939879884301897876409847467119800293136643838117806130141030659269692031448283847911409126502025196469087884093076807854121717604528435136002415867083
y = 10074912914213508631420765620784413466570858181966727547338209393071573353551213217600806586299023901625034946724213
n = 167908172755079385864716897695513030660553919301934409681210763749727536722398027958629268482499100608025554396933773154683645615083120905283181619647906045358631174674237455242955211996165382972055067541620477170429863892848862127083204138236540038524086429614874555987063767766002782758903781175206444000363
y_1 = inverse(y,n)
print (y_1) #求的y_1=120767757203578958585210106506900279530835092509275728786231189395197507531904275958501922794442252435531213382775156423807602446647054208285509617674318837456248330316405345069426057993321987160964922736621609954589723551844808673253402882502617206659891254447111831101800356683494544318645779132033417689137
m=(r0*y_1)%n
print (m)#m=132288743457835124151763401161601136907232894311021370371623222730229965405368291422424437262673460775173730282236255189029014525871960648079266980732282548692001577699250628330231029750069436541928513960555755217516146983366830366524305382207680448780159762592623162523952789378857095230406698398161513875033

修改：下面这一part是最初没有简单无用的分析
这里应该还是要考虑到数字大小，不知道为什么
由于$m=r0*y^{-1}$ >>$n、r0$ >> $y$
如果知道r0，m，n的值，想通过求m模n的乘法逆元，再求得y
得到的结果需要模一次n，也就是

$m*m^{-1} mod\ n \equiv 1$ $r0 = (y * m) mod \ n$

两边同乘$m^{-1}$

$r0*m^{-1}=q$ $q mod \ n =y$

因此，在求flag的时候就需要模多一次n
对于r1 = (x * m) % n
由于我们知道r1，m，n的值，类似的，先通过求m模n的乘法逆元，然后可以求得x

$m*m^{-1} mod\ n \equiv 1$ $r1 = (x * m) mod \ n$

两边同乘$m^{-1}$

$r1*m^{-1}=q$ $q mod \ n =x$

m=745957509435219482734373253804065981190948437248355256150465242442432959045431082969859790720189299044887304311722294690152135839444419143214225213328407525753297755021918427145980049335533779804728785413269062910067309714052603591286688787620248422230483101998934871770529606844223269545467008437232325215908344786459547781392201492805051480246088158164570526005111371529954392879157843010695015939697102297822823152011929046829089244920809488280319679486696992650250433965732956012223732584167766555822478417782403940234311102211185014412371857788936016990149145449451013424482481542514501793884162283176004977371
r1=105084272748264545777918765251804955981747011423695761842563445096939882269112639284807907661779031158819140579730636212690913001865142790989296999645422093830570725060828634302857073362387686345561952108096388797147863938775327062182858148523836274897976493706637533409419483577687121544409394830323932412378
n = 167908172755079385864716897695513030660553919301934409681210763749727536722398027958629268482499100608025554396933773154683645615083120905283181619647906045358631174674237455242955211996165382972055067541620477170429863892848862127083204138236540038524086429614874555987063767766002782758903781175206444000363
m_1 = inverse(m,n)
print (m_1) #pe0e1_1=19706179920600360885968620517595985375134457548794618756250071204517642343613121420780533457897131183638061174880584305539325536367809880091359294059526662451356875890079226688005841695211753359322882824625946215219643410127813143165996979983929806369787299898197876211308675510037223001230160576100468732937
x=(m_1*r1)%n
print (x) #x=6269705279244416808234713583799989269823960623996760701
flag=long_to_bytes(x)
print (flag) #print ("flag:(%s)" %(flag))
#b'Aurora{did_not_enctypr}'

修改：
m=132288743457835124151763401161601136907232894311021370371623222730229965405368291422424437262673460775173730282236255189029014525871960648079266980732282548692001577699250628330231029750069436541928513960555755217516146983366830366524305382207680448780159762592623162523952789378857095230406698398161513875033
r1=105084272748264545777918765251804955981747011423695761842563445096939882269112639284807907661779031158819140579730636212690913001865142790989296999645422093830570725060828634302857073362387686345561952108096388797147863938775327062182858148523836274897976493706637533409419483577687121544409394830323932412378
n = 167908172755079385864716897695513030660553919301934409681210763749727536722398027958629268482499100608025554396933773154683645615083120905283181619647906045358631174674237455242955211996165382972055067541620477170429863892848862127083204138236540038524086429614874555987063767766002782758903781175206444000363
m_1 = inverse(m,n)
print (m_1) #pe0e1_1=19706179920600360885968620517595985375134457548794618756250071204517642343613121420780533457897131183638061174880584305539325536367809880091359294059526662451356875890079226688005841695211753359322882824625946215219643410127813143165996979983929806369787299898197876211308675510037223001230160576100468732937
x=(m_1*r1)%n
print (x) #x=6269705279244416808234713583799989269823960623996760701
flag=long_to_bytes(x)
print (flag) #print ("flag:(%s)" %(flag))

可以看到全程不用处理tmp和m

解决python3 无法直接bytes_to_long的方法
进入文件\python\lib\site-packages\Crypto\Util\number.py中

定位到def bytes_to_long(s):
将
for i in range(0, length, 4):
    acc = (acc << 32) + unpack('>I', s[i:i+4])[0]
return acc
替换为
for i in range(0, length, 4):
    if isinstance(s[i:i+4],str):
        acc = (acc << 32) + unpack('>I', s[i:i+4].encode())[0] 
    else:
        acc = (acc << 32) + unpack('>I', s[i:i+4])[0]
return acc

Author：DGZ

原文链接：https://dgz-cyber.github.io/2020/03/20/Aurora%E6%8B%9B%E6%96%B0%E8%B5%9B%E2%80%94%E2%80%94%E5%85%B3%E4%BA%8Emod/

发表日期：March 20th 2020, 6:45:56 am

更新日期：April 5th 2020, 12:21:56 am

Next Post

BJDCTF WP - MISC、CRYPTO、RE
Previous Post

烤鸡翅（根）及烤蛋挞液记录

CATALOG

