Cultura

La preziosa difficoltà di fattorizzare

Moltiplicare dei fattori (anche tanti) per ottenere un prodotto è un’operazione semplice, ma altrettanto non può dirsi dell’operazione inversa, infatti, partendo da un numero noto non è per niente immediato individuare i fattori primi che lo hanno generato. La complessità, chiaramente, aumenta all’aumentare delle dimensioni del numero da fattorizzare. La difficoltà dell’operazione appena descritta è alla base degli algoritmi di crittografia a chiave pubblica.

Il concetto di fondo è molto intuitivo: due soggetti, mittente e destinatario dei messaggi, per mantenere la riservatezza delle informazioni che devono scambiarsi, sono costretti a ricorrere ad una chiave per cifrare il contenuto.

A fronte della semplice strategia da adottare, emerge un problema di non poco conto. Le parti in gioco, infatti, hanno soltanto due modi per entrare in possesso della chiave segreta, il primo modo è di concordare a priori le chiavi e custodirne gelosamente una copia ciascuno; il secondo modo è di rivelarsi la chiave al momento stesso dello scambio dei messaggi.

E’ evidente che entrambi i modi obbligano i due soggetti ad incontrarsi fisicamente poiché non sarebbe per niente sicuro trasmettere la chiave attraverso mezzi di comunicazione. Si dovrebbero, perciò, incontrare prima dello scambio dei messaggi per anticiparsi reciprocamente la chiave segreta nel caso del primo modo descritto e dovrebbero, invece, incontrarsi contestualmente allo scambio del messaggio nel caso del secondo modo descritto.

Nella realtà, la possibilità di incontrarsi è un’ipotesi da non prendere neanche in considerazione. Senza ricorrere ad esempi riguardanti la sicurezza militare o casi analoghi di urgenza e gravità, basta considerare un aspetto straordinariamente importante della rete internet, cioè le transazioni economiche.

I pagamenti online richiedono la comunicazione cifrata dei dati delle carte di credito e quindi la possibilità di un preliminare incontro tra venditore e acquirente è, nella maggior parte dei casi, fuori discussione; anche nel caso in cui ciò fosse possibile, una tale procedura azzererebbe tutti i vantaggi degli acquisti online.

I limiti emersi in questa breve descrizione del fenomeno, sono stati brillantemente superati grazie al sistema crittografico a chiave pubblica che sfrutta, e porta al limite, la caratteristica di asimmetria tra l’operazione di moltiplicazione e la sua operazione inversa cioè la fattorizzazione. Moltiplicare dei fattori per ottenere un numero con centinaia di cifre è relativamente facile e richiede soltanto un po’ di pazienza, fattorizzare un numero con centinaia di cifre è un’impresa proibitiva. Dietro la crittografia a chiave pubblica c’è esattamente questa operazione.

Un soggetto genera due numeri primi molto grandi che chiamiamo N1 e N2 di cui  mantiene segreta l'identità e che rappresentano la sua chiave privata. Una volta generati se ne calcola il prodotto P = N1 x N2 e si rende pubblico il risultato. Dovendo cifrare un messaggio, si procede dunque a crittografarlo con la chiave pubblica del destinatario che è il solo a poterlo decifrare facendosi riconoscere come l'unico in possesso dei due fattori il cui prodotto ha generato esattamente quel valore.

Il messaggio così cifrato risente perciò di un duplice ancoraggio, uno alla chiave privata e uno alla chiave pubblica. L’accesso ai contenuti è consentito soltanto a chi è in possesso dell’informazione simmetrica che rappresenta il completamento univoco delle operazioni di prodotto e fattorizzazione.

Il sistema RSA, il critto-sistema più diffuso, utilizza chiavi a 1024 bit per applicazioni civili e chiavi a 2048 bit per usi militari, dimensioni che rendono pressoché impossibile la decifrazione da parte di malintenzionati.

Domenico Signorelli

