Matematica e Crittografia
Palmieri Lucia
Sirica Alessia
12 Dicembre 2019
La Crittografia
- Scrittura convenzionale segreta, decifrabile solo da chi sia a conoscenza del codice.
Didattica
- Gioco enigmistico consistente nell'analizzare le relazioni tra le lettere e le parole date, così da trarne considerazioni e suggerimenti che portano alla formazione di parole o frasi compiute di lunghezza data.
Dall'antichità al II secolo d.C.
Antichità
Atbash
Testi Sacri
(Vecchio Testamento)
250 a.C.
Codici
Frase da cifrare: IL SOLE BRILLA
Frase cifrata: RO HLOV YIROOZ
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
Frase da cifrare: IL SOLE BRILLA
Frase cifrata: VX EAXR ODVXXN
Le prime nove lettere dell'alfabeto vengono sostituite in modo tale che la somma della lettera da sostituire e la lettera sostituente risulti uguale a 10.
Atbah
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
C=3 viene sostituita con G=7
C + G = 3 + 7 = 10
Cifrario di Cesare,
II secolo d.C.
Cesare
Frase da cifrare: AVE CAESAR
Frase cifrata: DYH FDHVDU
Matematica del cifrario di Cesare
Cifrario di Cesare
0 1 2 . . . . . . . . . . . . . . 25
C(x)=x+3 (mod26) dove
- x è il valore senza codifica
- C(x) è il valore codificato
- 26 è lunghezza dell'alfabeto
Codifica
C(0)=0+3=3 congruo 3(mod26)
C(25)=25+3 =28 congruo 2(mod26)
C(8)=8+3 =11 congruo 11(mod26)
C(14)=14+3 =17 congruo 17(mod26)
Cinv(x)=x-3 (mod26)
Cinv(3)=3-3 congruo 0(mod26)
Cinv(2)=2-3=-1+26congruo25(mod26)
Cinv(11)=11-3 congruo 8(mod26)
Cinv(17)=17-3 congruo 14(mod26)
1° Guerra Mondiale
1914-1918
1GM
Rivest, Shamir, Adleman
RSA
Chiavi
pubbliche
e
chiavi
private
Definizione di numero primo
Si definisce numero primo un numero naturale che ha solo due divisori distinti: 1 e se stesso.
Fattorizzazione di numero primo
Fattorizzare un numero naturale significa riscriverlo come prodotto di numeri primi.
Esempio: 48510 = 2*3*3*5*7*7*11
Algoritmo RSA
- L'insieme di numeri minori di n che sono anche primi con n si chiama funzione di Eulero e si esprime come F(n).
- Se n=pq essendo p e q due numeri primi, allora F(n)=(p-1)(q-1).
- Grazie al "piccolo teorema di Fermat", si sa che se a è un numero intero maggiore di 0 e p un numero primo, allora a^(p-1) è congruo 1(mod p).
- Per il teorema di Eulero, se MCD(n,a)=1 allora a^F(n) è congruo 1(mod 1)
Perchè fidarsi?
- Non esiste un algoritmo per calcolare i numeri primi
- Non conosciamo la disposizione dei numeri primi
Privacy
- Il test di primalità per un numero n è piuttosto veloce
- La fattorizzazione di un numero n è molto lenta
Carta di credito
Carta di Credito
1*2=2
3*2=6
5*2=10
7*2=14
9*2=18
1*2=2
3*2=6
5*2=10
- 2+6+1+5+9+2+6+1=32
- 2+4+6+8+0+2+4+2=28
- 32+28=60
- AB forma il codice del paese di origine del prodotto
- CDEFG identifica l'impresa produttrice
- HIJKL indica il codice del prodotto che è stato assegnato all'impresa
- M corrisponde alla cifra di controllo
Un futuro quantistico
9 Dic 2019
Futuro
Grazie per l'attenzione
Conclusioni