La Crittografia al Liceo Matematico · La Crittografia al Liceo Matematico Liceo Majorana, Roma...

La Crittografia al Liceo Matematico

Liceo Majorana, Roma

Seminario Nazionale sui Licei Matematici 3a edizione

Fisciano, 19 settembre 2019

prof. Alex Saltuari

Sistemi misti(parasostituzione)

Considerazioni combinatorichealfabeti di espansione / contrazione

Algoritmo diDiffie-Hellman

SOSTITUZIONE POLIALFABETICA - tavola di Vigenère - chiavi “lunghe” e chiavi casuali - analisi statistiche e valutazione dell’efficacia - aritmetica dell’orologio ROMPERE LA SOSTITUZIONE P.

- Analisi delle frequenze - Analisi di Friedman - Metodo di Kasiski

IL RUOLO DEL “CASO” NELLA CRITTOGRAFIA - macchina di Turing - definizione di Kolmogorov di seq. casuale

CRITTOGRAFIA MODERNA - il protocollo del doppio lucchetto - trasformazioni che commutano - generazione speculare di chiavi - funzioni unidireazionali

CONTROMOSSE - metasimboli a rompere il verme - vermi generati da chiavi - vermi autogeneranti - vermi fagocitanti

Congruenze modulo n per la generazionedi tracce di permutazione

Esempi di steganografia

ClassificazioneSostituzione/Trasposizione

Scitale,Cifrario di Cesare

concetto di CHIAVEe metodo Sacco

Metodi di TRASPOSIZIONE con chiave - trasposizioni a rettangolo (colonna, Zigzag,...) - grafici di rimescolamento - metodi a “griglia bucata” (Cardano, griglie quadrate) - chiave scalare

ITERAZIONE E RAPPRESENTAZIONE - iterazione e valutazione dell’efficacia - tabella e traccia di permutazione - iterazione tramite traccia - periodo della permutazione - rappresenrtazione per cicli disgiunti - trasformazione inversa

SOSTITZIONE MONOALFABETICA - Alfabeti cifranti e decifranti - Sostituzione monoalfabetica per trasposizione dell’alfabeto - alfabeti intervertiti - tavole alfanumeriche

ROMPERE LA SOSTITUZIONE M. - Analisi delle frequenze - Analisi delle frequenze - Analisi delle doppie - Confronto di lingue diverse - Messaggi “casuali”

CONTROMOSSE - Tavole con omofoni - Metasimboli - codici “perfetti”

Grafici di rimescolamento

sistema binarioe codice ASCII

codice Morse

legge di Benford

concetto diCHIAVE PUBBLICA

Percorso di Crittografia svolto al Liceo Majorana di Roma

Novembre 2018Aprile 2019

30 - 40 ore


GRIGLIE DI ROTAZIONE

B R E DT U I NV T I OO E N M




GRIGLIA DI ROTAZIONE




B U O N




B U O N D I V E




B U O N D I V E R T I M




B U O N D I V E R T I M E N T O

B R E D T U I N V T I O E N N M



B U O N D I V E R T I M E N T OB U O ND I V ER T I ME N T O


La griglia viene usata sia per decifrare che per cifrare.



• Come bisogna bucare la griglia affinché sia «di rotazione»?

• Quante griglie di rotazione esistono?


• Come posso informare il mio interlocutore della posizione dei «fori»

nel modo più conciso possibile?

• Le griglie di rotazione «mescolano» bene le lettere?

• Come posso migliorare il metodo?



• Come bisogna bucare la griglia affinché sia «di rotazione»? • Quante griglie di rotazione esistono?








A B C AC D D BB D D CA C B A

Creazione dello schema base




Schema base








Schema base

Esempi



• Come bisogna bucare la griglia affinché sia «di rotazione»?









B U O N D I V E R T I M E N T OB R E D T U I N V T I O E N N M

B U O ND I V ER T I ME N T O


B U O N D I V E R T I M E N T OB R E D T U I N V T I O E N N MB V O T T R U E I N I E M N D O





B V O TT R U EI N I EM N D O

