La Teoria di Shannon
Monica Bianchini
[email protected]
Dipartimento di Ingegneria dell’Informazione
Università di Siena
Introduzione
• Nel 1949, Claude Shannon pubblicò un
articolo intitolato “Communication Theory
of Secrecy Systems”, sul Bell Systems
Technical Journal, che ebbe ricadute
fondamentali sui successivi studi sulla
crittografia
La segretezza perfetta  1
•
•
•
Vi sono due approcci fondamentali per descrivere la
sicurezza di un crittosistema
Sicurezza computazionale  È una misura dello sforzo
computazionale richiesto per violare il crittosistema
o Un crittosistema è computazionalmente sicuro se
il miglior algoritmo per violarlo richiede un tempo
macchina “irragionevole” (non è una vera prova,
ha significato puramente pratico)
o Un crittosistema è dimostrabilmente sicuro se il
problema di violarlo è riducibile a qualche
problema noto di cui si conosce la difficoltà
Sicurezza incondizionata  È una misura della sicurezza
del crittosistema quando non si pongono limiti alla
quantità di calcoli che Oscar può eseguire
o Un crittosistema è incondizionatamente sicuro se
non può essere violato, neanche avendo a
disposizione risorse (spazio-temporali) infinite
La segretezza perfetta  2
•
Quando si discute della sicurezza di un crittosistema,
occorre anche definire il tipo di attacco cui le
tecniche di sicurezza si rivolgono
•
Shift cipher, Substitution cipher, Vigenere cipher non
sono computazionalmente sicuri per attacchi tipo
Ciphertext-only
•
Shift cipher, Substitution cipher, Vigenere cipher
sono incondizionatamente sicuri per attacchi tipo
Ciphertext-only se un unico elemento del plaintext
viene codificato utilizzando una data chiave
•
La sicurezza incondizionata di un sistema non può
essere studiata dal punto di vista della complessità
computazionale, dato che si ipotizzano risorse infinite
 il framework appropriato è quello probabilistico
La segretezza perfetta  3
•
Definizione 1
Siano X e Y variabili casuali. Indichiamo con p(x) e p(y),
rispettivamente, le probabilità che X assuma valore x e Y
assuma valore y. La probabilità congiunta, p(x,y), è la
probabilità che X e Y assumano congiuntamente i rispettivi
valori. La probabilità condizionale p(x|y) descrive la probabilità
che X assuma valore x, se Y vale y. Le variabili casuali X e Y
sono indipendenti se p(x,y)=p(x)p(y), per tutti i possibili valori x
di X e y di Y
•
Le probabilità congiunte sono correlate
p(x,y)=p(x|y) p(y) e p(x,y)=p(y|x) p(x), da cui…
•
Teorema 1 (Teorema di Bayes)
p(x) p(y|x)
Se p(y)>0, allora p(x|y) = ____________
•
p(y)
dalle
formule
Corollario 1
X e Y sono variabili indipendenti se e solo se p(x|y)=p(x),
per ogni x,y
La segretezza perfetta  4
• Sia P la distribuzione di probabilità sullo spazio P dei
plaintext; denotiamo la probabilità a priori di occorrenza
del plaintext x con pP (x)
• Supponiamo che la chiave k venga scelta da Alice e Bob
utilizzando un qualche tipo di distribuzione di probabilità
(potrebbe essere uniforme, ma non è necessario) e sia
pK(k) la probabilità di k
• Poiché la scelta della chiave è precedente alla scrittura di
qualsiasi messaggio, k e x sono eventi indipendenti
• Le due distribuzioni di probabilità P e K inducono una
distribuzione di probabilità C su C
• Per una data chiave k K, sia C (k)={ek(x): x P }, cioè
C (k) rappresenta l’insieme dei possibili testi cifrati se la
chiave è k; allora, per ogni y C
pC(y)=

{k: yC(k)}
pK(k) pP (dk(y))
La segretezza perfetta  5
•
Inoltre, per ogni yC e xP, la probabilità condizionale
che si ottenga y, dato x, può essere calcolata come…
pC(y|x) =
•

{k: x=dk(y)}
pK(k)
È infine possibile calcolare la probabilità condizionale che
si abbia il plaintext x, dato il testo cifrato y,
pP (x) 
pK(k)
{k: x=dk(y)}
pP (x|y) = ____________________

