Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia...

52
Introduzione alla Crittografia Progetto Lauree Scientifiche Liceo Scientifico “N. Tron”, 23 gennaio 2007 Progetto Lauree Scientifiche Introduzione alla Crittografia

Transcript of Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia...

Page 1: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Introduzione alla Crittografia

Progetto Lauree Scientifiche

Liceo Scientifico “N. Tron”, 23 gennaio 2007

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 2: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Introduzione

Problema: A deve fare arrivare a B un certo messaggio, senza cheC venga a conoscenza del contenuto.

Soluzione: A codifica il messaggio in base a regole concordate traA e B e spedisce il messaggio a B. B, conoscendo le regole dicifratura , e in grado di decodificare il messaggio e risalireall’originale. Se C viene in possesso del messaggio cifrato ma nonconosce le regole di cifratura, non e in grado di risalire almessaggio originale.

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 3: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Introduzione

Problema: A deve fare arrivare a B un certo messaggio, senza cheC venga a conoscenza del contenuto.

Soluzione: A codifica il messaggio in base a regole concordate traA e B e spedisce il messaggio a B.

B, conoscendo le regole dicifratura , e in grado di decodificare il messaggio e risalireall’originale. Se C viene in possesso del messaggio cifrato ma nonconosce le regole di cifratura, non e in grado di risalire almessaggio originale.

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 4: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Introduzione

Problema: A deve fare arrivare a B un certo messaggio, senza cheC venga a conoscenza del contenuto.

Soluzione: A codifica il messaggio in base a regole concordate traA e B e spedisce il messaggio a B. B, conoscendo le regole dicifratura , e in grado di decodificare il messaggio e risalireall’originale.

Se C viene in possesso del messaggio cifrato ma nonconosce le regole di cifratura, non e in grado di risalire almessaggio originale.

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 5: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Introduzione

Problema: A deve fare arrivare a B un certo messaggio, senza cheC venga a conoscenza del contenuto.

Soluzione: A codifica il messaggio in base a regole concordate traA e B e spedisce il messaggio a B. B, conoscendo le regole dicifratura , e in grado di decodificare il messaggio e risalireall’originale. Se C viene in possesso del messaggio cifrato ma nonconosce le regole di cifratura, non e in grado di risalire almessaggio originale.

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 6: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Terminologia

P = {messaggi in forma originale}

C = {messaggi in forma codificata}

Sia f una funzione invertibile da P a C

P f−→ C f −1

−−→ P

La quaterna (P, C, f , f −1) e detta crittosistema, la funzione fchiave di cifratura e la funzione f −1 chiave di decifrazione.

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 7: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Terminologia

P = {messaggi in forma originale}

C = {messaggi in forma codificata}

Sia f una funzione invertibile da P a C

P f−→ C f −1

−−→ P

La quaterna (P, C, f , f −1) e detta crittosistema, la funzione fchiave di cifratura e la funzione f −1 chiave di decifrazione.

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 8: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Terminologia

P = {messaggi in forma originale}

C = {messaggi in forma codificata}

Sia f una funzione invertibile da P a C

P f−→ C f −1

−−→ P

La quaterna (P, C, f , f −1) e detta crittosistema, la funzione fchiave di cifratura e la funzione f −1 chiave di decifrazione.

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 9: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Esempi

Metodo di Cesare

: Consideriamo l’alfabeto con 21 lettere. Sian ≤ 21 un intero fissato; data una lettera x , sia

f (x) =

