home - links - about - rss

FCSC 2021 - RSA Destroyer [FR]

Il s'agit d'un challenge a 200 points au FCSC 2021.

RSA Destroyer description

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 :

$$p = a_p2^{1024} - a_pe_p + u_p$$
$$q = a_q2^{1024} - a_qe_q + u_q$$

En posant \(X_p = -a_pe_p + u_p\) et \(X_q = -a_qe_q + u_q\), on a

$$p = a_p2^{1024} + X_p$$
$$q = a_q2^{1024} + X_q$$

Aussi,

$$n = p \times q = a_pa_q2^{2048} + (X_qa_p + X_pa_q) 2^{1024} + X_pX_q$$

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 :

N en base 16

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

$$a_p2^{1024} + X_p = p$$
$$a_q2^{1024} + X_q = q$$

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} :-).


Creative Commons License