Newsgroup: it.comp.sicurezza.pgp
Titolo: Craccare una chiave da 2048 bit?

http://punto-informatico.it/p.asp?i=42675
Una crew di hacker che si fa matrixianamente chiamare Neo ha recentemente
annunciato di aver messo a disposizione la propria rete di calcolo
distribuito, basata su di un software simile a quello utilizzato in
SETI@home, per un progetto il cui obiettivo è quello di crackare la chiave
crittografica adottata da Microsoft per firmare digitalmente i software che
girano su Xbox. 
[...]
Trovare la chiave crittografica di Xbox significherebbe poter far girare su
questa console qualsiasi software senza la necessità di intervenire
sull'hardware. L'unico problema è costituito dalla lunghezza della chiave,
pari a 2048 bit, che secondo alcuni richiederebbe decine di anni se non
addirittura secoli o millenni di elaborazione per essere trovata, e questo
anche disponendo di risorse di calcolo imponenti come quelle solitamente
accessibili ai progetti di computing distribuito.
Ma i ragazzi del Neo Project, forse sperando in un colpo di fortuna o in una
partecipazione di massa al progetto, si sono detti ottimisti e pronti a
giocare la sfida fino in fondo.
[...]
Commenti di Lapo:
l'articolo è un po' scevro di particolari e il sito anche per cui non posso
dare grandi commenti, ma se è una chiave (RSA, suppongo?) da 2048 bit
davvero allora "la veggio dura"... ci vuole sicuramente un tempo maggiore
della "vita" della console 0=)
http://www.rsasecurity.com/rsalabs/challenges/factoring/faq.html#HowMuchDoesItCost
...non lascia molte speranze, non vedo neanche perché quel progetto lo
avessero INIZIATO.
Comunque che sia da 2048 lo dice solo l'articolo, che sia RSA l'ho pensato
di sana pianta perché non lo dice (o almeno non l'ho tovato!)... quindi ci
sono molti punti "aperti".
Sono comunque felice di scoprire (se le mie supposizioni sono vere) che
Microsoft sta imparando osa sia la crittografia "seria"... ^_^
-- 
L a p o   L u c h i n i
l a p o @ l a p o . i t
w w w . l a p o . i t /

 Microsoft sta imparando osa sia la crittografia "seria"... ^_^
Considerando che c'è di mezzo la m$, io ridurrei i tempi di fattorizzazione
di un fattore 100 o 1000 :-)
Cristiano

> Fattorizzando 10 chiavi (RSA) da 210 bit, il tempo minimo impiegato è
stato
Scusami, per fattorizzare intendi  trovare i numeri primi la cui
moltiplicazione dia la chiave ?

moltiplicazione dia la chiave ?
Sě.


 richiederebbero sempre molti ma molti secoli (allo stato attuale di cose).
A scuola vorrei portare come argomento 'l'algoritmo RSA' ma gli 'ordini di
grandezza' delle chiavi non li ho per ora ben chiari:
2048 bit corrispondono a numeri con 616 cifre.
Una chiave pubblica e' composta di 2 valori: vuol dire che se si cifra a
2048 bit si utilizzano valori per le chiavi corrispondenti a 616 cifre?
Con queste grandezze e i PC attuali se i tempi per invertire la funzione per
violare la cifratura sono decisamente biblici, quanto e' pero' lungo il
tempo per cifrare?
Cio' che scriverei per la scuola e' tratto da un vecchio numero di 'quaderni
di scienze' che ho trovato in biblioteca:
-------------------------------
<E' famoso il fatto che nel 1994, una squadra di 600 volontari, unendo in
una rete internazionale i loro computer, workstation e supercomputer e
approfittando dei loro momenti di inattivita', ripartendosi frazioni del
problema globale siano alla fine riusciti a scomporre adeguatamente un
numero N alla 129, dal quale, ricavando i valori della chiave privata,
riuscirono a decriptare il messaggio criptato RSA che Martin Gardner aveva
scritto nell'agosto 1977 in un articolo intitolato 'Un nuovo tipo di
cifrario che richiederebbe milioni di anni per essere decifrato' pubblicato
su Scientific American.
Con valori di N di almeno 10 alla 138ª la cifratura RSA può essere
considerata inviolabile, ma ad esempio per alcune operazioni bancarie
importanti N tende a valere a 10 alla 308.>
-------------------------------
Cio' e' ancora valido attualmente?
Nelle 'operazioni bancarie' N quanto vale attualmente?
Regards,
 Mattex
 