Valutazione attuale:  / 7
ScarsoOttimo 

Commenti   

 
+1 #11 pmchiaro 2014-05-13 16:00
Neanche io ho scritto articoli al riguardo ne tanto meno sono un utilizzatore esperto di RSA. Non essere sempre così acido!

Il tuo esempio non è semplice come promettevi, ma si sa molte tematiche della matematica non possono essere semplificate oltre un certo limite.

Non ho controllato i tuoi numeri anche perché non ho alcuna autorità per bacchettarti.

Ti faccio comunque le mie congratulazioni per il bel'esempio con cui hai dimostrato di volere e sapere dare contributi costruttivi :))

Peccato che l'articolo di Signorelli non sia più in home page e che quindi pochi possano vedere il tuo esempio numerico!
Citazione
 
 
+1 #10 Dario Oliveri 2014-05-12 20:34
"Certo, conoscendo l'algoritmo è facile decrittare al primo colpo"..

Se non si può "diffondere l'algoritmo" perchè sennò è troppo facile da aggirare allora non è un algoritmo sicuro.

L'esempio te lo faccio anche se non credevo di doverlo fare io visto che non ho scritto articoli a riguardo:) e assolutamente non sono un esperto di RSA, sono soltanto un suo utilizzatore :D.

Scelgo 2 numeri primi (li scelgo piccoli così potete verificare i conti con Excell):

A = 307
B = 73

calcolo il prodotto

C = A*B = 73*307 = 11359

calcolo E

E = (A-1)*(B-1) = 306*72 = 22032

scelgo un numero "M" tra 3 ed "E"

M=19

verifico che il Massimo Comun Divisore tra M e C sia 1

MCD(19,11359) = 1

bene siamo stati fortunati, in caso contrario scegliamo un altro numero

A questo punto abbiamo la chiave pubblica che è formata dai due numeri

(11359,19)

Chiunque può usare la nostra chiave pubblica per cifrare un messaggio, se ad esempio Pippo vuole mandarci il messaggio "3", Pippo deve calcolare:

3^19= 1162261467

Poi Pippo prende il resto della divisione per l'altro pezzo della chiave pubblica

1162261467 mod 11359 = 8587



---IL MESSAGGIO CIFRATO e' 8587



Prendiamo un numero D tale che

D*M mod E = 1

ad esempio prendiamo D = 26

Per decifrare il messaggio devo fare

8587^26 mod 11359 = 3, ho riottenuto il messaggio originale;)

-- L'osservatore occasionale vede transitare nella rete solo i seguenti numeri
(11359,19,8587)


Anche conoscendo l'algoritmo (RSA di pubblico dominio), non riesci a trovare li messaggio 3 a meno di non procedere per tentativi (in tal caso ti basterebbe fattorizzare 11359, che siccome è un numero piccolo è abbastanza semplice, ma richiede comunque un po di tentativi)

Spero di non aver sbagliato i conti altrimenti mi bacchetti ;) correrò il rischio.
Citazione
 
 
0 #9 pmchiaro 2014-05-09 15:28
Certo, conoscendo l'algoritmo e facile decrittare al primo colpo.

Ma tu, che sicuramente sei più esperto di me in RSA, perché non ci fai l'esempio semplice con numeri primi piccoli?
Sarebbe veramente costruttivo :))
Citazione
 
 
0 #8 Dario Oliveri 2014-05-07 19:44
Certo, volevi tenere le cose semplici, e io ti ho soltanto mostrato che il tuo algoritmo era così semplice che si poteva risalire al messaggio senza neanche fare "tentativi" ma direttamente "al primo colpo".

RSA è semplicissimo da usare (per numeri piccoli). Potevi fare un esempio di quello invece. Era solo una critica costruttiva;)
Citazione
 
 
+3 #7 pmchiaro 2014-04-29 09:23
Dario, nella realtà nessuno si sognerebbe di usare un algoritmo così semplice, e numeri primi così piccoli. Inoltre nello esempio si usano due chiavi private, mentre nella realtà (RSA) una è pubblica e l’altra privata. L’esempio serve a far capire / ricordare che:

