Crittografia e Statistica con
le calcolatrici grafiche
Massimo Borelli, Sergio Invernizzi, Andrea Sgarro
A.D.T., Monopoli, 2002.
Crittografia e Statistica con
le calcolatrici grafiche
•
•
•
•
Perché la crittografia?
Un po’ di storia
Le esperienze precedenti
Il ruolo delle calcolatrici grafiche
Perché la crittografia?
•
•
•
•
•
•
algebra
aritmetica modulare
algoritmi
calcolo combinatorio
statistica
...
Perché la crittografia?
• Nuovi obiettivi
• Nuove metodologie nella didattica
Perché la crittografia?
• Un dato di fatto
– abilità logiche in diminuzione nel tempo
• I rimedi proposti
– algebra, geometria euclidea, ...
• Inconveniente?
– sistema ipotetico deduttivo (ITIS? IPSIA?)
Perché la crittografia?
• Il Nucleo di Ricerca Didattica di Trieste
–
–
–
–
–
–
“problem solving”
capacità deduttive
il linguaggio naturale
formulare congetture o confutare ipotesi
clima di gioco
“laboratorio” di matematica
Perché la crittografia?
• Al giorno d’oggi..
– autenticazione
– protezione “tattica”
– protezione “strategica”
Un po’ di storia
• ... nell’Antico Testamento ..
a b c d
k l m
    ...   
z y x w
p o n
• ... BBL = YYO (cifrario a sostituzione)
Un po’ di storia
• ... Giulio Cesare ..
a b c d
x y z
    ...   
d e f g
a b c
• ... CALMO = FDOPR (cifrario a rotazione)
Un po’ di storia
• in generale: cifrario completo
– 26! = 1026 possibilità
• è sufficiente??
Un po’ di storia
• No!!! Edgar Allan Poe, “Lo scarabeo d’oro”
• A = 11% , E = 11% , I = 10% , ... , B = 1% , Z
= 0.8% , Q = 0.5%
• (Al Kindi, 800 d.C. , L.B.Alberti)
Un po’ di storia
• Cifrari polialfabetici (B. de Vigenère)
a
b
c
d
v
z
b
c
d
e
...
z
a
c
d
e
f
d
e
f
g
e
f
g
h
...
...
...
...
t
u
v
z
u
v
z
a
a
b
b
c
c
d
...
...
r
s
s
t
v
z
a
b
...
t
u
z
a
b
c
u
v
• Messaggio in chiaro + chiave = messaggio
cifrato
Un po’ di storia
• Messaggio in chiaro + chiave = messaggio
cifrato
a
b
c
d
e
f
...
b
c
d
e
f
g
c
d
e
f
g
h
d
e
f
g
h
i
e
f
g
h
i
l
...
...
...
...
...
...
p
q
r
s
t
u
...
...
...
...
...
...
...
t
u
v
z
a
b
u
v
z
a
b
c
v
z
a
b
c
d
z
a
b
c
d
e
...
• (in chiaro) Parigi val bene una messa
• (chiave) flauto fla utof lau tofla
• (cifrato) ulrfcz dll vacl gnu gsaea
Un po’ di storia
• Il successo? Elevato periodo della chiave..
• 1500: macchine meccaniche
• 1900: macchine elettromeccaniche (ad
esempio: Enigma)
• oggi ...
Un po’ di storia
• ... Data Encryption Standard: 256 chiavi
• ... One Time Pad: chiave casuale periodo
infinito
• ... Rivest Shamir Adleman: chiave pubblica!
Le esperienze precedenti
• dal 1989, NRD Trieste:
• 2000, Berardi e Beutelspacher
• 2002, ICTM2 Creta
Le esperienze precedenti
• cifrari a rotazione
– tecnologia livello zero
– gioco
– approccio ”semantico” invece di “statistico”
• ...
Le esperienze precedenti
• cifrari a sostituzione completa
– “frase segreta”, EVVIVA LA TECNOLOGIA
–
E V I A L T C N O G Z U S R Q P M H F D B
Le esperienze precedenti
• Risultati:
–
–
–
–
–
frequenza relativa
principio di massima verosimiglianza
istogrammi delle frequenze
funzione biunivoca, funzione inversa
aritmetica modulare
Il ruolo delle calcolatrici
• a.s.2002/2003, biennio istituto professionale
• Finalità:
– introduzione alla statistica
– introduzione alle calcolatrici grafiche
Il ruolo delle calcolatrici
• Operativamente..
• ... introduzione “standard”...
• .. analisi dei testi cifrati con la TI (vediamo
come!)
... come passo da MS Word alla TI?
• Salvo il file .doc in formato .txt separando ogni
carattere
• Apro in Excel il file, traspongo, codifico in ASCII
e cifro il messaggio
• Incollo in Word il messaggio cifrato e salvo in
formato .txt
• Con TI Graph Link, “import ASCII data”, salvo
L1, “link send”
... come realizzo un cifrario a
sostituzione in modo facile (1)
•
•
•
•
L1-1 STO L2
L2*17+7 STO L3
(L3 modulo 26) STO L2
...
... come realizzo un cifrario a
sostituzione in modo facile (2)
• int (L2 +1.1) STO L3 (per evitare decimali)
... come realizzo un cifrario a
sostituzione completo (1)
• seq(X,X,1,26,1)
STO L2
• For(K,26,2,-1)
• int(rand*K+1) STO
A
• L2(K) STO S
• L2(A) STO L2(K)
• S STO L2(A)
• End
• 1 2 3 4 5 ... 24 25 26
• K = 26
• A = 4 (a caso)
• scambia 4 con 26
• 1 2 3 26 5 ... 24 25 4
• ripeti , K = 25, 24, 23...
... come realizzo un cifrario a
sostituzione completo (2)
• For(K,1,dim(L1),1)
• L1 messaggio in chiaro,
L2 chiave (permutazione)
• L2(L1(K)) STO L3(K) • L1(K) K-esima lettera in
chiaro
• L2(L1(K) K-esima lettera
• End
permutata
Il ruolo delle calcolatrici
• .. agli studenti? Frequenze assolute e relative
EGTCWPCXQNVCWPTG...
Il ruolo delle calcolatrici
• EGTCWPCXQNVCWPTG...
• C? G? K? A! E! I!
• CERAUNAVOLTAUNRE...
Il ruolo delle calcolatrici
• ulteriori passi... One Time Pad
messaggio in chiaro
chiave (casuale)
mess. cifrato (casuale!)
• .. casualità
01010101010101
01001101101011
00011000111110
Riferimenti
• crittografia: [email protected]
• calcolatrici: [email protected]
• sperimentazione: [email protected]