Francesco Fassò, Andrea Giacobbe

Università degli studi di Padova

Note del corso di
Laboratorio Computazionale
A.A. 2009—2010

Capitolo 2: crittografia

2.1 Proprietà dei numeri primi

In questo capitolo useremo a piene mani l'aritmetica modulare. Facciamo quindi un piccolo ripasso di teoria dei numeri.

Mathematica ha molte funzioni relative ai numeri naturali, ed ai primi

2.1 Proprietà dei numeri primi

FactorInteger[1567]
FactorInteger[1566]

Prime[2]
Prime[10]

PrimePi[3]
PrimePi[π]
PrimePi[30]
PrimePi[30.1]

2.1 Proprietà dei numeri primi

Esercizio 2.1.2: creare la lista di tutti i numeri primi minori od uguali ad n

Suggerimento: un modo non molto efficiente ma concettualmente semplice  è di produrre tutti i primi n mumeri primi e poi selezionare quelli ≤ n. Il comando per selezionare è Select

Impariamo ad usare Select. Ha bisogno di lista e criterio

2.1 Proprietà dei numeri primi

criterio[x_]:= x<10

criterio[1]

2.1 Proprietà dei numeri primi

lista=Table[i,{i,1,11}]

2.1 Proprietà dei numeri primi

Ci sono molti funzioni–criterio già preconfezionate

Select[lista,EvenQ]

2.1 Proprietà dei numeri primi

NB : la "funzione criterio" va passata senza argomento. Si scrive test e non test[x]  o test[y]

Motivo: al solito, scrivere esplicitamente la variabile nella funzione è un nostro bisogno psicologico.

2.1 Proprietà dei numeri primi

Altro tentativo vogliamo creare la lista dei primi n numeri primi (che ovviamente eccede n) e poi selezionare quelli minori od uguali ad n

test[n_, m_] := m <= n
test[12, 10]

Select[Table[Prime[i],{i,1,12}],test]

2.1 Proprietà dei numeri primi

Si usano le pure functions

