Table des matières

Déchiffrement RSA : fondements mathématiques et solution

RSA est un système de chiffrement à clé publique inventé par Rivest, Shamir et Adleman en 1977. Il permet à la fois de chiffrer des messages et de signer numériquement des documents.

Ce système de chiffrement est basé sur l’opération mathématique d’exponentiation modulaire. Pour chiffrer un message m avec la clé publique (n,e), on calcule :

$$c \equiv m^e \pmod{n}$$

1. Problème posé

Ici nous connaissons

c = 63775417045544543594281416329767355155835033510382720735973 = m^e mod n (message chiffré)
e = 65537 (exposant public)
n = 632459103267572196107100983820469021721602147490918660274601 (module)

Le problème est ici de retrouver m (le message déchiffré) connaissant e, n et c.

On cherche m tel que c = m^e mod n.

2. Théorèmes fondamentaux utilisés

2.1 Théorème fondamental de l’arithmétique

Tout nombre entier n > 1 peut être décomposé de manière unique en produit de nombres premiers.

Application : n peut être factorisé en n = p × q où p et q sont premiers.

2.2 Théorème d’Euler

Pour tout entier a premier avec n : a^φ(n) ≡ 1 (mod n) où φ(n) est l’indicatrice d’Euler qui compte le nombre d’entiers premiers avec n.

Corollaire important :

Pour n = p × q avec p et q premiers : φ(n) = (p-1)(q-1)

2.3 Théorème de Bachet-Bézout (via algorithme d’Euclide étendu)

Pour deux entiers a et b, il existe x et y tels que ax + by = PGCD(a,b)

Application : Permet de trouver d tel que e × d ≡ 1 (mod φ(n))

2.4 Petit théorème de Fermat

Si p est premier et a n’est pas divisible par p, alors : a^(p-1) ≡ 1 (mod p)

3. Méthode de résolution

Nous allons utiliser pour résoudre ce problème le logiciel SageMath (anciennement Sage).

Il s’agit d’un logiciel libre généraliste de calcul mathématique.

Le projet SageMath vise à « développer une alternative open source viable » aux systèmes de calcul formel Magma, Maple, et Mathematica ainsi qu’au logiciel de calcul numérique MATLAB.

SageMath peut être téléchargé via https://www.sagemath.org/ ou utilisé en ligne via https://sagecell.sagemath.org/

3.1 Factorisation de n

La première étape consiste à factoriser n comme produit de 2 entiers p et q

# Valeurs fournies dans le challenge
n = 632459103267572196107100983820469021721602147490918660274601
e = 65537
c = 63775417045544543594281416329767355155835033510382720735973

# Étape 1 : Factorisation de n
print("Étape 1 : Factorisation de n")
F = factor(n)
p = F[0][0]  # Premier facteur premier
q = F[1][0]  # Second facteur premier
print(f"p = {p}")
print(f"q = {q}")
print(f"Vérification n = p × q : {n == p * q}")

Résultat :

p = 650655447295098801102272374367
q = 972033825117160941379425504503
Vérification n = p × q : True

3.2 Calcul de l’indicatrice d’Euler

Par le corollaire du théorème d’Euler :

phi = (p-1) * (q-1)

3.3 Calcul de la clé privée d

Utilisation de l’algorithme d’Euclide étendu pour trouver d tel que : e × d ≡ 1 (mod φ(n))

d = inverse_mod(e, phi)

3.4 Déchiffrement

Par le théorème d’Euler et ses conséquences :

m = power_mod(c, d, n)

4. Preuve de la correction

Soit $m$ le message original, $c$ le message chiffré, $n = pq$ avec $p$ et $q$ premiers, $e$ l’exposant public et $d$ l’exposant privé.

Démonstration

