Newsgroup: it.comp.sicurezza.crittografia
Titolo: Fattorizzazione di interi

Salve a tutti...
Sono in periodo di tesina (oggi per me la scuola è iniziata, non
finita purtroppo) e, dopo aver capito come funziona il cifrario RSA dal
punto di vista matematico, volevo calcolare quanto tempo ci vorrebbe
per riuscire a fattorizzare un intero x con l'algoritmo "General Number
Field Sieve" ( 
http://en.wikipedia.org/wiki/General_number_field_sieve
)
Su wikipedia viene riportata la sua complessità computazionale, ma i
conti non mi tornano. Potete darmi una mano? ;)

 "General Number Field Sieve"
Forse può servire questo vecchio thread su sci.crypt:
http://groups.google.it/group/sci.crypt/tree/browse_frm/thread/efbc379921e77d96/5182b76301e62bde?rnum=41&hl=en&q=cristiano+gnfs&_done=%2Fgroup%2Fsci.crypt%2Fbrowse_frm%2Fthread%2Fefbc379921e77d96%2F466c79228b6ba03e%3Ftvc%3D1%26q%3Dcristiano+gnfs%26hl%3Den%26#doc_8b5695cb6148e483
Se quel thread non fosse utile, potremmo ritornare sull'argomento in questo 
ng.
Cristiano 
Inviato da X-Privat.Org - Registrazione gratuita 
http://www.x-privat.org/join.php

Cristiano ha scritto:

Grazie del link ;)
Io ho provato a calcolare il tempo necessario per fattorizzare un
numero intero di 200 cifre con GNFS e, dalla formula:
e^[(c + o(1)) * (log N)^(1/3) * (log log N)^(2/3) ]
mi risulta 1,81514792 * 10 ^ 188
Poi ho calcolato quante operazioni al secondo fa un processore da 2.2
GHz :
2,2 * 10^9
Quindi divido il numero di operazioni totali, dato dalla formulaccia di
prima, per il numero di operazioni al secondi del processore e risulta
che sarebbero necessari
8,25067236 * 10 ^ 178
ovvero
2.61627104 * 10 ^ 171
anni...
Cosa ho sbagliato? Non è un po' troppo ?

 8,25067236 * 10 ^ 178
Utilizzando il "mio" numero di operazioni, questo numero diventa 
1839465684723 s, pari ad appena 58329 anni.


Cristiano ha scritto:

Già, scusa... Avevo sbagliato...
Dai conti torna anche a me un numeri di anni pari a 58328 per
fattorizzare tramite GNFS un intero di 200 cifre, cioè di 663 bit...
A me pare un po' troppo...

m.e...@gmail.com
 ha scritto:

Ho fatto il calcolo anche con un numero da 1024 bit (308 cifre)
prendendo in considerazione il 1° PC della TOP500 che riesce a
compiere 280 TFlop/s:
http://www.top500.org/lists/2005/11
il risultato è di 14583 anni... Continua a sembrarmi troppo anche
perchè altrimenti che ragione ci sarebbe di usare anche le chiavi da
2048 bit!!!

2048 bit!!!
La formula fornisce una stima decisamente esagerata dato che la 
fattorizzazione di RSA200 richiese circa 55 anni-equivalenti di un AMD 2,2:
http://www.rsasecurity.com/rsalabs/node.asp?id=2093
 

nella tua valutazione, come attacco all'algoritmo RSA stai considerando 
solo la fattorizzazione di interi per individuare i due numeri interi p 
e q tali che m = p * q.
Purtroppo questo non è l'unico attacco possibile per craccare l'RSA.
Esistono diversi attacchi:
-chosen-ciphertext
-Punti fissi
-Cycling attack
-Attacco causato da una chiave privata troppo "piccola"
-Attacco a partire da una conoscenza parziale della chiave privata (e 
"piccolo")
-Cifre esposte della chiave privata (e "piccolo")
-Attacco ad una trasmissione a molti (e "piccolo")
-Attacco a messaggi collegati in modo noto ("e piccolo")
-Attacco a messaggi collegati in modo parzialmente casuale ("e piccolo")
-Timing attacks
-Random Faults
-Bleichenbacher's attack
Pertanto la chiave da 2048 è ormai indispensabile.
Ciao,
Ugo Chirico
http://www.ugosweb.com
Se fosse questo l'unico attacco allora le chiavi da 2048 sarebbero inutili
solo la fattorizzazione  che Si usano le chiavi


Hai totalmente ragione...
Io ho considerato solo quell'aspetto volutamente, mi serve per la mia
tesina ;)
Il problema è che il risultato a cui sono arrivato è impossibile:
Sul sito di RSA Security, in merito alla fattorizzazione di un numero
composto da 200 cifre proprio con l'algoritmo in questione , si legge:
"The sieving effort is estimated to have taken the equivalent of 55
years on a single 2.2 GHz Opteron CPU"
l'url: 
http://www.rsasecurity.com/rsalabs/node.asp?id=2879
Però con la formula che ho riportato (la riporta anche wikipedia),
calcolando il tempo impiegato per fattorizzare un numero di 200 cifre
con un processore da 2.2 GHz, mi risulta che si impiegherebbero 58328
anni... Che è un "po' tanto" di più dei 55 anni a cui fa riferimento
RSA Security.
Qualcuno può aiutarmi a capire come mai ho un risultato così
sballato?
ugos ha scritto:


sballato?
Da quello che ho letto la formula da te citata non puň essere usata per 
stime assolute ma solo per stime relative.