Bentrovati!

smart-m-lock-slide

Nella scorsa puntata (qui) ci eravamo lasciati sul più bello. Avevamo parlato delle curve ellittiche, del fatto che i punti di esse possono essere sommati e che si possono calcolare i multipli dei punti.

Oggi parleremo invece di come usare queste operazioni per cifrare dei messaggi. Sono dei passaggi complicati quindi quella che propongo qui è una semplificazione che può far comodo a tutti (esperti, studenti e chi-proprio-di-matematica-meno-ne-sa-meglio-sta). Per aiutarvi metterò qui e là del testo all’interno di tag MATH-MODE. Queste porzioni di testo non sono molto influenti ai fini del discorso, così chi desidera può saltarle. Servono giusto per dare delle informazioni in più per chi ne vuole sapere/capire di più.

Il metodo che vi proporrò è quello di El Gamal. Per chi non lo avesse già fatto (molto male… :P), consiglio la lettura dei miei post precedenti sulla crittografia, per avere una infarinatura sull’argomento. Eccoli qui: (1) Introduzione alla crittografia e (2) RSA.

Ci limiteremo a parlare di uno dei possibili ed esistenti algoritmi. A mio parere è veramente affascinante.

Have fun!

crittografia_matrix

Ad un punto del messaggio

Ricordo brevemente l’operazione definita nel precedente post: come in tutte le operazioni binarie a due oggetti ne viene associato un terzo dello stesso tipo. Esempi cardine sono la somma e la motiplicazione tra numeri (da due numeri se ne ottiene un terzo). Quello che facciamo qui è “sommare” due punti su una curva ellittica, ottenendo un terzo punto costruito mediante un procedimento geometrico a partire dai primi due.

Vogliamo quindi usare le curve ellittiche e l’operazione definita sui loro punti per definire questo metodo di crittografia. Scegliamo una curva ellittica E ed un numero primo p.

I passi da seguire sono i seguenti:

  1. trasformare il messaggio in numero e successivamente in un punto della curva E. (Non è magia, vedremo a breve come si fa)
  2. Cifrare il messaggio.
  3. Decifrarlo ed ottenere il messaggio originale.

Esiste un teorema di Weierstrass che garantisce la possibilità, sotto opportune condizioni su p, che i punti di E possano essere identificati come quelle coppie (x,y) soddisfacenti una equazione della forma $$y^2 = x^3 +ax+b$$ dove a,b sono valori tra 0 e p-1. Stiamo scegliendo di ridurci nell’insieme dei valori interi modulo p. Vorrei sottolineare che p è un intero molto grande.

Poiché vogliamo usare l’operazione su E definita nella parte 1 (eccovi il link se volete ripassare), dobbiamo trasformare il messaggio che si desidera inviare in un punto della curva. Sembra che stiamo farneticando ma in realtà dobbiamo solo capire come si fa.

Prima di tutto si esprime il messaggio m come intero tra 0 e $$\frac{p}{100} – 1$$. Questo semplicemente associando ad ogni lettera la sua posizione nell’alfabeto!

Poi si calcolano i valori $$x_i = 100m + i$$ con $$i=0,\dots,99$$. Infine si valuta il valore $$z_i = x_i^3 + ax_i + b$$ al variare di i e ci si ferma al più piccolo valore i per cui $$z_i$$ è un quadrato modulo p.

Questo non è scontato ed esiste un criterio di Eulero che fornisce una condizione sufficiente affinché ciò si verifichi. Vedi (wiki).

Una volta trovata questa i, si calcola il valore $$y_i$$ tale che $$y_i^2 \cong z_i$$ modulo p. Notiamo che il punto $$M=(x_i, y_i)$$ è un punto della curva ed è questo il punto che per noi rappresenta il messaggio iniziale m.

Chiaramente si può tornare indietro eh. Dato il punto $$M=(x_i,y_i)$$, si calcola la parte intera inferiore di $$\frac{x_i}{100}$$ e la si chiama j. Si calcola quindi il valore $$x_i – j$$ e lo divide per 100. Il risultato è proprio il messaggio (numero) originale m.

Non è stato facile ma almeno abbiamo trovato un parallelo, ovvero un ponte che unisce messaggi (intesi come numeri) e punti sulla curva ellittica. Questo procedimento non è infallibile e, per come abbiamo fatto noi, la probabilità che vada male è $$2^{-100}$$. Piccola eh…ma c’è! Per ora andiamo avanti soddisfatti del nostro operato.

Il passo successivo sarà modificare il punto M, ovvero cifrarlo e spedirlo al destinatario in modo che egli sia l’unico a poter ritrovare il valore originale. Ma procediamo per gradi.

Dimmi la tua chiave pubblica e ti dirò chi sei

woody_buzz

