Divertiamoci con la Matematica

Supponiamo di avere una scatola piena di collane. Ogni collana è formata da n sferette di vetro colorato, equidistanti. Le sferette sono fissate su un sostegno rigido di forma circolare, uguale per tutte le collane. Esse segnano quindi i vertici di un poligono regolare di n lati.

Per creare le collane si sono utilizzati c colori diversi. Pertanto possono esistere in tutto cⁿ colorazioni.

Per esempio se n = 3 e c = 2 ci sono 8 colorazioni:

Numeriamole da 1 a 8, dall'alto in basso. Se mettiamo le collane sul tavolo e le ruotiamo (senza ribaltarle, con un movimento rigido piano), ci accorgiamo che anche se le colorazioni sono diverse, le collane possono apparire uguali.

Per esempio nella colorazione 2 la perlina 1 è B, la 2 è B e la 3 è N. Nella colorazione 5 abbiamo 1N, 2B, 3B. Basta ruotare una collana di 60° per ottenere l'altra: sono indistinguibili sul piano. Le colorazioni {BBN, NBB, BNB} danno luogo alla stessa collana. Diciamo che esse formano una classe (detta orbita nella teoria dei gruppi). Vi sono altre tre classi: {BBB}, {NNN}, {NNB, BNN, NBN}. In conclusione, per quante collane ci siano nella scatola, nelle ipotesi fatte ci possono essere soltanto 4 collane diverse.

Nel caso appena visto le classi possiedono tutte 1 oppure 3 ( = n) elementi.

Però non è sempre così. Se n = 4, per esempio, la classe {BNBN, NBNB} ha 2 elementi. Le classi con un solo elemento sono ovviamente formate dalle colorazioni monocromatiche: ai c colori corrispondono c classi di un solo elemento.

La classe di una colorazione si ottiene, come si è detto, prendendo una collana che abbia quella colorazione e ruotandola in tutti i modi nel piano.

Ci sono n rotazioni da applicare: le rotazioni di angolo 2kπ/n con k che varia da 0 a n-1.

Si può anche lavorare semplicemente sulla colorazione (v₁, v₂, ..., v_n) (dove i v_j sono colori) iterando n volte lo shift ciclico:
la classe O di (v₁, v₂, ..., v_n) è:

Nell'insieme O, che è la classe (orbita) di (v₁, v₂, ..., v_n), sono elencati n elementi. Ma essi non sono necessariamente distinti.

Per esempio se i colori sono uguali:

allora O contiene un solo elemento:

In generale quando accade che O contenga meno di n elementi?

O contiene meno di n elementi se e solo se in O ci sono elementi che si ripetono. Poichè O è costruito ciclicamente, le ripetizioni possono soltanto essere periodiche: ci devono essere d elementi che si ripetono k volte, dove dk = n.

Segue allora questo importante risultato

Teorema 1 L'ordine di un'orbita O è un divisore di n.