P.S.: 'La quantita' di atomi nell'universo e' stimata in 10^60. (!?)'
--------------------------------
Inviato via 
http://usenet.libero.it

 P.S.: 'La quantita' di atomi nell'universo e' stimata in 10^60. (!?)'
Interessante, ma cosa c'entra?
Cristiano

 Interessante, ma cosa c'entra?
Nulla, e' solo che se e' vero mi consola un po' del fatto di sentirmi a
disagio con numeri cosi' grandi! :D
Regards,
 Mattex


 algoritmi'performanti'?				
Beh, la prima regola e' che per ottimizzare un algoritmo devi abbassarne
la complessita'. la potenza di calcolo con il passare degli anni cresce
linearmente, e anche unendo piu' calcolatori la situazione non cambia.
immagina di avere un algoritmo O(n^2). significa che aumentando la
grandezza dei dati, il numero di calcoli necessari aumenta
quadraticamente. Raddoppi i dati, quadruplichi il numero di operazioni.
Potrai anche raddoppiare la potenza di calcolo, ma il numero di
operazioni e' comunque quadruplicato, e il tempo necessario al calcolo
sara' comunque quadruplicato. Immagina che invece di raddoppiare i dati,
li quadruplichi, il numero di calcoli diventa 16 volte, per cui
anche raddoppiando la potenza di calcolo, il tempo e' 8 volte.... 
quindi il segreto e' quello di abbassare la complessita', sfruttando le
possibili ottimizzazioni sui cicli, nonche' trucchi... Comunque esiste
un limite inferiore, oltre il quale, senza avere ulteriori dati, non
puoi andare. tale ordine e' detto "theta" (oddio, o era omega?!? boh,
ora come ora mi sfugge....) per cui, ad esempio, una ricerca su una
lista ordinata non puo' essere migliore di O(log n), salvo avere
ulteriori dati (un dizionario... ma allora non e' piu' una lista
ordinata! :) )
Per _ora_ il miglior algoritmo di primality test (e di fattorizzazione
prima, sono problemi molto simili) e' O(log^6 n).
-- 
HappyCactus - Linux User #209744 - LFS User #6046 - >>> SMSPM1050 <<<
              YAGF Member Group >>> 
www.google.com
 <<<
Ci sono 10 categorie di persone al mondo: quelle che capiscono
il sistema binario e quelle che non lo capiscono.

 prima, sono problemi molto simili) e' O(log^6 n).
Magari fossero molto simili!
Se pensi che con un test deterministico di primalità certifichi numeri da
oltre 1000 bit in pochissimi secondi e che fattorizzare numeri da 1000 bit
richiede decenni...
Cristiano

 'performanti'?
Ci puoi giurare. Scommetto che un "normale" programma usato in crittografia
per trovare numeri primi da 1000-2000 bit impiega molto meno tempo del "tuo"
programmino d'esempio per numeri da 10-20 bit. Le tecniche usate sono
totalmente diverse.
Cristiano

 1000 bit richiede decenni...
Non ricordo dove l'ho letto, ma si diceva che la fattorizzazione e' solo
pochino piu' difficile di un test di primalita'. forse era sullo stesso
documento dell'universita' indiana (il secondo link). 


prima, sono problemi molto simili) e' O(log^6 n).
Veramente non mi risultavano cosě collegati, difatti il miglior algoritmo
attuale di fattorizzazione č l'NFS (number field sieve), con
O(e^(c * (ln n)^1/3 * (ln ln n)^2/3))



[...] These algorithms that are commonly used in practice are actually
faster than the ones proposed in [1].  The result in [1] is a very important
one in complexity theory, but probably have no (practical) impact in
cryptography.


 documento dell'universita' indiana (il secondo link).
