Algoritmi per la crittografia - panoramica elementare

In rete: www.elegio.it/doc/tn/algoritmi_crittografia.html

Crittografia: metodi base e considerazioni varie

Raccolgo qui la spiegazione di alcuni notissimi algoritmi per la crittografia cercando di esporli in un modo elementarissimo per non addetti ai lavori.
La mia opinione è che, nell'epoca digitale di internet, per mille ragioni è opportuno almeno conoscere i metodi per proteggersi da chiunque voglia violare il nostro diritto ad avere un nostro mondo personale e riservato.
Suggerisco vivamente a tutti di non fidarsi della propria capacità di escogitare accorgimenti che il più delle volte sono tipiche scoperte dell'acqua calda.
E' però certo che anche le cassaforti casalinghe possono rivelarsi utili per difenderci da ladri principianti ed occasionali e viceversa, il miglior sistema di cifratura può essere messo in crisi dalla donna delle pulizie che riordina la nostra scrivania o dal segretario o dal brigadiere incaricato di criptare il documento che gli consegnamo: sarebbe l'equivalente del venir rapinati mentre andiamo a depositare i gioielli di famiglia nella cassetta di sicurezza della banca.
Dunque una prudente tendenza al "far da sè" non dovrebbe essere nociva e quindi questi appunti potrebbero essere utili per capire il problema, poi progettare ed infine attuare il proprio cautelativo sistema di criptatura preliminare, l'estrema difesa sul Piave.

Elevamento a potenza

