Leonhard Euler (Eulero) e la crittografia
Leonhard Euler, in italiano noto come Eulero, è stato un matematico, fisico e astronomo svizzero.
Eulero è stato probabilmente il più prolifico matematico di tutti i tempi, avendo lasciato quasi 900 pubblicazioni e opere e dato contributi fondamentali ai più disparati campi della matematica.
Importante per la crittografia è il suo contributo alla teoria dei numeri, in particolare l’introduzione della funzione di Eulero e la dimostrazione del teorema di Fermat-Eulero, che sono oggi alla base del codice RSA.
La vita di Eulero
Eulero nacque a Basilea il 15 aprile 1707, figlio di Paul Euler, un pastore protestante, e di Marguerite Brucker. Dopo di lui nacquero due sorelle, Anna Maria e Maria Magdalena.
Paul Euler era amico della famiglia Bernoulli e di Johann Bernoulli, uno dei più famosi matematici d’Europa, che ebbe molta influenza su Leonhard.
Eulero entrò all’Università di Basilea tredicenne e si laureò in filosofia. A quel tempo riceveva anche lezioni di matematica da Johann Bernoulli, che aveva scoperto il suo enorme talento.
Il padre di Eulero voleva che il figlio diventasse teologo e gli fece studiare il greco e l’ebraico, ma Bernoulli lo convinse che il suo destino era invece la matematica.
Gli anni che seguirono furono scanditi da lavoro, viaggi e incontri in un periodo storico denso di mutamenti sociopolitici, soprattutto in Europa.
Dopo vari spostamenti tra la Russia e la Germania, la vista di Eulero peggiorò notevolmente, fino a diventare completamente cieco dall’occhio destro nel 1735, a seguito di una febbre cerebrale.
Allo stabilizzarsi della situazione politica in Russia Caterina la Grande, salita al potere nel 1766, lo invitò a San Pietroburgo. Egli accettò e ritornò in madrepatria, dove restò fino alla morte, il 18 settembre 1783.
Il teorema di Eulero
Il teorema di Eulero è un risultato fondamentale nella teoria dei numeri, con implicazioni significative nel campo della crittografia a chiave pubblica, in particolare nell’algoritmo di crittografia RSA, ed è strettamente correlato alla funzione totiente di Eulero, spesso indicata come φ(n).
Il Teorema di Eulero afferma che per qualsiasi numero intero a e n che sono coprimi (cioè mcd(a, n) = 1), vale la seguente congruenza aφ(n) ≡ 1(mod n), dove φ(n) è la funzione totiente di Eulero, che conta il numero di numeri interi fino a n che sono coprimi con n.
Per comprendere in profondità il Teorema di Eulero, è essenziale comprendere prima la funzione totiente di Eulero, il concetto di aritmetica modulare e la nozione di coprimalità.
La funzione totiente
La funzione di Eulero associa a un numero intero positivo n il numero dei numeri interi primi con n e minori di n (compreso l’uno); detto altrimenti i p tali che mcd(n, p) = 1.
Si tratta di una funzione basilare della teoria dei numeri, che interviene in molti teoremi come quello di Fermat-Eulero, oltre ad essere uno degli ingredienti fondamentali del cifrario RSA.
Per esempio, per n = 6 la funzione di Eulero vale 2 perché gli interi primi con 6 e minori di 6 sono solo 1 e 5; per n = 7 la funzione vale 6 perché essendo 7 primo tutti i numeri che lo precedono sono primi con 7.
L’applicazione in crittografia
Il teorema di Eulero è particolarmente significativo nell’algoritmo di crittografia RSA, che è un sistema crittografico a chiave pubblica ampiamente utilizzato.
RSA si basa sulla difficoltà di fattorizzare grandi numeri compositi e utilizza le proprietà della funzione totiente di Eulero e dell’aritmetica modulare.
In RSA, due numeri primi grandi p e q vengono scelti e il loro prodotto n = pq viene utilizzato come modulo sia per la chiave pubblica che per quella privata. Il totale φ(n) è calcolato come φ(n) = (p-1)(q-1).
Un esponente pubblico e è scelto in modo tale che e<φ(n) e mcd(e, φ(n)) = 1. L’esponente privato d viene quindi calcolato come l’inverso moltiplicativo modulare di e modulo φ(n), cioè ed ≡ 1(mod φ(n)).
La chiave pubblica è (e, n) e la chiave privata è (d, n).
Per crittografare un messaggio M, il mittente calcola il testo cifrato C come: C ≡ Me (mod n).
Per decifrare il testo cifrato C, il destinatario calcola il messaggio originale M come: M ≡ Cd (mod n).
Il Teorema di Eulero garantisce che questo processo di decrittazione funzioni correttamente perché: Med ≡ M (mod n).
Detto questo ed ≡ 1 (mod φ(n), esiste un numero intero k tale che: ed = 1 + kφ(n).
Così, Med = M1+kφ(n) = M (Mφ(n))k ≡ M1k = M (mod n).
Ciò dimostra la correttezza e la sicurezza dell’algoritmo RSA, sostenuto dal Teorema di Eulero.
Una vita per la matematica: il lascito di Eulero
Eulero è stato senz’altro il più grande fornitore di “denominazioni matematiche”, offrendo il suo nome a una quantità impressionante di formule, teoremi, metodi, criteri, relazioni, equazioni, e diede inoltre importanti contributi alla fisica e in particolare alla meccanica classica e celeste.
Complessivamente esistono 886 pubblicazioni di Eulero. Buona parte della simbologia matematica tuttora in uso venne introdotta da Eulero, per esempio i per l’unità immaginaria, Σ come simbolo per la sommatoria, f(x) per indicare una funzione e la lettera π per indicare pi greco.
Nel mondo della crittografia, e in generale della matematica applicata, certamente gli è riconosciuto il vanto di aver dato un contributo fondamentale alla nascita della crittografia RSA, un elemento essenziale della sicurezza del nostro tempo.