Come si fattorizzano i numeri RSA
Uno dei metodi più noti di crittografia a chiave pubblica, RSA, si basa sul fatto che è difficile trovare i due fattori primi di un numero molto grande. Per dimostrare che in effetti i loro algoritmi sono robusti, nel 1991 gli RSA Laboratories hanno indetto una gara nella quale bisognava trovare quali erano i due numeri primi che moltiplicati tra loro davano i numeri da loro presentati. La gara è stata ufficialmente chiusa nel 2007, ma comunque gli appassionati hanno continuato a lavorarci su. Era dal 2020 (subito prima del lockdown, nel caso qualcuno volesse fare delle battutine) che non c’erano nuove fattorizzazioni, ma a settembre 2026 ne sono state pubblicate due di nuove: RSA-260, un numero di 260 cifre, e RSA-896, un numero di 896 bit cioè 270 cifre. Come è stato possibile?
Per il caso di RSA-260 Alan Woodward ha scritto una spiegazione (relativamente) semplice della matematica che sta dietro la fattorizzazione di un numero N così grande. Usare il metodo banale (dividere N per tutti i numeri primi fino alla radice quadrata di N, e fermarsi quando il resto è zero) è impraticabile. L’idea che al momento funziona meglio è un’altra: cercare due numeri X e Y tali che X²−Y² sia un multiplo di N. Prendiamo per esempio N=91, un numero che tutti sanno non essere primo. Se X=20 e Y=6, abbiamo X²−Y² = 400−36 = 364 = 4·91. Ora, sappiamo che X²−Y² = (X+Y)(X−Y). Se non siamo così sfortunati per cui uno dei due fattori è un multiplo di N, sappiamo che i suoi due fattori primi sono uno da una parte e uno dall’altra; ci basta quindi trovare il massimo comun divisore tra X−Y e N. Nel nostro caso abbiamo 14 e 91; l’MCD è 7, che è uno dei fattori di 91. Ovviamente avremmo potuto fare la stessa cosa con X+Y, nel qual caso avremmo trovato 13. Questa è la prima idea alla base del General Number Field Sieve, GNFS per gli amici.
Tutto bellissimo, ma come troviamo X e Y? Qui arriva la seconda idea. Un numero si dice essere “facile” se è il prodotto di numeri primi piccoli. Per esempio 300 è 2·2·3·5·5, e 2, 3, 5 sono primi piccoli. Invece 1372081 è un numero primo, e quindi di primi piccoli nella sua fattorizzazione non ce ne sono. Il GNFS setaccia i numeri dell’ordine di N per trovare quelli che sono prodotti di primi piccoli e si salva la loro fattorizzazione; un crivello (sieve) che non è quello di Eratostene ma è pur sempre un crivello. Una volta che abbiamo tante fattorizzazioni, è relativamente semplice costruire dei quadrati perfetti: basta provare a moltiplicare coppie di candidati per avere un risultato dove tutti i primi appaiono un numero pari di volte. Lavorare con primi piccoli rende più semplice fare questi accoppiamenti, tutto qua. Tutto qua si fa per dire, perché comunque anche questo accoppiamento equivale a una moltiplicazione di matrici sparse di elementi 0 e 1. (“sparse” perché di 1 ce ne sono pochi.) Proprio il tipo di operazioni che fanno gli LLM, tra l’altro. In realtà non si usano gli interi ma gli anelli Z[r], dove r è la radice di un polinomio irriducibile, che cioè non ha radici intere; in questo modo si riducono molto i candidati possibili e quindi si velocizza la computazione.
Naturalmente “velocizzare” è sempre relativo: Eric Lu, che ha fattorizzato RSA-260 con la sua startup Cognition, ha detto che l’operazione è costata 13,5 anni di GPU, per un costo teorico di 400000 dollari. In realtà ha usato tempo morto dei computer di Cognition, quindi il costo è teorico. Inolte ha usato un assistente software IA, Devin, per accelerare le operazioni. La stima di Lu è che si potrebbe dimezzare il costo senza grandi modifiche, e il costo per craccare RSA-1024 sarebbe intorno ai 30 milioni di dollari. Considerando che le chiavi a 1024 bit sono state deprecate nel 2013; la lunghezza minima di chiave suggerita è 2048 bit, e anche il GNFS non può fare molto. Si potranno fare miglioramenti? Non si sa, ma così ad occhio non credo che l’IA possa aiutare in questo campo, se non appunto a migliorare il software attuale.
