RSA的一个小trick

2018-10-14

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

题目条件如下：

e=65537
n1=23813929634961916607351565880455941766670447113389071712756695324346844628401731716721342593051007386272154527731664038624979611788014212477351852945244505409460937047258358062539110381430391840699958786987625931706228387994323041218966203797392082298285118826348211114759651033904573709571472601260689154545949713245271655372366964733467694911683404472839031932865195076679363440004259157441442904092160547940620462275523928770007343760308099893870201392965037704560065286860197211399375405419620507897112217284427055511050820476779226202266877872708788417574738346625361066145535064835057037859284000257460115692751L
n2=23813929634961916607351565880455941766670447113389071712756695324346844628401731716721342593051007386272154527731664038624979611788014212477351852945244505409460937047258358062539110381430391840699958786987625931706228387994323041218966203797392082298285118826348211114759651033904573709571472601260689154673727252437046185126099084752843732400209032782207790902956024459189700856089587545302854326571561755007254420608514135036673700243280752364319986331493694769729841789115612749641973878393284804681876299531933348630664123809944975501332215753682284226293973903784246618067269627749460102002825975011735463170307L
encrypt=18605789682603602447496491798717321758798293700581905324029316650457391496265655270825055100678097929357061608642146193773598093988238186832894784951616085628646685595376101261377731258729834390380505295109894703902052847643842156614062711247564519297808798554671766259798926540994634858657655351713982599673967765484141456377356967352743349134262973092564982272405212241089526282547070247316071159193009664342169931360323767519419547890738439815871541842638219161372841320792826512207337857015266817573319095062799628537492791048391092577478382005012019416835632572465215950053539506334972912038960318318733757235757L

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

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

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

这样的话，可以推导：

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，写出脚本：

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/