Salve a tutti di nuovo! Benvenuti a questa parte 3 della serie sulle curve ellittiche e sulla crittografia basata su di esse.

Nella parte 1 avevamo introdotto le curve ellittiche (link) e nella parte 2 avevamo spiegato il metodo di El Gamal (link). In questa parte inizieremo spiegando un metodo chiamato double-lock e poi andremo ad indagare la vulnerabilità di questo tipo di crittografia. Buona lettura!

Il doppio lucchetto

images

Esistono metodi alternativi al metodo di El Gamal. Uno di questi è il metodo del doppio lucchetto. Prendiamo sempre Buzz e Woody e sia sempre M il punto da cifrare, come nello scorso post. Se non ti ricordi la notazione, vallo a rileggere!!!

L’idea è questa: A manda una scatola a B e ci appone un lucchetto, la manda a B ed anch’esso vi appone un lucchetto. Poi la scatola con 2 lucchetti torna ad A che rimuove il suo e lo rimanda a B. A quel punto vi è un solo lucchetto che B aveva apposto. Quindi B lo apre e riceve il contenuto.

Nel nostro caso, prima di tutto Buzz e Woody sceglieranno una curva ellittica nel campo dei numeri modulo p.

Poi, Buzz moltiplicherà M per la sua chiave privata $$d_B$$ e lo manderà a Woody. Woody la moltiplicherà per la sua chiave privata $$d_W$$ e lo rimanderà a Buzz. Tale messaggio double-locked lo chiameremo $$X=d_W d_B P$$.

Esso è in grado di rimuovere la sua chiave privata moltiplicando per l’inverso moltiplicativo modulo p della sua chiave. Così come succedeva per l’RSA, vedi il post link.

Quindi moltiplicando per l’inverso moltiplicativo di $$d_B$$, il punto risultante sarà $$d_W M$$. Ricevendolo, Woody lo moltiplicherà per l’inverso moltiplicativo della sua chiave ottenendo il messaggio in chiaro.

Ma un passo per volta: prima di tutto $$d_B$$ e $$d_W$$ devono essere coprimi con p, altrimenti niente inversi moltiplicativi. Essi sono definiti come quei valori $$e_B$$ e $$e_W$$ tali che $$e_B d_B \cong 1$$ e $$e_W d_W \cong 1$$ modulo p.

Dal teorema di Eulero, essi esistono se e solo se $$d_B$$ e $$d_W$$ sono coprimi con p.

Ricapitoliamo con qualche formula in più:

1) Buzz cifra M in $$Z = d_B M$$ e lo manda a Woody.

2) Woody moltiplica per $$d_W$$, ottiene $$X = d_W X = d_W d_B M$$ e lo rimanda a Buzz.

3) Buzz riceve X e lo moltiplica per $$e_B$$ ottenendo $$Y = d_W e_B d_B M = d_W M$$. Lo rimanda così a Woody.

4) Woody lo moltiplica per $$e_W$$ ottenendo $$e_W Y = e_W d_W M = M$$ ovvero il messaggio originale.

Quindi dopo 4 passaggi finalmente Buzz ha inviato il messaggio a Woody.

Vorrei sottolineare che tutte le operazioni vanno fatte modulo p. Inoltre i valori $$e_W$$ e $$e_B$$ sono privati tanto quanto $$d_W$$ e $$d_B$$.

Questo metodo, detto double-lock, è usato soprattutto per i protocolli che prevedono una firma digitale. In questo modo si verifica anche la genuinità del mittente.

Sicurezza è la parola d’ordine

Web-security-stock

Sia nel post precedente (parte 2) che nel primo paragrafo, non abbiamo mai parlato di sicurezza. Nell’introduzione della prima parte avevo accennato al fatto che il governo americano usa questo tipo di crittografia per cifrare i suoi segreti, quindi una idea di quanto inaccessibile sia la abbiamo. Ma vediamo qualcosa nel dettaglio e concentriamoci sulla cifratura Double Lock. Supponiamo che Mr. Potato intercetti le comunicazioni tra Woody e Buzz e che voglia decifrare il messaggio.

Quindi nelle sue mani (diciamo mani) ottiene i valori $$Z=d_B M$$, $$X=d_W Z =d_W d_B M$$ e $$Y=e_B Z = e_B d_W d_B M = d_W M$$. Il suo scopo è quello di ottenere M, quindi vorrebbe risalire ad M da Z, X e Y. Innanzi tutto potrebbe sfruttare la conoscenza di $$d_W d_B M$$ e di $$d_B M$$ per ricavarsi $$d_W$$. Trovata $$d_W$$ potrebbe andare alla ricerca di $$e_W$$ e finalmente calcolare $$e_W d_W M$$ che è M!!

Perciò i problemi sono due e sono riassumibili in questo modo:

1) Dato il punto Q=nP, noto solo P, trovare n.

2) Dato d, numero modulo p, trovare il suo inverso moltiplicativo.

Parliamo prima del secondo problema. Ne avevamo già accennato qualcosa negli altri post sulla crittografia. Se p è molto molto grande, è complicato calcolare l’inverso moltiplicativo, ma un computer (anche uno smartphone) è in grado di ottenerlo in un tempo ragionevole.

Il vero problema in questo caso è il primo. E’ noto come problema del logaritmo discreto. Svisceriamolo!

Logarithm is back!

Logarithm_keys

Quindi il problema è il seguente: dato P e dato Q multiplo di P, trovare n tale che Q=nP. Come si fa?

Scrivere esplicitamente le formule per nP è molto complesso, quindi ci limiteremo a fare un discorso qualitativo. Fare nP significa sommare P con se stesso n volte. La somma di due punti di una curva ellittica prevede il calcolo delle coordinate (ascissa e ordinata) del punto somma, utilizzando il metodo spiegato nella prima parte (link). Bisogna fare dei quadrati e risolvere un sistema non lineare. Per di più non si lavora nei numeri reali, ma sempre con numeri interi e ristretti modulo il primo p.

Grazie a risultati dovuti ad un grande matematico di nome Weil, possiamo trasferire questo problema ad un problema numerico ma comunque complicato. In definitiva, dobbiamo essere in grado di risolvere un problema del tipo: presi a e b interi coprimi con p, trovare, se esiste, il valore x per cui $$a^x \cong b$$ modulo p.

Questo problema del logaritmo discreto è molto molto molto difficile da risolvere. Se p fosse un numero piccolo, allora si potrebbe fare addirittura a mano…ma in generale p è immensamente grande! La difficoltà di risolvere questo rende la cifratura ellittica una delle più sicure esistenti.

Certamente esistono degli algoritmi in grado di attaccare il problema e in alcuni casi risolverlo. Per evitare di incorrere in simili casi, la soluzione è quella di aggiornare frequentemente sia la curva di cifratura che l’intero p. Questo sicuramente può essere di grande aiuto per non far capire al Mr. Potato della situazione i vostri messaggi segreti.

Conclusione

Vi ho dato in questo ultimo post sulla crittografia ellittica una visione delle cose veloce e completamente incompleta. Ci sarebbero un mondo di cose cui dedicarsi e non basterebbero 100 post! Quindi per ora vi saluto, magari ritornerò a parlare dell’argomento in futuro…chi lo sa!

By the way, vi è piaciuto? Spero di sì.

Alla prossima belli!!!!

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.