这次比赛太惨了，终究还是我太次了呀。一道密码都没出，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 = 0
for i in range(len(a0)-len(b0)):
ans = ans*10+a0[i]-48
for i in range(len(b0)):
ans = ans*10+(a0[i+len(a0)-len(b0)]+b0[i]+4)%10
return ans
def mul(a,b):
if(a<b):
a0 = str(b).encode()
b0 = str(a).encode()
else:
a0 = str(a).encode()
b0 = str(b).encode()
ans = 0
for i in range(len(b0)):
ans = ans*10+((a0[i+len(a0)-len(b0)]+2)*(b0[i]+2))%10
return ans
m = 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==a
(x+y)%10==a,
(
x
?
y
)
%
10
=
=
b
(x*y)\%10==b
(x?y)%10==b? 的（x,y）
Ⅱ.验证
将x,y添到（p,q）中，后将p和q相乘，判断
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 = 49042009464540753864186870038605696433949255281829439530955555557471951265762643642510403828448619593655860548966001304965902133517879714352191832895783859451396658166132732818620715968231113019681486494621363269268257297512939412717227009564539512793374347236183475339558666141579267673676878540943373877937
def 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)
p = int('1' + str(pq0[1][0]))
q = pq0[1][1]
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重置再用来存放新的所有可能。
四、总结
这题，想到了方法，但自己没能实现，卡在了回溯，可又不需要回溯（🤡竟是我自己），太菜了太菜了。还是看了别人现成脚本改的，需要更加努力啊。
|