Simple RSA

这是 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
入手点在 next_prime，因为 next_prime 往往和原数相差很小，就出现了漏洞导致N可分解
考虑N的四个质因子，分别表示为

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 两个因子
两个因子相减 得到 p = (t + x*y + 10*x*x) / (z - 100*x)
因为 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 哪个大，所以要小心 t 的正负