Newsgroup: it.comp.sicurezza.crittografia
Titolo: Considerazioni sulla sicurezza della crittografia

Ciao a tutti,
vorrei sottoporre alla vostra considerazione qualche calcoletto...
Prendiamo in esame un algoritmo di fattorizzazione (in pseudo codice):
---
Input: intero n>=2 (n=p*q con p,q primi)
Output: p,q
p=2
found=false
while(!found) do
        if (n mod p=0) then found=true
        else p++
return p, n/p
---
Se bn è il numero di bit necessari per rappresentare n, la complessità di
questo algoritmo risulta essere 2^(bn/2) (fidatevi), quindi il numero di
operazioni necessarie per la fattorizzazione e di conseguenza il tempo
aumentano in maniera esponenziale in base al numero di bit con cui è
composta la chiave.
Il numero di bit che riesce a fattorizzare questo algoritmo nel tempo t (in
secondi) è (log è in base 2): bn/2=log(t) --> bn=log(t)/2
Quindi, se per esempio bn è di 512, il tempo per fattorizzare l'ipotetica
chiave n (appunto di 512bit) è t=2^(512/2)=10^77sec (supponendo
un'operazione al secondo). Se facciamo andare l'algoritmo su un computer
con processore a 1Ghz (10^9 operazioni/secondo) in 10^68 secondi si
dovrebbero trovare p e q. Se un anno sono 10^8 secondi, in totale
occorrerebbero 10^60 anni.
Se noi facessimo funzionare l'algoritmo in una macchina 10 volte + potente,
a parità di tempo t per trovare p e q servirebbero (1/10)(2^(bn/2)
operazioni perchè l'algoritmo ci impiegherebbe 1/10 del tempo che ci
metteva prima.
Poniamo t=(1/10)(2^(bn/2)) considerando sempre una operazione al secondo.
Un pò di passaggi: 2^(bn/2)=10t -> bn/2=log(10t) -> bn/2=log(t)+log(10)
quindi bn è dato da: log(t)/2 + log(10)/2 -> log(t)/2 + ~1,66.
Il numero di bit che si riuscirebbero a fattorizzare, a parità di tempo, in
una macchina 10 volte + potente, aumenterebbe solamente di 1,66.
Facciamo finta che esista un supercomputer che lavori a 1000THz (10^15
operazioni/secondo).
A parità di tempo l'algoritmo ci impiegherebbe un t=(1/10^15)(2^(bn/2)) ->
(10^15)t=2^(bn/2) -> bn/2=log(10^15)(t) -> bn/2=log(t)+log(10^15) quindi il
numero di bit in + che riuscirebbe a fattorizzare diventa: bn=log(t)/
+log(10^15)/2 -> bn=log(t)/2 + ~25
Questo fa capire che anche aumentando in maniera esagerata le prestazioni
del computer, attualmente, data la grandezza delle chiavi in circolazione,
credo che perfino per l'FBI o qualsiasi ente governativo sarebbe
impossibile rivelare un messagio criptato con PGP o simili.
Non sò con le fibre ottiche...
C'è da dire che l'algoritmo per fattorizzare impiegato di solito non è
quello che ho scritto io in cima all'email, ma, se nn dico caxate, dovrebbe
ridurre il tempo di fattorizzazione da 10^68sec a 10^40sec, bho non sò, cmq
facciamo finta di avere una chiave da 2048bit: t=10^308sec supponendo
un'operazione al secondo. Il tempo impiegato dal supercomputer di prima
diverrebbe: t'=10^308/10^15=10^293sec, metti che l'algoritmo sia efficente,
e poniamo il tutto a 10^200sec, in anni sarebbero 10^192, in secoli 10^190,
in millenni 10^189 etc etc... bhe avete capito...
Tutto questo per dire che secondo me la crittografia con PGP è veramente
sicura e non esiste ente governativo o altro che possa leggere quello che
scriviamo una volta criptato, sempre finchè ci sarà l'algoritmo per la
fattorizzazione che ha complessità 2^n! Se i vari enti hanno scoperto
algoritmi con efficienza migliore... allora sn guai, ma credo sia altamente
improbabile... Cn tutte le superteste che ci sono in giro tra matematici
etc, vuoi che proprio i militari ci siano riusciti?
Che ne pensate??
Mi scuso per eventuali errori, dato che in mate nn sn una cima... cmq era
solo per dare una piccola dimostrazione e far capire...
Ciao Ciao
        Manuel

 Che ne pensate??
Sembra quasi impossibile che i militari abbiano trovato algoritmi migliori,
mentre migliaia di ricercatori non ci siano riusciti.
Tuttavia, i militari *potrebbero* avere computer incredibilmente più potenti
di quanto noi possiamo immaginare, basati su tecnologie che in campo civile
sono appena in stato embrionale. Chi può dirlo!
Cristiano

etc, vuoi che proprio i militari ci siano riusciti?
Lo sai che l'ente che ha assunto tra le sue file il maggior numero di
matematici e' proprio l'NSA?
Ciao
FIFO

 campo civile sono appena in stato embrionale. Chi può dirlo!
La sicurezza ce la da' il fatto che attualmente il problema della
fattorizzazione e' un problema NP. Possono anche aumentare la velocita'
dei loro calcolatori, ma finche' essa cresce linearmente, saranno sempre
sconfitti.
A questo punto il problema passa da quello della crittografia a quello
della sicurezza generica dei sistemi. 
Un esempio lampante e molto istruttivo e' quello dato dal caso del boss
mafioso Nicodemo Scarfo Jr.[1].
[1]
http://abcnews.go.com/sections/scitech/CuttingEdge/cuttingedge011221.html
-- 
*    HappyCactus - Linux User #209744 - BOFH Certified Engineer    *
*           27/11/2003 Rilaciata la prima relase di qixl!          *
*    
http://sourceforge.net/projects/qixl
 : una gui per iSiloXC    *
*  
www.google.com
 / 
groups.google.com
 : cercare prima di chiedere  *


In ogni caso i matematici assunti dall'NSA non potranno mai essere piů di
tutti gli altri matematici sparsi per il Mondo.
Secondo me, possiamo stare sicuri che il miglior algoritmo che gira sui
computer che noi conosciamo č l'algoritmo che tutti conosciamo.
Cristiano

computer che noi conosciamo č l'algoritmo che tutti conosciamo.
Sicuri e' una parola grossa...inoltre in campi come la matematica non
conta la quantita' ma la qualita'...ne puo' bastare anche uno di
matematico per fare un algoritmo impensabile per il resto del mondo
(altri matematici compresi)...basti pensare ai teoremi di Fermat.
Ciao
FIFO

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
FIFO wrote:
| Sicuri e' una parola grossa...inoltre in campi come la matematica non
| conta la quantita' ma la qualita'...ne puo' bastare anche uno di
| matematico per fare un algoritmo impensabile per il resto del mondo
| (altri matematici compresi)...basti pensare ai teoremi di Fermat.
Veramente mi sembra che in generale (compreso l'esempio che citi), nno
sia una questione di "singolo genio" ma di "i tempi sono pronti".
Basta vedere quante migliaia di volte la stessa cosa "innovativa" è
stata inventata da due matematici che neanche si conoscevano, ai due
lati del globo, nello stesso istante.
La probabilità che questo succeda, nell'ipotesi "singolo genio" è
praticamente trascurabile, mentre è pensabile che succeda così spesso
nell'ipotesi "i tempi sono pronti".
Teorema di Fermat compreso... se anche Wiles è stato la singola persona
a dimostrare il caso semistabile della congettura di Taniyama-Shimura,
sono certo che entro 30 anni qualche altro appassionato avrebbe fatto lo
stesso... la congettura era lì, "pronta" per essere dimostrata.
- --
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 /
http://www.megatokyo.it
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (Cygwin)
Comment: Using GnuPG with Mozilla - 
http://enigmail.mozdev.org
iEYEARECAAYFAkAzLgYACgkQaJiCLMjyUvvMyQCeLklIMd8k82q3ERMwxMW67KH5
iNMAoPqPnLdfgtxW3Q3QGMm3ym8EKRof
=331F
-----END PGP SIGNATURE-----

 saranno sempre sconfitti.
Linearmente rispetto a cosa? Normalmente si considera che la velocità
raddoppia ogni 24 mesi.
Cristiano

stesso... la congettura era lì, "pronta" per essere dimostrata.
La tua certezza, non e' dimostrabile. E, per l'appunto, stiamo parlando
di Matematica. Il tuo discorso mi sa tanto di quelli che hanno assistito
all'"uovo di colombo"!
Ciao
FIFO

 (altri matematici compresi)...basti pensare ai teoremi di Fermat.
Leggendo i molti documenti (in inglese) inerenti alla crittografia, puoi
renderti conto della discreta percentuale di essi in cui si dice qualcosa
tipo: "Il risultato [di un algoritmo crittografico] è stato dimostrato
*indipendentemente* anche da Pinco Pallino [oltre che da Caio]", "Caio ha
*indipendentemente* dimostrato il teorema così e cosà", cioè lo stesso
teorema "innovativo" viene dimostrato da più matematici che non hanno la più
pallida idea del lavoro degli altri.
Nei secoli scorsi, la matematica era monopolio quasi esclusivo di alcuni
facoltosi che non dovevano arare i campi 14 ore al giorno per cui solo
alcuni avevano il "lampo di genio".
Oggi, la matematica è dominio di chiunque ed è molto probabile che più
persone arrivino agli stessi risultati (prima o poi); se oggi un ricercatore
militare scopre un nuovo algoritmo di fattorizzazione, è molto probabile che
domani un altro matematico arrivi indipendentemente allo stesso risultato.
Cristiano

Solo un paio di considerazioni.
- Quando apparve l'algoritmo RSA, l'NSA dichiarò che lo stesso algoritmo era
già stato scoperto dai suoi studiosi, ma era stato tenuto segreto.
- L'attacco a forza bruta agli algoritmi di crittazione è l'ultima spiaggia:
prima si tentano altri metodi (ad esempio si cerca di "intuire" qualche parte
del file per avere un appiglio tramite cui ottenere la chiave; se si sa
che una persona inizia sempre i suoi file con una forma di benvenuto tipica,
allora questo è un buon punto di partenza).

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
giorgix wrote:
| - Quando apparve l'algoritmo RSA, l'NSA dichiarò che lo stesso
algoritmo era
| già stato scoperto dai suoi studiosi, ma era stato tenuto segreto.
Sì, appunto... ^_^
| - L'attacco a forza bruta agli algoritmi di crittazione è l'ultima
spiaggia:
| prima si tentano altri metodi (ad esempio si cerca di "intuire"
qualche parte
| del file per avere un appiglio tramite cui ottenere la chiave; se si sa
| che una persona inizia sempre i suoi file con una forma di benvenuto
tipica,
| allora questo è un buon punto di partenza).
Un algoritmo crittografico che abbia attacchi "known plaintext" (come
quello che citi) conosciuti e possibili è un algoritmo da considerarsi
"rotto" e "da non usare".
Nessuno degil algoritmi "seri" oggi in uso ha (per ora) problemi del
genere...
- --
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 /
http://www.megatokyo.it
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (Cygwin)
Comment: Using GnuPG with Mozilla - 
http://enigmail.mozdev.org
iEYEARECAAYFAkA1WOYACgkQaJiCLMjyUvtZCgCaA8yPLgKMr72JOahPNufe+k/C
yPQAoOvHWj5OhVoKa+v4jjqcHMw+vuPA
=/Nol
-----END PGP SIGNATURE-----