(Ricordo che l'ordine di un insieme è il numero degli elementi che contiene)

Le classi con un solo elemento sono quelle monocromatiche. Ci sono c classi monocromatiche, una per ogni colore. Diciamo t il numero delle classi che possiedono n elementi. Ricordiamo che in tutto ci sono cⁿ colorazioni. Il Teorema seguente esprime quanto detto.

Teorema 2

Per ogni intero c, se n è primo si ha:

cⁿ = c + nt

Questo è esattamente il contenuto di quello che ora viene chiamato il Piccolo Teorema di Fermat.

Teorema 3 - Piccolo Teorema di Fermat (PTF)

Se n è primo allora, per ogni intero c si ha

cⁿ º c (mod n)

(Ricordiamo che a º b (mod n) significa che n divide la differenza a - b).

Per avere una dimostrazione esplicita del PTF bisogna però attendere quasi un secolo.

Eulero nacque 301 anni fa, nel 1707. E' una delle stelle fisse del firmamento matematico, attorno alle quali ruota tutto il sapere.

Nel 1736 Eulero pubblicò la dimostrazione di un teorema che comprende il PTF come caso particolarissimo.

Per enunciare il Teorema di Eulero occorre introdurre la funzione φ, detta appunto funzione di Eulero.

Definizione della funzione φ di Eulero φ(n) = numero degli interi minori di n e coprimi con n

Esempi

- Se n è primo, tutti gli interi che lo precedono sono coprimi con n, dunque in questo caso φ(n) = n - 1.

- Consideriamo n = 10. Gli interi che precedono 10 e sono coprimi con 10 sono:

1, 3, 7, 9
Pertanto φ(10) = 4.

- Consideriamo n = 15. Gli interi che precedono 15 e sono coprimi con 15 sono:

1, 2, 4, 7, 8, 11, 13, 14
Pertanto φ(15) = 8.

Teorema 4 - Teorema di Eulero Se a è coprimo con n, si ha     aφ(n) ≡ 1 (mod n)

Esempi

- Poichè 3 è coprimo con 10 si ha 3^φ(10) = 3⁴ ≡ 1 (mod 10), ovvero
   10 divide 3⁴ - 1.

- Poichè 2 è coprimo con 15 si ha 2^φ(15) = 2⁸ ≡ 1 (mod 15), ovvero
   15 divide 2⁸ - 1.

Diciamo funzione aritmetica una funzione definita sugli interi.

Tra le funzioni aritmetiche più importanti spicca proprio la funzione di Eulero, funzione dalle mille e mille sorprendenti proprietà, funzione che appare ovunque in matematica, dall'aritmetica alla teoria analitica dei numeri, dalla combinatorica all'algebra.

La funzione φ è una funzione aritmetica moltiplicativa. Questo significa che

Se a e b sono coprimi, allora φ(ab) = φ(a)φ(b) per esempio φ(60) = φ(4)φ(15) = 2×8 = 16

Nel caso di φ si ha

Teorema 5 φ(pe) = (p - 1)pe-1

Esempio

φ(81) = φ(3⁴) = 2×3³ = 54.

φ(25) = φ(5²) = 4×5 = 20.

φ(2025) = φ(81×25) = φ(81)φ(25) = 54×20 = 1080

Esercitazione 3.1

Calcolare φ(44088044)

La seguente è una identità molto elegante, soddisfatta dalla funzione φ

Teorema 6 å d|n  j(d) = n

Nel Teorema 6 la sommatoria è estesa ai divisori di n.

Esempio

Verifichiamo il Teorema 6 per n = 15. I divisori di 15 sono 1, 3, 5, 15. In effetti:

φ(1) + φ(3) + φ(5) + φ(15) = 1 + 2 + 4 + 8 = 15

Esercitazione 3.2

Verificare il teorema 6 per n = 60.

Teorema 7 NC(n, x) =   1 n å d|n  j( n d ) xd

Esempi

- Se n è primo, n possiede solo due divisori, 1 e n. Pertanto in questo caso

NC(n, x) = j(n)x + j(1)xn n = (n-1)x + xn n

Il fatto che, quando n è primo, la frazione a destra sia sempre un numero intero dimostra ancora una volta il PTF.

- Ovviamente se abbiamo un solo colore (cioè se x = 1) c'è una sola collana colorata, qualsiasi sia n, ovvero NC(n, 1) = 1.
Si noti che questa è una riformulazione del Teorema 6, dunque il Teorema 6 si ottiene come corollario del Teorema 7.

- NC(12, x) = (1/12)×(4x + 2x² + 2x³ + 2x⁴ + x⁶ + x¹²)

Esercitazione 3.3

Scrivere i polinomi NC(n, x) per n compreso tra 1 e 10.

RSA è un metodo crittografico tra i più potenti attualmente utilizzati. RSA è un acronimo che contiene le iniziali dei nomi dei tre creatori: Ron Rivest, Adi Shamir, e Leonard Adleman.

Sono personaggi veramente molto, molto interessanti. Leonard Adleman, nato il 31 Dicembre 1945, è il creatore del "DNA computing". Proprio come Leonardo è attivo in campi tra di loro lontanissimi: ha importanti pubblicazioni sui numeri primi e, al tempo stesso, fa ricerca in un laboratorio di biologia molecolare.

Ronald "Ron" Rivest è del 1947. Adleman lo descrive come un "uomo del Rinascimento", capace di raggiungere ogni meta. Tra le altre cose ha creato le famose funzioni hash MD2, MD4 e MD5. L'ultimo premio (tra i tanti) che ha vinto (nel 2007) è il prestigioso Marconi Prize.

Adi Shamir è nato a Tel Aviv nel 1952. E' uno dei massimi esperti mondiali della difficile arte di rompere i codici. Nel 1986 vinse il premio Baker della IEEE per la sua scoperta di un sistema veloce che permetteva di rompere il codice crittografico di Merkle-Hellman.
La sua mente "tagliente" sembra già scritta nel suo cognome. Secondo una tradizione ebraica shamir è il nome di un "ente" (per molti rabbini un verme) in grado di tagliare ogni pietra. I lettori interessati all'argomento possono leggere questo bellissimo lavoro di Lia Mangolini: La vera natura del "magico Shamìr" (copia locale).

Fu Ron che nel 1977 coinvolse Leonard e il "magico Shamir" nella creazione del sistema crittografico che ora porta il loro nome.

Rivest decise di mettere in moto un nuovo progetto di ricerca nel campo della crittografia dopo avere letto l'articolo "New Directions in Cryptography", di Whitfield Diffie e Martin E. Hellman. In questo, ormai famoso, lavoro i due autori proponevano l'idea, veramente innovativa e potente, dei sistemi a chiave pubblica, senza però essere in grado di fornire esempi concretamente applicabili.

Il metodo RSA si basa su cinque fatti:

1. Ogni intero coprimo con n possiede un inverso modulo n.
2. Il Teorema di Eulero.
3. E' facile trovare numeri primi grandi.
4. Nessuno sa fattorizzare numeri grandi.
5. Nessuno sa estrarre le radici e-esime modulo n, se n è grande.

Questi fatti sono affermazioni di tipo molto diverso.

I punti 1 e 2 sono dimostrati, sono teoremi, sono semplicemente veri.

I punti 3, 4 e 5 hanno in comune l'aggettivo "grande". Evidentemente la sua presenza crea un certo disagio, in mezzo a espressioni come "numeri", "numeri primi", "radici e-esime", le quali hanno un significato ben preciso e univoco. Il significato di "grande" varia a seconda del contesto, e con lo sviluppo tecnologico, "grande" diventa sempre più grande! Mettete in luogo di "grande": "ha più di duecentocinquanta cifre", e va bene per tutto il 2008, ci scommetto.

Nel punto 3 appare "è facile". Significa che esistono algoritmi veloci per generare numeri primi. Per esempio sul mio piccolo portatile, con Mathematica, trovo primi di 200 cifre in 0.1 secondi, di 300 in 0.3 secondi, di 500 in 2 secondi (in media). Il discorso è abbastanza complesso. Il tempo dipende sia dalla densità dei primi che dalla velocità dell'algoritmo che si usa per testare la primalità. Il primo algoritmo polinomiale (per una breve discussione sugli algoritmi polinomiali si veda qui) che assolve questo compito è del 2002. In pratica si usano però algoritmi probabilistici, che sono molto veloci.

Il "nessuno sa" dei punti 4 e 5 significa che non sono attualmente noti algoritmi veloci per fattorizzare gli interi o per estrarre le radici e-esime. Non siamo però in grado di dimostrare che tali algoritmi non esistano.

Utilizzando l'agoritmo AEE visto nel primo divertimento, siamo in grado di provare il fatto 1).

Teorema 8 - Inversi modulo n

Dati due interi a, n, a possiede un inverso modulo n se e solo se a è coprimo con n.

Dimostrazione -

Se a possiede un inverso b modulo n allora si ha ab ≡ 1 (mod n). Questo significa che n|(ab - 1).

Esiste quindi k tale che ab - 1 = kn e 1 = ab - kn. Questo implica che MCD(a, n) = 1, in quanto ogni intero che divide sia a che n deve dividere 1.

Vediamo ora l'altra implicazione.

Supponiamo che MCD(a, n) = 1. Utilizzando il citato AEE si trovano due interi h, k tali che ha + kn = 1.
Questo implica che n|(ha - 1) ovvero che ha ≡ 1 (mod n). Pertanto h è l'inverso di a modulo n.

Esempio Cerchiamo l'inverso di 3 modulo 13. Utilizzando AEE si trova che 1 = 9×3 - 2×13.
Quindi 9 è l'inverso di 3 modulo 13.

1  2  3  4  5  6  7  8  9  10  11  12
1  7  9  10 8  11 2  5  3  4   6   12

L'algoritmo crittografico RSA

Ricordiamo che la scrittura z = x mod y significa che z è il resto della divisione di x per y.

Per esempio 2008 = 8002 mod 2997.

mod è un'operazione a due argomenti: z è il risultato della operazione; x, y sono gli argomenti.

Invece l'espressione z ≡ x (mod y) è un enunciato. Si legge z è congruo a x modulo y e significa, come detto sopra, che y divide la differenza z - x.

Se è vero che z ≡ x (mod y) e 0 ≤ z < y allora z = x mod y, e viceversa.

Per esempio 5005 ≡ 8002 (mod 2997) è vero, ma non è vero che 5005 = 8002 mod 2997.

L' RSA è un sistema a chiave pubblica. Vi sono sistemi veloci e sicuri di cifratura (come l' AES: Advanced Encryption Standard) che richiedono la condivisione da parte degli utenti di una chiave segreta. Questo crea il problema dello scambio delle chiavi: come fanno A e B a scambiarsi una chiave segretamente? Ci vuole un sistema di crittografia, ma se anche questo richiede una chiave segreta .... Per uscire da questo circolo vizioso occorrono metodi di cifratura che non richiedono la segretezza della chiave utilizzata per cifrare. La chiave cifrante è resa pubblica. Solo la chiave per decifrare è tenuta segreta, ed nota soltanto all'utente che ha creato e pubblicizzato la chiave pubblica. Ovviamente occorre (ed questo il difficile nella ideazione di un sistema a chiave pubblica) che la chiave segreta non possa essere facilmente dedotta dalla chiave pubblica.

