Solution de mk_4362 pour RSA WTF

Table des matières

On a quoi ?

On ne nous fournit pas spécialement d’explication, mais deux fichiers, un script python et le fichier de sortie qu’il produit :

rsa-wtf.py
output.txt

Mais après tout pas besoin de beaucoup d’explications …

On comprend quoi ?

On analyse un peu le script fournit

le flag est lu
découpé en blocs de 8 octets
chaque bloc est chiffré indépendamment (AES_CBC) avec un nouvel IV et une nouvelle clef pour chacun
lors de la génération des secrets, le concepteur fait quelques opérations bizzares (‘RSA-like…’) :

    self.k = getrandbits(666)
    self.p = getPrime(512)
    self.q = getPrime(512)
    self.dp = pow(self.k, -1, self.p - 1)
    self.dq = pow(self.k, -1, self.q - 1)

Et puis sans grande raison sont envoyés dans le fichier de sortie :

l’iv considéré
le bloc chiffré correspondant
p, q, dp et dq

Que faire ?

Alors, on se doute bien que k, p, q, dp et dq sont liés, et qu’il va nous falloir retrouver chaque k pour chaque bloc et retrouver notre flag en clair …

dp est l’inverse de k modulo (p-1)
dq est l’inverse de k modulo (q-1)

dp = inv(k) [p-1]  ==>  k = inv(dp) [p-1]
dq = inv(k) [q-1]  ==>  k = inv(dq) [q-1]

Donc il exite n1 et n2 entiers tels que :

k = inv(dp) + n1 * (p-1)
k = inv(dq) + n2 * (q-1)

Et :

inv(dp) + n1 * (p-1) = inv(dq) + n2 * (q-1)

On connait tout sauf n1 et n2, il n’y a plus qu’à trouver des candidats pour chacun des blocs du chiffré.

Une fois que l’on a n1 par exemple, on retrouve k et on peut déchiffrer le bloc.

Comment

Il y a peut-être plus malin, mais j’ai utilisé le solver z3

Voilà le morceau intéressant :

def find_k(p, q, dp, dq):
    a1 = pow(dp, -1, p-1)
    a2 = pow(dq, -1, q-1)

    n1 = Int("n1")
    n2 = Int("n2")

    s = Solver()

    s.add( a1 + n1 * (p-1) == a2 + n2 * (q-1) )
    s.add( n1 > 0 )
    s.check()
    tmp = str(s.model())

    # ok, la fin c'est moche mais je ne sais toujours pas
    # comment récupérer en tant qu'entiers les solutions proosées
    # je prends la string et je parse pour extraire n1 et n2
    t1 = tmp[1:-1].split(',\n')[0].strip()
    t2 = tmp[1:-1].split(',\n')[1].strip()

    if t1.startswith('n1 = '):
        n1 = int(t1.split(' = ')[1])
        n2 = int(t2.split(' = ')[1])
    else:
        n2 = int(t1.split(' = ')[1])
        n1 = int(t2.split(' = ')[1])
    
    # Retourne la clef
    return a1 + n1 * (p-1)

Solve

python3 solve.py                                                                                                                        ✔  fcsc_2025 🐍  12:51:44   
b'FCSC{ymUE6UxW8S2hNYQzjSjhHL5V4Kjc4FtHEZViPfjd6b92gdZjUbaBUEiy27UD1oqFiv}'

Code complet

import json
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Util.Padding import unpad
from z3 import *

def find_k(p, q, dp, dq):
    a1 = pow(dp, -1, p-1)
    a2 = pow(dq, -1, q-1)

    n1 = Int("n1")
    n2 = Int("n2")

    s = Solver()

    s.add( a1 + n1 * (p-1) == a2 + n2 * (q-1) )
    s.add( n1 > 0 )
    s.check()
    tmp = str(s.model())

    t1 = tmp[1:-1].split(',\n')[0].strip()
    t2 = tmp[1:-1].split(',\n')[1].strip()

    if t1.startswith('n1 = '):
        n1 = int(t1.split(' = ')[1])
        n2 = int(t2.split(' = ')[1])
    else:
        n2 = int(t1.split(' = ')[1])
        n1 = int(t2.split(' = ')[1])
    
    return a1 + n1 * (p-1)

datas = json.loads(open("output.txt","r").read())

flag = b''

for bloc in datas:
    iv = bytes.fromhex(bloc[0])
    c = bytes.fromhex(bloc[1])
    p = bloc[2]
    q = bloc[3]
    dp = bloc[4]
    dq = bloc[5]

    k = find_k(p, q, dp, dq)
    k = SHA256.new(str(k).encode()).digest()
    E = AES.new(k, AES.MODE_CBC, iv = iv)
    flag += unpad(E.decrypt(c), 16)

print(flag)