Writeup RektSA

par T0t0r0, T35H

Description

Il s’agit d’un challenge de cryptographie qui comme son nom l’indique implique RSA. Ici pas de message chiffré à déchiffrer, on nous donne N et e bien entendu, ainsi que certaines informations pour retrouver d.

Plus précisément, nous avons un challengte RSA à trois facteurs premiers et les informations suivantes nous sont données :
N=pqrN=pqr
e=65537e=65537 le classique

Aϕ[2z]A \equiv \phi [2^z] où z= 2050
rr

On remarque que la connexion au challenge est très courte, ce qui fait que la méthode de résolution doit être simple/rapide/facilement calculable/ne comporte que des opérations élémentaires a priori.

Méthode rapide, solution attendue

On se rend compte rapidement que p et q sont petits, et même que (p-1)(q-1) est plus petit que 2^z et que donc (p1)(q1)[2z](p-1)(q-1) [2^z] correspond à (p-1)(q-1) lui-même.

On cherche d donc un angle d’approche est de trouver ϕ\phi=(p-1)(q-1)(r-1) dont on connaît les LSB :

Aϕ[2z]A \equiv \phi [2^z]
donc
A(p1)(q1)(r1)[2z]A \equiv (p-1)(q-1)(r-1)[2^z]

On aimerait garder ce (p-1)(q-1) dans un coin pour la raison précédente. On se dit donc qu’il faut simplifier ce (r-1) qui nous dérange. (r-1) n’est pas inversible mais par exemple r12\frac{r-1}{2} l’est (c’est bien un entier car r est premier) (on a choisi 2 car c’est petit).

On a donc Ar121[2z]A * \frac{r-1}{2}^{-1}[2^z] = 2(p-1)(q-1)

A partir de là, le membre de gauche étant calculable et connaissant r, nous pouvons calculer ϕ\phi puis de1[ϕ]d \equiv e^{-1} [\phi]

Ci-après le code pour résoudre le challenge, merci comme souvent à pwntools :

from pwn import *
import gmpy2

e=65537
conn = remote('qual-challs.rtfm.re', 9001, level='error')
conn.recvuntil('N: ', drop=True)
N = int(conn.recvline(keepends=False).decode())
conn.recvuntil('phi: ', drop=True)
A = int(conn.recvline(keepends=False).decode())
conn.recvuntil('r: ', drop=True)
r = int(conn.recvline(keepends=False).decode())
conn.recvuntil('d', drop=True)
r_1=gmpy2.invert((r-1)//2,2**2050)
phi=(A*r_1%2**2050)*(r-1)//2

d=gmpy2.invert(e,phi)
conn.sendline(str(d))
print conn.recvuntil('}') #on va print notre précieux (flag)
conn.close()

Pérégrinations, autre méthode beaucoup plus lente et coûteuse

Celle-ci ne marche pas dans le cadre de notre challenge, dû à la connexion se terminant beaucoup trop rapidement pour avoir le temps de finir les calculs, mais je la poste, cela m’a rappelé les clés corrompues RSA et les LSB sur d.

On sait que ϕ=(p1)(q1)(r1)\phi = (p-1)(q-1)(r-1).
Donc cette équation est en particulier vraie modulo 2^z .
En réduisant l’équation on a donc A(p1)(q1)(r1)[2z]A \equiv (p-1)(q-1)(r-1) [2^z] où :
A, r et z sont connus
q=Npr\frac{N}{pr}
ce qui nous donne une équation modulaire du second degré ayant pour seule inconnue p :
0(r1)p2+((r1)(n+1)A)pn(r1)[2z]0 \equiv (r-1)*p^2+((r-1)*(n+1)-A)*p-n*(r-1) [2^z]n=Nrpn=\frac{N}{rp}

C’est résolvable par exemple via Sage : plusieurs réponses/solutions sont bien sûr données mais il suffit de trouver un facteur de N/un élément de l’énumération donnée en sortie qui divise N.

Et à partir de là c’est facile/évident, on déroule : nous avons les valeurs de p, q (en calculant le ratio de N sur pr) et r, nous pouvons donc calculer ϕ\phi = (p-1)(q-1)(r-1) puis de1[ϕ]d\equiv e^{-1} [\phi] avec Sage, python3.8 et sa fonction pow qui supporte ENFIN les inverses, python2 (RIP) avec gmpy2,… bref vous avez compris :)