Sia A un utente di RSA. Vediamo in dettaglio la costruzione della chiave pubblica. Chiamiamo questa parte "fase K".

K1 - A calcola due primi p, q di grandezza opportuna in relazione al livello di segretezza richiesto.
       Supporremo p < q.

K2 - A calcola N = pq e F = φ(N) = (p - 1)(q - 1).
       A questo punto p, q vengono eliminati per sempre.

K3 - A sceglie un intero E coprimo con F.
       La chiave publica di A è la coppia (N, E).

La chiave segreta si determina in un singolo passo (S):

S - Utilizzando AEE (o simili) A calcola d'inverso D di E modulo F: ovvero ED = 1 + kF.
      Ora F viene eliminato per sempre.

Vediamo ora come si cifra un messaggio M. E' ovvio che ogni testo si può codificare con una sequenza di numeri interi. Supponiamo allora che M sia un intero. L'unica richiesta su M è che sia coprimo con N. Si può garantire questo formattando i messaggi in modo tale che si abbia sempre M < p.

Vediamo il metodo di cifratura (C) di M.

C - Se B vuole inviare il messaggio M ad A, B legge la chiave pubblica di A (N, E), e calcola V = M^E mod N.
     B invia V ad A.

Se un individuo H diverso da A intercetta V, che cosa può fare?
H conosce E, N e M^E mod N. H non è in grado di estrarre la radice E - esima di V modulo N, quindi non ha accesso a M per questa via.