B U O N D I V E R T I M E N T OB R E D T U I N V T I O E N N MB V O T T R U E I N I E M N D OB I M T N V R N U D I O O E T E



B I M TN V R NU D I OO E T E






B R E D T U I N V T I O E N N MB V O T T R U E I N I E M N D OB I M T N V R N U D I O O E T E

B I M TN V R NU D I OO E T E











Disastro!

Applicando il metodo 4 volte le lettere si rimettono in ordine. Perché è successo?

Studiamo la permutazione






T0

T1

T2

T3

T4




T0

T1

T2

T3

T4



LA NON CAMBIA MAI POSIZIONE




T0

T1

T2

T3

T4

ANCHE LA NON CAMBIA MAI POSIZIONE






T0

T1

T2

T3

T4

OPPURE SÌ?



1 9 13 510 2 6 147 15 11 316 8 4 12

1 2 3 45 6 7 89 10 11 1213 14 15 16



Studiamo la permutazione applicando la trasformazione al messaggio «1,2,3,4,…,16»

1 9 13 510 2 6 147 15 11 316 8 4 12

1 2 3 45 6 7 89 10 11 1213 14 15 16



1 6 12 15 4 7 9 14 2 5 11 16 3 8 10 131 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16L’elemento che occupa la

posizione 1 resta nella posizione 1.

1 9 13 510 2 6 147 15 11 316 8 4 12

1 2 3 45 6 7 89 10 11 1213 14 15 16



1 6 12 15 4 7 9 14 2 5 11 16 3 8 10 131 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16L’elemento che prima

occupa la posizione 2 poi finisce nella posizione 6.

1 9 13 510 2 6 147 15 11 316 8 4 12

1 2 3 45 6 7 89 10 11 1213 14 15 16



1 6 12 15 4 7 9 14 2 5 11 16 3 8 10 131 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16L’elemento che prima

occupa la posizione 3 poi finisce nella posizione 12.



1 6 12 15 4 7 9 14 2 5 11 16 3 8 10 131 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

… e così via …

1 9 13 510 2 6 147 15 11 316 8 4 12

1 2 3 45 6 7 89 10 11 1213 14 15 16

1 6 12 15 4 7 9 14 2 5 11 16 3 8 10 131 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16



TABELLA DI PERMUTAZIONE

1 6 12 15 4 7 9 14 2 5 11 16 3 8 10 131 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16



TABELLA DI PERMUTAZIONE

TRACCIA DI PERMUTAZIONE

Successione numerica che definisce in modo completo la permutazione

1 6 12 15 4 7 9 14 2 5 11 16 3 8 10 131 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16



Seguiamo gli spostamenti dei vari elementi

11 6 1215 4 7 9 14 2 5 1116 3 8 1013

2 3 4 5 6 7 8 9 101112 1314 1516



12

6

7

9

3

12

16

13

4

15

10

58

14

11


11 6 12 15 4 7 9 14 2 5 1116 3 8 1013

2 3 4 5 6 7 8 9 101112 13 14 1516



12

6

7

9

3

12

16

13

4

15

10

58

14

11


12

6

7

9

3

12

16

13

4

15

10

58

14

11

11 6 12 15 4 7 9 14 2 5 1116 3 8 1013

2 3 4 5 6 7 8 9 101112 13 14 1516




11 6 12 15 4 7 9 14 2 5 1116 3 8 1013

2 3 4 5 6 7 8 9 101112 13 14 1516

12

6

7

9

3

12

16

13

4

15

10

58

14

11




11 6 12 15 4 7 9 14 2 5 1116 3 8 1013

2 3 4 5 6 7 8 9 101112 13 14 1516

12

6

7

9

3

12

16

13

4

15

10

58

14

11



… e così via …

12

69

3

1213

4

1558

14

111

periodi delle singole orbite

4 4 4 2 1

periodo complessivo

mcm(1,4,4,4,2,1)=4

7 16 10



12

6

7

9

3

12

16

13

4

15

10

58

14

11



(1)(2,6,7,9)(3,12,16,13)(4,15,10,5)(8,14)(11)

RAPPRESENTAZIONE PER CICLI DISGIUNTI


