這是 ISITDTU 的一道RSA題

題目是這樣的

from Crypto.Util.number import *
import random
flag = 'Hidden'


def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        #raise Exception('modular inverse does not exist')
        print "aaa"
    else:
        return x % m


def next_prime(n):
    num = n + 1
    while True:
        if isPrime(num):
            return num
        num += 1


p = random.randint(1 << 251, 1 << 252)
i = 10
p = next_prime(p)
p1 = next_prime(p*10)
p2 = next_prime(p1*10)
p3 = next_prime(p2*10)


N = p*p1*p2*p3
e = 65537
c = pow(bytes_to_long(flag), e, N)
print c
# 153348390614662968396805701018941225929976855876673665545678808357493865670852637784454103632206407687489178974011663144922612614936251484669376715328818177626125051048699207156003563901638883835345344061093282392322541967439067639713967480376436913225761668591305793224841429397848597912616509823391639856132
print N
# 603040899191765499692105412408128039799635285914243838639458755491385487537245112353139626673905393100145421529413079339538777058510964724244525164265239307111938912323072543529589488452173312928447289267651249034509309453696972053651162310797873759227949341560295688041964008368596191262760564685226946006231

這題思路就很清晰，就是要求信息 m
入手點(diǎn)在 next_prime漠嵌，因?yàn)?next_prime 往往和原數(shù)相差很小弓摘，就出現(xiàn)了漏洞導(dǎo)致N可分解
考慮N的四個(gè)質(zhì)因子，分別表示為

p = p
p1 = p*10+x
p2 = p*100+x*10+y
p3 = p*1000+x*100+y*10+z

所以用 yafu 分解大N凡辱，得 p*p3 和 p1*p2 兩個(gè)因子
兩個(gè)因子相減 得到 p = (t + x*y + 10*x*x) / (z - 100*x)
因?yàn)?xyz 都很小
所以爆破 xyz 可以得到 p

#coding: utf-8

t = -76478092637783866041186253218284943370377825118125630644332110668682405063331370
n = 603040899191765499692105412408128039799635285914243838639458755491385487537245112353139626673905393100145421529413079339538777058510964724244525164265239307111938912323072543529589488452173312928447289267651249034509309453696972053651162310797873759227949341560295688041964008368596191262760564685226946006231

for x in xrange(600):
    print x
    for y in xrange(500):
     for z in xrange(600):
       if z != 100*x:
           p = (t + x*y + 10*x*x) / (z - 100*x)
           if n % p == 0:
               print "p = {}".format(p)

然后可以用 next_prime(p*10) 依次求出 p1, p2, p3
接著求 fn(phi) 和 d侨舆，最后解出 m

ps: 注意不確定 p*p3 和 p1*p2 哪個(gè)大秒紧，所以要小心 t 的正負(fù)