H sa che la chiave segreta D, che permette di recuperare M, è l'inverso di E modulo φ(N). Però H non conosce φ(N), e non può calcolarlo senza conoscere p, q. Siccome H non è nemmeno in grado di fattorizzare N, non può fare nulla.

Veniamo ora ad A. Ecco come A decodifica C. Chiamo questa fase T.

Fase T

A calcola V^D mod N. Il numero che trova è proprio M. Infatti
V^D mod N =
(M^E)^D mod N =
M^ED mod N =
M^{1 + kF} mod N =
M × (M^F)^k mod N =
M × (M^φ(N))^k mod N =
M.

L'ultimo passaggio è giustificato dal Teorema di Eulero, che implica M^φ(N) = 1 mod N.
Inoltre si deve osservare che M mod N = M perché M < N.

Il calcolatore è in fase sperimentale. Quindi, se osservate malfunzionamenti siate pazienti e segnalatemeli.

Poichè si tratta di uno script e - inoltre - la moltiplicazione non è ottimizzata in alcun modo, l'esecuzione non è veloce. Se i numeri in ingresso sono grandi e/o la CPU del vostro computer è lenta possono occorrere diversi secondi. In questo caso - dipende dal sistema operativo - può apparire una allerta del sistema che vi avverte che uno script sta rallentando il computer e vi chiede se volete fermarlo. Fate come volete, ma sappiate che, aspettando, avrete alla fine il risultato. L'allerta può apparire parecchie volte. Questo non accade comunque, nemmeno sul mio vetusto portatile, con i numeri che userò negli esempi. Nel calcolatore c'è anche un timer. Il tempo impiegato per ogni calcolo eseguito appare (in secondi) nella finestrina in basso.

