ICRYPTOLOGIE

traditionnelle

ICRYPTOLOGIE

traditionnelle

Sommaire

1. Les fondements p. 9

2. Confusion & Diffusion p. 21

3. Cryptages composés p. 39

I. 1Les fondements

I. 1Les fondements

1. Modèle

2. Entropies

3. Confidentialité parfaite

4. Distance d’unicité

Sommaire

1. Modèle

Ek Dk’yx

x

Cryptanalyse

passiveactive

Cryptographie

Gestion des clés

texteen clair

texteen clair

(en)cryptageclé k

Cryptogramme décryptageclé k’

Système cryptographique

• <P, C, K ; E, D>– P, C, K ensembles finis– E : P x K C– D : C x K P

• Notations– x P y C k, k’ K– y = E (x,k) x = D (y,k’)– k’ = f(k) k = f-1(k’) f bijective

x

y

k

k’

y = E (x,k)x = D

(y,k’)k’ = f(k)k = f-1(k’)

Propriétés- D (E(x,k),k’) = x- E(x1,k1) = E(x2,k2) (k1=k2 x1=x2)

P

C K

Propriétés

• pour E et D connus – y est déterminé par x et k

– x est déterminé par y et k’

en général k est indépendant de x

on souhaite que y soit indépendant de x

2. Entropies

• Entropies brutes– H(P) entropie de P– H(C) entropie de C– H(K) entropie de K

• Entropies conditionnelles– H(C/K,P) = 0 C déterminé par P et K– H(P/K,C) = 0 P déterminé par C et K– H(K,P) = H(K) + H(P) K et P indépendants

Propriétés

H(K/C) = H(K) + H(P) - H(C)• Preuve

Rappel H(X,Y) = H(Y,X) = H(Y/X) + H(X)

H(K,P,C) = H(C/K,P) + H(K,P) = H(K) + H(P)

H(K,P,C) = H(P/K,C) + H(K,C) = H(K,C)

H(K/C) = H(K,C) - H(C) = H(K) + H(P) - H(C)

3. Confidentialité parfaite

• <P, C, K ; E, D >

confidentialité parfaite :

P et C indépendants : H(P/C) = H(P) :

xP yC p(x/y) = p(x)

• C(k) = {E (x,k), xP} ensemble des textes cryptés avec k

€

p(y) = p(k) • p(Dk (y)) {k|y∈C (k )}

∑

€

p(y) = p(k) • p(Dk (y)) {k|y∈C (k )}

∑

€

p(y / x) = p(k) {k|x= Dk (y )}

∑

€

p(y / x) = p(k) {k|x= Dk (y )}

∑

€

p(x / y) =p(x) • p(y / x)

p(y)

€

p(x / y) =p(x) • p(y / x)

p(y)

Confidentialité parfaite

x P y C p(y/x) = p(y)

x P y C p(x/y) = p(x)

Théorème 1

• <P, C, K ; E, D > assure une confidentialité parfaite H(K) ≥ H(P)

• PreuveH(P/C) = H(P,C) - H(C) H(P,C) = H(K,P,C) - H(K/P,C)H(P/C) ≤ H(K,P,C) - H(C) = H(P,K,C) - H(C) =

H(P/K,C) + H(K,C) - H(C) = H(K,C) - H(C) = H(K/C) ≤ H(K)

H(P/C) = H(P) hypothèse de confidentialité parfaiteH(P) ≤ H(K)

Théorème 2

• <P, C, K ; E, D > assure une confidentialité parfaite |K| ≥ |C|

• Preuve

y C p(y) > 0 sinon on retire y de C

confidentialité parfaite

x P y C p(y/x) = p(y) > 0

à tout message en clair on peut faire correspondre tout cryptogramme possible

x P y C k K y = E (x,k)

x P y1, y2 C k1, k2 K

y1 = E (x, k1) y2 = E (x, k2)

y1 ≠ y2 k1 ≠ k2 E est une fonction pour chaque texte en clair x, tous les cryptogrammes y doivent être différents, donc toutes les clefs doivent être distinctes

il est possible que y = E(x, k1) = E(x, k2) k1 ≠ k2

un même texte en clair peut être crypté avec 2 clefs différentes et donner le même cryptogramme

il doit y avoir au moins autant de clefs que de cryptogrammes

|K| ≥ |C|C Q F D

Théorème 3

• <P, C, K ; E, D > |K|=|C|=|P|assure une confidentialité parfaite – k n’est utilisée qu’une seule fois kK p(k) = 1/|K| xP, yC, k unique, Ek(x) = y

• Preuve …

• Hypothèse : confidentialité parfaite|C| = | {E (x,k) | x P k K } | ≤ |K| il existe au moins une clef k qui crypte un x en un y

|C| = |K| | {E (x,k) | x P k K } | = |K|Il y a autant de clefs que de cryptogrammes Il n’existe qu’une seule clef k qui crypte un x en un y

Soit |K| = n , P = { xi | 1 ≤ i ≤ n } , y C et

ki | E (xi, ki) = y

On appelle ki la clef qui crypte xi en y

€

p (x i / y) = p (y / x i) . p (x i)

p(y)

€

p (x i / y) = p (y / x i) . p (x i)

p(y)

€

= p (ki) . p (x i)

p(y)

€

= p (ki) . p (x i)

p(y)

€

p (x i / y) = p (x i)

€

p (x i / y) = p (x i)

toutes les clefs de cryptage ont la même probabilité

€

p (ki) = p (y)