GRIGLIA 6x6

Definisce una trasformazione T (indipendente dal messaggio)

Mettiamo in pratica quanto visto finora…


GRIGLIA 6x61 2 3 4 5 6 7 8 9 28 29 30 31 32 33 34 35 36

...4 9 16 19 27 29 31 35 1 5 11 12 13 15 20 23 34 36⎡ ⎤⎢ ⎥⎣ ⎦

Tabella di permutazione della trasformazione T

( )( )( )( )

1 4 19 2 9 35 34 23 10

3 16 25 21 ... ... 20 6 29 11

15 24 18 32

36

Rappresentazione per cicli disgiunti di T



GRIGLIA 6x61 2 3 4 5 6 7 8 9 28 29 30 31 32 33 34 35 36

...4 9 16 19 27 29 31 35 1 5 11 12 13 15 20 23 34 36⎡ ⎤⎢ ⎥⎣ ⎦


( )( )( )( )

1 4 19 2 9 35 34 23 10

3 16 25 21 ... ... 20 6 29 11

15 24 18 32

36



9 elementi

22 elementi

4 elementi

1 elementi

T ha un periodo pari a mcd(9,22,4,1) = 396


GRIGLIA 6x61 2 3 4 5 6 7 8 9 28 29 30 31 32 33 34 35 36

...4 9 16 19 27 29 31 35 1 5 11 12 13 15 20 23 34 36⎡ ⎤⎢ ⎥⎣ ⎦


( )( )( )( )

1 4 19 2 9 35 34 23 10

3 16 25 21 ... ... 20 6 29 11

15 24 18 32

36



9 elementi

22 elementi

4 elementi

1 elementi

T ha un periodo pari a mcd(9,22,4,1) = 396Trova la traccia di permutazione della trasformazione .


GRIGLIA 6x6


Trova la traccia di permutazione della trasformazione

3 1625

217

30

12

1422

8311317

2628

5

27

3320

629 11 1

4

19

2

935

34

23

10

15

18

243236

9orbita di

elementi22orbita di

elementi

4orbita di

elementielementofisso


GRIGLIA 6x6


Trova la traccia di permutazione della trasformazione

3 1625

217

30

12

1422

8311317

2628

5

27

3320

629 11 1

4

19

2

935

34

23

10

15

18

243236

9orbita di

elementi22orbita di

elementi

4orbita di

elementielementofisso

GRIGLIA 6x6

Problema di Aritmetica Modulare

collegamento


Rappresentazione grafica delle diverse tracce di permutazione

T0T0

Ancora sulle rappresentazioni delle trasposizioni



T0 T1T0 T1



T0 T1 T2T0 T1 T2



T0 T1 T2T0 T1 T2

L’iterazione pare funzionare, rendendo la permutazione apparentemente più irregolare. Come si può quantificare il disordine?

L’iterazione pare funzionare, rendendo la permutazione apparentemente più irregolare. Come si può quantificare il disordine?

T0 T1 T2



T0 T1 T2

Fissato un algoritmo di ordinamento, misuriamo il disordine con il numero di operazioni necessarie a rimettere la sequenza in ordine.

Possibile soluzione

Informaticacollegamento

T0 T1 T2



T0 T1 T2

T394 T395 T396T394 T395 T396

2

W D 2 J Z 6Y N S 7 F GH 3 R K 4 O

1A P L 8 5C M Q T UV X E I B 9

0

A B C D E FG H I J K LM N O P Q RS T U V W XY Z 1 2 34 5 6 7 8 9

0


Vediamo un altro modo di usare la trasposizione per cifrare un messaggio

La tecnica di sostituzione

2

W D 2 J Z 6Y N S 7 F GH 3 R K 4 O


0


0


Vediamo un altro modo di usare la trasposizione per cifrare un messaggio

La tecnica di sostituzioneAlfabeto cifrante

2

W D 2 J Z 6Y N S 7 F GH 3 R K 4 O


0


0


F I S C I A N 2 1 96 S A 2 S W 3 T

OR 1 Q 9

0MESSAGGIO IN CHIARO