Ci sono quattro aree di testo: ARG1, ARG2, ARG3 e Risultato. Tutti i lettori hanno certamante confidenza con queste particolari sezioni di un documento. In esse si scrivono e si leggono dati, e si può fare il taglia-incolla.

Cominciamo a usarlo, si impara subito. Per ora fate quello che faccio io.

Scrivo 44424 in ARG1 e 4319 in ARG2. Premo il tasto MOD. Risultato 1234 (Tempo = 0 sec).
Significa che il resto della divisione di 44424 per 4319 (ovvero 44424 mod 4319) è 1234.

Premo MCD e leggo 617 (0 sec.). Significa che 617 è il massimo comun divisore di 44424 e 4319.

Se premo MOLT trovo il prodotto 191867256 dei due interi (0 sec.).

Se premo POT arriva un avviso. Il risultato è (considerato da me) troppo grande. Ho posto un limite, per cui - al momento - la massima potenza di 2 che viene calcolata è 2⁵⁷⁷.

Inserisco 2 577, rispettivamente in ARG1 e ARG2. Trovo (1.252 sec.):

49466080294620906812100504203929438007026269820242367982812611218579445021306373434063280212248608997919534285
2032278678702730068613502419935092310203786335833213544297398272

(Domanda: qual è la massima potenza di 10 che viene calcolata? Rispondete senza provare, con un ragionamento matematico.)

Lascio 2 e 577 al loro posto. Premo INVMOD. Trovo 289 (0.01 sec.). Significa che 289 è l'inverso di 2 mod 577.
In generale INVMOD calcola l'inverso (se esiste, cioè se ARG1 e ARG2 sono coprimi) di ARG1 modulo ARG2.

Verifico. Scrivo 577 in ARG3 e 289 in ARG2. Premo MOLTMOD.
MOLTMOD calcola sempre ARG1×ARG2 mod ARG3.
Naturamente ottengo 1 (0 sec.).

Non cambio ARG1 e ARG3. Metto 577 in ARG2. Premo POTMOD.
POTMOD calcola sempre ARG1^ARG2 mod ARG3.
Trovo che 2 = 2⁵⁷⁷ mod 577 (0.07 sec.).
Se al posto di 2 metto un qualsiasi intero x minore di 577 trovo che si ha sempre x = x⁵⁷⁷ mod 577.
Questo accade perché 577 è primo, in virtù del PTF di cui abbiamo parlato sopra.