Questo metodo che sto per descrivere si basa sul criterio di crittografia a chiave pubblica. Significa che ogni utente che vuole scambiare messaggi definisce una sua chiave pubblica ed una sua chiave privata. Per comunicare con lui, gli altri utenti utilizzano la sua chiave pubblica (che è di conseguenza nota a tutti) per cifrare il messaggio e lui, ovvero il ricevente, decifra tale messaggio con la sua chiave privata (che è ovviamente nota solo a lui).

Quindi, per questo metodo dobbiamo definire la chiave privata e quella pubblica per ogni utente. Ma come si sceglie?

Ricordiamo che avevamo fissato la curva ellittica E e il primo p. Ora fissiamo anche un punto P di ordine n, ovvero un punto di E tale che nP=O, il nostro punto all’infinito. Dobbiamo sceglierlo in modo che n sia un numero primo.

Questa volta immaginiamo che, in una delle loro avventure, Buzz Lightyear debba mandare un messaggio di importanza giocattolare a Woody. Come vedete dalla foto…Woody è molto preoccupato!

Quindi ciò che è noto a tutti, compreso ad un possibile intercettatore, è la quaterna $$(E,p,P,n)$$.

Passiamo alla pratica: scegliamo $$E: y^2 = x^3 + 2x + 4$$, $$p=7$$ e $$P=(0,2)$$. Come vedremo, sapere n non sarà poi così fondamentale per questo esempio.

Buzz e Woody devono quindi definire una chiave privata ed una pubblica. Essi scelgono liberamente un numero $$d$$ compreso tra 1 e n-1 e definiscono questo come loro chiave privata. Poi, calcolando $$Q=dP$$ ottengono la loro chiave pubblica. Supponiamo quindi che la chiave pubblica di Woody sia $$Q=3P=(6,6)$$. [Evito di scrivere tutti i conti per semplicità…le operazioni su una curva ellittica sono sempre molto laboriose!!]

Ora Buzz, il mittente, vuole inviare il messaggio sotto forma di punto $$M=(6,1)$$ della curva E. Sceglie un valore casuale k tra 0 e n-1 e invia quindi a Woody due punti così ottenuti:

1. $$C_1 = k P$$

2. $$C_2 = M + kQ$$

Supponiamo che k=2, perciò, sempre evitando conti, $$C_1=2(0,2)=(2,4)$$ e $$C_2=(6,1)+2(6,6)=(6,6)$$. [Omettiamo sempre i conti! Ricordatevi che quel + è l’operazione sulla curva ellittica!!]

MATH MODE ON
Per Buzz saranno $$(d_B, Q_B)$$ e per Woody $$(d_W, Q_W)$$, dove il valore di Q è ottenuto come spiegato sopra per entrambi.
Buzz vuole inviare il punto M. Sceglie k tra 0 e n-1 e calcola:
1. $$C_1 = k P$$
2. $$C_2 = M + kQ_W$$
Quindi usa la chiave pubblica di Woody per cifrare il messaggio. Con queste due informazioni Woody sarà capace di trovare M.
MATH MODE OFF

Quindi Woody riceve i punti (2,4) e (6,6)…e che ci fa? Usa la sua chiave privata!

Prende la sua chiave privata e la moltiplica per $$C_1$$ ottenendo il valore di $$kQ$$ e poi lo sottrae a $$C_2$$. Ovvero quello che fa è: $$C_2-dC_1 = (6,6)-3(2,4) = (6,1)$$. [Abbiamo sempre omesso i conti…come prima! ‘Ste curve ellittiche so laboriose!!]

Ma guarda un po’, ha ottenuto proprio M!

Quindi usando una chiave che solo lui aveva, Woody ha decifrato correttamente il messaggio originale!!!

MATH MODE ON
Ricevendo $$C_1$$ e $$C_2$$, Woody usa $$d_W$$ e fa $$C_2 – d_W C_1 = M + kQ_W – d_W k P = M + kQ_W – kQ_W =M.$$
Ottiene M!
MATH MODE OFF

Ed ecco qui. Questo si chiama metodo di El Gamal ed è uno dei metodi base di crittografia basata sulle curve ellittiche. Complesso ma molto efficace. Nell’esempio che abbiamo che appena fatto, poiché p è 7, trovare il modo di rompere il codice è facile. Ma immaginate p di una decina di cifre…i tentativi che Mr Potato dovrebbe fare per decifrare il messaggio intercettato sono molti…forse troppi!

Conclusione

Per oggi mi fermo qui! Spero che al di là della difficoltà io sia riuscito a farvi apprezzare un minimo questo stupendo algoritmo!

Per chi ne volesse sapere di più consiglio la lettura di una tesi di laurea che noi di Math is in the Air abbiamo trovato googlando: eccola qui.

Alla prossima, per una interessantissima parte 3!

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