{k: yC(k)}
pK(k) pP (dk(y))
La segretezza perfetta  6
• Segretezza perfetta  Oscar non può ottenere
nessuna informazione sul plaintext dall’osservazione
del testo cifrato
• Formalmente…
o Definizione 2
Un crittositema è perfettamente segreto se
pP (x|y) = pP (x), per ogni xP, yC, cioè la
probabilità a posteriori del plaintext x, dato il
testo cifrato y, è identica alla probabilità a priori
di x
• Shift cipher garantisce la segretezza perfetta
La segretezza perfetta  7
• Teorema 2
Supponiamo che le 26 chiavi di Shift cipher vengano
utilizzate con egual probabilità, 1/26. Per ogni
distribuzione di probabilità del plaintext, Shift cipher
garantisce la segretezza perfetta
• Infatti…
P=C=K=Z26. Sia yZ26, allora:
1 p (y-k)
1 p (y-k)= __
p (y)=  p (k) p (d (y))=  __
C
kZ26
K
P
k
kZ26
P
P
kZ26
26
26
Per y fissato, y-k (mod 26) è una permutazione in Z26
e pP è una distribuzione, da cui
kZ26
(y)=1.

pP (y-k) =
yZ26

pP
Di conseguenza pC(y)=1/26, per ogni y Z26. Inoltre
pC(y|x)=pK(y-x (mod 26))=1/26, dato che,  x,y, l’unica
chiave k tale che ek(x)=y è k=y-x (mod 26). Infine, per
pP (x) 1/26
pP (x) pC(y|x)
pP (x)
il Teorema di Bayes
pC(y)
1/26
pP (x|y) = ____________
= __________
=
La segretezza perfetta  8
•
•
•
•
•
Pertanto Shift cipher è inviolabile, a patto di usare
una diversa chiave casuale per codificare ciascun
carattere nel plaintext
Per il Teorema di Bayes, la condizione pP (x|y) = pP (x),
è equivalente alla pC (y|x) = pC (y), per ogni xP, yC.
Pertanto, se pC (y)>0, per ogni yC esiste almeno una
chiave k tale che ek(x)=y |K |>|C |
Inoltre, per ciascun crittosistema si ha |C |>|P |, dato
che le funzioni di codifica sono iniettive
Nel caso particolare in cui |K |=|C |=|P |, vale il
seguente…
Teorema 3
Sia (P,C,K,E,D ) un crittosistema per cui |K |=|C |=|P |.
Il crittosistema garantisce segretezza perfetta se e
solo se ciascuna chiave viene selezionata con ugual
probabilità, 1/|K | e per ogni xP, yC, esiste un’unica
chiave k tale che ek(x)=y
La segretezza perfetta  9
• Infatti…
Supponiamo che il crittosistema garantisca segretezza
perfetta. Poiché per ogni xP, yC esiste almeno una
chiave k tale che ek(x)=y,
|C |=|{ek(x): k K }||K |
Tuttavia nell’ipotesi di uguaglianza |K |=|C |, non esistono
due chiavi k1k2 tali che ek 1 (x)=ek 2 (x)=y  esiste
esattamente una chiave k tale che ek(x)=y.
Sia n=|K |. Sia P={xi: 1  i  n} e sia yC fissato.
Indicando con k1,k2,…kn, le n chiavi in K, sia ek i (xi)=y,
1  i  n. Per il Teorema di Bayes…
pC(y|xi) pP (xi)
pK(ki) pP (xi)
pP (xi|y) = ____________
= __________
pC(y)
pC(y)
L’ipotesi di segretezza perfetta, pP (xi|y)=pP (xi), implica
pK(ki)=pC(y), 1  i  n  le chiavi vengono selezionate in
modo equiprobabile (=pC(y)) e essendo in numero di |K|,
pK(k)=1/|K |
One-time Pad  1
• Un crittosistema che realizza la segretezza perfetta è
One-time Pad, ideato da Gilbert Vernan nel 1917 per
la crittatura dei messaggi telegrafici
• One-time Pad fu ritenuto “inviolabile” per molti anni,
anche se la dimostrazione della sua segretezza è
dovuta a Shannon (oltre 30 anni dopo che era stato
formulato)
Sia n1 un intero, e siano P =C =K=(Z2)n
Per x=(x1,x2,…xn), y=(y1,y2,…yn) e k=(k1,k2,…kn)
ek(x)=(x1+k1,x2+k2,…,xn+kn) (mod 2)
dk(y)=(y1+k1,y2+k2,…,yn+kn) (mod 2)
One-time Pad  2
• La segretezza perfetta di un crittosistema, tuttavia,
comporta notevoli svantaggi:
o Dato che |K ||P |, il numero di chiavi che devono
essere comunicate in maniera sicura è almeno pari
alla dimensione del plaintext
o One-time Pad richiede n bit di chiave per codificare
n bit di plaintext
o La stessa chiave può essere utilizzata una sola volta:
da questa ipotesi dipende l’incondizionata sicurezza
del sistema (ed il nome “one-time” dell’algoritmo)
o One-time Pad è vulnerabile per attacchi del tipo
Known plaintext, poiché la chiave k può essere
calcolata come XOR di x ed ek(x)  Per ogni
messaggio, una nuova chiave deve essere creata ed
inviata su un canale sicuro
One-time Pad  3
• Queste limitazioni hanno rallentato il successo
commerciale dei crittosistemi sicuri, anche se One-time
Pad ha trovato applicazioni in ambito diplomatico e
militare
• Lo sviluppo storico della crittografia ha teso invece alla
creazione di crittosistemi in cui una sola chiave può
essere utilizzata per codificare molti messaggi,
mantenendo salva, almeno, la sicurezza computazionale
• Data Encryption Standard  DES  realizza questo
requisito
Crittosistemi prodotto  1
• Un’altra idea introdotta da Shannon nel 1949 fu quella
di combinare più crittosistemi, formandone il “prodotto”,
idea che è alla base dei crittosistemi attuali come, ad
esempio, DES
• Sia C=P. Crittosistemi di questo tipo si dicono
endomorfi. Siano S1=(P,P,K1,E1,D1) e S2=(P,P,K2,E2,D2)
due crittosistemi endomorfi che condividono lo stesso
plaintext. Il prodotto dei due crittosistemi è
(P,P,K1K2,E,D )
• Una chiave del crittosistema prodotto ha la forma
k=(k1,k2), con k1K1 e k2K2
• Le regole di codifica/decodifica del crittosistema
prodotto sono
e(k1,k 2) (x)=ek2 (ek1 (x))
d(k1,k2) (x)=dk1 (dk2 (x))
Crittosistemi prodotto  2
•
•
Poiché tutti i crittosistemi hanno associata, allo spazio
delle chiavi, una distribuzione di probabilità, occorre
definire la distribuzione di probabilità anche per lo
spazio delle chiavi del crittosistema prodotto, come…
pK(k1,k2)=pK 1(k1)pK 2(k2)
cioè viene scelta k1 in base alla distribuzione K1 e quindi,
indipendentemente, k2 secondo K2
Per descrivere un esempio di crittosistema prodotto,
introduciamo MULTIPLICATIVE Cipher
Sia P = C =Z26 e sia K={aZ26: MCD(a,26)=1}
Per a K, si definisce
ea(x)=a x (mod 26)
da(y)= a-1y (mod 26)
x,yZ26
Crittosistemi prodotto  3
•
•
•
•
•
Sia M Multiplicative cipher ed S Shift cipher (entrambi
con distribuzione omogenea delle chiavi)
 MS è Affine cipher
In questo caso, MS=SM, cioè i due crittosistemi
commutano: la proprietà non è vera in generale.
L’operazione di prodotto è, invece, sempre associativa
Considerando il prodotto di un crittosistema endomorfico
S per se stesso, si ottiene il crittosistema SS, che si
indica con S2
In generale, Sn è un crittosistema iterato
Un crittosistema S è idempotente se S2=S. Shift,
Substitution, Affine, Hill, Vigenere e Permutation cipher
sono tutti idempotenti
Crittosistemi prodotto  4
Se un crittosistema non è idempotente, vi è un
potenziale aumento della sicurezza considerando
l’iterato n-esimo  DES consiste di 16 iterazioni
• Un modo per costruire crittosistemi non idempotenti è
quello di considerare il prodotto di due diversi
crittosistemi (se i crittosistemi sono idempotenti, non
devono commutare)
• Molti dei crittosistemi più semplici possono essere
proficuamente impiegati nel prodotto: il prodotto fra
crittosistemi substitution-permutation è una tecnica
usata molto comunemente
•