E` probabile, vista la difficoltà d'implementazione del loro test.
Comunque non vorrei essere frainteso. Scrivere un programma per fattorizzare
è paragonabile allo scrivere un programma per testare se un numero è primo,
ma l'efficienza del programma per fattorizzare è immensamente inferiore a
quella dell'altro.
Cristiano

 crittografia]) è accettabile, il Rabin-Miller è decisamente da preferirsi:
Ma la probabilità di sbagliare può essere resa talmente bassa da essere
trascurabile (mantenendo una velocità molto alta).
Per esempio è molto più probabile che ti cada un aereo sulla testa o, più
semplicemente, che l'implementazione che sfrutta i numeri primi sia bacata,
piuttosto che MR si sbagli.
Cristiano

 primi di Sophie Germain)
Non solo (e non proprio). I due primi (del modulo n) devono avere un grande
fattore per: p - 1 (fattore che chiamiamo f), f - 1 e p + 1.
Io continuo ancora ad usare i "primi forti" nei miei programmi (tanto il
tempo per trovarli aumenta solo del 10% circa) ma, in effetti, fattorizzando
con le curve ellittiche i primi forti diventano deboli :-)
Cristiano

con le curve ellittiche i primi forti diventano deboli :-)
Già, l'ECPP non mi pare che abbia "particolari requisiti" sul primo che si
cerca di "provare", quindi ogni primo è "uguale"... o almeno Mathworld non
parla di tali requisiti 0=)


quella dell'altro.
Non capisco :-?
Intendi che "scrivere un programma per fattorizzare" è simile a "un
programma per dimostrare la primalità", così come potrebbe essere simile a
"un programma di word-processing"?
Tra i primi due e il terzo l'unica differenza che noto è che i primi hanno
come requisito l'uso di un qualche teorema o algoritmo pensato da un
matematico, mentre il secondo ha come richiesta di avere una buona
interfaccia grafica, ma nno vedo molta utilità nel paragonare le "difficoltà
di passare da teorema a programma funzionante"... a quel punto *tutti* gli
algoritmi preparati da altri hanno una difficoltà simile ^_^
Mi sa che ti ho frainteso comlpetamente, stavolta ^_^


trascurabile (mantenendo una velocità molto alta).
Sì, infatti come test "pratico" resta il migliore.


inferiori ai 64 kB di ram).
Però!
Mi incuriosisci MOLTO.
Sono cose "particolarmente avanzate" o posso prendere come "sfida personale"
il cercare di re-inventarle?
Il tempo di "accesso" si riduce di molto?
(già con il mio trucco dei "solo dispari" l'accesso ad un numero richiede
uno "shift a destra" anziché un semplice indirizzamento, ma questo è
certamenet trascurabile dato il tempo necessario per le chiamate di metodo e
il temop necessaria a recuperare il bit richiesto dalla word che lo
contiene)


primi è utile solo se è in RAM imho).
Mi correggo: anche fino a 10^22 conviene tenerli come bitset che come lista.
Conviene perfino anche rispetto a una lista dove ogni numero occupa il
numero minimo di bit richiesto dal numero più grande in lista!
Dato che *DOVREI* studiare per l'università e ne ho zero voglia ho *PERFINO*
fatto una dimostrazione che asintoticamente conviene il bitset *SEMPRE* 0=)
In un "bitset di soli numeri dispari" lo spazio occupato è: 1 bit per ogni
due numeri qualsiasi, chiamo 'b' questa funzione.
In una "lista a numero minimo di bit" lo spazio occupato è: n bit per ogni
numero primo, chiamo 'l' questa funzione.
Quindi, se 'n' è il numero massimo che voglio avere in tabella:
b(n) = ceil(n/2)
l(n) = pi(n)*ceil(log(n)/log(2))
Al posto di l(n) consideriamo un caso ideale in cui posso avere un numero
frazionario di bit per ogni numero, in modo da eliminare il fastidiocso
ceil()
l'(n) = pi(n)*log(n)/log(2)
Ma ricordandosi la formula asintotica per pi(n):
pi(n) ~ n/(log n)
l'(n) ~ (n/(log n))*(log(n)/log(2))
Possiamo semplificare il (log n), ottenendo:
l'(n) ~ n/log(2)
Dato che:
2 > log(2)
Abbiamo quindi:
b(n) < l'(n) <= l(n)
Da notare che anche "1 > log(2)" quindi l'ottimizzazione di tenere i soli
numeri dispari non è necessaria per la dimostrazione (è comunque così
semplice da fare che non vedo perché non utilizzarla).


 parla di tali requisiti 0=)
Sì, provando a fattorizzare moduli ottenuti da primi casuali e quelli
ottenuti da primi forti non noto differenze. Ma questo vale anche per il
multiple polynomial quadratic sieve (che detto tra noi è ottimo!).
Cristiano

 semplice da fare che non vedo perché non utilizzarla).
Ottima dimostrazione (mi fido ciecamente :-) ).
Scherzi a parte, č vero. Tanto piů che l'accesso al vettore di bit č piů
veloce dell'accesso al vettore di numeri primi (almeno con il P4).
Cristiano

 Mi sa che ti ho frainteso comlpetamente, stavolta ^_^
Mi sono spiegato male. Volevo dire che la difficoltà d'implementazione è
simile.
Cristiano

 il cercare di re-inventarle?
Non per sottovalutarti, ma la faccenda č macchinosa... :-)
Non so se l'avevi capito, ma il metodo non l'ho inventato io. L'ha
inventato D. J. Bernstein e trovi il codice sorgente nel web (primegen).
Se vuoi una versione "compattata" (e ovviamente funzionante,
ultra-testata) te la spedisco.
A differenza del crivello "liscio", con primegen puoi spingerti fino a
numeri da 50 bit in tempi ragionevoli (senza aumentare la ram
necessaria).
Cristiano

 sono primi). [...]
Esatto.
Per la precisione, lo uso per creare una tabella di numeri primi che uso
quando cerco i numeri primi di dimensioni crittografiche.
Prima di usare MR, vedo se un candidato è divisibile per i primi 1000 o
2000 numeri primi; essendo molti i candidati scartati con la divisione,
diminuisce di molto i numeri da sottoporre al test di MR (con grande
beneficio per la velocità).
Cristiano

veloce dell'accesso al vettore di numeri primi (almeno con il P4).
Oddio, addirittura "più veloce" forse è eccessivo.. ma a ben pensarci
dipende dal tipo di accesso:
accesso del tipo "dimmi l'ennesimo primo":
per il vettore è O(1)
per il bitset è O(n) [ricerca sequenziale contando i primi incontrati]
accesso del tipo "dimmi se il numero n è primo":
per il vettore è O(ln n) [ricerca dicotomica in vettore ordinato]
per il bitset è O(1)
Ben vedendo il vettore è più efficente in un caso di ricerche con equale
probabilità, ma in un programma di crittografia direi che al 99% dei casi la
domanda è se un numero è primo o meno, e non quale è l'ennesimo primo =)



Quello non è un "Crivello di Eratostene" ma un "Crivello di Atkin" e usa le
"forme quadratiche" chein questo momento non mi sono più familiari delle
"forme modulari" o delle "curve ellittiche" 0=)
Scarico il paper e demando la lettura/studio a un futuro... certo che se
quello che dice è vero (ed *è* vero) è impresisonante la differenza di
performance... io *CREDEVO* che, dato che già il povero Eratostene, usa SOLO
somme, non si potesse diminuire la complessità -_-
Da quel che leggo lui usa MENO di una somma per numero... (mentre Eratostene
ne usa parecchie... una per ogni divisore primo di ogni numero)


beneficio per la velocità).
Io invece l'ho usato per implementare i certificati di primalità di Pratt.
Mi piacciono molto di più degli ECPP: sono molto più "logici" graficamente,
e poi il piccolo teorema di Fermat lo "capisco", la teoria delle curve
ellittiche devo ancora "assimilarla"...


simile.
Gh, ok.
dipende molto anche dall'algoritmo usato però... se un Pollard Rho lo si
scrive in 5 minuti circa, un NFS puoi impiegarci anche una settimana, mi
sa... (a dire il vero attualmente ci metterei un tempo pressoché infinito,
dato che non ne ho ancora capito bene la teoria)


[riguardo alla velocità delle implementaizone dell'AKS]
Ripensandoci comunque non bisogna scordare che ilpaper parla di ASINTOTI...
e gli asintoti sono delle brutte bestie, è vero che per capire che 1023 è
primo ci mette 3 secondi quando PollardRho (in Java!) ci mette circa 0ms,
però chi ci dice che già a quelle dimensioni è O(ln^12 n)?
Nessuno 0=)
Giusto per fare un esempio il seguente numero è *FACILISSIMO* da
fattorizzare con il PollardRho mentre è molto più difficile con gli altri
metodi. Questo nonostante PollardRho sia, asintoticamente, uno dei peggiori
tra gli "algoritmi non triviali".
97714584631340851267008241099169220015767110197088054464058014854550\
31700590446085370088811656212041062090475915163270448122642003478149\
10972058386824696264720261658590021085253979957753116341472641605789\
29031563334062113711236464203339881414660711970879598914029610837375\
395957365551329882977129150494739434497
(ovviamente ho costruito questo numero *apposta* per essere debole contro il
PollardRho ^_^)


 dato che non ne ho ancora capito bene la teoria)
Stessa cosa per me. Avendo MPFS, pensavo d'implementare anche NFS (che è
ancora più veloce). Ieri guardavo i documenti per NFS; c'avessi capito
un accidente! :-)
A proposito, ho postato una domanda su un ng matematico, ma non m'hanno
risposto; forse tu...
MPFS richiede asintoticamente
exp( ( 1 + o(1)) (log n)^(1/2) (log log n)^(1/2) )
e ho alcuni tempi d'esecuzione per n=60-240.
GNFS richiede
exp( ( 1.9 + o(1)) (log n)^(1/3) (log log n)^(2/3) )
Hai idea se è possibile stimare il tempo d'esecuzione di GNFS conoscendo
i tempi dell'altro?
Cristiano

 dipende dal tipo di accesso:
Non dimenticare che la cache gioca un ruolo fondamentale e che le
operazioni sui bit sono velocissime.
Io inizialmente, per un programma, usavo un vettore di numeri primi (da
32 bit in una versione e da 64 bit in un'altra). Sono passato al vettore
di bit perché era piů veloce (l'accesso era sequenziale).
Poi sono passato a primegen che stacca entrambi i metodi di molte
lunghezze.
Cristiano

multiple polynomial quadratic sieve (che detto tra noi č ottimo!).
Beh, era il migliore fino all'avvento dell'NFS... molto di recente, no?
Io no ho ancora avuto il tempo e la voglia (e le 'palle', se mi passate il
termine 0=) per studiarmeli abbastanza da implementaril =)


i tempi dell'altro?
è molto difficile stimare dei tempi a partire da degli asintoti: non si sa
per numeri "quanto grandi" sono approssimazioni decenti e non si sanno le
"costanti"... sono rigorosi solo all'infinito.
Solo che "infinito" per un algortimo può essere "n > 1000", per altri (tipo
l'ECPP) è "n > 10^10"... (prima difatti il certificatore di Pratt è molto
più veloce, nonostante asintoticamente sia peggiore)


 ne usa parecchie... una per ogni divisore primo di ogni numero)
Sono rimasto scettico fino a quando non l'ho usato. Non potevo
immaginare un abisso simile tra i due crivelli.
La sfortuna è va bene solo per numeri "piccoli" (non crittografici).
Cristiano

 tra gli "algoritmi non triviali".
E` vero; MPNF, dopo alcuni minuti, non l'ha ancora fattorizzato.
Però Brent, Williams p+1, Pollard p-1 (per non parlare di Lenstra) lo
fattorizzano all'istante.
Comunque, per AKS (guardando le implementazioni) giurerei che il tempo
aumenta all'aumentare della grandezza dei numeri (anche se l'efficienza
tende asintoticamente al meglio del meglio).
Penso che difficilmente un algoritmo simile diventerà utile in
crittografia.
Cristiano

 aiuterebbe anche col crivello di Atkin 0=)
