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

11 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!

  5. Marco Basolu's Gravatar Marco Basolu
    febbraio 7, 2019    

    Ciao, vorrei chiederti aiuto proprio riguardo questo tipo di esercizi
    Se ho un messaggio M=5 e voglio trasformarlo in un punto di una curva ellittica E67 (1,1) come procedo?
    Se è possibile te ne prego con qualche passaggio, è per un esame e mi servirebbe tanto grazie mille!

    • Francesco Bonesi's Gravatar Francesco Bonesi
      febbraio 9, 2019    

      Ciao Marco,
      in generale la conversione di un messaggio m (già convertito in numero) in un punto della curva E: E: y^2=x^3+ax+b si fa così:
      1) Per i che va da 0 a 99, si calcola x_i=100*m+i.
      2) Poi si calcola z_i=x_i^3+ax_i+b e ci si ferma non appena z_i è un quadrato perfetto, cioè se esiste y_i tale che y_i^2 = z_i modulo p.
      A questo punto il tuo messaggio m diventa il punto M (x_i, y_i).

      Ricorda che è necessario lavorare in un campo finito per fare questo gioco, quindi devi conoscere p.

      Se devi cifrarlo invece, segui quanto ho scritto nel post. In tal caso devi avere la chiave pubblica per cifrare e la chiave privata per decifrare.

      Se hai bisogno chiedi ancora :)

      • Francesco Bonesi's Gravatar Francesco Bonesi
        febbraio 9, 2019    

        Se con E67 (1,1) intendevi:

        p=67 e E: y^2 = x^3 + x + 1 e m=5

        Allora prendendo i = 8 => x_8 = 5*100 + 8 = 508 = 39 (mod 67)
        Allora z_8 = 64 (mod 67)
        e quindi y_8 = 8 (8^2 = 64)

        Per cui il punto è (39, 8).

        Spero di averti aiutato.

        • Marco Basolu's Gravatar Marco Basolu
          febbraio 10, 2019    

          Inanzi tutto grazie mille per la risposta e la cortesia.
          Volevo chiederti, visto che nel mio libro di testo c'è scritto che: "si fissa un intero positivo h tale che (m + 1)h < p, e si considerano come potenziali valori dell’ascissa del punto della curva gli interi x = mh + i"
          Per come hai svolto l'esercizio dovrebbe essere h=100, ma non dovrebbe rispettare la regola (m + 1)h < p?

          • Francesco Bonesi's Gravatar Francesco Bonesi
            febbraio 17, 2019    

            Sì, h deve rispettare quella regola se non vuoi lavorare con i moduli. Dato che p è primo, se il prodotto (m+1)h viene visto modulo p il problema non si presenta.
            Chiaramente se non vuoi usare i moduli devi rispettare la regola (m + 1)h < p . Spero di averti aiutato.

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>

Iscriviti alla nostra newsletter

Resta aggiornato sui nostri post e su quello che facciamo.

Canale Telegram dedicato alla Matematica

Iscriviti sul nostro canale Telegram

MIA15 - Nomination

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

Seguici su Twitter

Tag Cloud

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!

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