Il s'agit d'un challenge a 200 points au FCSC 2021.
Voici le contenu de rsa_destroyer.py
:
# **This** destroyes the RSA cryptosystem.
from Crypto.Util.number import isPrime, bytes_to_long
from Crypto.Random.random import getrandbits
def fastPrime(bits, eps = 32):
while True:
a, e, u = getrandbits(eps), getrandbits(eps), getrandbits(4 * eps)
p = a * (2 ** bits - e) + u
if isPrime(p):
return p
def generate(bits = 2048):
p = fastPrime(bits // 2)
q = fastPrime(bits // 2)
return p * q, 2 ** 16 + 1
n, e = generate()
p = bytes_to_long(open("flag.txt", "rb").read())
c = pow(p, e, n)
print(f"e = {e}")
print(f"n = {n}")
print(f"c = {c}")
On nous donne également la sortie d'une exécution :
e = 65537
n = 444874973852804286630293120525019547982392964519934608680681255396764239795499482860997657663742247333836933457910503642061679607999128792657151145831533603267962151902191791568052924623477918783346790554917615006885807262798511378178431356140169891510484103567017335784087168191133679976921108092647227149255338118895695993606854195408940572577899625236666854544581041490770396755583819878794842828965377818593455075306655077757834318066860484956428681524881285058664687568640627516452658874124048546780999256640377399347893644988620246748059490751348919880389771785423781356133657866769589669296191804649195706447605778549172906037483
c = 95237912740655706597869523108017194269174342313145809624317482236690453533195825723998662803480781411928531102859302761153780930600026069381338457909962825300269319811329312349030179047249481841770850760719178786027583177746485281874469568361239865139247368477628439074063199551773499058148848583822114902905937101832069433266700866684389484684637264625534353716652481372979896491011990121581654120224008271898183948045975282945190669287662303053695007661315593832681112603350797162485915921143973984584370685793424167878687293688079969123983391456553965822470300435648090790538426859154898556069348437896975230111242040448169800372469
Résolution
Les nombres premiers générés par la fonction fastPrime
se retrouvent tous être de la forme \(a2^{1024} - ae + u\), avec \(a\) et \(e\) inférieurs à \(2^{32}\), et \(u\) inférieur à \(2^{128}\).
On écrit alors \(p\) et \(q\) de la manière suivante :
En posant \(X_p = -a_pe_p + u_p\) et \(X_q = -a_qe_q + u_q\), on a
Aussi,
On remarque que \(n\) se décompose facilement en base \(2^{1024}\), avec de petits coefficients à chaque fois. En effet,
- Le coefficient de \(2^{1024 \times 0}\) est \(X_pX_q\) qui est de l'ordre de \(2^{256}\) par construction (le plus gros terme est \(u_pu_q\)).
- Le coefficient de \(2^{1024 \times 1}\) est \(X_qa_p + X_pa_q\), qui est de l'ordre de \(2^{160}\)
- Enfin, le coefficient de \(2^{1024 \times 2}\) est simplement \(a_pa_q\), donc de l'ordre de \(2^{64}\).
En observant \(n\) en base 16, il est assez facile de voir chacun de ces coefficients :
On peut facilement extraire leur valeurs, et obtenir les équations suivantes :
- \(a_pa_q =\)
0xbf0a8dd7d8f16cad
\(= 13765971169208528045\) - \(X_qa_p + X_pa_q =\)
0x1002c0b6fc6c3c2949b0a1e097f3c51eff2e8919
\(= 1462483866390329830822836164002145062407975244184\) - \(X_pX_q =\)
0x526e422445cbd24c429d60a4a3d75cfd20d09708a2945d9ad2d3b65a55f110eb
\(= 37284463254120829734596659590852831388840149328402126048476097877596519338219\)
A partir de la, on peut regarder la factorisation de \(a_pa_q\) afin d'essayer de retrouver \(a_p\) et \(a_q\) distinctement. De même pour \(X_p\) et \(X_q\).
On note que même si \(X_pX_q\) est un nombre d'environ 256 bits , sa factorisation est rapide car \(X_p\) et \(X_q\) n'ont aucune raison d'être premiers.
Une fois qu'on a trouvé \(a_p,a_q,X_p,X_q\), on a
donc c'est gagné.
Voilà un bout de code qui essaye toutes les possibilités de factorisation pour ces deux coefficients:
import sys
import itertools
from sage.all import factor, product
from math import ceil
n = [..]
e = 65537
c = [..]
# Récupère les coefficients directement depuis n
apaq = n // (2**2048)
XpXq = n % (2**1024)
XpXq_facs = [f for f,_ in factor(XpXq)]
apaq_facs = [f for f,_ in factor(apaq)]
for i in range(1,len(apaq_facs)):
for aps in itertools.combinations(apaq_facs, i):
ap = product(aps)
aq = apaq // ap
for j in range(1,len(XpXq_facs)):
for Xps in itertools.combinations(XpXq_facs, j):
Xp = product(Xps)
Xq = XpXq // Xp
if XpXq + (Xp*aq + Xq*ap) * 2**1024 + ap*aq*2**2048 == n:
p = ap*2**1024 + Xp
q = aq*2**1024 + Xq
d = pow(e, -1, (p-1)*(q-1))
m = pow(c, int(d), n)
print(int.to_bytes(m, ceil(m.bit_length()/8), "big").decode())
sys.exit()
En le lancant, on obtient notre super flag FCSC{cd43566923980e47f6630e82c2d9a55b388f01043bc78b9ce3354ce02acf22e8}
:-).