文章目录
- 题目
- 解题过程
题目
from Crypto.Util.number import *
from gmpy2 import *flag = b'xxx'
t = len(flag)//3
part1 = bytes_to_long(flag[:t])
part2 = bytes_to_long(flag[t:2*t])
part3 = bytes_to_long(flag[2*t:])
q = getPrime(1024)
p = next_prime(q)
n = p * qo = getPrime(11)
r = pow(part1, o, p)
z = pow(part2, o, p)h1 = (13 * o + 14 * r + r * z + o * z ** 13) % p
h2 = (o ** 13 + r ** 12 + 3 * o * r + o * z * 233) % p
h3 = pow(part3,65537,n)print(f'n = {n}')
print(f'h1 = {h1}')
print(f'h2 = {h2}')
print(f'h3 = {h3}')# n = 10850335281775104384842309756387507121367947910896225110655535291748404338588972388693259827067445607230128971155491201985083085890729703137967791325100758142692285049056390126354246953310462082980059949946896088251642305978444680455930662301007461492978866538439458231120357274252592800042668860820459885960472737650446805378098344941597805604577797736381125259746781740429143953876454912647201590679786164678547559344304709889497251430904453036692562053570137262921657887410908992378188055660327282373869435308218926170927366572909858720457530661616332620263301130036238239402855045548920085800254012799063199438351
# h1 = 68971374440570454964336249870184699116849273092766598492393855724166755705038579719086135125490382149633066088736614770735555426661202444613481222308690955829177344713094803125405000495549811601138114210065623933916822257443366983845366477473811412048210602195672314631662681949260715610527325398006214477393
# h2 = 89557070262276493140173989636483552685176823962865601733383032051273942127575151309428084885522955047935745792156087951603894535351765100905696886714983834431355512680521411571740092935206188975497781396247799052916245218545834226095135276633422884113241438747017792108934964361391672183324214279475682695463
# h3 = 1311626365146856567785446974305480952394390450877042514912868019585929680223703697129400820765966547191027907141852232429577556122050933660875292235305985538892538821817570539411355339774474418018682334787217004485252794403892893871864009361554731318803763221581009731474777526380398647174787569510518293833348676730943915073911916070766302422834190969513630361764429111809259665372926096307389623440860840605142551951919723403665762066543095024186705959708920942727754417048332722263643582752118944418881587666520088786189326167958303315156763867706697503512512849397447463575294489956813935149823414834222869976238
解题过程
根据题目代码p = next_prime(q)
可知,p
和q
相邻,直接对n
开方然后取下一个素数,直到被n
整除为止,此时的p
为所求。之后简单RSA解密即可求得flag3
#sage
n = 10850335281775104384842309756387507121367947910896225110655535291748404338588972388693259827067445607230128971155491201985083085890729703137967791325100758142692285049056390126354246953310462082980059949946896088251642305978444680455930662301007461492978866538439458231120357274252592800042668860820459885960472737650446805378098344941597805604577797736381125259746781740429143953876454912647201590679786164678547559344304709889497251430904453036692562053570137262921657887410908992378188055660327282373869435308218926170927366572909858720457530661616332620263301130036238239402855045548920085800254012799063199438351
p_near = gmpy2.iroot(n,2)[0]
while n%p_near!=0:p_near = gmpy2.next_prime(p_near)
p = p_near
q = n//p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m3 = pow(h3,d,n)
flag3 = long_to_bytes(int(m3))
接下来,我们已知条件
h 1 = 13 ∗ o + 14 ∗ r + r ∗ z + o ∗ z 13 m o d p h_1 = 13*o+14*r+r*z+o*z^{13} \space mod \space p h1=13∗o+14∗r+r∗z+o∗z13 mod p
h 2 = o 13 + r 12 + 3 ∗ o ∗ r + 233 ∗ z ∗ o m o d p h_2 = o^{13}+r^{12}+3*o*r+233*z*o \space mod \space p h2=o13+r12+3∗o∗r+233∗z∗o mod p
对 h 2 h_2 h2变换,可得
⇒ 233 ∗ o ∗ z = ( h 2 − o 13 − r 12 − 3 ∗ o ∗ r ) m o d p \Rightarrow 233*o*z = (h_2-o^{13}-r^{12}-3*o*r) \space mod \space p ⇒233∗o∗z=(h2−o13−r12−3∗o∗r) mod p
⇒ z = ( h 2 − o 13 − r 12 − 3 ∗ o ∗ r ) ∗ ( 233 ∗ o ) − 1 m o d p \Rightarrow z = (h_2-o^{13}-r^{12}-3*o*r)*(233*o)^{-1} \space mod \space p ⇒z=(h2−o13−r12−3∗o∗r)∗(233∗o)−1 mod p
当o
已知时,z
是一个在模p
下关于r
的等式(等下会用到)
那么,我们利用 h 1 h_1 h1构建一个在模p
上面的多项式环,设r
为变量,方程如下
f = 13 ∗ o + 14 ∗ r + r ∗ z + o ∗ z 13 − h 1 f = 13*o+14*r+r*z+o*z^{13} -h_1 f=13∗o+14∗r+r∗z+o∗z13−h1
方程中的z
其实是一个关于r
的等式,也就是说这个方程只有一个变量r
由于o = getPrime(11)
,它是一个11bit的素数,其范围在 [ 2 10 , 2 11 − 1 ] [2^{10},2^{11}-1] [210,211−1],可以使用爆破的方法来找到合适的o
。
爆破素数o
,然后计算出方程的解,也就是r
。遍历每一个方程的解(解出的方程可能不止一个解),然后普通RSA解密,判断其明文是否包含flag{
字符串,包含的话,此时的o
即为所求。
正向爆破代码:
#sage
#find o,r,z
Flag = False
for o in trange(2**10+1,2**11,1):if is_prime(o):P.<r> = PolynomialRing(GF(p))z = inverse_mod(o*233,p)*(h2 - o^13 - r^12 -3*o*r)f = (13 * o + 14 * r + r * z + o * z ** 13) - h1result = f.roots()if result!=[]:for r in result:try:d1 = gmpy2.invert(o,p-1)find_m = pow(int(r[0]),d1,p)find_flag = long_to_bytes(int(find_m))if b'flag{' in find_flag:print(f'o = {o}')Flag=Truebreakexcept:passif Flag==True:break
爆破时间约为40分钟,🐏慢,慢得流脓!
逆向爆破代码:
#sage
#find o,r,z
Flag = False
for o in trange(2**11-1,2**10,-1):if is_prime(o):P.<r> = PolynomialRing(GF(p))z = inverse_mod(o*233,p)*(h2 - o^13 - r^12 -3*o*r)f = (13 * o + 14 * r + r * z + o * z ** 13) - h1result = f.roots()if result!=[]:for r in result:try:d1 = gmpy2.invert(o,p-1)find_m = pow(int(r[0]),d1,p)find_flag = long_to_bytes(int(find_m))if b'flag{' in find_flag:print(f'o = {o}')Flag=Truebreakexcept:passif Flag==True:break
逆向爆破,因为o=1949靠近 2 11 − 1 2^{11}-1 211−1,所以花费时间比较短,大概5分钟左右。
PS:至于为什么要写逆向爆破代码,主要是因为从头爆破起太慢了。而笔者一个很懒的人,懒得等。
最后将o=1949
带入,求解出r
,再把r
带入解出z
,分别RSA解密即可得到flag1
和flag2
,然后把flag1、flag2、flag3
拼接起来即可得到最终的flag
。
#sage
from Crypto.Util.number import *
import gmpy2
from tqdm import *
n = 10850335281775104384842309756387507121367947910896225110655535291748404338588972388693259827067445607230128971155491201985083085890729703137967791325100758142692285049056390126354246953310462082980059949946896088251642305978444680455930662301007461492978866538439458231120357274252592800042668860820459885960472737650446805378098344941597805604577797736381125259746781740429143953876454912647201590679786164678547559344304709889497251430904453036692562053570137262921657887410908992378188055660327282373869435308218926170927366572909858720457530661616332620263301130036238239402855045548920085800254012799063199438351
h1 = 68971374440570454964336249870184699116849273092766598492393855724166755705038579719086135125490382149633066088736614770735555426661202444613481222308690955829177344713094803125405000495549811601138114210065623933916822257443366983845366477473811412048210602195672314631662681949260715610527325398006214477393
h2 = 89557070262276493140173989636483552685176823962865601733383032051273942127575151309428084885522955047935745792156087951603894535351765100905696886714983834431355512680521411571740092935206188975497781396247799052916245218545834226095135276633422884113241438747017792108934964361391672183324214279475682695463
h3 = 1311626365146856567785446974305480952394390450877042514912868019585929680223703697129400820765966547191027907141852232429577556122050933660875292235305985538892538821817570539411355339774474418018682334787217004485252794403892893871864009361554731318803763221581009731474777526380398647174787569510518293833348676730943915073911916070766302422834190969513630361764429111809259665372926096307389623440860840605142551951919723403665762066543095024186705959708920942727754417048332722263643582752118944418881587666520088786189326167958303315156763867706697503512512849397447463575294489956813935149823414834222869976238
e = 65537#get flag3 and p
p_near = gmpy2.iroot(n,2)[0]
while n%p_near!=0:p_near = gmpy2.next_prime(p_near)
p = p_near
q = n//p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m3 = pow(h3,d,n)
flag3 = long_to_bytes(int(m3))o = 1949
P.<r> = PolynomialRing(GF(p))
z = inverse_mod(o*233,p)*(h2 - o^13 - r^12 -3*o*r)
f = (13 * o + 14 * r + r * z + o * z ** 13) - h1
r = f.roots()[0][0]
z = inverse_mod(o*233,p)*(h2 - o^13 - r^12 -3*o*r)d = gmpy2.invert(o,p-1)
#get flag1
m = pow(r,d,p)
flag1 = long_to_bytes(int(m))
#get flag2
m2 = pow(z,d,p)
flag2 = long_to_bytes(int(m2))print(flag1+flag2+flag3)
flag:
flag{c8f3ad650e7075488801e0e4cb91a4ba}
【许多今日之心心念念,无非是来年之付诸一笑。】