€

p (ki) = p (y)

confidentialité parfaite

p (ki) = 1 / |K|C Q F D

• Réciproque

€

p (y) = p(k) p(D(y,k)) = {k y∈C (k )}

∑ p(k) p(D(y,k)) = p(k) {k y∈C (k )}

∑ = 1

K

€

p (y) = p(k) p(D(y,k)) = {k y∈C (k )}

∑ p(k) p(D(y,k)) = p(k) {k y∈C (k )}

∑ = 1

K

€

p (y / x) = p (k) = 1

K

€

p (y / x) = p (k) = 1

K

€

p (x / y) = p (y / x) . p(x)

p(y)

€

p (x / y) = p (y / x) . p(x)

p(y)

€

= p(x)

€

= p(x)

une seule clef k utiliséeavec la probabilité 1 / |K|

C Q F D

4. Distance d’unicité

• Entropie d’un langage– P vocabulaire

– L P*langage sur P

– Exemple langue anglaise• H(P2) 3,9 bits

• H(L) 1,25 bits€

H(L) = lim n →∞ ⏐ → ⏐ ⏐ H(P n )

n

€

H(L) = lim n →∞ ⏐ → ⏐ ⏐ H(P n )

n

• Redondance d’un langage

– Exemple L = langue anglaise• V = {a, b, … z} |P| = 26

• H(L) 1,25 bits

• R(L) = 1 - 1,25/log226 1 - 1,25/5 0,75

– Expérience de Claude Shannon• Compréhension d’un texte en retirant aléatoirement 75% des

lettres !

€

R(L) =1−H(L)

log2 P

€

R(L) =1−H(L)

log2 P

Distance d’unicité

• Théorème de ShannonU est la plus petite valeur de n, nombre de lettres de yC,

telle que la clef k pour laquelle il existe x P, y = E

(x,k) soit unique

€

U =H(K)

R(L)log2 P =

H(K)

log2 P − H(L)

€

U =H(K)

R(L)log2 P =

H(K)

log2 P − H(L)

€

y ∈ Cn

€

y ∈ Cn

€

K (y) = k ∈ K ∃ x ∈ P n E(x,k) = y{ }

€

K (y) = k ∈ K ∃ x ∈ P n E(x,k) = y{ }

€

Sn = p(y) (K(y) −1y∈C n

∑ )

€

Sn = p(y) (K(y) −1y∈C n

∑ )

€

= p(y) K(y) − p(y)y∈C n

∑y∈C n

∑

€

= p(y) K(y) − p(y)y∈C n

∑y∈C n

∑

€

= p(y) K(y) − 1y∈C n

∑

€

= p(y) K(y) − 1y∈C n

∑

€

H(K /Cn ) = H(K) + H(P n ) − H(Cn )

€

H(K /Cn ) = H(K) + H(P n ) − H(Cn )

€

H(P n ) ≈ n HL = n (1− RL ) log2 P

€

H(P n ) ≈ n HL = n (1− RL ) log2 P

€

H(Cn ) ≤ n log2 C

€

H(Cn ) ≤ n log2 C

€

H(K /Cn ) ≥ H(K) − n RL log2 P

€

H(K /Cn ) ≥ H(K) − n RL log2 P

K (y) : ensemble des clefs k décryptanty sur un texte x de longueur n

|K(y)| - 1 : nombre de clefs « parasites » Sn : nombre moyen de clefs parasites

propriété de toutsystème cryptographique

définition de la redondance

si n suffisamment grand

|C| = |P|

Preuve

€

H(K /Cn ) = p(y) H(K / y) y∈C n

∑

€

H(K /Cn ) = p(y) H(K / y) y∈C n

∑

€

≤ p(y) log2 K(y) y∈C n

∑

€

≤ p(y) log2 K(y) y∈C n

∑

€

≤ log2 p(y) K(y) y∈C n

∑

€

≤ log2 p(y) K(y) y∈C n

∑

€

= log2(Sn +1)

€

= log2(Sn +1)

€

log2(Sn +1) ≥ H(K /Cn ) ≥ H(K) − n RL log2 P

€

log2(Sn +1) ≥ H(K /Cn ) ≥ H(K) − n RL log2 P

€

Sn ≥ K

PnRL

− 1

€

Sn ≥ K

PnRL

− 1

équivoque sur K sachant Cn

propriété de l’équivoque

inégalité de Jensen

propriété de Sn

établi précédemment

nombre moyen de clefs parasites quand les clefs sont équiprobables

€

n0 ≈ log2 K

RL log2 P

€

n0 ≈ log2 K

RL log2 P

n0 est la plus petite valeur de n telle queLe nombre moyen de clefs parasites est nul

Exemple

€

log2(Sn +1) ≥ H(K /Cn ) ≥ H(K) − n RL log2 P

€

log2(Sn +1) ≥ H(K /Cn ) ≥ H(K) − n RL log2 P

€

n RL log2 P ≥ H(K) − log2(Sn +1)

€

n RL log2 P ≥ H(K) − log2(Sn +1)

€

n0 ≈ H(K)

RL log2 P

€

n0 ≈ H(K)

RL log2 P

dans le cas où les clefs sont équiprobables

Pour un cryptogramme de 25 lettres, en moyenne, un seul cryptage est possible

|P| = 26 |K| = 26! R(L) = 0,75 U = log226! / 0,75 . 4,7 25

cryptage d’un mot en langue anglaise par substitution mono-alphabétiqueen supposant toutes les clefs équiprobables