Newsgroup: it.comp.sicurezza.crittografia
Titolo: Progressi della fattorizzazione 'casalinga'

Abbiamo parlato in varie occasioni della fattibilità di fattorizzare un 
modulo RSA in tempi "utili".
Riassumendo brevemente le vecchie stime sui tempi, nell'agosto 2003 dicevo 
che estrapolando i tempi ottenuti utilizzando il MPQS, si poteva pensare di 
fattorizzare (con metodi "caserecci") un modulo da 384 bit in circa 7 anni.
A settembre 2003 dicevo che da prove più recenti "un singolo utente con un 
veloce pc può sperare di fattorizzare un modulino da 500 bit in qualche 
decina d'anni" e che usando PPSIQS (il programma più veloce che ero riuscito 
a trovare), per fattorizzare un modulo da 384 bit, avrei impiegato 
mediamente appena 332 giorni.
Dopo solo qualche giorno, sempre con PPSIQS, dicevo che un modulo da 384 bit 
lo si sarebbe potuto fattorizzare (sempre con metodi "caserecci") in un 
tempo compreso tra 61 e 111 giorni (in base a piccole variazioni dei 
parametri utilizzati in una formula interpolatrice più appropriata rispetto 
a quelle che ho usato in precedenza).
Saltando al presente, proprio pochi giorni fa, ho trovato un programma che 
implementa il MPQS in maniera veramente efficiente e neanche a farlo 
apposta, ho trovato pure il codice sorgente in C per implementare il metodo 
Levenberg-Marquardt (ottimo per essere usato nell'interpolazione di dati 
sperimentali).
Inutile dire che non ho resistito alla tentazione di fare nuove prove di 
fattorizzazione e rendervi partecipi. :-)
Con l'ottimo "msieve" ho fattorizzato 188 moduli da 231 a 321 bit (sono 
state necessarie poco più di 64 ore con un E6400 a 2,4 GHz).
MPQS ha un tempo d'esecuzione sub-esponenziale che la letteratura descrive 
così:
 1)   t(x) = e ^ [ (1+o(1)) * sqrt( x * ln x) ]
in cui x = ln(N).
Ma in tutti questi anni non mi ha mai convinto, in quanto troppo 
"restrittiva" perché impone che l'esponente di x e di ln(x) sia fissato a 
0,5.
Ho deciso, allora, di utilizzare la formula più generale:
 t(x) = e ^ [ (1+o(1)) * x^a * (ln x)^(1-a) ]
usata, ad esempio, per il NFS e che per a=0,5 è chiaramente identica a 
quella precedente.
Per essere calcolabile, l'ho trascritta così:
 2)   t(x) = b * e ^ [ x^a * (ln x)^(1-a) ]
e sono rimasto meravigliato dalla sorprendente attendibilità del risultato 
(verificata in maniera ragionevolmente approfondita).
Tralasciando il parametro 'b' (che serve solo per scalare i tempi), è 
interessante aver appurato che il parametro 'a' sembrerebbe compreso tra 
0,478 e 0,479, dimostrando che l'efficienza dell'algoritmo è decisamente 
migliore di ciò che la formula 1 lascia ipotizzare (pur restando ben lontano 
dallo 0,33 del NFS).
Il buon accordo tra i valori sperimentali e quelli interpolati è visibile in 
questo grafico:
http://www.webalice.it/cristiano.pi/msieve_gra.gif
in cui si nota anche una piccola "anomalia" intorno ai 280 bit.
Ho anche uploadato la schermata in cui il programma d'interpolazione (che ho 
scritto per l'occasione con il minimo indispensabile) mostra che per 
interpolare un numero al limite dei 384 bit dovrei impiegare poco più di 5 
giorni:
http://www.webalice.it/cristiano.pi/msieve_interpol.gif
Pur essendo evidente la grande riduzione dei tempi rispetto alle stime del 
2003, è evidente anche l'impossibilità di fattorizzare (con metodi 
"caserecci") in tempo utile gli attuali moduli RSA. Per esempio, un modulo 
da "appena" 1024 bit richiederebbe circa 4 miliardi di anni usando il mio PC 
e msieve. Tuttavia, tutti questi anni potrebbero essere ridotti di svariati 
ordini di grandezza utilizzando hardware specializzato ed opportuni metodi 
di parallelizzazione, magari implementando il più efficiente GNFS. Un 
fattore superiore a 10^9 rispetto ai miei modestissimi mezzi sembra più che 
verosimile, per cui, un'organizzazione motivata a farlo potrebbe 
fattorizzare un modulo da 1024 bit in circa 1 anno.
Dalle prove che ho fatto, per ottenere un margine di sicurezza decisamente 
più rassicurante, basterebbe passare a moduli da 1240 bit che dovrebbero 
aumentare di 3 ordini di grandezza i tempi richiesti.
Qualche commento?
Cristiano 

fattorizzare un modulo da 1024 bit in circa 1 anno.
Premesso che non sono in grado di entrare nei dettagli tecnici del
calcolo: perché pensi che un fattore di 10^9 sia ragionevole?
E se aumentassero i costi in modo proporzionale? Sarebbe ragionevole
pensare che una qual si voglia informazione possa valere decine di
migliaia di miliardi di Euro?
Una domanda da profano: dal punto di vista computazionale la
fattorizzazione è l'unica parte significativa della "rottura" della
chiave o c'è da considerare un fattore moltiplicativo nella stima dei
tempi? 
In altre parole tempo "rottura chiave" = 1* "tempo fattorizzazione" 
o
tempo "rottura chiave" = k * "tempo fattorizzazione" 
con k >>1 ?
      Ciao
      Michele

 con k >>1 ?
La prima.
Una volta che conosci i due numeri primi del modulo, calcoli la chiave 
privata in qualche millesimo di secondo.
Ciao
Cristiano 

 apparecchiatura che costa migliaia di volte di più.
come questa 
http://www.eurotech.com/IT/innovazione.aspx?pg=apenext
 che già 
più di 3 anni fa macinava 15 Teraflops a costo (relativamente) contenuto.
-- 
Post

 state necessarie poco più di 64 ore con un E6400 a 2,4 GHz).
Il soggetto delle due frasi citate è lo stesso?
Ed entrambi sono l'msieve che si trova qua? <
http://www.boo.net/
~jasonp/qs.html>
In quel caso, come mai hai usato MPQS e non NFS e, almeno stando alla
documentazione, il medesimo programa dovrebbe supportare?
Per ora ho solo dato una rapida lettura alla pagina su citata, ma sono
proprio curioso di fare in prima persona qualcuno dei test di cui
parli... (non che non mi fidi dei numeri che dici, ma fare le cose di
persona dà sempre una certa soddisfazione, no?)