Blog divulgativo sulla matematica applicata

RSA alla corte di Re Artù: un esempio di crittografia a chiave pubblica

042317360749242104072325

No, non sono impazzito! Come vi ho detto nel mio precedente post (link qui), il bello della crittografia è riuscire a spedire messaggi che siano comprensibili solo per il diretto interessato e assolutamente senza senso per tutti gli altri. Sempre la volta scorsa abbiamo visto alcuni metodi, piuttosto semplici, per cifrare messaggi; oggi invece ci occuperemo di uno dei sistemi più utilizzati al mondo: il sistema RSA.

rsa_key_security

Il motivo per cui ho deciso di scrivere un post sull'RSA è che vale davvero la pena di conoscere (anche se in parte e/o superficialmente) come i nostri dati, password e conti correnti vengono protetti. Sicuramente non lo troverete semplice ma probabilmente è un bene, non credete? I concetti matematici alla sua base non sono difficili ma la loro applicazione lo è! I tre inventori ci hanno messo anni...ed erano professori e ricercatori al MIT (chi non lo conoscesse può andare a leggere cos'è su wikipedia qui)! Quindi non è assolutamente uno scherzo!!

Il titolo di questo paragrafo è proprio cifrato usando l’RSA ed una volta svelato il trucco sarete anche voi capaci di decifrarlo senza dubbio e senza inganno!

Prima di arrivarci, però, permettetemi di prenderla leggermente alla larga!

Il piccolo Fermat ed Eulero

Con questo paragrafo non vorrei spaventarvi ma solamente farvi vedere un po' di matematica che c'è dietro quello che faremo. Quindi anche se non capite tutto, non spaventatevi e andate avanti comunque! (Tradotto: guardate, fate finta di niente e passate oltre!)

Pierre de Fermat, matematico francese divenuto famoso soprattutto per il suo “Ultimo teorema”, dà il suo nome anche al cosiddetto “piccolo teorema di Fermat”. Esso afferma che se a è un numero tra 1 e p-1, dove p è un numero primo, allora a^{p-1} \cong 1 \; mod \; p.

Tuttavia esistono versioni più generali di questo teorema. Eulero disse (e dimostrò) che se a e n sono coprimi (cioè il massimo comun divisore tra a e n è 1), allora a^{\phi(n)} \cong 1 \; mod \; n, dove \phi(n) è il numero di interi più piccoli e coprimi con n. Ecco, magari già la stiamo facendo troppo complicata. DON'T PANIC! (citazione dalla Guida Galattica per Algebristi).

Vediamo qualche esempio: i numeri coprimi con un primo p sono tutti gli interi precedenti, quindi \phi(p)=p-1. Quindi sto dicendo che a^{p-1} \cong 1 \; mod \; p (notate che è il piccolo teorema di Fermat!!). Oppure, se p e q sono numeri primi \phi(pq)=(p-1)(q-1). Perciò a^{(p-1)(q-1)} \cong 1 \; mod \; pq se a non è divisibile per p e per q.

Sapendo, quindi, che \phi(3)=3-1=2, preso un qualunque numero a non divisibile per 3, si ha che a^2 è congruo a 1 modulo 3. Per esempio, se scelgo 16, 16^2=256 che è congruo a 1 modulo 3. Infatti 256 si ottiene moltiplicando 3 per 85 e aggiungendo 1. Se prendessimo, invece, i due numeri primi 3 e 7, il prodotto tra di loro fa 21 e \phi(21) = (7 - 1)(3-1) = 12. Infatti, i numeri precedenti a 21 e coprimi con esso sono 1,2,4,5,8,10,11,13,16,17,19 e 20, e sono appunto 12 numeri! Quindi se prendiamo uno di questi 12 numeri, mettiamo 2, e lo eleviamo a \phi(20)=12, otteniamo 4096 che diviso per 21 da resto 1. Infatti 4096 si ottiene moltiplicando 21 per 195 e aggiungendo 1.

Non entriamo in tutti i dettagli del caso (lo so che in realtà volevate!!) ma abbiamo bisogno di questo per mandare i nostri messaggi segretissimi.

Messaggi segretissimi alla corte di Re (Semola) Artù

disney_spada_roccia_RSA

Ci siamo: RSA. E' un acronimo ma ovviamente non sta per Re (Semola) Artù! Prende, infatti, il nome dalle iniziali dei tre inventori Rivest, Shamir e Adleman. Fu inventato nel 1978 e ad oggi è il sistema più usato al mondo data la sua quasi imbattibilità. Per spiegarvi in modo semplice come funziona farò un esempio; più avanti inoltre troverete il caso generale…se preferite potete anche solo leggere l’esempio, non mi offendo assolutamente, anzi!

Di solito in questi casi tutti i libri di crittografia iniziano con “Bob vuole scrivere un messaggio ad Alice…”, ma a me non piacciono né Alice né Bob…hanno troppi segreti! Io invece dico che Re Artù vuole scrivere un messaggio a Mago Merlino. Mettiamo che questo messaggio è “ciao”. Traduciamo “ciao” in numeri, ogni lettera ha il numero ad essa associato nell’alfabeto, ovvero “c=03”, “i=09”, “a=01” e “o=13”. Quindi: “ciao”=03090113.

