2021长安杯-高校组-Crypto-easyrsa-Wp

这次比赛太惨了，终究还是我太次了呀。一道密码都没出，esayrsa一点也不easy，这题还是赛后一个半小时候后出的。

一、题目

from Crypto.Util.number import *def add(a,b):if(a<b):a0 = str(b).encode()b0 = str(a).encode()else:a0 = str(a).encode()b0 = str(b).encode()ans = 0for i in range(len(a0)-len(b0)):ans = ans*10+a0[i]-48for i in range(len(b0)):ans = ans*10+(a0[i+len(a0)-len(b0)]+b0[i]+4)%10return ansdef mul(a,b):if(a<b):a0 = str(b).encode()b0 = str(a).encode()else:a0 = str(a).encode()b0 = str(b).encode()ans = 0for i in range(len(b0)):ans = ans*10+((a0[i+len(a0)-len(b0)]+2)*(b0[i]+2))%10return ansm = bytes_to_long(flag)
e = 65537
p = getPrime(512)
q = getPrime(512)
n = p*q
c = pow(m,e,n)
print(add(p,q))
print(mul(p,q))
print(n)
print(c)
''' 10399034381787849923326924881454040531711492204619924608227265350044149907274051734345037676383421545973249148286183660679683016947030357640361405556516408 6004903250672248020273453078045186428048881010508070095760634049430058892705564009054400328070528434060550830050010084328522605000400260581038846465000861 100457237809578238448997689590363740025639066957321554834356116114019566855447194466985968666777662995007348443263561295712530012665535942780881309520544097928921920784417859632308854225762469971326925931642031846400402355926637518199130760304347996335637140724757568332604740023000379088112644537238901495181 49042009464540753864186870038605696433949255281829439530955555557471951265762643642510403828448619593655860548966001304965902133517879714352191832895783859451396658166132732818620715968231113019681486494621363269268257297512939412717227009564539512793374347236183475339558666141579267673676878540943373877937 '''

二、分析

1.add()函数

add()函数功能是将a和b相加但不进位，应该可以算是半加吧

懂得都懂~

2.mul()函数

mul()函数功能和add()函数功能类似，对应位两数相乘但不进位

嗯，懂得都懂！

3.解题思路

其实这题和之前的中海大校赛和第五空间那个异或题类似。

那个异或题告诉我们p^q，然后就是暴力搜索，依靠n来验证。

这题也一样，知道add和mul可以分解出每个位子上可能的数，然后暴力组合再相乘用n来验证。

然后拿了异或那题的脚本改一改，改出来了。

Ⅰ.分解

在0~9中寻找满足$(x+y)\%10==a$,$(x?y)\%10==b$? 的（x,y）

Ⅱ.验证

将x,y添到（p,q）中，后将p和q相乘，判断$p?q$的低位是否等于n的低位（低位长度为p或q的长度）

若相等，则p,q则是可能的值。

为啥这样验证，我懂但讲不明白，终究还是太菜了

Ⅲ.储存

创建列表pq0，用来保存当前一步所有可能的（p,q）.

三、题解

from Crypto.Util.number import *
from gmpy2 import *a = 10399034381787849923326924881454040531711492204619924608227265350044149907274051734345037676383421545973249148286183660679683016947030357640361405556516408
b = 6004903250672248020273453078045186428048881010508070095760634049430058892705564009054400328070528434060550830050010084328522605000400260581038846465000861
n = 100457237809578238448997689590363740025639066957321554834356116114019566855447194466985968666777662995007348443263561295712530012665535942780881309520544097928921920784417859632308854225762469971326925931642031846400402355926637518199130760304347996335637140724757568332604740023000379088112644537238901495181
c = 49042009464540753864186870038605696433949255281829439530955555557471951265762643642510403828448619593655860548966001304965902133517879714352191832895783859451396658166132732818620715968231113019681486494621363269268257297512939412717227009564539512793374347236183475339558666141579267673676878540943373877937def adddddddd(k, p0, q0):if (p0 * q0) % (10 ** (k + 1)) == n % (10 ** (k + 1)):pq0.append((p0, q0))a0 = str(a)
b0 = str(b)
pq0 = [(0, 0)]
for k in range(len(b0)):pq, pq0 = pq0, [(0, 0)]for i in range(10):for j in range(10):if (i + j) % 10 == int(a0[-k - 1]) and (i * j) % 10 == int(b0[-k - 1]):for (p, q) in pq:p = (p + i * 10 ** k)q = (q + j * 10 ** k)adddddddd(k, p, q)
#print(pq0)
p = int('1' + str(pq0[1][0]))
q = pq0[1][1]
#p=12092931636613623040737253079065768977037831274116990695362696899634198318309588587556607732878944639910799730236593646983127255905400637167879667181506829
#q=8307103755174226983699771812499382664784661030503034013965679561410051699975573257899430944515587916063550418050690024796566861042630720583592848475010689
#print(isPrime(p))
phi = (p - 1) * (q - 1)
d = inverse(65537, phi)
print(long_to_bytes(pow(c, d, n)))

exp中我觉得最典的就是

pq, pq0 = pq0, [(0, 0)]

这玩意属实没想到，将所有可能放到pq0中，然后将pq0拷贝到pq中用来进行下一步，pq0重置再用来存放新的所有可能。

四、总结

这题，想到了方法，但自己没能实现，卡在了回溯，可又不需要回溯（?竟是我自己），太菜了太菜了。还是看了别人现成脚本改的，需要更加努力啊。