g=test[#,12]&

g[10]

Oppure una costruzione "originale"  di funzione di 2 variabili

testprimo[n_][m_]:=m <= n

2.1 Proprietà dei numeri primi

È così facile decidere se un numero è primo o no?

Il vecchio manuale dice: "PrimeQ first tests for divisibility using small primes, then uses the Miller–Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test."

PrimeQ[11]
PrimeQ[21]

Dunque, il fatto che PrimeQ[n] valga True non assicura in modo certo che n sia primo

2.1 Proprietà dei numeri primi

Che vorrà mai dire? Cosa vuol dire che si usa un test di tipo probabilistico per fare un'affermazione di primalità di un numero?

Il primo più facile argomento probabilistico è quello che usa il piccolo teorema di Fermat. Che è un teorema in algebra modulare.

2.1 Proprietà dei numeri primi

L'aritmetica modulare è l'algebra fatta sull'anello (Subscript[ℤ, m]) anzichè sugli interi

Il numero intero m è chiamato modulo

Dato un qualsiasi altro intero n, si può sempre fare la divisione di n per m. Ovvero vale sempre che esiste un qualche k intero tale che n=k m + r

Il resto della divisione r è un buon rappresentate di n nella classe di equivalenza modulo m

2.1 Proprietà dei numeri primi

Per ciò che riguarda l'aritmetica modulare esistono i comandi

■ Mod[n,m]: che porge il resto della divisione di n per m, ovvero fornisce in modo unico un rappresentante di [n] in (Subscript[ℤ, m])

■ PowerMod[a,b,m] che fornisce [(a^b)] in (Subscript[ℤ, m])

2.1 Proprietà dei numeri primi

Il comando PowerMod è enormemente più veloce che elevare a potenza in ℤ e poi calcolare il resto.

I numeri che produce un elevamento a potenza, molto rapidamente, non sono più gestibili dalla macchina, mentre ridurre modularmente a passi intermedi produce sempre numeri trattabili e facili da moltiplicare

Testiamo i comandi Mod e PowerMod

Mod[5,3]

PowerMod[3,2,4]

2.1 Proprietà dei numeri primi

Due interi a ed b si dicono congrui modulo m, e si scrive a ≡b mod m  se a-b=k m

Essere congrui è una relazione di equivalenza. L' insieme delle classi di equivalenza si indica con (Subscript[ℤ, m]) e si identifica con l' insieme {0,1,...,m-1}

Gli elementi di (Subscript[ℤ, m]) si possono scrivere come [a], dove a è un elemento di ℤ e rappresenta una classe di equivalenza

Ovviamente, [a] = [a + m] = [a + 2 m] =. .. = [a + λ m]

2.1 Proprietà dei numeri primi

Definizione: dato un gruppo G ed un suo elemento a, l'ordine di a è il più piccolo intero positivo m tale che (a^m)=1

Teorema (di Lagrange): dato un gruppo finito G, ogni suo elemento ha ordine che divide |G| (la cardinalità di G)

Consideriamo ora l'anello (Subscript[ℤ, m]). Il sottoinsieme degli elementi di (Subscript[ℤ, m]) moltiplicativamente invertibili (SuperStar[(Subscript[ℤ, m])]) è un gruppo finito.

2.1 Proprietà dei numeri primi

Se m=p è primo, allora (SuperStar[(Subscript[ℤ, p])]) è un gruppo finito di cardinalità p-1.

I suoi elementi sono tutte le classi diverse da [0], ovvero tutte le classi [a] con GCD[a,p]=1. Segue che

Teorema (piccolo teorema di Fermat): se p è primo allora per ogni a coprimo con p vale (a^(p-1))≡ 1 mod p

2.1 Proprietà dei numeri primi

In realtà, in letteratura il piccolo teorema di Fermat viene spesso enunciato in una forma equivalente

Teorema (piccolo teorema di Fermat): se p è primo allora per ogni a intero vale (a^p)≡ a mod p

La relazione tra i due enunciati è molto facile da dimostrare. Basta osservare che se a è coprimo con p allora nell'anello (Subscript[ℤ, p]) esiste la classe (([a])^(-1)). E quindi,  in (Subscript[ℤ, p]), (([a])^(p-1))≡ [1] equivale a (([a])^p)≡[a]

D'altro canto, se  GCD[a,p]=p allora [a]=[0] e quindi le identità di entrambe i teoremi sono valide per gli a non coprimi con p.

2.1 Proprietà dei numeri primi

La funzione Greatest Common Divisor è implementata in Mathematica, ed ha la sintassi GCD[m, n]

GCD[3,4]

GCD[3,6]

2.1 Proprietà dei numeri primi

Il converso del piccolo teorema di Fermat non è vero!

In altre parole, non è vero che se: per ogni a coprimo con m (ovvero tale che GCD[m,a]=1 vale l'identità (a^(m-1))≡1 mod m, allora m è primo...

... ma quasi

2.1 Proprietà dei numeri primi

Per controllare che m soddisfi alla proprietà appena enunciata, non occorre testare che per ogni a coprimo vale (a^m)≡1 mod m. Infatti se vale (x^m)≡1 mod m e (y^m)≡1 mod m, allora vale (((x y))^m)≡1 mod m.

Basterebbe quindi testare la condizione (x^m)≡1 mod m solo per i primi che possono essere fattori degli a<m

Ma anche questo è esagerato. Non sembra quasi un criterio tipo "crivello di Eratostene" (un test di divisibilità per tutti i primi <m)

2.1 Proprietà dei numeri primi

Il test di quasi–primalità fa infatti molto meno: testa solo per alcuni primi. Cominciamo con il definire una famiglia più vasta, che chiamiamo probabilmente–primi.

Definizione: un numero m è un probabilmente–primo se m è coprimo con 2 (è dispari) e se vale l'identità
	(2^(m-1))≡ 1 mod m

2.1 Proprietà dei numeri primi

Cominciamo con il definire una famiglia più vasta, che chiamiamo probabilmente–primi.

Definizione: un numero m è un quasi–primo se m è coprimo con 2 e 3 e se inoltre valgono le identità
	(2^(m-1))≡ 1 mod m
	(3^(m-1))≡ 1 mod m

Non è stato possibile dimostrare che l'insieme dei numeri m non primi ma quasi–primi (ovvero che soddisfano alla definizione sopra) sia un insieme infinito.

I numeri con questa proprietà si chiamano quasi–primi

2.1 Proprietà dei numeri primi

Esercizio 2.1.4:  scriviamo una funzione probabilistica ProbabilePrimePi[n] che ad un naturale n associa il numero di interi minori od uguali di n che sono probabilmente primi

Perché non fare meglio e controllare se m è ancora più probabilmente primo? Ovvero se vale anche che  (3^(m-1))≡1 mod m  e così via.

2.1 Proprietà dei numeri primi

Suggerimenti: una volta definite le appropriate funzioni test, usate il comando And (con i compagni Or e la negazione !) per accorpare più controlli

Esercizio 2.1.5:  scrivere una funzione probabilistica QuasiPrimePi[n] che ad un naturale n associa il numero di interi minori od uguali di n che soddisfano al criterio di primalità sia con base 2 che con base 3.

Esercizio 2.1.6:  scrivere una funzione probabilistica ErroriQuasiPrime[n] che ad un naturale n associa il numero di interi minori od uguali di n che soddisfano al criterio di primalità sia con base 2 che con base 3 ma che non sono primi per Mathematica.

2.1 Proprietà dei numeri primi

Ovviamente, ci sono test di primalità molto più sofisticati di quello che vi ho raccontato. Esiste un package, il PrimalityProving, che si carica con il comando

Needs["PrimalityProving`"]

E che permette di usare funzioni che testano la primalità in vario modo

ProvablePrimeQ[(2^10)]

Leggete cosa fa PrimeQCertificate

2.2 Il metodo di Giulio Cesare

Passiamo ora alla crittografia. Un messaggio è una stringa di testo, per esempio "buongiorno a tutti"

La crittazione (codifica) si basa sulle seguenti idee

■ Si trasforma la stringa di testo in una lista di numeri, che sono più facili da trattare. Ad esempio A->1,B->2, ... (useremo i codici ASCII). Chiamiamo T questa trasformazione

■ Si usa poi una trasformazione da ℕ in sè  (per la precisione, di un sottoinsieme degli interi che contiene il nostro alfabeto) la più complicata possibile (ma comunque qualcosa di computabile) e la più segreta possibile. Chiamiamo S questa trasformazione.

■ In questa prima fase, si potrebbe voler tornare ad un messaggio alfabetico usando (T^(-1)), l'inversa di T. In realtà è inutile farlo, il messaggio crittato è una stringa di simboli (in questo caso numeri)

2.2 Il metodo di Giulio Cesare

Il messaggio così crittato  ( o criptato) si può inviare in modo insicuro.

Anche se un "terzo indesiderato" intercetta il messaggio non importa, tanto non lo può leggere. Forse conosce la funzione T, ma non conosce S e tantomeno la sua inversa.

La decrittazione (o decodifica) si fa percorrendo al contrario i passi della crittazione:

■ Se il messaggio è alfabetico, si applica T, e si ottiene una lista di interi

■ A questa lista si applica (S^(-1)), l'inversa di S

2.2 Il metodo di Giulio Cesare

Regole del gioco: si deve assumere

■ che tutti (anche i nemici o gli hackers etc) conoscano T

■ che tutti conoscano qualcosa di S, che S(egreta) non può rimanere tale a lungo . Il motivo è che queste cose non possono essere tenute segrete : esse sono note a chi ha scritto i programmi, alla ditta che  ha venduto il software etc.

Un primo modo di ovviare a queste fughe di notizie è quello di usare una funzione S che dipende da dei parametri dette chiavi private e tenendo questi segreti, ovvero comunicandoli solo a chi deve saperli

2.2 Il metodo di Giulio Cesare

NB : è irragionevole pensare di fare crittografia usando una sola bijezione T  segreta. Troppo facile che ci siano spie o che qualcuno riesca a "crack–are" la mappa.

2.2 Il metodo di Giulio Cesare

Vediamo preliminarmente come fare la codifica numerica di una stringa di testo, cioè la funzione T

Il comando di Mathematica per trasformare una stringa in caratteri ASCII è ToCharacterCode["stringa", "ASCII"] (la nostra mappa T).

La sua inversa è FromCharacterCode[lista, "ASCII"] (NB : gli argomenti devono essere stringhe, cioè uno o più caratteri racchiusi fra "...")

2.2 Il metodo di Giulio Cesare

ToCharacterCode["a"]

ToCharacterCode["buongiorno a tutti","ASCII"]

2.2 Il metodo di Giulio Cesare

In ASCII le lettere minuscole a, b, c, ..., z sono numerate progressivamente con i numeri da 97 a 122

Verificarlo: basta creare una stringa battendo TUTTI i tasti alfabetici, trasformarla con ToCharacterCode, e infine ordinarla

Per ordinare una lista numerica (con l'ordine naturale di ℝ) si usa il comando Sort[lista]. Tale comando viene con la sua versione più raffinata Sort[lista,ordine], dove ordine è una funzione di due variabili a valori in True o False

ord[{a_,b_},{c_,d_}]:=b<d

2.2 Il metodo di Giulio Cesare

Vediamo se sono "tutti", usiamo la funzione insiemistica Complement

ToCharacterCode["qwertyuiopasdfghjklzxcvbnm"]//Sort

Complement[Range[97,122],ToCharacterCode["qwertyuiopasdfghjklzxcvbnmz"] ]

Vediamo se sono "e soli"

Complement[ToCharacterCode["qwertyuiopasdfghjklzxcvbnmz"],Range[97,122]]

2.2 Il metodo di Giulio Cesare

Per cominciare, useremo un alfabeto ristretto. Codificheremo solo le lettere minuscole  a->1,b->2,...z->26 e lo spazio <spazio>->27

Possiamo farlo o definendo la funzione Verso[stringa] in modo tale che Verso["a"] = 1, .... Verso["z"]=26. Questa funzione prende una stringa e rende una lista di numeri

... e la sua funzione inversa Da[lista] che prende una lista di numeri e rende una stringa

Molto comodo è sottrarre 96 dal codice ASCII

2.2 Il metodo di Giulio Cesare

Verso[stringa_]:=ToCharacterCode[stringa,"ASCII"]-96;
Da[lista_]:=FromCharacterCode[lista+96,"ASCII"]

Verso["buongiorno a tutti"]

Da[Verso["buongiorno a tutti"]]

2.2 Il metodo di Giulio Cesare

Il solo problema è che lo spazio bianco ha codice ASCII  32. E quindi si la funzione Verso lo mappa sul numero negativo - 64.

Un modo semplice per far assegnare lo spazio al codice 27 è di sostituire -64 con 27

VersoCC[str_]:=Verso[str]/.{ -64 -> 27}

DaCC[lst_]:=Da[lst/.{27 ->-64}]

VersoCC["buongiorno a tutti"]

2.2 Il metodo di Giulio Cesare

Ovviamente, la cosa funziona perchè la funzione - è listable (oppure mappabile). Ovvero

Subtract[{100,102},96]
{100,102}-96

Abbiamo visto varie volte il concetto di listabile. Vuol dire che

f[x_]:=x^2

f[{1,2}]

2.2 Il metodo di Giulio Cesare

Dobbiamo ora definire la funzione S in modo tale che sia una bijezione. Per farlo:
■ usiamo una regola inventata (a -> b, b -> c, ... o  più astuta)
■ usiamo algoritmi matematici

L'algoritmo matematico più semplice è
■ scelgo  un intero m (maggiore del numero dei caratteri dell'alfabeto, 27 per noi). Il naturale m si chiama modulo
■ scelgo un intero a<m 
■ uso la bijezione di (Subscript[Z, m])-> (Subscript[Z, m]) che manda [x] -> [a][x]=[a x ]

2.2 Il metodo di Giulio Cesare

Ci siamo quindi ridotti ad usare l'aritmetica modulare.

Ovvero ci siamo ridotti ad usare la struttura di anello di (Subscript[Z, m]), il quale ha moltiplicazione e somma che sono 
■ commutative, 
■ associative, 
■ la moltiplicazione distribuisce sulla somma
■ esiste un elemento neutro per la somma [0]. Ovvero tale che  [0] + [a] = [0 + a] = [a]
■ esiste un elemento neutro per il prodotto [1]. Ovvero tale che [1][a]=[1 a]=[a])

2.2 Il metodo di Giulio Cesare

Ricordiamo l'ipotesi fondamentale per poter decrittare: la funzione S deve essere una bijezione

La funzione S[x]->[a][x] è invertibile se e solo se l'elemento [a] ha inverso moltiplicativo

In ℤ questo è possibile solo con n=1 o -1

2.2 Il metodo di Giulio Cesare

In (Subscript[Z, m]) ci sono molte più possibilità. Infatti

2 * 3 = 6 ≡ 1 (mod 5)
5 * 5 = 25 ≡ 1 (mod 8)

Ricordiamo quindi quando, dato un positivo a esiste un altro positivo b tale che [a][b]=[1]

Bisogna e basta che a b≡1 mod m

Con Mathematica ci dovremmo chiedere quando, dato a,  esiste b tale che  Mod[a b,m]=1

2.2 Il metodo di Giulio Cesare

Proposizione: un intero a ha inverso modulo m se e solo se m ed a sono coprimi

Dimostrazione: a,m sono coprimi implica che esistono numeri h e k tali che h a+k m=1

Questo implica che  h a≡1 Mod m

Quindi [h]=[b] è l' inversa di [a] modulo m

2.2 Il metodo di Giulio Cesare

Possiamo usare PowerMod per chiedere a Mathematica di calcolare non solo potenze dirette di un numero in (Subscript[ℤ, m]), ma anche potenze inverse.

L'inversa di a in (Subscript[ℤ, m]) si ottiene calcolando PowerMod[a,-1,m]

PowerMod[3,-1,4]

PowerMod[3,-1,6]

2.2 Il metodo di Giulio Cesare

Si ha quindi che b è strettamente legato ad a da una regola facile, quindi rendere noto {a,m} è equivalente a rendere noto {b,m}

La coppia {a,m} (e quindi {b,m}) si dicono chiave privata

La crittazione moderna si basa sul fatto che esistono bijezioni date da leggi per cui questo è falso

2.2 Il metodo di Giulio Cesare

Insomma, la nostra funzione di crittazione sarà quindi

f(n)=a n mod m

La funzione di decrittazione sarà invece

(f^(-1))(n)=b n mod m

Importante osservare che la bijezione andrà tra il nostro alfabeto ed i numeri {1,....,m-1}

2.2 Il metodo di Giulio Cesare

Non vogliamo usare lo zero perché queste trasformazioni mandano sempre zero in zero, e si darebbe l' appiglio di una lettera nota

Quindi il nostro alfabeto deve avere m-1 caratteri ... anche se volendo si introducono caratteri "dummies"

2.2 Il metodo di Giulio Cesare

Questi codici crittografici e semplici generalizzazioni del tipo

n ->a n+c mod m

dove anche c è parte della chiave privata sono facilmente decifrabili

Una volta nota la funzione per crittare, si ricava in un attimo la funzione per decrittare, con PowerMod[a, -1, m]

2.2 Il metodo di Giulio Cesare

Quindi la chiave per crittare e decrittare devono tenere ben nascoste a tutti con l' eccezione delle persone fidate con cui si vuole comunicare

Il sistema non è sicuro anche perché è un sistema per sostituzione, lo si può violare facendo fare al computer una analisi di frequenza.

Inoltre, ha un numero relativamente basso di possibili crittazioni

2.2 Il metodo di Giulio Cesare

Noi faremo qualcosa di simile all'analisi di frequenza: listeremo tutte le possibili  traduzioni e controlleremo al computer quali sono ragionevoli da prendere in considerazione ... abbastanza vocali, presenza di parole del vocabolario, ecc

Possiamo farlo perché ci sono relativamente poche traduzioni

Questi metodi sono molto antichi. Venivano usati già da Giulio Cesare che ne era perfino considerato l'inventore

2.2 Il metodo di Giulio Cesare

Esercizio 2.2.1: Scrivere funzioni
	F(x) = 5x  Mod 28
	Finv(x) = l'inversa di F
che eseguono la codifica/decodifica con chiave privata {5,28} per un singolo numero. Combinarle poi con le funzioni VersoCC e DaCC per ottenere due funzioni Critta[stringa] e Decritta[stringa] che crittano/decrittano una stringa testuale con l'alfabeto ristretto che abbiamo scelto.

2.2 Il metodo di Giulio Cesare

Implementiamo le funzioni f ed finv di codifica/decodifica di una lista

Sia le funzioni definite che la funzione Mod sono per definizione listabili. Dunque, si possono usare sia Mod che F ed Finv per codificare/decodificare liste invece che singole lettere

PowerMod[5,-1,28]

F[x_]:=Mod[5x,28]
Finv[x_]:=Mod[17 x, 28]

F[{2,3,4}]
%//Finv

2.2 Il metodo di Giulio Cesare

Partiamo da una stringa, trasformiamola in una lista con VersoCodiceCaratteri, crittiamola con f, ritrasformiamola in una stringa con DaCodiceCaratteri

F[a_,m_][x_]:=Mod[a x,m]
Finv[a_,m_][x_]:=Mod[PowerMod[a,-1,m] x, m]

Critta[a_,m_][stringa_]:=DaCC[F[a,m][VersoCC[stringa]]]

Decritta[a_,m_][stringa_]:=DaCC[Finv[a,m][VersoCC[stringa]]]

Critta[13,29]["buongiorno a tutti"]

Decritta[13,29][%]

2.2 Il metodo di Giulio Cesare

Esercizio 2.2.2: estendere le funzioni Critta e Decritta tenendo inespressi i parametri {a,m}  (la chiave privata). Definire quindi funzioni Critta[stringa,a.m] e Decritta[stringa,a,m] (oppure Critta[a,m][stringa] e Decritta[a,m][stringa]).

2.2 Il metodo di Giulio Cesare

Si dovranno definire delle funzioni F ed Finv che dipendono dai parametri m,a.

F[a_,m_][lista_]:=Mod[a lista,m]
Finv[a_,m_][lista_]:=Mod[PowerMod[a,-1,m] lista,m]

Anche F ed Finv così definite sono "listable" sul  loro primo argomento? Si, ovvero se si scrive una lista al posto di una variabile la funzione viene applicata elemento per elemento

F[5,28][{1,2,3,4,5,6}]

Finv[5,28][%]

2.2 Il metodo di Giulio Cesare

Bisogna ora comporre con VersoCC e DaCC

Critta[a_,m_][stringa_]:=DaCC[F[a,m][VersoCC[stringa]]]

Decritta[a_,m_][stringa_]:=DaCC[Finv[a,m][VersoCC[stringa]]]

Critta[5,28]["buongiorno a tutti"]

Decritta[5,28][%]

2.2 Il metodo di Giulio Cesare

Proviamo con una scelta diversa di numeri

Critta[9,28]["buongiorno a tutti"]

Decritta[9,28][%]

2.2 Il metodo di Giulio Cesare

E se sbagliamo a scegliare la chiave e non ne prendiamo una di coprima?

Critta[7,28]["buongiorno a tutti"]

Decritta[7,28][%]

2.2 Il metodo di Giulio Cesare

Il metodo di Giulio Cesare è un metodo per sostituzione, ovvero ogni lettera si trasforma sempre nello stesso numero. Questo è un grave difetto, infatti

Esercizio 2.2.3: avete intercettato il file "msg1.txt", e sapete che il messaggio è stato crittato usando un algoritmo di sostituzione x->a x Mod 31 di chiave privata {a,31}. La codifica numerica preliminare è  stata eseguita utilizzando la codifica a->1,..,z->26,< >->27,<'>->28,< ,>-> 29,< .>->30. Dopo la crittazione  il  messaggio è stato ritrasformato in una stringa testuale usando l'inversa della stessa codifica. Decrittatelo!

Suggerimento: importare il messaggio usando Import["msg1.txt"] stando attenti che la directory di lavoro sia quella in cui sia il file (usare i comandi Directory[] per sapere in che directory siete, SetDirectory["path"] per cambiare la directory, FileNames[] per sapere quali sono i files nella directory
NotebookDirectory[] per ottenere la directory in cui risiede il notebook.

2.2 Il metodo di Giulio Cesare

Esercizio 2.2.4: avete intercettato il file "msg2.dat" che consiste in una lista di numeri da 1 a 255. Il messaggio è stato crittato usando la codifica ASCII prima ed un algoritmo di sostituzione x ->a x mod 256 poi. Decrittarlo. 

La lista di frasi decrittate è lunga, automatizzate la ricerca delle frasi che "potrebbero" essere una decrittazione del messaggio scrivendo una funzione che seleziona le "traduzioni" con una percentuale alta di caratteri alfanumerici, oppure di vocali.

Suggerimento: importare il messaggio usando Import["msg2.dat"]. L'oggetto importato è un vettore del tipo {{(Subscript[a, 1])],{(Subscript[a, 2])},...{(Subscript[a, 2])}}, con (Subscript[a, i])∈{1,256}. Usate Flatten per eliminare una parentesi ed ottenere così {(Subscript[a, 1]),...,(Subscript[a, n])}. Usare poi Count e Select per selezionare le decrittazioni che hanno le caratteristiche di un messaggio intelleggibile.

2.3 Il metodo di Hill

Idea del metodo : Il metodo di "Giulio Cesare" visto nella lezione precedente usava la funzione di crittatura
		f :{0} U {1,...,m-1}->{0} U {1,...,m-1}, x ->a x mod m
ove m ed a<m  sono coprimi

Questo metodo permette di definire una permutazione tra le lettere (ovvero i numeri corrispondenti alle lettere), e permette di calcolare facilmente l' inversa da usare per la decrittazione

Tale metodo è un metodo di sostituzione : ogni lettera è sostituita con un'altra.

2.3 Il metodo di Hill

Il metodo di Hill è una generalizzazione del metodo di Giulio Cesare. Il metodo dice di

■ raggruppare le cifre del messaggio a gruppi di n . Si formano dunque  dei vettori interi

■ decomporre il messaggio numerico in vettori  di lunghezza n :
{(Subscript[x, 1]),...,(Subscript[x, N])}={{(Subscript[x, 1,])...,(Subscript[x, n])},{(Subscript[x, n+1,])...,(Subscript[x, 2n])}, ... }={ (Subscript[v, 1]), (Subscript[v, 2]),...}  
se serve, completare l' ultimo vettore con qualcosa di noto

■ trasformare questi vettori con una matrice intera invertibile Mod m

2.3 Il metodo di Hill

Il bello di questo metodo è che non usa sostituzioni. Cioè la lettera "a" non diventa sempre la lettera diciamo "z"

L' immagine della lettera a dipende dal vettore a cui appartiene

2.3 Il metodo di Hill

Una matrice A∈M(n×n,ℤ) definisce una mappa lineare di (ℤ^n)->(ℤ^n). Vogliamo che tale mappa sia invertibile

Definizione: una matrice intera A è invertibile mod m se esiste una matrice intera B tale che A B ≡ 𝟙 mod m

Con 𝟙 si intende la matrice identica n×n

La funzione di crittazione applicata al singolo vettore è 
	F[v]≡A.v  mod m

2.3 Il metodo di Hill

La funzione inversa è del tipo Finv[v]≡B.v mod m

La matrice A, e dunque B, assieme al loro modulo, ma non lo diciamo visto che  A,B∈M(n,(Subscript[ℤ, m])),  sono una chiave privata.

Anche in questo caso, data A, è facile trovare  B, basta invertire la matrice. Se siamo nei reali ℝ la cosa è ovvia

2.3 Il metodo di Hill

Ripassiamo un attimo la teoria delle matrici in un anello

Un anello K è un insieme con somma + e prodotto *, con elementi neutri per somma 0 e prodotto 1 e con inversi solo per la sommma - A, ma non necessariamente con inversi  per il prodotto

Fatto: sia K un anello. Una matrice A∈M(n,K)  è invertibile in  M(n,K)  se e solo se det A è invertibile in K

2.3 Il metodo di Hill

Dimostrazione: la dimostrazione è costruttiva.

Se A è invertibile il suo determinante è invertibile in K perché  1=det (A.B)=det A det B

Ma se il determinante di A è invertibile. Basta scrivere la matrice dei cofattori e dividere per il det A.

L' unica cosa problematica è la divisione per det A, ma la possiamo fare perché esso è invertibile in K.

2.3 Il metodo di Hill

Conseguenze: una matrice intera A è invertibile in ℤ, cioé ha inversa intera se e solo se det A = ±1

Segue quindi che una matrice intera A è invertibile nell'anello (Subscript[ℤ, m]), cioé ha inversa Mod m 
se e solo se  m e det A sono coprimi.

2.3 Il metodo di Hill

Suggerimento: l'inversa di una matrice A si calcola con Inverse. Con un'opzione si può calcolare l' inversa nell'anello (Subscript[ℤ, m]). Il comando è Inverse[A,Modulus->m]

(* Per brevita`,definiamo una funzione che fa l'inversa mod m *)
ModInv[A_,m_]:=Inverse[A,Modulus -> m]

2.3 Il metodo di Hill

A={{1,6},{2,9}}
Det[A]

GCD[3,28]

ModInv[A,28]

A.%

2.3 Il metodo di Hill

Per creare i vettori, bisogna usare il comando di Mathematica che partiziona una lista (la lista dei codici caratteri) in sottoliste. Esiste il comando Partition[lista,n]

tb=Range[10]

Partition[tb, 2]

Partition[tb, 3]

2.3 Il metodo di Hill

Per rimediare, bisogna aggiungere alla lista un pò di 27 (spazi bianchi) per portarla alla lunghezza giusta.

Bisogna naturalmente usare PadRight[ lista, N , symbol]

PadRight[{1,2},1,27]

2.3 Il metodo di Hill

L'unica domanda a cui rispondere è quanti elementi bisogna aggiungere ad una lista per arrivare ad un multiplo di n?

Se la lista ha K elementi dobbiamo portarlo al più piccolo multiplo di n che sia ≥ K

Ceiling[n]  è il più piccolo intero ≥n (Cosa farà mai Ceiling[a,b] ? E Floor)

Ceiling[10]

2.3 Il metodo di Hill

2.3 Il metodo di Hill

Quindi per crittare si: 
1. trasforma la stringa in lista di numeri
2. si spezza la lista in vettori
3. si applica ad ogni vettore la matrice A
4. si tolgono le parentesi
5. si torna (eventualmente) ad una stringa

Per togliere le parentesi, si usa il comando Flatten.

Tornando indietro con la procedura opposta ci si trova una stringa con alla fine molti spazi finali. Bisognerebbe rimuovere i 27 finali (con While, ci sono modi più intelligenti?). Ma in realtà n on dà molto fastidio lasciarli.

2.3 Il metodo di Hill

Esercizio 2.3.2: Scrivere le funzioni HillCritta[A,m][stringa], che parte da una stringa e restituisce una lista di numeri da 0 a 255 ottenuti crittando alla Hill un testo, e  HillDecritta[A,m][lista] che fa il contrario. Testare poi le funzioni per una stringa abbastanza lunga ed una matrice A  2x2 invertibile mod 256 scelta da voi. 

Usando un istogramma Histogram[dati,{xmin,xmax,dx}], confrontare la distribuzione dei codici caratteri per il messaggio non crittato e per quello crittato. Si può argomentare sulla base degli istogrammi che il metodo di crittazione non è un algoritmo di sostituzione?

Suggerimento: se il messaggio contiene lettere accentate latine come à, è, é, ì, ò, ù, forse sarà necessario specificare che si usa il characterencoding "ISOLatin1".

2.3 Il metodo di Hill

La crittazione  v->A v  mod m  è abbastanza sicura nel senso che, anche se si conosce la forma dell' algoritmo e la dimensione n del vettore v, per decrittare l'algoritmo bisogna determinare la chiave A

Il numero delle matrici mod m di dimensione n x n è (m^(((n^2)))), anche se non tutte sono invertibili mod m, ma ciascuna va testata almeno per l'invertibilità

2.3 Il metodo di Hill

Il numero è grande se n è un pò grande. Per esempio 
  (27^(2x2))≈5*(10^5)
(27^(3x3))≈8*(10^12)
  (27^(4x4))≈8*(10^22)
  (27^(5x5))≈6*(10^35)

Naturalmente, si può anche prendere m>27, anzi, in genere lo si fa perchè i simboli che si usano non sono solo le lettere minuscole

2.3 Il metodo di Hill

Nonostante la quantità di chiavi sia notevole, anche in questo caso un metodo alla 
"crivello di Eratostene" (proviamo con tutte le chiavi e facciamo scegliere al computer quali decrittazioni non vanno scartate) è ragionevole.

Soprattutto se n è piccolo, può essere facile decrittare il messaggio se si riesce a indovinare un pezzo del messaggio lungo (n^2) (per es, "ciao" alla fine del messaggio, se n = 2).

Anche in questo caso, si possono usare varianti del tipo

v ->A v+c mod m

con c un vettore di dimensione n, a entrate intere in (Subscript[ℤ, m])

2.3 Il metodo di Hill

Esercizio 2.3.3: Avete intercettato il file "msg3.txt" e sapete che il messaggio è stato crittato usando un algoritmo di Hill di chiave una matrice A∈ M(2,(Subscript[ℤ, 33])) che in particolare ha determinante 1. 

La codifica numerica preliminare è  stata eseguita utilizzando la codifica 
<accentograve>->0, a->1, ..., z->26,<spazio>-> 27, <duepunti>-> 28, P-> 29, <accentoacuto>->30, <duepunti>->31, <punto>->32

Dopo la crittazione  il  messaggio è stato ritrasformato in una stringa testuale usando l'inversa della stessa codifica. Decrittare la stringa scrivendo una funzione che automatizza i tentativi di violazione del codice.

Suggerimento: La chiave privata usata è una matrice di determinante 1 (con inversa di det 1). Assumete come possibili chiavi solo matrici di det 1 (sono "solo" 31680 contro le 633600 matrici invertibili).

2.3 Il metodo di Hill

Funzioni utili per l'esercizio: definiamo il grosso dei valori, per tutte le lettere minuscole

Verso[n_]:=ToCharacterCode[n,"ASCII"]-96;
Da[n_]:=FromCharacterCode[n+96,"ASCII"];

aggiustiamo l'altro pò di caratteri che appartengono al nostro alfabeto

VersoCC[str_]:=
Verso[str]/.{ -64 -> 27,-52->28,-16->29,-57->30,-38->31,-50->32};
DaCC[lst_]:=
Da[lst/.{ 27->-64 ,28->-52,29->-16,30->-57,31->-38,32->-50}];

2.4 Il metodo RSA

Siamo al metodo più sicuro per la crittazione. Inventato da Rivest–Shamir–Adleman nel 1977

Richiamiamo la funzione φ di Eulero ed il teorema di Euler–Fermat

La funzione di Euler φ è la funzione che dato n numero naturale vale

φ(n)=numero degli interi positivi≤n coprimi con n

In Mathematica, la funzione si chiama EulerPhi

2.4 Il metodo RSA

Naturalmente, se n=p è primo, allora φ(p)=p-1. Se invece n non è primo la funzione ha un risultato meno prevedibile

EulerPhi[5]

EulerPhi[6]

Solo 1 e 5 sono coprimi con 6

2.4 Il metodo RSA

Ricordiamo che PrimePi[n] è invece il numero dei primi minori od uguali ad n

Mentre EulerPi[n] è il numero di tutti i naturali minori od uguali ad n e coprimi con n

Plot[{PrimePi[x],EulerPhi[Floor[x]],x-1},{x,0,30},
PlotStyle->{Red,Green,Black}]

Plot[{PrimePi[x],EulerPhi[Floor[x]],x-1},{x,0,100},
PlotStyle->{Red,Green,Black}]

2.4 Il metodo RSA

Siano (Subscript[a, 1]),...,(Subscript[a, φ(m)]) un insieme di numeri tali che i loro residui modulo m formino una lista completa di residui modulo m coprimi con m (lista m-completa per dirla brevemente)

Facciamo delle prove:

Coprimi[n_]:=Select[Range[n],(GCD[#,n]==1)&]

2.4 Il metodo RSA

Allora per ogni k tale che GCD[k, m]=1 la lista

k (Subscript[a, 1]),...,k (Subscript[a, φ(m)])

forma un insieme dello stesso tipo

Controlliamo se è vero su esempi

Coprimi[8]
Coprimi[8] 7
Mod[%,8]

2.4 Il metodo RSA

Proposizione: se m ed n sono coprimi ed (Subscript[a, 1]),...,(Subscript[a, φ(m)])  è una lista m-completa di residui modulo m coprimi con m mentre (Subscript[b, 1]),...,(Subscript[b, φ(n)]) è una lista n-completa di residui modulo n coprimi con n. Allora l'insieme (Subscript[a, i]) n + (Subscript[b, j]) m, con i=1,φ(n), j=1,φ(m) è una lista m*n–completa di residui modulo m*n coprimi con m*n

Dimostrazione: dobbiamo mostrare che:

a. in questa lista i gli elementi sono coprimi con n*m
b. la lista contiene tutti rappresentanti distinti in (Subscript[ℤ, n*m])
c. ogni coprimo minore di n*m stà in questa lista

2.4 Il metodo RSA

a. (coprimi)se (Subscript[a, i])m +(Subscript[b, j])n non è coprimo con m*n allora (Subscript[a, i]) non è coprimo con n è (Subscript[b, j]) non è coprimo con m

b. (distinti) se (Subscript[a, i])n + (Subscript[b, j]) m ≡ ((Subscript[a, h]) n + (Subscript[b, k])m) mod m n

allora (Subscript[a, i]) n ≡ (Subscript[a, h]) n mod m  e (Subscript[b, j])m ≡ (Subscript[b, k])m mod n

quindi, visto che GCD[m, n]=1, posso dividere per n (risp m) le due equazioni ed ottenere che (Subscript[a, i])≡ (Subscript[a, h])mod m e (Subscript[b, j])≡ (Subscript[b, k])mod n

2.4 Il metodo RSA

c. (completa)  ogni numero minore od uguale ad m n si scrive come  a m+b n visto che m ed n sono coprimi.

Se GCD[a m + b n, m n] = 1 allora

GCD[a m + b n, n] = GCD[a m + b n, m] = 1 e quindi

2.4 Il metodo RSA

GCD[a m, n] = 1  e GCD[b n, m] = 1.

Perciò GCD[a, n] = 1  e GCD[b, m] = 1,

quindi a n + b m sta nella lista (Subscript[a, i]) n + (Subscript[b, j]) m

2.4 Il metodo RSA

Un ovvio corollario alla proposizione appena dimostrata è il teorema di moltiplicatività della funzione di Euler

Teorema (moltiplicatività della φ di Euler): Se  m e  n sono coprimi allora φ (m n) = φ (m) φ (n)

Vale inoltre un famoso teorema di Euler–Fermat che estende il piccolo teorema di Fermat già visto

2.4 Il metodo RSA

Teorema (piccolo teorema di Fermat): dato p primo, per ogni intero a vale 
	(a^(φ(p)+1))=(a^p)≡ a mod m

La sua estensione è quella che ci preme, e recita

Teorema (di Euler–Fermat): dati m ed a coprimi, allora
	(a^(φ(m)+1))≡ a mod m

2.4 Il metodo RSA

Dimostrazione: sappiamo che GCD[a,m]=1.

Vale quindi il seguente fatto:

Prendiamo {(Subscript[a, 1]), ..., (Subscript[a, φ(m)])} la lista completa di elementi (Subscript[a, i ])minori di m e coprimi con m

Ovvero prendiamo una lista m-completa {(Subscript[a, 1]), ..., (Subscript[a, φ(m)])}

2.4 Il metodo RSA

allora la lista  {a (Subscript[a, 1]), ..., a (Subscript[a, φ(m)])} è ancora una lista m-completa

Segue che l'elemento Π (Subscript[a, i])≡Π (a (Subscript[a, i])) mod m

D' altro canto, tale prodotto conta φ(m) addendi, quindi Π (Subscript[a, i])≡ (a^(φ(m) ))Π (Subscript[a, i]) mod m

2.4 Il metodo RSA

Ma... il prodotto Π (Subscript[a, i]) è invertibile in (Subscript[Z, m]), e quindi

(a^(φ(m)))≡ 1 mod m

Quando GCD[a, m]≠1 allora il teorema non vale

Esercizio 2.4.1: Mostrare per esempi che il teorema di Euler-Fermat è falso se a non è coprimo con m. Si scelga m=(p^2) con p primo.

2.4 Il metodo RSA

Si ha quindi che il teorema di Euler–Fermat vale per ogni x∈ℤ quando p è primo (ovvero per ogni x∈ℤ vale (x^(φ(m)+1))≡ x mod p (vale per gli x coprimi con p, ma vale trivialmente per gli x divisibili per p).

Vale infatti per gli x coprimi con p, ma vale anche trivialmente per gli x divisibili per p.

Continua a valere per ogni x∈ℤ solo quando m è prodotto di primi con molteplicità 1. Non lo dimostriamo, ma mostriamo il primo passo, che è quello che ci interessa.

2.4 Il metodo RSA

Corollario (quasi immediato): se p e q sono primi distinti, allora per ogni x∈ℤ, non importa se coprimo con p q, vale

(x^(φ(p*q)+1))=(x^(φ(p)+φ(q)+1))=(x^((p-1)(q-1) + 1))≡ x mod p q

Dimostrazione: poniamo m=p q. Allora

φ (m) = φ (p q) = φ (p) φ (q) = ... perchè p e q – essendo primi distinti – sono coprimi

2.4 Il metodo RSA

...(p-1)(q-1), perché  φ(p)=p-1  visto che p è primo idem per q

Per il teorema di Euler–Fermat, (x^((p-1)(q-1) + 1))≡ x mod p q  per ogni x  coprimo con p q.

Se x non è coprimo con p q  o è multiplo di p q, e quindi in (Subscript[ℤ, p q]) l'equazione 0≡ 0 mod p q è verificata

oppure x=y (p^i) con y coprimo con p e q ed i naturale (oppure la possibilità simmetrica x = y (q^i)).

Segue che

(x^((p-1)(q-1)+1))= (y^((p-1)(q-1)+1))(p^(i(p-1)(q-1)+i))≡ y (p^i) (p^(i (p-1)(q-1))) mod p q

2.4 Il metodo RSA

Ma visto che p è diverso da q (e quindi coprimo con q) allora (p^(i (p-1)(q-1)))≡1 mod q, Ovvero

(p^(i (p-1)(q-1)))= 1 + λ q

Allora (p^i) (p^(i (p-1)(q-1)))= (p^i) + λ (p^i) q, Ovvero  (p^i) (p^(i (p-1)(q-1)))≡ (p^i) mod p q

Si conclude che y (p^i) (p^(i(p-1)(q-1)))≡ y (p^i) mod p q≡ x mod p q

Abbiamo mostrato che se x è un qualsiasi numero ed m = p q   con p e q primi allora

(x^((p-1)(q-1)+1))≡ ((x )^(φ(m)+1)) ≡ x mod p q

2.4 Il metodo RSA

Cosa ne facciamo di questa informazione? Dati due numeri primi distinti  p e q

Scegliamo, in modo casuale, un intero a coprimo con (p-1) (q-1) e tale che 1 <a<(p -1)(q-1) (molto spesso viene usato un numero a piccolo)

Visto che a è coprimo con (p-1) (q-1), allora ammette un inverso modulo (p-1) (q-1). Sia b  l'inverso modulo (p-1) (q-1) di a.

2.4 Il metodo RSA

Ora: il fatto che a e b siano inversi in (Subscript[ℤ, (p-1)(q-1)]) implica che

a b=k (p-1) (q-1)+1

per qualche intero k intero

Segue che, per ogni intero x vale

((((x^a)))^b)=(x^(a b))= (x^(k (p-1)(q-1)+1))=(x^(1-k))(x^(k[(p-1)(q-1)+1]))=(((x^(1-k))((x^((p-1)(q-1)+1))))^k)=...

(per il corollario quasi immediato)  …=(((x^(1-k))(x+h p q ))^k)=…

…=(x^(1-k))((x^k)+ h' p q)= x + h'' p q.

2.4 Il metodo RSA

Dunque ((((x^a)))^b)≡ x mod p q

Corollario (fondamentale): se p e q sono primi distinti, a è coprimo con (p-1) (q-1) e b è l'inversa di a in (Subscript[ℤ, (p-1) (q-1)]), allora  nell'anello (Subscript[ℤ, p q]) elevare alla a ed elevare alla b sono funzioni inverse una dell'altra.

Ribadiamo in formula. Le operazioni

F[x]=(x^a)mod p q	Finv[x]=(x^b)mod p q

sono funzioni di (Subscript[ℤ, p q]) in sè inverse l'una dell'altra.

2.4 Il metodo RSA

Possiamo ora definire l' algoritmo di crittazione  RSA. Siano dati due primi p e q, ed una chiave privata a tale che a sia coprimo con (p-1) (q-1)

Crittare significa prendere un messaggio, scrivere i codici ASCII, applicare alla lista di numeri ottenuti F. Non si può tornare indietro ad una lista di lettere e simboli perchè la lista dei numeri è modulo m>>numero codici ASCII

Decrittare significa prendere la lista dei numeri crittati, applicare Finv e tornare ad una lista di simboli che dovrebbe essere il messaggio.

2.4 Il metodo RSA

Il bello è che per crittare bisogna conoscere a ed m, per decrittare bisogna conoscere b ed m

Ma... calcolare b è facile se si conoscono p e q, impossibile se si conosce solo m

Infatti se conosco p e q basta calcolare l' inversa di a modulo (p-1) (q-1).

Se invece conosco solo a ed m,  dovrei fattorizzare m

2.4 Il metodo RSA

Quindi si può spiegare ad un totale estraneo come crittare, dandogli m ed a

Basta stare attenti a non spiegare come decrittare, ovvero stando attenti a tenere ben segreto il numero b, ed ovviamente anche i primi p, q (che comunque, tipicamente, non conosce neanche il detentore della chiave)

Questo sistema di crittazione ha quindi due chiavi, una chiave pubblica {a,m} ed una chiave privata {b,m}

Ovviamente, la chiave pubblica si da a chiunque la voglia conoscere, la chiave privata si tiene ben nascosta

2.4 Il metodo RSA

Come si usano le chiavi pubbliche e private?

Supponiamo Alice voglia spedire a Bob un messaggio. Ricordiamo che Bob ha reso pubblica la sua chiave {a,m=p q} ed ha tentuo ben segreta la chiave privata {b,m} (in effetti, solo b è segreta)

Alice scrive il messaggio per Bob, lo critta con la funzione F[a,m] usando la chiave pubblica {a,m} di Bob. Poi, spedisce il messaggio.

N.B. dopo aver usato F neanche Alice sa decrittare il messaggio, perchè non conosce b

2.4 Il metodo RSA

Esercizio 2.4.2: scegliamo due primi a caso tra i primi (10^8) primi, e scegliamo un a con meno di 11 cifre e coprimo con (p-1)(q-1). Sapendo a, p e q riuscite a trovare b? (usare PowerMod)

2.4 Il metodo RSA

Esercizio 2.4.3: scrivere una funzione che crea in modo random le chiavi pubbliche {a,m} e privata {b,m} per una crittazione RSA. Riuscite a creare delle chiavi con Mathematica che siano Mathematica-sicure? Ovvero si riesce a creare una coppia di primi p,q tali che m=p q non sia fattorizzabile per Mathematica?

Suggerimento: è sensato produrre chiavi partendo da primi che siano il più grande possibile. La funzione Prime[n] riesce a produrre primi con n fino a (10^9). Prendete quindi un primo a caso tra (10^8) e (10^9). Poi prendetene un'altro che sia diverso da p e poi scegliete a che sia coprimo con (p-1)(q-1) (usare due comandi While). Chiedere quindi al computer di rendere {a,m=p q} e {b,m}

Esercizio 2.4.4: supponendo data la chiave pubblica {a,m} (o privata {b,m}), definire le funzioni RSACritta ed RSADecritta che crittano/decrittano usando l'algoritmo RSA

Suggerimento: elevare a potenza usando PowerMod

2.4 Il metodo RSA

Se qualcuno riuscisse a fattorizzare m=p q sarebbe a cavallo, infatti gli basterebbe cercare l'inverso di a modulo (p-1) (q-1). Già fatto varie volte.

Per fortuna non c'è modo (al momento), dato m e sapendo che è prodotto di primi, di fattorizzare m e calcolare p e q (se m è abbastanza grande)

Se qualcuno inventasse un algoritmo veloce per fattorizzare i naturali, o per fattorizzare almeno il prodotto di due primi, il sistema di crittazione in uso diverrebbe inutilizzabile

2.4 Il metodo RSA

Si può usare il sistema anche per certificare la propria identità

Sia Alice che Bob hanno le loro chiavi pubbliche e private
■ Alice ha la chiave pubblica {(Subscript[a, A]) ,(Subscript[m, A])=(Subscript[p, A])(Subscript[q, A])} e la chiave privata {(Subscript[b, A]) ,(Subscript[m, A])=(Subscript[p, A])(Subscript[q, A])}
■ Bob ha la chiave pubblica {(Subscript[a, B]) ,(Subscript[m, B])=(Subscript[p, B])(Subscript[q, B])} e la chiave privata  {(Subscript[b, B]) ,(Subscript[m, B])=(Subscript[p, B])(Subscript[q, B])}

Alice prende il messaggio che ha scritto e lo critta con la sua chiave privata ovvero mappa 
	x->(x^(Subscript[b, A]))mod (Subscript[m, A])

2.4 Il metodo RSA

Ovviamente, Alice non può spedire il messaggio così crittato, dal momento che per decrittarlo basta usare la mappa
	x->(x^(Subscript[a, A]))mod (Subscript[m, A])
ed {(Subscript[a, A]),(Subscript[m, A])} sono pubblici

Ma Alice può ora crittare il messaggio con la chiave pubblica di Bob, ovvero agire sulla lista dei numeri ottenuta con la mappa
	x->(x^(Subscript[a, B]))mod (Subscript[m, B])

Ora può spedire tranquilla! Solo Bob conosce l' inversa a questa seconda  crittatura, che è la mappa
	x->(x^(Subscript[b, B]))mod (Subscript[m, B])

2.4 Il metodo RSA

Bob decritta il messaggio con la sua chiave privata
	x->(x^(Subscript[b, B]))mod (Subscript[m, B])...

Ed ottiene qualcosa che può provare a decrittare con la chiave pubblica di Alice
	x->(x^(Subscript[a, A]))mod (Subscript[m, A])

2.4 Il metodo RSA

Se ciò che ottiene è intelleggibile allora il messaggio  viene necessariamente da Alice, perchè solo lei conosce la mappa x->(x^(Subscript[b, A]))mod (Subscript[m, B]) che ha crittato il messaggio

Se il risultato non ha significato, allora qualcuno ha finto di essere Alice

2.4 Il metodo RSA

C'è un solo problema in questa idea, ed è dovuto al fatto che (Subscript[m, A]) potrebbe essere più grande di (Subscript[m, B])

In quel caso, infatti, la prima crittazione fatta da Alice crea una lista di numeri tipicamente più grandi di (Subscript[m, B])

La successiva crittazione con la chiave pubblica di Bob quozienta in (Subscript[Z, (Subscript[m, B])]) ed inficia l'unicità

La cosa si risolve rovesciando l'ordine delle operazioni

2.4 Il metodo RSA

A pensarci bene, così come è descritto il sistema RSA è una bufala

La crittazione è una mappa bijettiva di (Subscript[ℤ, m])-> (Subscript[ℤ, m]) data da [x]-> (([x])^a) ed inversa [x]->(([x])^b)

Quindi, preso un messaggio, ogni lettera corrisponde ad un numero e viene mappata sempre nello stesso numero di (Subscript[ℤ, m]). Quindi il sistema è per sostituzione.

Bisogna usare una qualche idea alla Hill.

2.4 Il metodo RSA

Bisogna usare il fatto di avere un mucchio si "spazio" in (Subscript[ℤ, m]), perchè m= p q >>0.

Supponiamo (ragionevolmente) di avere 255 caratteri a disposizione, ognuno codificato da un numero tra 0 e 255

Dato m, vogliamo raggruppare i codici ASCII del nostro messaggio in gruppi che rappresentano un numero in base 256

Ovviamente tale numero andrà tradotto in base decimale, e non dovrà essere più grande di m

Questo lo si calcola facilmente, basta ottenere la parte intera di ((Log[m])/(Log[256])) = Log[256,m]

2.4 Il metodo RSA

Esercizio 2.4.5i: definire due funzioni compatta[m,base][lista] che data una lista di numeri {(Subscript[a, 1]),(Subscript[a, 2]),...} scrivono la lista di numeri {(Subscript[b, 1]),(Subscript[b, 2]),...} in cui ciascun (Subscript[b, i]) è la scrittura in base 10 del numero che, in base 256, ha per cifre {(Subscript[a, (i -1)n +1]),(Subscript[a, 2]),...,(Subscript[a, i n])} con n la parte intera di Log[256,m] (rocordate il Padding qualora la lista degli (Subscript[a, i]) non fosse lunga un multiplo di n). Definire anche la funzione inversa e scompatta[m,base][lista] che rimanda la lista dei {(Subscript[b, 1]),...} negli {(Subscript[a, 1]),...}

Suggerimento: per il cambiamento di base potete usare il comando IntegerDigits

Esercizio 2.4.5ii: cambiare le funzioni RSACritta[a,m][messaggio] ed RSADecritta[b,m][lista] così da rendere realmente sicuro il sistema di crittazione. Provatelo con una m abbastanza grande e con un messaggio a vostro piacere abbastanza lungo. RSACritta è una funzioni a valori in una lista di numeri minori di m, RSADecritta è a volori nei messaggi.

2.4 Il metodo RSA

Problema pratico : chi assicura la corrispondenza tra la chiave privata e la persona fisica? Una Certification Authority

Questa autorità assegna a chi ne faccia domanda una chiave  pubblica, {a, m} ed una chiave privata {b,m}

2.4 Il metodo RSA

Rende poi pubbliche tutte le chiavi pubbliche degli enti a cui ha assegnato le chiavi

Chiunque può rivolgersi alla Authority e chiedere la chiave pubblica che l'Authority stessa ha assegnato ad Alice.

Insomma, non si chiede ad Alice la sua chiave, ma a chi ha l' autorità di assegnare chiavi e certifica che la data chiave {a, m} sia la chiave pubblica di Alice

2.4 Il metodo RSA

Il sistema di crittazione è sicuro? La risposta è si, se è difficile calcolare b data la chiave  pubblica {a,m}.

I numeri a,b,m sono legati dalle relazioni

m= p q 
a b≡1 mod (p-1) (q-1)

La sicurezza del metodo si basa (solo) sul fatto che è difficilissimo trovare i fattori primi p e q di un  numero m=p q molto grande, soprattutto se i due fattori primi sono molto grandi.

2.4 Il metodo RSA

Se p e q hanno qualche centinaio di cifre decimali, ed  m=p q  non è di qualche tipo speciale, un computer attuale ci metterebbe tempi lunghissimi (milioni di anni). Oggigiorno, nelle applicazioni importanti, si prendono p e q con circa 300 cifre.

Però, non è dimostrato che non si possano trovare algoritmi più veloci per fattorizzare i primi. Anzi, la ricerca per algoritmi di fattorizzazione è molto attiva

NB : Mathematica riesce a fattorizzare numeri fino a circa 40 cifre con il Package NumberTheory`FactorIntegerECM`

2.4 Il metodo RSA

Esercizio 2.4.6: avete intercettato il messaggio msg4.dat, destinato a Bob. La chiave pubblica di Bob è

m=154813148711273787009582211248127279
a=81635474617503514386564271476950293

Siccome la vostra macchina è in grado di fattorizzare m, dovreste riuscire a decrittare il messaggio. È realmente un messaggio segreto?