Fondements Numériques et Résolution de Systèmes

L'analyse des schémas cryptographiques basés sur RSA repose souvent sur des outils de théorie des nombres. L'algorithme d'Euclide étendu (ExtGCD) est fondamental pour résoudre les identités de Bézout, permettant de trouver les ivnerses modulaires ou de résoudre des équations diophantiennes linéaires.

Voici une implémentation optimisée et récursive de l'ExtGCD :

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    gcd, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return gcd, x, y

Lorsque l'on fait face à des systèmes de congruences où les modules ne sont pas nécessairement premiers entre eux, le Théorème des Restes Chinois (CRT) standard échoue. L'EXCRT (Extended CRT) permet de fusionner itérativement les congruences en utilisant l'ExtGCD pour gérer les facteurs communs.

def excrt(moduli, remainders):
    current_mod = moduli[0]
    current_rem = remainders[0]
    
    for i in range(1, len(moduli)):
        m2 = moduli[i]
        r2 = remainders[i]
        g, x, _ = extended_gcd(current_mod, m2)
        
        if (r2 - current_rem) % g != 0:
            return None  # Pas de solution
            
        lcm = (current_mod * m2) // g
        diff = (r2 - current_rem) // g
        current_rem = (current_rem + current_mod * (diff * x % (m2 // g))) % lcm
        current_mod = lcm
        
    return current_rem

Exploitation des Paramètres de Chiffrement

Dans les variantes de Rabin où l'exposant public est une puissance de 2 (par exemple e = 4), l'attaque standard ne s'applique pas directement. La méthode consiste à traiter le problème comme une série de racines carrées imbriquées. En calculant les racines carrées modulo p et p, puis en combinant les résultats via le CRT, on génère un ensemble de candidats. Seule l'itération et la vérification de la charge utile permettront d'isoler le message clair.

Lorsque les facteurs premiers p et q sont très proches, ou lorsque des variables cachées de petite taille sont liées au module, la théorie des fractions continues devient un outil puissant. En développant le rapport de deux valeurs proches (comme n1/n2 ou a/p) en fractions continues, les convergents successifs révèlent souvent les facteurs premiers ou les petites variables cachées.

def get_convergents(num, den):
    cf = []
    while den:
        cf.append(num // den)
        num, den = den, num % den
    
    convergents = []
    n0, n1 = 1, cf[0]
    d0, d1 = 0, 1
    convergents.append((n1, d1))
    
    for i in range(1, len(cf)):
        n2 = cf[i] * n1 + n0
        d2 = cf[i] * d1 + d0
        convergents.append((n2, d2))
        n0, n1 = n1, n2
        d0, d1 = d1, d2
    return convergents

Attaques de Lissage (Smoothness Attacks)

Les algorithmes de Pollard (p-1) et de Williams (p+1) exploitent la factorisation de p-1 ou p+1. Si ces valeurs sont composées de petits facteurs premiers (lisses), l'attaque réussit rapidement. Dans les scénarios où l'ensemble des petits facteurs premiers est connu à l'avance, il est inutile de calculer des factorielles ou des puissances itératives aveuglément. Il suffit d'élever la base modulo N à la puissance de chaque facteur premier connu de la liste, ce qui réduit considérablement la complexité computationnelle.

Pour l'attaque p+1, on utilise les suites de Lucas étendues. Le principe reste identique : on multiplie les termes de la suite par les facteurs premiers connus jusqu'à ce que le PGCD avec N révèle un facteur non trivial.

Racines d'Ordre Supérieur et Algorithme AMM

Lorsque l'exposant de déchiffrement n'est pas premier avec phi(N), l'extraction de racines modulo p nécessite l'algorithme Adleman-Manders-Miller (AMM). Cet algorithme généralise l'extraction de racines carrées (Tonelli-Shanks) aux racines e-ièmes.

Le processus consiste à décomposer p-1 = e^s * q, à trouver un non-résidu e-ième, puis à itérer pour éliminer les composantes de racines de l'unité. Voici une implémentation fonctionnelle de l'extraction de racine e-ième :

import random
import math
from gmpy2 import powmod, invert

def amm_extract_root(ciphertext, exponent, prime):
    # Trouver un non-résidu e-ième
    while True:
        g = random.randint(2, prime - 1)
        if powmod(g, (prime - 1) // exponent, prime) != 1:
            break
            
    s = 0
    q_val = prime - 1
    while q_val % exponent == 0:
        q_val //= exponent
        s += 1
        
    k = 1
    while (q_val * k + 1) % exponent != 0:
        k += 1
    alpha = (q_val * k + 1) // exponent
    
    a = powmod(g, exponent**(s - 1) * q_val, prime)
    b = powmod(ciphertext, exponent * alpha - 1, prime)
    c_val = powmod(g, q_val, prime)
    h = 1
    
    for i in range(1, s):
        d = powmod(b, exponent**(s - 1 - i), prime)
        if d == 1:
            j = 0
        else:
            j = (-int(round(math.log(d, a)))) % exponent
        b = (b * powmod(c_val, exponent * j, prime)) % prime
        h = (h * powmod(c_val, j, prime)) % prime
        c_val = powmod(c_val, exponent, prime)
        
    return (powmod(ciphertext, alpha, prime) * h) % prime

Si l'exposant e est composé (par exemple e = e1 * e2), il faut appliquer l'algorithme AMM pour la partie qui divise p-1, puis utiliser l'inverse modulaire standard pour la partie première avec p-1. Les solutions finales sont obtenues en combinant les ensembles de racines via le CRT.

Ingénierie des Certificats Cryptograpihques

Dans les environnements réels, les clés RSA ne sont pas transmises comme de simples entiers, mais encapsulées dans des formats standardisés comme PEM ou DER. Ces formats reposent sur la norme ASN.1 (Abstract Syntax Notation One), qui structure les données selon le modèle TLV (Tag, Length, Value).

Le tag 02 désigne un entier (INTEGER). Le champ de longueur qui suit indique le nombre d'octets de la valeur. Par exemple, 81 80 signifie que la longueur est encodée sur 1 octet (0x80 = 128 octets). Une clé privée RSA complète contient dans l'ordre : la version, le module n, l'exposant public e, l'exposant privé d, les facteurs p et q, ainsi que les paramètres CRT (dp, dq, qinv).

Lorsqu'un certificat est tronqué ou corrompu, l'analyse manuelle de la séquence hexadécimale permet de récupérer des paramètres partiels. En identifiant les balises 02 et en validant les longueurs, on peut extraire des fragments comme q, dp ou dq.

def parse_truncated_asn1(hex_data):
    # Fonction conceptuelle pour extraire les entiers d'un flux ASN.1 tronqué
    extracted_integers = []
    i = 0
    while i < len(hex_data):
        if hex_data[i:i+2] == '02':  # Tag INTEGER
            i += 2
            length_byte = int(hex_data[i:i+2], 16)
            i += 2
            
            if length_byte > 128:
                # Longueur multi-octets (ex: 81 80 -> 128)
                num_length_bytes = length_byte - 128
                actual_length = int(hex_data[i:i+num_length_bytes*2], 16)
                i += num_length_bytes * 2
            else:
                actual_length = length_byte
                
            value_hex = hex_data[i:i+actual_length*2]
            extracted_integers.append(int(value_hex, 16))
            i += actual_length * 2
        else:
            i += 2
    return extracted_integers

Si l'on parvient à extraire q et dq (où dq = d mod (q-1)), et que le message original est strictement inférieur à q, le déchiffrement peut être effectué directement modulo q sans avoir besoin de reconstruire le module n complet : m = c^dq mod q.