[祥云杯 2022]common_rsa WP by pcspcs

Problem: [祥云杯 2022]common_rsa

问题：

from Crypto.Util.number import getPrime, isPrime, bytes_to_long, inverse
from math import lcm
from secret import flag

def gen(g):
    bits = 512 - g.bit_length()
    while True:
        a = getPrime(bits)
        p = 2 * a * g + 1
        if isPrime(p):
            return p

flag = bytes_to_long(flag)
g = getPrime(320)
p = gen(g)
q = gen(g)
n = p * q
d = getPrime(135)
phi = lcm(p - 1, q - 1)
e = inverse(d, phi)
c = pow(flag, e, n)
print("n = {}".format(n))
print("e = {}".format(e))
print("c = {}".format(c))

题目简单明了，d很小只有135位，但\varphi没有直接使用(p-1)(q-1),而是使用了lcm(p-1,q-1),因为p和q有共有的大因子g,因此lcm结果明显比n少了很多位，所以常规的wiener攻击包括Boneh_Durfee方法无效，有对应论文用整数方程

可规约出(d,ka,kb)
crypto-attack中已有现成的轮子:wiener_attack_common_prime.py,拿来用即可，但要注意轮子有点小BUG，要指定m,t才不报错：

#!/bin/env python
#[祥云杯 2022]common_rsa
from sage.all import *
os.chdir('/mnt/s/crypto-attacks')
from attacks.rsa.wiener_attack_common_prime import attack
n2s = lambda m:bytes(ZZ(m).digits(256))[::-1]

n = 253784908428481171520644795825628119823506176672683456544539675613895749357067944465796492899363087465652749951069021248729871498716450122759675266109104893465718371075137027806815473672093804600537277140261127375373193053173163711234309619016940818893190549811778822641165586070952778825226669497115448984409
e = 31406775715899560162787869974700016947595840438708247549520794775013609818293759112173738791912355029131497095419469938722402909767606953171285102663874040755958087885460234337741136082351825063419747360169129165
c = 97724073843199563126299138557100062208119309614175354104566795999878855851589393774478499956448658027850289531621583268783154684298592331328032682316868391120285515076911892737051842116394165423670275422243894220422196193336551382986699759756232962573336291032572968060586136317901595414796229127047082707519

p,q,d = attack(n, e, 0.132, 2, 1)
flag = n2s(pow(c,d,n))
print(flag.decode())
#flag{9aecf8d8-6966-4ffa-96b0-2e744d28baf2}

flag:

NSSCTF{9aecf8d8-6966-4ffa-96b0-2e744d28baf2}