Mago Merlino sceglie due numeri primi 5 e 11 e li moltiplica ottenendo 55. Inoltre calcola \phi(55)=(5-1)(11-1)=40 e sceglie un numero coprimo con 40, ammettiamo 27. La coppia (55,27) si chiama chiave pubblica e come dice il nome è di pubblico dominio. Mago Merlino astutamente fa caso al fatto che 27*3 \cong 1 modulo 40. Il numero 3 è detto chiave privata e, come dice il nome, solo Mago Merlino la sa.

Re Artù, allora, prende la chiave pubblica di Merlino e ad ogni numero del messaggio da inviare fa la seguente operazione: eleva alla 27 e calcola modulo 55.. Quindi: “c=03” diventa 3^{27} modulo 55 che è congruo a 42 e così via per le altre lettere.

Facendo i conti si ottiene che “ciao=03090113” è criptato in “42040107”.

Mago Merlino riceve il messaggio “42040107” e vuole decifrarlo. Si ricorda che da qualche parte nella sua libreria ha la sua chiave privata. Dopo una faticosa ricerca la trova: era il numero 3! Prende ogni blocco di due numeri e fa la seguente operazione: eleva alla 3 e calcola modulo 55. Quindi: 42 diventa 42^3 modulo 55 che è congruo a 3…ma è proprio la lettera “c=03”!

Procedendo 4^3=64 \cong 9 modulo 55, che è la lettera “i=09”.

Andando avanti si vede che il messaggio ricevuto è proprio “ciao”, incredibile eh?!

Ma come mai funziona? Prima ho detto che l’astuto Merlino aveva trovato che 27*3 \cong 1 modulo 40, perciò se la lettera originale era “c=03”, Artù l’ha elevata alla 27 e successivamente Mago Merlino alla 3, ottenendo in sostanza 3^{27*3}. Essendo l’esponente congruo a 1 modulo 40 e usando quello che ci dice il teorema di Eulero ottengo che quel numero è congruo a 3 modulo 55, proprio come volevo!

In generale [advanced math mode on]: si traduce il messaggio in un numero X e lo si divide in blocchi. Si cifra un blocco alla volta, prendiamone uno: B. Mago Merlino sceglie due numeri primi p e q e li moltiplica ottenendo n=pq. Inoltre sceglie un numero f coprimo con \phi(n). Dà quindi ad Artù la coppia (n,f), ovvero la sua chiave pubblica. Esiste inoltre un numero d tale che fd\cong 1 modulo \phi(n). Tale numero d è detta chiave privata ed è in possesso di Merlino e nessun’altro. Re Artù prende il blocco B, lo eleva alla f e lo calcola modulo n: ottiene un certo numero C. Lo trasmette a Merlino, il quale, per decifrarlo, lo eleva alla d e lo calcola modulo n. Ovviamente in sostanza l’operazione fatta su B è B^{fd} e questo numero è congruo a B modulo n, grazie al teorema di Eulero (poiché fd \cong 1 modulo \phi(n)). [advanced math mode off]

La forza di questo metodo sta nel fatto che per calcolare la chiave privata bisogna conoscere \phi(n) e per conoscere quest’ultima bisogna sapere la fattorizzazione di n, ovvero i primi che lo compongono, cioè p e q. Ovviamente n è scelto in modo che trovare i suoi due primi sia molto difficile, ad esempio prendendoli di 30 cifre ciascuno! Inoltre non c’è bisogno di accordarsi su una chiave comune, ognuno ha la sua e ci si scrive usando la chiave pubblica dell’altro. Geniale eh?

So che non è certamente un metodo di facile utilizzo e da ciò ne deriva in parte la sua imbattibilità! In più il fatto di non avere una chiave comune, cosa che contraddistingueva i metodi precedenti, lo rende notevolmente più sicuro. Stai cioè codificando qualcosa non conoscendo tu stesso la chiave della codifica...sembra assurdo, ma è così!!

Ad ogni modo, usando lo stesso metodo di Re Artù, ho criptato il titolo del primo paragrafo di questo articolo. Siete in grado di decifrarlo?!?!

Per ora vi saluto, spero vi sia piaciuto il mio post. Alla prossima matematicavventura!

------------------------------------------------------------------------------------------------------------------------

Soluzione: 042317360749242104072325 si traduce in 091218161304192109131205, ovvero “Introduzione”. Se ci siete riusciti da soli, vi dico solo questo: 283601234904 !

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

Similar posts

3 commenti

  1. Michele's Gravatar Michele
    aprile 18, 2016    

    Quindi, il numero n, prodotto di p e q, deve essere necessariamente maggiore di B.

    • Davide's Gravatar Davide
      agosto 13, 2018    

      Ciao, bella spiegazione. C'è un passaggio che non mi è molto chiaro. Una volta ottentua la chiave pubblica ho a disposizione il numero 55, il numero 40, e il numero 27. Da questi numeri come si fa a ottenere il 3 della chiave privata ? Grazie

    • Francesco Bonesi's Gravatar Francesco Bonesi
      agosto 13, 2018    

      Grazie ad entrambi dei commenti.

      @Michele: sì esatto. Se il blocco B è maggiore di n, si riduce in blocchi più piccoli fino ad avere B < n.

      @Davide: in realtà servono solo 40 e 27. La chiave privata è infatti l'unico numero che, moltiplicato per 27, è congruo a 1 modulo 40. In questo caso, quel numero è 3 perché 3*27 = 81 = 2*40 +1. Questa pagina di Wikipedia può aiutarti a comprendere: https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

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