RSA的一个小trick

最近遇到了一个 RSA 的问题,涉及一个小小的 trick ,记录一下。

题目条件如下:

1
2
3
4
e=65537
n1=23813929634961916607351565880455941766670447113389071712756695324346844628401731716721342593051007386272154527731664038624979611788014212477351852945244505409460937047258358062539110381430391840699958786987625931706228387994323041218966203797392082298285118826348211114759651033904573709571472601260689154545949713245271655372366964733467694911683404472839031932865195076679363440004259157441442904092160547940620462275523928770007343760308099893870201392965037704560065286860197211399375405419620507897112217284427055511050820476779226202266877872708788417574738346625361066145535064835057037859284000257460115692751L
n2=23813929634961916607351565880455941766670447113389071712756695324346844628401731716721342593051007386272154527731664038624979611788014212477351852945244505409460937047258358062539110381430391840699958786987625931706228387994323041218966203797392082298285118826348211114759651033904573709571472601260689154673727252437046185126099084752843732400209032782207790902956024459189700856089587545302854326571561755007254420608514135036673700243280752364319986331493694769729841789115612749641973878393284804681876299531933348630664123809944975501332215753682284226293973903784246618067269627749460102002825975011735463170307L
encrypt=18605789682603602447496491798717321758798293700581905324029316650457391496265655270825055100678097929357061608642146193773598093988238186832894784951616085628646685595376101261377731258729834390380505295109894703902052847643842156614062711247564519297808798554671766259798926540994634858657655351713982599673967765484141456377356967352743349134262973092564982272405212241089526282547070247316071159193009664342169931360323767519419547890738439815871541842638219161372841320792826512207337857015266817573319095062799628537492791048391092577478382005012019416835632572465215950053539506334972912038960318318733757235757L

发现给了两个 n,一个密文,那就是根据两个 n 来计算私钥。
首先尝试分解两个 n,n1 无果,n2 分出一部分素因数:

image.png

显然 n2 不是两个素因数相乘,可以猜测 n1 是加密所用的 n。仔细观察 n1 和 n2 的高位都相同,相近,猜测n2可能是依据 n1 的 p 和 q 生成:

n1 = p * q
n2 = (p + x) * (q + y)

这样的话,可以推导:

1
2
3
4
p * q = n1
(p + x)(q + y) = n2
-> x * y + p * y + q * x = t (t = n2 - n1)
-> x * q^2 + (x * y - t) * q + n * y = 0

该方程有素数解即可,可爆破 x 和 y,写出脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import gmpy2
import libnum
e=65537
n1=23813929634961916607351565880455941766670447113389071712756695324346844628401731716721342593051007386272154527731664038624979611788014212477351852945244505409460937047258358062539110381430391840699958786987625931706228387994323041218966203797392082298285118826348211114759651033904573709571472601260689154545949713245271655372366964733467694911683404472839031932865195076679363440004259157441442904092160547940620462275523928770007343760308099893870201392965037704560065286860197211399375405419620507897112217284427055511050820476779226202266877872708788417574738346625361066145535064835057037859284000257460115692751L
n2=23813929634961916607351565880455941766670447113389071712756695324346844628401731716721342593051007386272154527731664038624979611788014212477351852945244505409460937047258358062539110381430391840699958786987625931706228387994323041218966203797392082298285118826348211114759651033904573709571472601260689154673727252437046185126099084752843732400209032782207790902956024459189700856089587545302854326571561755007254420608514135036673700243280752364319986331493694769729841789115612749641973878393284804681876299531933348630664123809944975501332215753682284226293973903784246618067269627749460102002825975011735463170307L
encrypt=18605789682603602447496491798717321758798293700581905324029316650457391496265655270825055100678097929357061608642146193773598093988238186832894784951616085628646685595376101261377731258729834390380505295109894703902052847643842156614062711247564519297808798554671766259798926540994634858657655351713982599673967765484141456377356967352743349134262973092564982272405212241089526282547070247316071159193009664342169931360323767519419547890738439815871541842638219161372841320792826512207337857015266817573319095062799628537492791048391092577478382005012019416835632572465215950053539506334972912038960318318733757235757L

t=n2-n1
f1 = lambda x, y: pow(x * y - t, 2) - 4 * n1 * x * y
f2 = lambda x, y, s: (t - x * y - s) / (2 * x)

for x in range(1,3000):
for y in range(1,3000):
print x,y
if f1(x, y) >= 0:
s, b = gmpy2.iroot(f1(x, y), 2)
if b:
if gmpy2.is_prime(f2(x,y,int(s))):
print "Success"
p=f2(x,y,int(s))
q=n1/p
d=gmpy2.invert(e,(p-1)*(q-1))
print libnum.n2s(pow(encrypt,d,n1))
exit()

解出明文。

参考:
https://err0rzz.github.io/2017/11/14/CTF%E4%B8%ADRSA%E5%A5%97%E8%B7%AF/

-------------本文结束感谢您的阅读-------------
0%