{x + n se x + n ≤ 21

x + n − 21 se x + n > 21

Chiavi possibili: 21.

Esempio: n = 7A B C D E F G H I L M N O P Q R S T U V ZH I L M N O P Q R S T U V Z A B C D E F G

GIULIO CESARE → PRESRV LNCHBN

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 10: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Esempi

Metodo di Cesare: Consideriamo l’alfabeto con 21 lettere. Sian ≤ 21 un intero fissato; data una lettera x , sia

f (x) =

{x + n se x + n ≤ 21

x + n − 21 se x + n > 21

Chiavi possibili: 21.

Esempio: n = 7A B C D E F G H I L M N O P Q R S T U V ZH I L M N O P Q R S T U V Z A B C D E F G

GIULIO CESARE → PRESRV LNCHBN

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 11: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Esempi

Metodo di Cesare: Consideriamo l’alfabeto con 21 lettere. Sian ≤ 21 un intero fissato; data una lettera x , sia

f (x) =

{x + n se x + n ≤ 21

x + n − 21 se x + n > 21

Chiavi possibili: 21.

Esempio: n = 7A B C D E F G H I L M N O P Q R S T U V ZH I L M N O P Q R S T U V Z A B C D E F G

GIULIO CESARE → PRESRV LNCHBN

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 12: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Esempi

Metodo di Cesare: Consideriamo l’alfabeto con 21 lettere. Sian ≤ 21 un intero fissato; data una lettera x , sia

f (x) =

{x + n se x + n ≤ 21

x + n − 21 se x + n > 21

Chiavi possibili: 21.

Esempio: n = 7A B C D E F G H I L M N O P Q R S T U V ZH I L M N O P Q R S T U V Z A B C D E F G

GIULIO CESARE → PRESRV LNCHBN

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 13: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Esempi

Metodo di Cesare: Consideriamo l’alfabeto con 21 lettere. Sian ≤ 21 un intero fissato; data una lettera x , sia

f (x) =

{x + n se x + n ≤ 21

x + n − 21 se x + n > 21

Chiavi possibili: 21.

Esempio: n = 7A B C D E F G H I L M N O P Q R S T U V ZH I L M N O P Q R S T U V Z A B C D E F G

GIULIO CESARE → PRESRV LNCHBN

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 14: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Esempi

Cifratura Monoalfabetica: Consideriamo un qualsiasi riordinamentodell’alfabeto fissato, e si sostituisca ogni lettera con la letteracorrispondente.

Chiavi possibili: 21!

Esempio:A B C D E F G H I L M N O P Q R S T U V ZQ E R T U I O P A S D F G H L Z C V B N M

CIAO → RAQG

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 15: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Esempi

Cifratura Monoalfabetica

: Consideriamo un qualsiasi riordinamentodell’alfabeto fissato, e si sostituisca ogni lettera con la letteracorrispondente.

Chiavi possibili: 21!

Esempio:A B C D E F G H I L M N O P Q R S T U V ZQ E R T U I O P A S D F G H L Z C V B N M

CIAO → RAQG

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 16: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Esempi

Cifratura Monoalfabetica: Consideriamo un qualsiasi riordinamentodell’alfabeto fissato, e si sostituisca ogni lettera con la letteracorrispondente.

Chiavi possibili: 21!

Esempio:A B C D E F G H I L M N O P Q R S T U V ZQ E R T U I O P A S D F G H L Z C V B N M

CIAO → RAQG

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 17: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Esempi

Cifratura Monoalfabetica: Consideriamo un qualsiasi riordinamentodell’alfabeto fissato, e si sostituisca ogni lettera con la letteracorrispondente.

Chiavi possibili: 21!

Esempio:A B C D E F G H I L M N O P Q R S T U V ZQ E R T U I O P A S D F G H L Z C V B N M

CIAO → RAQG

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 18: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Esempi

Cifratura Monoalfabetica: Consideriamo un qualsiasi riordinamentodell’alfabeto fissato, e si sostituisca ogni lettera con la letteracorrispondente.

Chiavi possibili: 21!

Esempio:A B C D E F G H I L M N O P Q R S T U V ZQ E R T U I O P A S D F G H L Z C V B N M

CIAO → RAQG

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 19: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Esempi

Cifratura Monoalfabetica: Consideriamo un qualsiasi riordinamentodell’alfabeto fissato, e si sostituisca ogni lettera con la letteracorrispondente.

Chiavi possibili: 21!

Esempio:A B C D E F G H I L M N O P Q R S T U V ZQ E R T U I O P A S D F G H L Z C V B N M

CIAO → RAQG

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 20: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Esempi

Metodo di Vigenere

: Fissiamo una qualsiasi parola come chiave dicifratura, ad esempio SOLE.

Questa parola individua 4 funzioni del tipo ”Cesare”: f1 = x + 17,f2 = x + 13, f3 = x + 10, f4 = x + 5.

Per cifrare un messaggio con questa chiave, la prima lettera si cifracon f1, la seconda con f2, la terza con f3, la quarta con f4, laquinta con f1, la sesta con f2, . . .

Esempio: QUESTO METODO NON E SICURO −→ MMQAPEZB ....

Possibili chiavi: infinite.

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 21: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Esempi

Metodo di Vigenere: Fissiamo una qualsiasi parola come chiave dicifratura, ad esempio SOLE.

Questa parola individua 4 funzioni del tipo ”Cesare”: f1 = x + 17,f2 = x + 13, f3 = x + 10, f4 = x + 5.

Per cifrare un messaggio con questa chiave, la prima lettera si cifracon f1, la seconda con f2, la terza con f3, la quarta con f4, laquinta con f1, la sesta con f2, . . .

Esempio: QUESTO METODO NON E SICURO −→ MMQAPEZB ....

Possibili chiavi: infinite.

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 22: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Esempi

Metodo di Vigenere: Fissiamo una qualsiasi parola come chiave dicifratura, ad esempio SOLE.

Questa parola individua 4 funzioni del tipo ”Cesare”: f1 = x + 17,f2 = x + 13, f3 = x + 10, f4 = x + 5.

Per cifrare un messaggio con questa chiave, la prima lettera si cifracon f1, la seconda con f2, la terza con f3, la quarta con f4, laquinta con f1, la sesta con f2, . . .

Esempio: QUESTO METODO NON E SICURO −→ MMQAPEZB ....

Possibili chiavi: infinite.

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 23: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Esempi

Metodo di Vigenere: Fissiamo una qualsiasi parola come chiave dicifratura, ad esempio SOLE.

Questa parola individua 4 funzioni del tipo ”Cesare”: f1 = x + 17,f2 = x + 13, f3 = x + 10, f4 = x + 5.

Per cifrare un messaggio con questa chiave, la prima lettera si cifracon f1, la seconda con f2, la terza con f3, la quarta con f4, laquinta con f1, la sesta con f2, . . .

Esempio: QUESTO METODO NON E SICURO −→ MMQAPEZB ....

Possibili chiavi: infinite.

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 24: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Esempi

Metodo di Vigenere: Fissiamo una qualsiasi parola come chiave dicifratura, ad esempio SOLE.

Questa parola individua 4 funzioni del tipo ”Cesare”: f1 = x + 17,f2 = x + 13, f3 = x + 10, f4 = x + 5.

Per cifrare un messaggio con questa chiave, la prima lettera si cifracon f1, la seconda con f2, la terza con f3, la quarta con f4, laquinta con f1, la sesta con f2, . . .

Esempio: QUESTO METODO NON E SICURO −→ MMQAPEZB ....

Possibili chiavi: infinite.

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 25: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Esempi

Metodo di Vigenere: Fissiamo una qualsiasi parola come chiave dicifratura, ad esempio SOLE.

Questa parola individua 4 funzioni del tipo ”Cesare”: f1 = x + 17,f2 = x + 13, f3 = x + 10, f4 = x + 5.

Per cifrare un messaggio con questa chiave, la prima lettera si cifracon f1, la seconda con f2, la terza con f3, la quarta con f4, laquinta con f1, la sesta con f2, . . .

Esempio: QUESTO METODO NON E SICURO −→ MMQAPEZB ....

Possibili chiavi: infinite.

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 26: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Problemi

1 La cifratura di Cesare e facilmente decifrabile, dato il numeroristretto di possibili chiavi

2 Le cifrature monoalfabetiche e di Vigenere, pur avendo unnumero elevato di possibili chiavi, sono decifrabili tramiteconsiderazioni di tipo linguistico (ripetizioni di gruppi dilettere, analisi delle frequenze, . . . )

3 Anche complicando notevolmente i precedenti sistemi dicifratura, la conoscenza del messaggio cifrato e della chiave dicifratura comporta la decifrazione del messaggio. Pertanto lachiave di cifratura deve rimanere segreta

Il problema maggiore e quello della distribuzione delle chiavi

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 27: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Problemi

1 La cifratura di Cesare e facilmente decifrabile, dato il numeroristretto di possibili chiavi

2 Le cifrature monoalfabetiche e di Vigenere, pur avendo unnumero elevato di possibili chiavi, sono decifrabili tramiteconsiderazioni di tipo linguistico (ripetizioni di gruppi dilettere, analisi delle frequenze, . . . )

3 Anche complicando notevolmente i precedenti sistemi dicifratura, la conoscenza del messaggio cifrato e della chiave dicifratura comporta la decifrazione del messaggio. Pertanto lachiave di cifratura deve rimanere segreta

Il problema maggiore e quello della distribuzione delle chiavi

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 28: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Problemi

1 La cifratura di Cesare e facilmente decifrabile, dato il numeroristretto di possibili chiavi

2 Le cifrature monoalfabetiche e di Vigenere, pur avendo unnumero elevato di possibili chiavi, sono decifrabili tramiteconsiderazioni di tipo linguistico (ripetizioni di gruppi dilettere, analisi delle frequenze, . . . )

3 Anche complicando notevolmente i precedenti sistemi dicifratura, la conoscenza del messaggio cifrato e della chiave dicifratura comporta la decifrazione del messaggio. Pertanto lachiave di cifratura deve rimanere segreta

Il problema maggiore e quello della distribuzione delle chiavi

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 29: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Problemi

1 La cifratura di Cesare e facilmente decifrabile, dato il numeroristretto di possibili chiavi

2 Le cifrature monoalfabetiche e di Vigenere, pur avendo unnumero elevato di possibili chiavi, sono decifrabili tramiteconsiderazioni di tipo linguistico (ripetizioni di gruppi dilettere, analisi delle frequenze, . . . )

3 Anche complicando notevolmente i precedenti sistemi dicifratura, la conoscenza del messaggio cifrato e della chiave dicifratura comporta la decifrazione del messaggio. Pertanto lachiave di cifratura deve rimanere segreta

Il problema maggiore e quello della distribuzione delle chiavi

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 30: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Problemi

1 La cifratura di Cesare e facilmente decifrabile, dato il numeroristretto di possibili chiavi

2 Le cifrature monoalfabetiche e di Vigenere, pur avendo unnumero elevato di possibili chiavi, sono decifrabili tramiteconsiderazioni di tipo linguistico (ripetizioni di gruppi dilettere, analisi delle frequenze, . . . )

3 Anche complicando notevolmente i precedenti sistemi dicifratura, la conoscenza del messaggio cifrato e della chiave dicifratura comporta la decifrazione del messaggio. Pertanto lachiave di cifratura deve rimanere segreta

Il problema maggiore e quello della distribuzione delle chiavi

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 31: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Da chiave privata a chiave pubblica

Come rendere sicuro lo scambio delle chiavi?

1 A spedisce il messaggio a B all’interno di una scatola chiusacon un lucchetto LA, di cui solo A possiede la chiave

2 B riceve la scatola chiusa con LA, aggiunge un altro lucchettoLB , di cui solo B ha la chiave, e rispedisce la scatola a A

3 A, ricevuta la scatola con il doppio lucchetto, toglie LA erispedisce la scatola a B

4 B toglie il lucchetto LB , apre la scatola e legge il messaggio

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 32: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Da chiave privata a chiave pubblica

Come rendere sicuro lo scambio delle chiavi?

1 A spedisce il messaggio a B all’interno di una scatola chiusacon un lucchetto LA, di cui solo A possiede la chiave

2 B riceve la scatola chiusa con LA, aggiunge un altro lucchettoLB , di cui solo B ha la chiave, e rispedisce la scatola a A

3 A, ricevuta la scatola con il doppio lucchetto, toglie LA erispedisce la scatola a B

4 B toglie il lucchetto LB , apre la scatola e legge il messaggio

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 33: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Da chiave privata a chiave pubblica

Come rendere sicuro lo scambio delle chiavi?

1 A spedisce il messaggio a B all’interno di una scatola chiusacon un lucchetto LA, di cui solo A possiede la chiave

2 B riceve la scatola chiusa con LA, aggiunge un altro lucchettoLB , di cui solo B ha la chiave, e rispedisce la scatola a A

3 A, ricevuta la scatola con il doppio lucchetto, toglie LA erispedisce la scatola a B

4 B toglie il lucchetto LB , apre la scatola e legge il messaggio

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 34: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Da chiave privata a chiave pubblica

Come rendere sicuro lo scambio delle chiavi?

1 A spedisce il messaggio a B all’interno di una scatola chiusacon un lucchetto LA, di cui solo A possiede la chiave

2 B riceve la scatola chiusa con LA, aggiunge un altro lucchettoLB , di cui solo B ha la chiave, e rispedisce la scatola a A

3 A, ricevuta la scatola con il doppio lucchetto, toglie LA erispedisce la scatola a B

4 B toglie il lucchetto LB , apre la scatola e legge il messaggio

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 35: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Da chiave privata a chiave pubblica

Come rendere sicuro lo scambio delle chiavi?

1 A spedisce il messaggio a B all’interno di una scatola chiusacon un lucchetto LA, di cui solo A possiede la chiave

2 B riceve la scatola chiusa con LA, aggiunge un altro lucchettoLB , di cui solo B ha la chiave, e rispedisce la scatola a A

3 A, ricevuta la scatola con il doppio lucchetto, toglie LA erispedisce la scatola a B

4 B toglie il lucchetto LB , apre la scatola e legge il messaggio

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 36: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Da chiave privata a chiave pubblica

Come eliminare lo scambio delle chiavi?

1 A spedisce a tutte le persone con cui desidera comunicare unacopia di un lucchetto LA, di cui solo A possiede la chiave

2 Se B vuole spedire un messaggio ad A, lo mette in una scatolae la chiude con LA.

3 A, ricevuta la scatola, toglie LA con la chiave che solo luipossiede, apre la scatola e legge il messaggio.

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 37: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Da chiave privata a chiave pubblica

Come eliminare lo scambio delle chiavi?

1 A spedisce a tutte le persone con cui desidera comunicare unacopia di un lucchetto LA, di cui solo A possiede la chiave

2 Se B vuole spedire un messaggio ad A, lo mette in una scatolae la chiude con LA.

3 A, ricevuta la scatola, toglie LA con la chiave che solo luipossiede, apre la scatola e legge il messaggio.

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 38: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Da chiave privata a chiave pubblica

Come eliminare lo scambio delle chiavi?

1 A spedisce a tutte le persone con cui desidera comunicare unacopia di un lucchetto LA, di cui solo A possiede la chiave

2 Se B vuole spedire un messaggio ad A, lo mette in una scatolae la chiude con LA.

3 A, ricevuta la scatola, toglie LA con la chiave che solo luipossiede, apre la scatola e legge il messaggio.

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 39: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Da chiave privata a chiave pubblica

Come eliminare lo scambio delle chiavi?

1 A spedisce a tutte le persone con cui desidera comunicare unacopia di un lucchetto LA, di cui solo A possiede la chiave

2 Se B vuole spedire un messaggio ad A, lo mette in una scatolae la chiude con LA.

3 A, ricevuta la scatola, toglie LA con la chiave che solo luipossiede, apre la scatola e legge il messaggio.

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 40: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

RSA (Rivest, Shamir e Adleman)

Il sistema si basa sull’esistenza di funzioni f per cui e moltocomplicato determinare f −1, conoscendo solo f

1 A costruisce una coppia (f , f −1) che soddisfa la precedenteproprieta, e rende pubblica la chiave di cifratura f

2 Se B vuole comunicare con A, codifica il messaggio usando fe lo spedisce a A

3 A decodifica il messaggio usando la chiave di decifrazionef −1, nota solo a lui

4 Sistema a chiave pubblica

f e detta chiave pubblicaf −1 e detta chiave privata

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 41: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

RSA (Rivest, Shamir e Adleman)

Il sistema si basa sull’esistenza di funzioni f per cui e moltocomplicato determinare f −1, conoscendo solo f

1 A costruisce una coppia (f , f −1) che soddisfa la precedenteproprieta, e rende pubblica la chiave di cifratura f

2 Se B vuole comunicare con A, codifica il messaggio usando fe lo spedisce a A

3 A decodifica il messaggio usando la chiave di decifrazionef −1, nota solo a lui

4 Sistema a chiave pubblica

f e detta chiave pubblicaf −1 e detta chiave privata

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 42: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

RSA (Rivest, Shamir e Adleman)

Il sistema si basa sull’esistenza di funzioni f per cui e moltocomplicato determinare f −1, conoscendo solo f

1 A costruisce una coppia (f , f −1) che soddisfa la precedenteproprieta, e rende pubblica la chiave di cifratura f

2 Se B vuole comunicare con A, codifica il messaggio usando fe lo spedisce a A

3 A decodifica il messaggio usando la chiave di decifrazionef −1, nota solo a lui

4 Sistema a chiave pubblica

f e detta chiave pubblicaf −1 e detta chiave privata

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 43: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

RSA (Rivest, Shamir e Adleman)

Il sistema si basa sull’esistenza di funzioni f per cui e moltocomplicato determinare f −1, conoscendo solo f

1 A costruisce una coppia (f , f −1) che soddisfa la precedenteproprieta, e rende pubblica la chiave di cifratura f

2 Se B vuole comunicare con A, codifica il messaggio usando fe lo spedisce a A

3 A decodifica il messaggio usando la chiave di decifrazionef −1, nota solo a lui

4 Sistema a chiave pubblica

f e detta chiave pubblicaf −1 e detta chiave privata

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 44: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

RSA (Rivest, Shamir e Adleman)

Il sistema si basa sull’esistenza di funzioni f per cui e moltocomplicato determinare f −1, conoscendo solo f

1 A costruisce una coppia (f , f −1) che soddisfa la precedenteproprieta, e rende pubblica la chiave di cifratura f

2 Se B vuole comunicare con A, codifica il messaggio usando fe lo spedisce a A

3 A decodifica il messaggio usando la chiave di decifrazionef −1, nota solo a lui

4 Sistema a chiave pubblica

f e detta chiave pubblicaf −1 e detta chiave privata

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 45: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

RSA (Rivest, Shamir e Adleman)

Il sistema si basa sull’esistenza di funzioni f per cui e moltocomplicato determinare f −1, conoscendo solo f

1 A costruisce una coppia (f , f −1) che soddisfa la precedenteproprieta, e rende pubblica la chiave di cifratura f

2 Se B vuole comunicare con A, codifica il messaggio usando fe lo spedisce a A

3 A decodifica il messaggio usando la chiave di decifrazionef −1, nota solo a lui

4 Sistema a chiave pubblica

f e detta chiave pubblicaf −1 e detta chiave privata

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 46: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

RSA (Rivest, Shamir e Adleman)

Il sistema si basa sull’esistenza di funzioni f per cui e moltocomplicato determinare f −1, conoscendo solo f

1 A costruisce una coppia (f , f −1) che soddisfa la precedenteproprieta, e rende pubblica la chiave di cifratura f

2 Se B vuole comunicare con A, codifica il messaggio usando fe lo spedisce a A

3 A decodifica il messaggio usando la chiave di decifrazionef −1, nota solo a lui

4 Sistema a chiave pubblica

f e detta chiave pubblica

f −1 e detta chiave privata

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 47: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

RSA (Rivest, Shamir e Adleman)

Il sistema si basa sull’esistenza di funzioni f per cui e moltocomplicato determinare f −1, conoscendo solo f

1 A costruisce una coppia (f , f −1) che soddisfa la precedenteproprieta, e rende pubblica la chiave di cifratura f

2 Se B vuole comunicare con A, codifica il messaggio usando fe lo spedisce a A

3 A decodifica il messaggio usando la chiave di decifrazionef −1, nota solo a lui

4 Sistema a chiave pubblica

f e detta chiave pubblicaf −1 e detta chiave privata

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 48: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Schema delle lezioni

Lezione 1: Metodi crittografici classici a chiave privata.Aritmetica modulare.

Lezione 2: Algoritmo di Euclide, Piccolo Teorema di Fermat,fattorizzazione in fattori primi

Lezione 3: Sistemi a chiave pubblica; RSA

Lezione 4: Firma digitale

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 49: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Schema delle lezioni

Lezione 1: Metodi crittografici classici a chiave privata.Aritmetica modulare.

Lezione 2: Algoritmo di Euclide, Piccolo Teorema di Fermat,fattorizzazione in fattori primi

Lezione 3: Sistemi a chiave pubblica; RSA

Lezione 4: Firma digitale

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 50: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Schema delle lezioni

Lezione 1: Metodi crittografici classici a chiave privata.Aritmetica modulare.

Lezione 2: Algoritmo di Euclide, Piccolo Teorema di Fermat,fattorizzazione in fattori primi

Lezione 3: Sistemi a chiave pubblica; RSA

Lezione 4: Firma digitale

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 51: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Schema delle lezioni

Lezione 1: Metodi crittografici classici a chiave privata.Aritmetica modulare.

Lezione 2: Algoritmo di Euclide, Piccolo Teorema di Fermat,fattorizzazione in fattori primi

Lezione 3: Sistemi a chiave pubblica; RSA

Lezione 4: Firma digitale

Progetto Lauree Scientifiche Introduzione alla Crittografia

Page 52: Introduzione alla Crittografia...Progetto Lauree Scientifiche Introduzione alla Crittografia Introduzione Problema: A deve fare arrivare a B un certo messaggio, senza che C venga

Schema delle lezioni

Lezione 1: Metodi crittografici classici a chiave privata.Aritmetica modulare.

Lezione 2: Algoritmo di Euclide, Piccolo Teorema di Fermat,fattorizzazione in fattori primi

Lezione 3: Sistemi a chiave pubblica; RSA

Lezione 4: Firma digitale

Progetto Lauree Scientifiche Introduzione alla Crittografia