RektSA pour les nuls

Avant-Propos

Si vous recherchez une solution avec un haut niveau de Math ou de Crypto, passez votre chemin ma solution est réalisable avec 3 opérations digne d’un enfant de 6ème. Si vous cherchez une solution simple, ce Write-Up est fait pour vous.

Le contexte

Les éléments donnés :

N : produit de p, q et r
Phi : Résultat de : Φ\Phi % 22050
r : partie de N et Φ\Phi

Nota : J’ai appelé Phi la partie donnée et Φ\Phi le vrai phi du RSA.

Les formules utiles :

Φ\Phi = (p-1) (q-1) (r-1)
N = p x q x r
d = invert(e, Φ\Phi)

Le but à atteindre :

Le but de l’épreuve est de trouver d, il nous faut donc trouver Φ\Phi

La résolution :

La théorie

On sait que Φ\Phi % 22050 = phi
On a donc Φ\Phi = X . 22050 + phi
phi étant connu, il ne nous manque que X
X s’obtient en divisant Φ\Phi par 22050 et en prenant la valeur entière du résultat.
A 22050 près N et Φ\Phi sont très proche, on a N, on peut donc trouver rapidement quelques X pouvant résoudre notre problème.

X \approx N//22050

Pour trouver le bon X il suffit de vérifier que (r-1) soit un multiple du Φ\Phi trouvé.

La pratique

X = N//2**2050  
  
for i in range(10):  
    vrai_phi = (phi + ((X-i)*2**2050))  
    if vrai_phi % (r-1) == 0:  
        d = Cryptodome.Util.number.inverse(0x10001, vrai_phi)  
        tn.write(str(d).encode('ascii')+b'\n')  
        print (tn.read_all().decode('ascii'))

On calcule le X et on laisse le soin à l’ordinateur de tester les 10 valeurs précédentes.
On obtient un résultat instantanément à chaque lancement.

Le code complet de 14 lignes :-)

import telnetlib  
import Cryptodome.Util.number  
  
tn = telnetlib.Telnet("qual-challs.rtfm.re",9001)  
tab_reponse = tn.read_until(b'Give me d:').split(b': ')  
N = int(tab_reponse[1].replace(b'\nphi',b''))  
phi = int(tab_reponse[2].replace(b'\nr',b''))  
r = int(tab_reponse[3].replace(b'\nGive me d:',b''))  
X = N//2**2050  
  
for i in range(10):  
    vrai_phi = (phi + ((X-i)*2**2050))  
    if vrai_phi % (r-1) == 0:  
        d = Cryptodome.Util.number.inverse(0x10001, vrai_phi)  
        tn.write(str(d).encode('ascii')+b'\n')  
        print (tn.read_all().decode('ascii'))

Conclusion

Juste une citation du rasoir d’Occam :
La solution la plus simple est toujours la meilleure
(c’est pour vous aider dans le vote pour la bière)

Une seconde pour les personnes ayant abandonnées trop tôt :
La persévérance est une qualité déterminante du succès.