Fword CTF 2020 | Mini Cooper - crypto-writeup-public

#!/usr/bin/python
from Crypto.Util.number import *
from random import *
from gmpy2 import *
from fractions import * 
from binascii import hexlify
from secret import flag

#Setting up params
a = randrange(2**10,2**11)
b = randrange(2**12,2**13)
c = randint(2,2**1024)

p = next_prime((a * c) + randint(2,2**512))
q = next_prime((b * c) + randint(2,2**512))

n = p * q
e=randint(1024,70000)
while True:
    if ( (e & (e+1) == 0) and gcd(e,(p-1)*(q-1))==1):
        exp=e 
        break
    e+=1

m=int(hexlify(flag.encode()).decode(),16)

enc=pow(m,exp,n)


print ("n : "+str(n))
print ("a : "+str(a))
print ("b : "+str(b))
print ("enc : "+str(enc))

RSA - Suspicious Prime

比較的小さい $a, b$ と $c$ があって、 $p = a * c + \alpha, q = b * c + \beta$

$e$ は小さい範囲

$N = pq = (ac + \alpha)(bc + \beta) = abc^2 + ac\beta + bc\alpha + \alpha\beta$

サイズ的には $abc^2 \simeq 2^{10+12+2048}, ac\beta \simeq 2^{10+1024+512}, bc\alpha \simeq 2^{12+1024+512}, \alpha\beta \simeq 2^{1024}$

$\frac{N}{ab} = c^2 + \frac{c\beta}{b} + \frac{c\alpha}{a} + \frac{\alpha\beta}{ab}$

こちらは大体 $c^2 \simeq 2^{2048}, \frac{c\beta}{b}\simeq 2^{1024+512-2}, \frac{c\alpha}{b} \simeq 2^{2 + 1024 + 512}, \frac{\alpha\beta}{ab} \simeq 2^{1024 - 22}$