Ci sono tre memorie: MEM1, MEM2 e MEM3. Il funzionamento è uguale per tutte. Chiamo MEM una qualsiasi di esse. Se premo MEM, in MEM viene scritto il numero che si trova nell'area di testo contrassegnata nella tendina. Di default c'è ris.
RIC1, RIC2 e RIC3 trasferiscono il contenuto della relativa memoria nell'area di testo contrassegnata nella tendina. L'area designata per default è 3 (ovviamente ARG3).

Potete benissimo fare a meno delle memorie facendo copia-incolla, con l'ausilio di un paginetta su cui scrivere, per esempio il notepad. Comunque utilizzeremo il tutto nei prossimi esempi.

Per comodità del lettore ho messo qui l'elenco dei primi compresi tra 1000000 e 2000000 (sono 70435).

Voglio crearmi una chiave pubblica per RSA. Seguo i punti K1, K2 e K3. Prendo due primi a caso. Per esempio il primo e l'ultimo dell'elenco :) Metto il primo in ARG1 e il secondo in ARG2, premo MOLT e poi MEM1. Trovo che il prodotto N vale 1999998999979.

Ho p = 1000003, q = 1999993, N = 999998999979 (memorizzato in MEM1).

Ora trovo F = φ(N) = (p - 1)(q - 1) = 1000002×1999992 = 1999995999984. Trasferisco F in ARG2 così:

Premo MEM2, nella tendina di RIC2 attivo 2, premo RIC2.

Penso una chiave pubblica E. Provo con E = 6487. Scrivo 6487 e premo INVMOD. Nell'area Risultato si legge "I due numeri non sono coprimi!".

Verifico premendo MCD, per pura curiosità. Trovo che hanno MCD uguale a 499. Dunque 6487 non va bene. Metto 6463 in ARG1. Premo INVMOD e trovo 1453501657423. Questa è la chiave segreta D (fase S). La memorizzo in MEM2, premendo MEM2. Questo cancella F, sostituendolo con D.
Premo Cancella. Cancella libera le tre aree di ingresso, ma non tocca né Risultato né le memorie.

La situazione è la seguente:

p, q e F sono stati cancellati. N è in MEM1, D è in MEM2. Rendo pubblica la coppia (E, N) = (6463, 999998999979).

Supponiamo ora che Q mi voglia inviare il messaggio M = 9976 in modo segreto, con RSA (face C).

Q calcola M^E mod N e trova 9976⁶⁴⁶³ mod 999998999979 = 31567716510.

Pertanto Q mi invia V = 31567716510.

Io decodifico V con l'uso del calcolatore (fase T).
Copio V in ARG1.
Sistemo sul 2 la tendina di RIC2, e lo premo. La mia chiave segreta, 1453501657423, che era stata memorizzata in MEM2, appare in ARG2. In ARG3 continua a esserci N = 999998999979. Premo POTMOD e trovo il messaggio: 9976 (1.842 sec.).

Esercitazione 3.4

Scambiate messaggi segreti con un amico utilizzando RSA.

Esercitazione 3.5

La chiave pubblica (E, N) di Franco è (17, 1961).

Intercettate un messaggio cifrato inviato a Franco, V = 1044.

Trovate il messaggio originale M.

Esercitazione 3.6

La chiave pubblica (E, N) di Franco è (17, 4284575317803629).

Intercettate un messaggio cifrato inviato a Franco, V = 2056123342775479.

Venite a sapere che F = φ(N) = 4284575114499420.

Trovate il messaggio originale M.

Esercitazione 3.7 (difficile)
Gli utenti A e B hanno, rispettivamente, chiavi pubbliche (Q, N) e (R, N).

Q e R sono, per ipotesi, coprimi.

Ad A e a B viene inviato lo stesso messaggio M.

Pertanto A riceve V = MQ mod N, e B riceve W = MR mod N.

Voi intercettate V e W.

Trovate M.

Esercitazione 3.8 (per chi ha risolto 3.7)
Fornite un esempio numerico del metodo che avete usato in 3.7

Inviate le vostre risposte e soluzioni a umberto.cerruti@unito.it