Il metodo si basa sul fatto che il calcolo dell'inverso moltiplicativo di un esponente è molto difficile e solo fattibile, se gli interi non sono molto grandi, con calcolatori comunque molto potenti.
Dato una coppia di interi c e d tali due numeri sono inversi moltiplicativi se risulta:
(a^c ) ^d ≡ (a^d ) ^c ≡ a^{c · d} ≡ a^{d · c} ≡ a mod N
(Il simbolo ≡ si legge "congruo a" e significa che sono uguali i resti della divisione del primo e del secondo membro se il divisore è l'intero specificato come modulo).
Se per esempio consideriamo come modulo il numero 77, evidentemente non primo ma fattorizzabile in 7·11, si può vedere che l'inverso moltiplicativo di 53 è 17 e viceversa. In altre parole elevando un qualsiasi intero positivo, minore di 77 a 53 modulo 77 e poi il risultato alla potenza 17-esima, operando sempre modulo 77, si riottiene l'intero di partenza. In particolare, provando con 5 si trova che 5⁵³ ≡ 59 mentre 59¹⁷ ≡ 5 e similmente provando con 6 si vede che 6⁵³ ≡ 62 mentre 62¹⁷ ≡ 6 etc.
L'esponente c è l'esponente di cifratura mentre l'esponente d è l'esponente di decifrazione. Ovviamente i due esponenti possono essere scambiati di ruolo e quindi d può essere usato come esponente di cifratura e c come esponente di decifrazione.
Il valore del modulo N e l'esponente di cifratura devono essere resi pubblici ossia devono essere fatti conoscere a chiunque mi vuol mandare un messaggio mentre devo tenere segretissimo l'esponente d di decifrazione poichè il calcolo di d, anche se sono noti c ed N è enormemente difficile da fare da parte di chiunque, amico o nemico che volesse scoprirlo.
Naturalmente, per aumentare la sicurezza, cercherò di far conoscere solo agli amici i valori di N e soprattutto di c ma se, per disgrazia, questi due numeri cadessero in mano al nemico che, ad esempio, li estorce con la tortura ad uno dei miei amici, o se uno degli amici fosse un giuda, questo non consentirebbe comunque al nemico di decrittare i messaggi che gli altri amici mi mandano o mi hanno precedentemente mandato o che mi continueranno a mandare ignorando che il nemico è riuscito a scoprire N e c.
Un amico che mi vuole mandare il messaggio b impedendo al nemico di capirlo mi spedisce:
t ≡ b^c mod N
Ed io, quando ricevo il messaggio t uso il mio esponente segreto d, che solo io ho potuto calcolare, e calcolo:
b ≡ t^d mod N
Dunque chiunque conosca c ed N può spedire un messaggio che io riesco a decifrare ma io non ho la certezza che il messaggio che ricevo mi provenga da un amico e non da un nemico che si è impossessato di c e di N e che, dunque, può fingere di essere mio amico. Questo implica che i messaggi che ricevo, per essere credibili ossia darmi la certezza che mi arrivano da un amico, debbono essere autenticati con un qualche sistema che per ora tralasciamo di spiegare.
Per potere applicare questo metodo bisogna capire come scegliere in parte a caso, in parte tramite calcoli, i numeri fondamentali del metodo ossia c, d ed N.
La scelta va fatta in modo che un nemico che conosca c ed N non riesca a scoprire d se non con una enorme fortuna, andando per tentativi, o tramite supercalcolatori di enorme potenza.

Scegliere due numeri primi sufficientemente grandi. Più grandi sono più il metodo diventa resistente all'attacco nemico. I due numeri primi siano p e q.

Si scelga un numero che sia coprimo sia di p − 1 che di q − 1 che sarà l'esponente di criptatura c. Due numeri sono detti coprimi se non esiste nessun numero superiore ad uno che divida esattamente entrambi. Un semplice controllo è che c non divida esattamente nè p−1 nè q−1. Se poi questa condizione necessaria si rivelasse non sufficiente basterebbe tentare con un altro valore di c.
Un metodo sicuro ma che limita un pò la scelta di c, benché in modo non grave, è quello di scegliere c in modo che sia primo e maggiore sia di p che di q ma ovviamente sia minore di (p − 1)·(q − 1).

Si calcoli, con apposito algoritmo il numero :
d ≡ c⁻¹ mod (p − 1)·(q − 1)
questo implica che bisogna applicare l'algoritmo per l'inverso di un intero modulo un altro intero. Questo tipo di algoritmo è molto noto, facile da programmare e notevolmente veloce. L' inverso potrebbe non esistere ma essendo la scelta di c arbitraria, si potrà cambiarla e ritentare fino a quando l'algoritmo non riesce ad arrivare al risultato cercato ossia d. Il numero d ottenuto in questo modo, va tenuto segreto ossia non comunicato neppure al migliore degli amici.

Si ottiene N come prodotto p·q e si comunica agli amici c ed N.

La robustezza dipende dal fatto che per fare l'inverso di c modulo (p − 1)·(q − 1) bisogna conoscere o p o q scoprendo cioè quali sono i due fattori di N. Ma la fattorizzazione è una operazione di elevatissimo costo computazionale che cresce rapidissimamente al crescere dei due fattori. Dunque solo il nemico capace di fattorizzare N saprebbe calcolare d e decrittare i messaggi che gli amici mi mandano.
Ecco un esempio pratico con numeri un po' grossi ma ancora ragionevoli per calcoli con la calcolatrice tascabile. Decido di comunicare agli amici che userò 10001 e che l'esponente di crittatura è 257. Naturalmente non dico a nessuno che l'esponente di decrittazione è 6401 e nessuno è capace di calcolarlo perchè il calcolo sarebbe troppo difficile (se 10001 non fosse un numero iperpiccolo per questi scopi).
Un amico vuole mandarmi, in segreto, la data della fine del mondo decisa da Osama Bin Laden ossia il 2005. Allora usa il mio esponente e calcola 2005²⁵⁷ ≡ 1747 mod 10001. Io allora uso il mio inverso moltiplicativo segreto e calcolo 1747⁶⁴⁰¹ ≡ 2005 mod 10001 ossia riottengo il messaggio segreto, l'anno della fine del mondo. Il segreto è protetto dal fatto che nessuno sa scoprire che 10001 = 73·137 e pertanto (73−1)·(137−1) = 9792; dunque nessuno sa calcolare 257⁻¹ mod 9792 ovvero 257⁹⁷⁹⁰ mod 9792 sfruttando il fatto che in algebra modulare modulo N, l'inverso, ossia la potenza −1, corrisponde alla potenza N−2.

Metodo del doppio scambio (ovvero di Massey-Omura)

Sia io che i miei amici (ed eventualmente i nostri nemici) sanno che verrà utilizzato il primo P.
Se un amico vuole spedirmi il messaggio b mod P mi manda il messaggio elevato ad un disturbo c scelto da lui a piacere e tenuto segretissimo.
Dunque al primo passo io ricevo b^c mod P ed a mia volta rispondo scegliendo un mio disturbo d e mandandogli come risposta il messaggio (b^c )^d mod P ossia il numero che ho ricevuto elevato al disturbo che io ho scelto ossia d.
A questo punto l'amico sa che se toglie il suo disturbo il messaggio resterà comunque illeggibile perchè resterà comunque disturbato dal mio disturbo. Pertanto calcola l'inverso di c ossia trova γ = c⁻¹ mod P ed eleva la mia risposta a γ e dunque mi rispedisce b^d mod P.
Ma io conosco il valore di d e quindi posso facilmente calcolarmi l'inverso ossia δ = d⁻¹ mod P ed elevando la risposta alla mia risposta alla potenza δ ottengo finalmente il messaggio originario ossia b.
Il vantaggio di questo metodo è il fatto che basta solo conoscere un numero primo P grande a sufficienza e disporre dell'algoritmo di calcolo dell'inverso modulo P. In letteratura sono stati pubblicati moltissimi numeri primi giganteschi ma facilmente memorizzabili. I più grandi sono i primi di Mersenne che hanno la forma 2^q−1 con q a sua volta primo. I numeri di Mersenne fino ad ora scoperti (2005) sono oltre 40 e alcuni di essi hanno oltre 8 milioni di cifre binarie (ad esempio quello con q=13466917 o quello con q=20996011) ossia sono più grandi di un Mbyte. Dunque questo metodo consente criptature di difficoltà veramente mostruosa.
L'ovvio difetto di questo metodo è il fatto di richiedere lo scambio di tre messaggi in luogo di uno solo. Resta comunque il fatto della estrema mutabilità delle procedure dato che i valori dei disturbi c e d possono essere sempre cambiati senza preavviso.

Metodo del generatore in versione additiva

Un generatore g, altrimenti detto radice primitiva rispetto ad un primo P, è un intero tale per cui:
g^b ≡ g mod P solo se b = P.
Dimostrare che g è un generatore di P è un calcolo non difficile se è nota la fattorizzazione di P−1 ma per il momento si immagini di non dover fare questo calcolo ossia di essere capaci di calcolare un g qualsiasi rispetto a P. Al limite si supponga che qualcuno abbia calcolato per noi quale è un g che sia una radice primitiva del primo P.
La scelta del numero g e del primo P può essere pubblica e dunque non è nocivo il fatto che la conosca anche un nostro nemico.
Supponiamo ora che io voglia usare il semplice metodo dell'addizione di una perturbazione modulare ai messaggio. Supponiamo dunque che io mi accordi con tutti i miei amici su quale perturbazione va tolta da me e aggiunta da loro ai messaggi che devo ricevere. Sia d il numero che costituisce il disturbo ovvero la perturbazione con cui mascherare il testo b del messaggio.
Se dunque un amico mi vuol spedire il messaggio b calcola:
t ≡ b + d mod P
Il nemico, anche se intercetta il testo t non capisce il messaggio perchè ignora il valore di d ma io e i miei amici conosciamo il valore di d per cui, appena ricevo il messaggio io calcolo:
b ≡ t − d mod P
e riottengo il messaggio b. Ovviamente se il nemico cattura e tortura uno dei miei amici o se uno degli amici mi tradisce il nemico diventa capace di decrittare tutti i messaggi che ho ricevuto e riceverò dai miei amici ignari. Un disastro!
Per evitare che questo succeda occorre che io e i miei amici usiamo ciascuno un disturbo d diverso almeno da amico ad amico. Per far questo io comunico a tutti i miei amici la mia chiave che è g^a e tengo per me, segretissimo, il numero a. Quando un amico mi vuol mandare un messaggio mi manda due numeri ossia:
[ g^k mod P, t ≡ b + (g^a )^k mod P ]
ossia eleva ad un k arbitrario il generatore, fa lo stesso col mio numero pubblico g^a mod P ed usa come disturbo d questo valore calcolato.
Io che conosco il valore di a posso a mia volta scoprire che disturbo è stato usato calcolando d = (g^k )^a mod P e posso dunque sottrarre il disturbo al messaggio disturbato per ottenere quello originario.

Metodo del generatore in versione moltiplicativa

La versione moltiplicativa differisce dalla versione additiva per come il disturbo viene combinato col messaggio. Nella versione additiva il disturbo b viene addizionato mentre nella versione moltiplicativa il disturbo viene moltiplicato per il messaggio.
Anche nella versione moltiplicativa si fa in modo che il disturbo non debba essere comunicato esplicitamente dal mittente al ricevente ma il ricevente comunica pubblicamente la base da usare per generare il disturbo mentre il mittente informa il ricevente del valore del disturbo se la base indicata dal ricevente fosse stata l'unità. Dunque il mittente invia la seguente coppia di valori:
[ g^k mod P, t ≡ b · (g^a )^k mod P ]
Dunque il ricevente, conoscendo l'esponente con cui ha elevato il generatore eleva il disturbo unitario alla potenza di quell'esponente ed ottiene il disturbo che il mittente a usato per moltiplicare il messaggio.
Per riottenere il messaggio originario il ricevente divide il messaggio disturbato per il valore del disturbo.
La versione moltiplicativa del metodi di elevamento a potenza è nota come criptosistema di ElGamal e sembra essere più complicata e dunque più resistente di quella additiva visto che richiede l'esecuzione di un prodotto e il calcolo del disturbo inverso ovvero d⁻¹.

Metodi composti

I metodi precedentemente illustrati sono metodi che "sfidano il nemico" provocandolo ad attaccare i messaggi che io ed i miei amici ci scambiamo spudoratamente alla luce del sole senza timore di informarlo che abbiamo qualcosa da dirci che non vogliamo che lui capisca. Ovviamente il nemico sarà tentato di risolvere gli enigmi col metodo usato da Alessandro Magno per sciogliere il nodo di Gordio che, sciolto, dava il diritto fatale di dominare la Persia. Alessandro usò un colpo di spada e i miei nemici potrebbero tentare di indurmi a confessare i miei segreti con metodi poco teneri.
Il settore della crittografia che punta a non allarmare il nemico nascondendogli il fatto che io sto colloquiando con i miei amici si chiama steganografia ( in inglese steganography ) ossia scrittura mascherata e questi metodi diventano sempre più applicabili quanto più cresce la massa di dati normalmente scambiati nel mondo tra qualsiasi coppia di individui.
Esistono in rete molti programmi che aiutano a realizzare immagini che nascondono messaggi. Un qualsiasi giornale in rete pubblica un notevole numero di immagini e se tali immagini sono originali ossia mai pubblicate da altre fonti sarà possibile nascondere in esse qualsiasi messaggio che richieda una piccola quantità di dati rispetto alla mole dei dati costituenti il messaggio innocente.
La situazione è ancora migliore se si considera la sempre maggior diffusione di filmati che richiedono una mole di dati enormemente superiore ai dati richiesti da una singola fotografia. I singoli fotogrammi ripresi da una qualsiasi telecamera sono affetti da molti disturbi casuali che possono essere mescolati a messaggi che già di per sè simulano disturbi casuali. In questo caso la tecnica di confrontare fotografie provenienti da varie fonti per scoprire se in qualcuna ci sono leggere modifiche rappresentate da un messaggio mascherato viene messa in difficoltà: è logico che qualcuno voglia rielaborare un filmato già diffuso da altri per renderlo meglio fruibile in rete e dunque è credibile il fatto che qualcuno possa desiderare di realizzare una versione propria ( più piccola ) di un file già disponibile da altre fonti. Trattandosi di una variante giustificabile e non confrontabile con nessun'altra, sarà molto difficile appurare se i disturbi di tale variante sono dovuti a cause accidentali o se nascondono un messaggio.
La modifica di fotografie, file audio o filmati è comunque un metodo macchinoso che richiede, oltre tutto, la complicità di qualcuno autorizzato a pubblicare i file in rete.
Personalmente, pur associato alla steganografia ma non necessariamente, preferirei il sistema di sfruttare le immagini e altri grossi file presenti nelle pagine web ma all'insaputa dei gestori dei siti dove sono pubblicate. Per far questo basterebbe realizzare messaggi che non contengano caratteri ma indirizzi a dove trovare il carattere effettivo. Un qualsiasi file (mettiamo l'immagine del Papa benedicente pubblicata sul sito ufficiale del Vaticano ) è facilmente scaricabile e leggibile come una sequenza di byte (un byte è un gruppo di otto bit e rappresenta un intero tra 0 e 255 ed inoltre esiste una convenzione universale UNICODE che fa corrispondere ogni byte ad un simbolo o lettera dell'alfabeto per cui, ad esempio, il byte che indica il numero 65 indica anche la A maiuscola e quello che indica il numero 97 indica anche la a minuscola).
Un file gigantesco, usato magari per memorizzare un intero filmato, è difficilmente maggiore di un miliardo di byte e siccome mi occorrono quattro byte per rappresentare un intero inferiore a 2 miliardi ne deriva che invece di scrivere in un solo byte il numero 65 ossia la lettera A, posso usarne quattro per scrivere 2378132 ossia il numero d'ordine del byte nel file immagine del Papa che contiene il byte che vale 65. Ovviamente, nell'immagine papale esisteranno decine di migliaia di byte che valgono 65 e dunque io ho una enorme libertà di indicare, in modo del tutto equivalente, la lettera "A" e nessuno potrà mai sapere che 2378132 indica la lettera "A" se non sa che sto usando l'immagine del Papa innocentemente pubblicata dal Vaticano.
Usando un file in cui faccio uso di indirizzi a byte di file pubblicati su internet posso rendere leggibile il messaggio solo per brevi periodi di tempo contando sul fatto che l'immagine venga mantenuta sul sito solo per un breve intervallo di tempo. E' ovvio che le immagini della terra, prese da satelliti vari, vengono frequentemente aggiornate e così pure i file con le quotazioni in borsa etc... e pertanto non ci sarà bisogno di "bruciare" il messaggio cartaceo o di chiedere la complicità di un qualsiasi gestore di siti solo per rendere illeggibili i messaggi salvo che per una breve finestra temporale....
Semplice e difficilmente rivelabile o rintracciabile fuori tempo utile!
Ovviamente l'uso di indici in luogo dell'uso diretto dei dati implica messaggi nettamente più grossi ma non è detto che a volte non convenga essere prolissi.

La combinazione dei metodi potrebbe puntare a distruggere la pubblicità della chiave pubblica.
In particolare gli ultimi due metodi basati sull'uso di un generatore pubblico g, comportano la trasmissione sprotetta di g^k ossia del disturbo che il mittente avrebbe usato se il ricevente avesse optato ( opzione suicida da non fare mai ) per un proprio disturbo unitario ossia... inesistente.
Ma questo vuol dire che il nemico ha accesso libero almeno ad una parte del segreto e dunque ha un punto di partenza gratuito per iniziare a decrittare il messaggio.
Se il ricevente ha però pubblicato anche un altro metodo di chiave pubblica ossia quello dell'elevamento a potenza è possibile non fare inutili regali e dunque criptare g^k elevandolo all'esponente c ed operando modulo N, purché N sia maggiore del primo P in modo da non rischiare di tagliare cifre significative in g^k. Il mittente spedirà dunque (g^k mod P)^c mod N oltre che, ovviamente, la parte contenente il vero messaggio ossia b · (g^a )^k mod P mentre il ricevente dovrà innanzi tutto sproteggere la chiave pubblica elevandola all'esponente d da lui solo conosciuto.
Si useranno dunque non una ma due barriere difensive perchè se dovesse cedere la prima, il nemico non riuscirebbe ad altro che a scoprire la chiave pubblica da utilizzarsi nel metodo di ElGamal.
Per finire non sarà male inquinare qualunque messaggio pubblico con un rumore concordato preventivamente tra tutti gli amici. Ovviamente questa sarà la più debole delle protezioni ma comunque servirà ad intralciare, tanto o poco, l'azione del nemico.

Appendice: come calcolare un generatore

Un generatore ovvero radice primitiva di P è una base che richiede il più alto esponente possibile perché il risultato sia congruo a 1 modulo P. Per un importantissimo teorema, il teorema di Fermat, se P è primo allora qualunque sia la base a, si trova che a^P−1 DEVE essere congruo ad 1 modulo P. Ma se a non è una radice primitiva esistono molti esponenti più piccoli di P−1 che permettono di ottenere la congruenza con l'unità, ciascuno applicato ad una appropriata base. Data dunque una base qualsiasi si dice ordine di quella base il più piccolo esponente per cui la base elevata a quell'esponente è congrua ad 1.
E' possibile dimostrare che l'ordine deve essere, inderogabilmente, un divisore esatto di P−1 e dunque per accertarsi che g sia veramente una radice primitiva basterebbe controllare che non sia possibile ottenere l'unità elevando g a tutti i possibili ordini inferiori che teoricamente potrebbe avere.
Se però è nota la fattorizzazione di P−1 ossia:
P − 1 = 2^k₀· (p₁)^k₁· (p₂)^k₂· · · (p_n)^k_n·
dove i vari p_k sono primi tra loro diversi, allora si dimostra che è sufficiente verificare che l'ordine non è uguale a (P−1)/2 nè a (P−1)/p_k per k = 1, 2,.... n.
Se infatti, in corrispondenza di tali esponenti si ottenesse l'unità potrebbe darsi che l'ordine sia ancora più piccolo ma dunque sicuramente inferiore a P−1 che è l'ordine che deve avere un generatore ovvero radice primitiva per poter dirsi tale.
Notare che il fatto che esista un g che soddisfi le suddette condizioni rappresenta una dimostazione che P è primo in base al teorema di Kraitchik e Lehmer derivato da un analogo di Lucas nel 1891.
Dato che il logaritmo è facilmente calcolabile se i fattori di P−1 sono primi piccoli, per trovare un g adeguato si cercheranno numeri primi costruiti, a priori, come fattori di un prodotto di pochi e grossi numeri primi incrementato di una unità e il fatto che si riesca a trovare un g che soddisfa le condizioni poste sarà automaticamente una dimostrazione che il numero così costruito è necessariamente primo. Se si cercasse un P−1 con due soli fattori e precisamente 2 e p₁ entrambi elevati ad 1, in caso di successo del test si scoprirebbe un così detto primo di Sophie Germain.

Vedere anche:

Piccola libreria per calcoli in algebra modulare

Il bugiardo si fingeva primo!

Versione del 29 agosto 2005 aggiornata ad aprile 2009