Non lo chiedere a me... :-)
Cristiano

 termine 0=) per studiarmeli abbastanza da implementaril =)
In effetti è un intreccio incredibile; mia accontento di MPQS (sto
vedendo che in altri post ho scritto MPFS; non so a che pensavo...).
Cristiano

altri con GMP).
Mah, usango GMP e Miracl "ultimi" sull'implementazione del francese ho avuto
tempo 3 volte inferiori con GMP (again, vedi post su sci.crypt).
Comunque il programma suddetto pare avere GROSSI problemi, quindi
probabilmente conta ben poco come test.


 tempo 3 volte inferiori con GMP (again, vedi post su sci.crypt).
Ho cercato ma non l'ho trovato. Che oggetto ha il post?
Cristiano




crittografia.
Non è neanche nato con quell'idea, per stessa ammissione degil autori.
D'altra parte il risultato teorico è strabiliante.
Anche il "teorema di Fermat" era dato per buono da decenni, ma finché non
l'hanno dimostrato... "era diverso". 0=)


vedendo che in altri post ho scritto MPFS; non so a che pensavo...).
Beato te, a me pareva complicato anche quello 0=)
Perň era tempo fa... prima o poi devo ri-darci un occhio =)


lunghezze.
Eh beh, se usa un decimo delle addizioni e un decimo della RAM =(
Devo 'troppo' studiarmelo bene....



Stranamente vedo solo la risposta di Yves... boh?
Cristiano

Stranamente vedo solo la risposta di Yves... boh?
Faccio prima a citarlo...
[please notice that I didn't modify the sources download from that website
in ANY way, so I must press ^C after a line is printed to get "single"
timings: I used wget and then nano to convert ("&gt;","&lt;","&amp;") to
(">","<","&")]
$g++ -O6 aks.cc -o aks
$g++ -O6 aks_gmp.cc -o aks_gmp -lgmp
$g++ -Imiracl/ -O6 aks_miracl.cc miracl/miracl.a miracl/big.o miracl/monty.o
miracl/poly.o miracl/polymod.o miracl/miracl.a -o aks_miracl
$ cat num10001 
10001
$ time ./aks_gmp <num10001 
n=10007, r=719, q=359, s=339, power of a prime.
^C10009, r=719, q=359, s=339 23
real    0m9.992s
user    0m9.909s
sys     0m0.008s
$ time ./aks_miracl <num10001 
n=10007, r=719, q=359, s=339, power of a prime.
^C10009, r=719, q=359, s=339 10
real    0m24.120s
user    0m23.920s
sys     0m0.016s
$ time ./aks <num10001 
n=10007, r=719, q=359, s=339, power of a prime.
^C10009, r=719, q=359, s=339 11
real    0m20.490s
user    0m20.378s
sys     0m0.001s


 Beato te, a me pareva complicato anche quello 0=)