Chiffrement : $$c \equiv m^e \pmod{n}$$
Par substitution dans le déchiffrement : $$c^d \equiv (m^e)^d \pmod{n}$$
Par les propriétés de l’exponentiation : $$c^d \equiv m^{ed} \pmod{n}$$
Par construction de $d$ : $$ed \equiv 1 \pmod{\phi(n)}$$ Donc il existe $k \in \mathbb{Z}$ tel que : $$ed = k\phi(n) + 1$$
En substituant : $$c^d \equiv m^{k\phi(n) + 1} \equiv m^{k\phi(n)} \cdot m \pmod{n}$$ $$\equiv (m^{\phi(n)})^k \cdot m \pmod{n}$$
Par le théorème d’Euler : Si $\gcd(m,n) = 1$, alors : $$m^{\phi(n)} \equiv 1 \pmod{n}$$
Donc : $$c^d \equiv 1^k \cdot m \equiv m \pmod{n}$$

Note importante

La preuve suppose que $\gcd(m,n) = 1$. Si ce n’est pas le cas, une preuve plus générale utilisant le théorème des restes chinois est nécessaire.

5. Solution finale

# Valeurs fournies dans le challenge
n = 632459103267572196107100983820469021721602147490918660274601
e = 65537
c = 63775417045544543594281416329767355155835033510382720735973

# Étape 1 : Factorisation de n
print("Étape 1 : Factorisation de n")
F = factor(n)
p = F[0][0]  # Premier facteur premier
q = F[1][0]  # Second facteur premier
print(f"p = {p}")
print(f"q = {q}")
print(f"Vérification n = p × q : {n == p * q}")

# Étape 2 : Calcul de l'exposant secret d
print("\nÉtape 2 : Calcul de l'exposant secret d")
# φ(n) = (p-1)(q-1) par le théorème d'Euler
phi = (p-1) * (q-1)
# d est l'inverse modulaire de e modulo φ(n)
d = inverse_mod(e, phi)
print(f"φ(n) = {phi}")
print(f"d = {d}")
# Vérification : e × d ≡ 1 [mod φ(n)]
print(f"Vérification e × d ≡ 1 [mod φ(n)] : {(e * d) % phi == 1}")

# Étape 3 : Déchiffrement
print("\nÉtape 3 : Déchiffrement")
# m = c^d mod n
m = power_mod(c, d, n)
print(f"Message déchiffré m = {m}")
print(f"Flag = FCSC{{{m}}}")

Résultats obtenus :

Étape 1 : Factorisation de n
p = 650655447295098801102272374367
q = 972033825117160941379425504503
Vérification n = p × q : True

Étape 2 : Calcul de l'exposant secret d
φ(n) = 632459103267572196107100983818846332449189887748436962395732
d = 168419004077477912728094456102758841477383186917096020076145
Vérification e × d ≡ 1 [mod φ(n)] : True

Étape 3 : Déchiffrement
Message déchiffré m = 563694726501963824567957403529535003815080102246078401707923
Flag = FCSC{563694726501963824567957403529535003815080102246078401707923}

Compléments

Le théorème des restes chinois (CRT - Chinese Remainder Theorem)

Principe simple

Le CRT dit que si vous connaissez les restes d’un nombre quand on le divise par plusieurs nombres premiers entre eux, alors vous pouvez retrouver ce nombre de manière unique (modulo le produit des diviseurs).

Exemple Simple

Imaginons que nous cherchons un nombre x qui vérifie :

x ≡ 2 [mod 3] (quand on divise x par 3, le reste est 2)
x ≡ 3 [mod 5] (quand on divise x par 5, le reste est 3)

Le CRT nous dit qu’il existe une solution unique modulo 15 (3 × 5). La réponse est x = 8, car :

8 ÷ 3 = 2 reste 2
8 ÷ 5 = 1 reste 3

Application en RSA

Dans RSA, le CRT est utilisé pour accélérer le déchiffrement quand on connaît p et q. Au lieu de calculer m = c^d mod n directement, on calcule :

m1 = c^d mod p
m2 = c^d mod q
Puis on combine m1 et m2 pour obtenir m

C’est plus rapide car p et q sont plus petits que n.

Algorithme de résolution simple

def crt_simple(r1, r2, n1, n2):
    """
    Trouve x tel que :
    x ≡ r1 [mod n1]
    x ≡ r2 [mod n2]
    """
    N = n1 * n2  # modulo total
    N1 = N // n1 # N/n1
    N2 = N // n2 # N/n2

    # Inverses modulaires
    y1 = inverse_mod(N1, n1)
    y2 = inverse_mod(N2, n2)

    # Solution
    x = (r1 * N1 * y1 + r2 * N2 * y2) % N
    return x

