Blog divulgativo sulla matematica applicata

Crittografia Ellittica [parte 2]: Buzz e Woody, messaggi puntuali, El Gamal

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.

Similar posts

6 commenti

  1. Francesco's Gravatar Francesco
    marzo 1, 2016    

    Si che è interessante, ma piuttosto complicato..Mi piacerebbe che introducessi/spiegassi come funzionano le "Criptomonete" come BitCoin... Ciao

    • Francesco Bonesi's Gravatar Francesco Bonesi
      marzo 1, 2016    

      Ciao Francesco,
      in realtà non conosco bene il funzionamento di BitCoin ma, chissà, magari in futuro faremo anche articoli su di queste cose!
      Grazie del commento! Ciao

  2. Francesco's Gravatar Francesco
    marzo 4, 2016    

    Ah, capisco , per quanto riguarda la "Crittografia Ellittica" sai chi la sta usando e per cosa perchè vorrei capire di più sull'utilizzo Graze Ciao

  3. rosario portoghese's Gravatar rosario portoghese
    marzo 20, 2016    

    Ciao, grazie, è molto interessante. Mi sfuggono due cose (tante in realtà ma due me le ricordo :-)):
    1. il numero m non identifica univocamente il messaggio, letterariamente intendo, perché lo stesso m si può ottenere con moltissime disposizioni delle stesse lettere, mi pare, corretto?
    2. cosa impedisce ad un terzo ascoltatore che conosce la chiave pubblica di decifrare il messaggio?

    • Francesco Bonesi's Gravatar Francesco Bonesi
      marzo 21, 2016    

      Ciao!
      Ti rispondo brevemente:
      1) scegliendo p abbastanza grande (intendo di almeno 60 o più cifre) il numero m identifica unicamente il messaggio se è un numero tra 0 e p-1/100. In generale tuttavia si associa un numero ad ogni lettera di m. Quindi quando cifrerai il tuo messaggio lo decomporrai in una successione di numeri e non lo vedrai mai come un numero di per sé. Nel cifrare il messaggio cifrerai le singole lettere che lo compongono. Ciò garantisce unicità. Ora è più chiaro?
      2) conoscere la chiave pubblica non implica la conoscenza della chiave privata. E' proprio questo il punto! La chiave pubblica è di pubblico dominio ed è un punto della curva ellittica: sarebbe Q=dP ove d è la chiave privata. Ecco, per calcolare d sapendo Q dovremmo essere in grado di risolvere un analogo del problema del logaritmo discreto. Non entro troppo nei dettagli, ma, se p è molto grande, i tempi di calcolo di d avendo Q diventano biblici! Risiede qui la forza del metodo.

      Se hai altre domande, chiedi pure!

  4. luglio 1, 2016    

    Dove si possono trovare altri esempi di crittografia di questo tipo per poter capire un po' meglio? Grazie mille!

Lascia una risposta

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

È possibile utilizzare questi tag ed attributi XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Partecipa all’indagine “Io e la Matematica”

Clicca sull'immagine sottostante per rispondere al breve e anonimo questionario:

MIA15 - Nomination

Conviditi con i tuoi contatti questo link!

Canale Telegram dedicato alla Matematica

Iscriviti sul nostro canale Telegram

MIA15 - Nomination

Rimani aggiornato sui più interessanti articoli di divulgazione matematica e non solo!

Iscriviti alla nostra newsletter

Resta aggiornato sui nostri post e su quello che facciamo.

Seguici su Twitter

Tag Cloud

Grazie per il sostegno ai #MIA2015

Grazie a tutti per averci votato ai "Macchia Nera Awards 2015" nella categoria "Miglior Sito Tecnico-Divulgativo".

Siamo arrivati in finale grazie al vostro sostegno!

MIA15 - Nomination