1)Oggi si usano due Chiavi.
2)Gli algoritmi sono basati sullo uso dei numeri primi.
3)Moltiplicare due numeri primi anche grandissimi è semplice.
4)Scomporre numeri molto grandi nei primi è complesso.

Un altro esempio elementare (facilmente rintracciabile su Internet):

1)A mette il messaggio in una cassaforte sicura la chiude con un lucchetto di cui solo lui ha la chiave ed invia la cassaforte a B.
2)B aggiunge alla cassaforte un suo lucchetto (di cui solo lui ha la chiave) e rispedisce la cassaforte ad A con i due lucchetti chiusi.
3)A apre il suo lucchetto, lo toglie e rispedisce la cassaforte a B con il lucchetto di B sempre chiuso.
4)B apre il suo lucchetto e legge il messaggio.

Inutile dire, se non per qualcuno, che nella realtà non si usano né casseforti né lucchetti.
Citazione
 
 
-4 #6 Dario Oliveri 2014-04-23 11:43
pmchiaro, il tuo metodo non funziona.
chiunque sia in ascolto sulla connessione vede i numeri
2574 e 18018 e 1638

18018/2574 = 7

A questo punto può risalire a 234

1638/7 = 234.

Riguardo all'articolo, su un sito come matematicamente mi sarei aspettato di vedere un esempio di RSA e almeno degli accenni su come fare a generare numeri primi molto grandi.
Citazione
 
 
0 #5 esercizi estenuanti 2014-04-17 05:18
ancora si insiste nella scuola media in esercizi estenuanti di scomposizione in fattori.Va bene per alcuni casi semplici o con regole che agevolano.Però solo acuni testi forniscono la fattorizzazione di serie di numeri..che essendo unica, una volta fatta ..basta..Dino Buzzati scrisse un raccontino a proposito di un "affascinante enigma matematico"stra namente poco usato nei testi scolastici.In pratica narra la vicenda di un Ragioniere che si astrae da tutto ed invecchia compilando una tabella aggiornatadi numeri primi minori di diecimilioni.In tanto passano 1 guerra mondiale, fascismo, nazismo, seconda guerra mondiale...ma non se ne accorge .
Citazione
 
 
+1 #4 Roberto1234 2014-04-14 15:35
Grazie, ora è chiaro il meccanismo.
Citazione
 
 
0 #3 Ricky101 2014-04-11 13:33
Io ho capito qualcosa di più nell'articolo "Dai Numeri Primi alla Crittografia" pubblicato nel numero 15 di Matematicamente Magazine.
Citazione
 
 
+2 #2 pmchiaro 2014-04-09 17:12
Qualunque messaggio può essere tradotto in una stringa più o meno lunga di numeri. Come crittare questa stringa? Supponiamo, per semplicità, che il messaggio sia “234”. Ecco come crittarlo con due invii e due numeri primi a caso scelti dal mittente e dal ricevente (senza che neanche loro ne siano reciprocamente a conoscenza).

Mittente: sceglie il numero primo 7. Calcola 7*234 = 1.638. Invia il numero.
Ricevente: sceglie il primo 11. Calcola 11*1.638 = 18.018. Restituisce il numero.
Mittente: riceve 18.018 e calcola 18.018/7 = 2.574. Invia il risultato al ricevente.
Ricevente: Calcola 2.574/11 = 234; che era il messaggio, decrittato, del mittente!
Citazione
 
 
-1 #1 Roberto1234 2014-04-06 11:29
Non è per nulla chiaro. Forse con un semplice esempio si potrebbe rendere più comprensibile l'articolo.
Grazie
Citazione
 

Aggiungi commento

I commenti devono essere approvati dall'amministratore

Codice di sicurezza
Aggiorna