Exemple pratique

# On cherche x tel que :
# x ≡ 2 [mod 3]
# x ≡ 3 [mod 5]

x = crt_simple(2, 3, 3, 5)
print(f"x = {x}")  # x = 8

# Vérification
print(f"x mod 3 = {x % 3}")  # 2
print(f"x mod 5 = {x % 5}")  # 3

Application du CRT à notre cas

# Valeurs du challenge
n = 632459103267572196107100983820469021721602147490918660274601
e = 65537
c = 63775417045544543594281416329767355155835033510382720735973

print("=== Challenge RSA ===")
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

# Méthode 1 : Déchiffrement classique
def rsa_decrypt_normal(c, e, n):
    print("\n=== Méthode 1 : Déchiffrement classique ===")

    # Factorisation de n
    print("Factorisation de n...")
    F = factor(n)
    p = F[0][0]
    q = F[1][0]
    print(f"p = {p}")
    print(f"q = {q}")

    # Calcul de phi(n)
    phi = (p-1) * (q-1)
    print(f"φ(n) = {phi}")

    # Calcul de d
    d = inverse_mod(e, phi)
    print(f"d = {d}")

    # Déchiffrement
    m = power_mod(c, d, n)
    return m, p, q, d

# Méthode 2 : Déchiffrement avec CRT
def rsa_decrypt_crt(c, e, p, q):
    print("\n=== Méthode 2 : Déchiffrement avec CRT ===")

    # Calcul de phi(n) et d
    phi = (p-1) * (q-1)
    d = inverse_mod(e, phi)

    # Calcul des exposants privés réduits
    dp = d % (p-1)
    dq = d % (q-1)
    print(f"dp = {dp}")
    print(f"dq = {dq}")

    # Déchiffrements partiels
    mp = power_mod(c, dp, p)
    mq = power_mod(c, dq, q)
    print(f"mp = {mp}")
    print(f"mq = {mq}")

    # Recombinaison CRT
    qInv = inverse_mod(q, p)
    h = (qInv * (mp - mq)) % p
    m = mq + h * q
    return m

# Exécution des deux méthodes
m1, p, q, d = rsa_decrypt_normal(c, e, n)
m2 = rsa_decrypt_crt(c, e, p, q)

# Affichage des résultats
print("\n=== Résultats ===")
print(f"Message (méthode classique) = {m1}")
print(f"Message (méthode CRT) = {m2}")
print(f"Les deux méthodes donnent le même résultat : {m1 == m2}")

# Vérification du déchiffrement
print("\n=== Vérification ===")
c_verify = power_mod(m1, e, n)
print(f"Rechiffrement correct : {c_verify == c}")

# Affichage du flag
print("\n=== Flag ===")
print(f"FCSC{{{m1}}}")

On obtient alors :

=== Challenge RSA ===
n = 632459103267572196107100983820469021721602147490918660274601
e = 65537
c = 63775417045544543594281416329767355155835033510382720735973

=== Méthode 1 : Déchiffrement classique ===
Factorisation de n...
p = 650655447295098801102272374367
q = 972033825117160941379425504503
φ(n) = 632459103267572196107100983818846332449189887748436962395732
d = 168419004077477912728094456102758841477383186917096020076145

=== Méthode 2 : Déchiffrement avec CRT ===
dp = 266836542059452988040736905959
dq = 300819232510280577583006669245
mp = 125633637047726032783383072253
mq = 502804747762674000536319770793

=== Résultats ===
Message (méthode classique) = 563694726501963824567957403529535003815080102246078401707923
Message (méthode CRT) = 563694726501963824567957403529535003815080102246078401707923
Les deux méthodes donnent le même résultat : True

=== Vérification ===
Rechiffrement correct : True

=== Flag ===
FCSC{563694726501963824567957403529535003815080102246078401707923}

Solution de s-celles pour SMIC (2)