Non penserai che l'ho scritto io!? :-)
E` quello fornito di serie con miracl.
Cristiano

 D'altra parte il risultato teorico è strabiliante.
Anch'io, da pratico allo stato puro :-) devo ammettere il grande rilievo
matematico di quell'algoritmo.
Cristiano

 [...]
La risposta dell'autore ti ha illuminato? :-)
Cristiano

La risposta dell'autore ti ha illuminato? :-)
A dire il vero mi sono illuminato da solo PRIMA della sua reply.. non avevno
notato che io scrivevo 10001 e il primo trovato era 10007 (e *non* 10001,
che giustamente non č primo).
Insomma tutto nasceva dal fatto che il 7 č abbastanza simile all'1 come
numero 0=)
Comunque resta *squallidamente lento* 0_o


E` quello fornito di serie con miracl.
Ah ok, a dire il vero era proprio quello che pensavo ^_^


Ah ok, a dire il vero era proprio quello che pensavo ^_^
Mi riferivo a qeusta riga, e non alla seguente riferita a Miracl...
(rileggerlo mi ha fatto notare l'ambiguità)


La sfortuna č va bene solo per numeri "piccoli" (non crittografici).
Io ancora non riesco a concepire come possa essere piů efficente nel tenere
i numeri in RAM.. capisco piů efficente nella ricerca, ma una volta trovati
nno immagino proprio come possa "stoccarli" in cosě poca RAM...
D'altra aprte se mi venisse in mente forse non sarebbe in risutlato "degno
di DJB e Atkin" 0=)
Non mi resta che scaricarmi il paper e cercare di raccapezzarmici...
(dubito)


 Comunque resta *squallidamente lento* 0_o
Purtroppo è vero :-(
Cristiano

 poca RAM...
Avevo iniziato a leggere la documentazione. E, in effetti, facendo
alcune prove con i polinomi più semplici mi ricordo che s'iniziava già a
vedere il vantaggio rispetto al crivelllo d'Eratostene.
Poi, però, *tentando* di capire la teoria dietro a primegen mi sono un
attimino perso :-)
Comunque, li calcola al volo a piccoli blocchi. Per esempio, io per
ottenere la massima velocità ho dovuto impostare il calcolo a 512 numeri
per volta (tenere i numeri nella cache aiuta moltissimo).
Cristiano

 (rileggerlo mi ha fatto notare l'ambiguitŕ)
Mi viene da ridere. Sai che noi due non ci capiamo in maniera
impressionante! :-)
Leggendo "Beato te, a me pareva complicato anche quello" ho pensato che
tu pensavi che l'avessi scritto io.
Leggendo "Ah ok, a dire il vero era proprio quello che pensavo ^_^" ho
pensato che tu pensavi che *non* l'avessi scritto io, cioč č come se tu
avessi pensato: "Sě, figuriamoci se questo qui ha scritto un prg per
NFS!".
Con l'ultimo messaggio mi hai confuso le idee :-)
In questo caso non ha alcuna importanza (stiamo qui a farci due risate)
ma cos'č che pensavi: che l'avessi o non l'avessi scritto io?
Cristiano

 EOF
$ time gpg --batch --gen-key foo
gpg: Generating a standard key
.++++++++++.++++++++++++++++++++.+++++++++++++++.+++++.++++++++++.++++++++++++++++++++.++++++++++.+++++++++++++++++++++++++++++++++++++++++++++.>+++++.....................................................+++++
+++++..+++++.+++++.++++++++++..++++++++++^^^
gpg: done
real    0m1.842s
user    0m1.483s
sys     0m0.062s


ma cos'č che pensavi: che l'avessi o non l'avessi scritto io?
E meno male che l'ultimo auto-reply voleva essere chiarificatore 0=)
Usiamo proprio l'italiano a due estremi perfettamente "legali" ma
ciononostante quasi totalmente incompatibili ^______^


>      Subkey-Length: 1024
Non so che significa tutta 'sta roba, ma probabilmente vengono generate
anche altre chiavi... Può essere? Comunque, anche in questo caso 2
secondi mi sembrano un po' troppi.
Cristiano

[Addendum]
Per completezza ho fatto altre prove.
Utilizzando l'identico programma (scritto con BCB1.0 e libreria miracl),
lo *stesso* numero primo forte da 522 bit viene trovato in 3 pc nei
seguenti tempi:
P2 450 MHz Win98se: 0,48 s
mobile AMD AthlonXP 1500+ 1,3 GHz WinXPpro: 0,36 s
P4 1,5 GHz WinME: 0,25 s
Cristiano

 ALLIBISCO: 3 secondi circa per dirmi che č una "potenza di primi".
Hai visto su sci.crypt la nuova versione di Aldo D. in UBASIC? Il thread
č "Proving primality of an integer".
Velocissima! Per certificare un primo da 1024 bit impiega circa 2
secondi.
Se non c'č sotto qualcosa di "strano", questa č finalmente
un'implementazione utile!
Cristiano

 un'implementazione utile!
Certo che i commenti al codice non aiuteranno molto chi e' in grado di
controllare se e' "strano" o no! :-/
Tra le poche note ho letto che questo algoritmo presenta dei limiti di
calcolo, overflow, ma piuttosto alti.
leggo di gente che usa PGP a 1024 bit, altri a 2048; perche' tutti non si
attestano sui valori piu' alti che penso siano piu' sicuri? Anche qui ci
sono dei limiti e quali sono i limiti massimi utilizzati per le chiavi PGP?
Potresti per cortesia farmi un effettivo esempio scritto dei 2 valori di una
ipotetica chiave PGP a 2048 bit?
Non ho ancora capito quanto alla fine siano effettivamente lunghe le chiavi
nella pratica reale.
Mi sembra pure che la conoscenza dei 2 valori di una chiave pubblica
facilitino la ricerca di quella privata: voglio dire che se anziche'
craccare una chiave si cracca un codice cifrato RSA, non conoscere neppure
la chiave pubblica e' un ulteriore svantaggio. Infatti uno dei 2 valori, il
modulo, e' comune ad entrambe le chiavi. Sbaglo?
--------------------------------
Inviato via 
http://usenet.libero.it

 dei 2 valori, il modulo, e' comune ad entrambe le chiavi. Sbaglo?
Non sbagli, il modulo è comune alle due chiavi.
Ma dire di non conoscere la chiave pubblica non ha molto senso; la
chiave pubblica *deve* essere nota a tutti se vuoi usare l'RSA.
Cristiano

 cifre decimali. Era questo che volevi sapere?
Nooo...! :-D si, grazie mille.
Ma c'e' un motivo per il '17' ? perche' mi sembra che conoscendo il modulo
(pubblico), se si restringe ancora l'esponente proprio a 17 cifre, il campo
della ricerca per craccare una chiave si dovrebbe accorciare di molto pur
essendo sempre un bel mucchio di numeri.
Pensa che mi stavo facendo l'idea che l'esponente dovesse avere ~300 cifre
decimali...
e forse gia' tu sai che io riesco a fare i calcoli soltanto con 7-8 cifre
sia per l'esponente che per il modulo. :-( Ora pero' anche grazie agli input
di L.A.P.O. e Mauro Z. mesi fa, in linea teorica ho ben capito come
scomporre l'esponente in moltiplicazioni di potenze con base 2, per cui
confido in un futuro miglioramento. Penso che provero' a mettere i risultati
della scomposizione in un array e mi chiedo solo a che valori potra' portare
la disponibilita' massima di 65000 (credo) valori memorizzabili nell'array.
Dovro' riorientarmi anche sulla costruzione delle chiavi: prima non me ne
ero occupato perche' gia' il mio calcolo andava in overflow con le chiavi
piu' grosse che mi ero calcolato (10 cifre). Penso che dovro' studiare
l'algoritmo di Euclide
   Esempio: (Deduzione del valore E non immediata)
              (E * 25) Mod 108 = 1
              13 * 25 = 325
              325 Mod 108 = 1
              E = 13
anche qui mi ero inventato un algoritmo io (essenzialmente faceva calcoli
finche' non ci azzeccava) ma se 'Euclide' resiste da 2000 anni forse e' il
caso che gli dia un'occhiata! :-D
Regards,
 Mattex


 anni forse e' il caso che gli dia un'occhiata! :-D
Forse sì :-)
Cristiano

 
Craccare chiavi oltre i 128 bit è una grande bella discussione accademica. 
Ma se si e' nel business della sicurezza, si sa che conviene perseguire 
altre strade ben piu' economiche (sia in termini di tempo che di denaro) 
per ottenere lo stesso scopo. Nel caso specifico, potrebbe costare di più 
il cracking che comprarsi il software originale ... ma questa è passione, 
non business.
Nel mondo reale, per poter essere prima prodotti all'origine e poi fruiti a 
destinazione, i dati che verranno cifrati (a 512, 1024, 2048, a quanti 
volete bit) devono esistere in chiaro da qualche parte ed in qualche 
momento. 
In particolare, a destinazione, i dati saranno messi in chiaro su un 
qualche file temporaneo per poter essere usati. Più efficiente ed efficace 
per gente molto motivata (Guardia di Finanza, Polizia, Servizi, etc...) 
cercare di avere quei dati all'inizio o alla fine del tubo che comprarsi 
dei Cray-2 e magari metterci anni per decifrare in mezzo al tubo.
Intercettazioni ambientali, analisi forense dei dischi (i file temporanei 
non sono poi così temporanei...), ordini dei giudici, la minaccia di farsi 
dieci anni nelle patrie galere, una pistola nove millimetri puntata alla 
tempia, .... metodi più economici e rapidi per avere i dati in chiaro non 
mancano.
--
Alex

 ha scritto nel messaggio
news:Ejn4a.130388$ZE.37...@twister2.libero.it...


 
Assolutamente d'accordo. Nel mio precedente post non intendevo dire che la 
crittografia forte è inutile. Il punto, probabilmente mal espresso, era che 
per le applicazioni "commerciali" e per gli obbiettivi delle normali 
aziende civili, esistono altri modi per "craccare" i canali cifrati (citati 
nel primo mio post) e che la crittografia non è l'UNICA risposta alle 
esigenze di segretezza delle informazioni.
Ciao,
-- 
Alex