MESSAGGIO CRITTATO


2

W D 2 J Z 6Y N S 7 F GH 3 R K 4 O


0


0

TECNICA DI SOSTITUZIONE


F I S C I A N 2 1 96 S A 2 S W 3 T

OR 1 Q 9

0MESSAGGIO IN CHIARO

MESSAGGIO CRITTATO



Punto debole delle tecniche viste finora

È NECESSARIO LO SCAMBIO DELLA CHIAVE DI CODIFICA / DECODIFICA (per esempio la posizione dei fori della griglia)

PROTOCOLLO DEL DOPPIO LUCCHETTO

ALICE BRUNO

Alice e Bruno vogliono comunicare segretamente


ALICE BRUNO

Alice e Bruno vogliono comunicare segretamente


Alice e Bruno concordano «pubblicamente» la trasposizione T che

useranno.

ALICE BRUNO

MESSAGGIO IN CHIARO

MESSAGGIO CIFRATO A volte

TA

Alice cifra il messaggio A volte. Il numero A è noto soltanto ad Alice.


ALICE BRUNO


Alice invia il messaggio cifrato a Bruno.

TA


ALICE BRUNO


ALICE BRUNO


Bruno riceve un messaggio (a lui incomprensibile) e lo cifra a sua volta B volte (B è noto solo a lui)

MESSAGGIO CIFRATO A+B volte

TB


ALICE BRUNO


Bruno invia il messaggio (sovra)cifrato ad Alice.

TA+B


ALICE BRUNOMESSAGGIO CIFRATO

B volte

Alice applica A volte la trasposizione T-1: quello che resta è il messaggio originario cifrato B volte.


T-A


ALICE BRUNO

Alice invia il messaggio cifrato a Bruno.

MESSAGGIO CIFRATO B volte

TB


ALICE BRUNO


ALICE BRUNO


Bruno riceve il testo e applica B volte la trasposizione T-1. Ciò porta il messaggio in chiaro.

MESSAGGIO CIFRATO B volte

MESSAGGIO IN CHIARO

T-B


Riassunto delle comunicazioni intercettate

{ Trasformazione T

Messaggio cifrato A volte (mediante T)

Messaggio cifrato A+B volte (mediante T)

Messaggio cifrato B volte (mediante T)


ALICE BRUNO

COMUNICAZIONE AVVENUTA

B B

A A A B


A BBB A

Discussione sul protocollo del doppio lucchetto.

In quale dei seguenti casi il protocollo del doppio lucchetto funziona?

B B

A A A B


A BBB A



A B funziona?

trasposizione Titerata A volte

trasposizione Titerata B volte

trasposizione T

trasposizione T sostituzione S

sostituzione R sostituzione S

trasposizione U

s ìn os ìn o

B B

A A A B


A BBB A


A B funziona?



trasposizione T



trasposizione U

s ìn os ìn o



B B

A A A B


A BBB A


A B funziona?



trasposizione T



trasposizione U

s ìn os ìn o

collegamento

Algebra (composizione di trasformazioni) B-1 A-1 B A


Considerazioni didattiche

• Alta motivazione da parte degli studenti

• Grande facilità a trasformare il percorso in attività laboratoriale

• Grande varietà di attività (caccia al tesoro a scuola, visite a musei, presentazione ai compagni, Kahoot,…)

Motivazioni «Matematiche»

• Percorso che permette di applicare competenze già acquisite (Calcolo Combinatorio, Informatica)

• Argomento «ponte» verso argomenti difficili da raggiungere (teoria dei Gruppi, macchina di Turing, sequenze pseudocasuali, …)

Collegamenti interdisciplinari

Argomento realmente interdisciplinare, specialmente in Storia e Italiano (per i «giochi» come i lipogrammi) , ma anche Storia dell’Arte, Informatica, Religione


Grazie per l’attenzione

La Crittografia al Liceo Matematico · La Crittografia al Liceo Matematico Liceo Majorana, Roma...

Documents

Transcript of La Crittografia al Liceo Matematico · La Crittografia al Liceo Matematico Liceo Majorana, Roma...