I. 2 Confusion & Diffusion Sommaire 1. Cryptages par substitution confusion 2.Cryptages par...

I. 2Confusion & Diffusion

I. 2Confusion & Diffusion

Sommaire

1. Cryptages par substitution

confusion

2. Cryptages par transpositions et permutations

diffusion

3. Autres cryptages

1. Cryptages par substitution

1.1 Cryptages mono-alphabétiques

1.2 Cryptages poly-alphabétiques

Dans tout ce qui suit on suppose k’ = k sauf stipulation contraire

1.1 Cryptages monoalphabétiques

1.1.1 Cryptages « naïfs »

1.1.2 Cryptages additifs

1.1.3 Cryptages par généraux par substitution

1.1.4 Cryptages affines

1.1.5 Cryptanalyse

1.1.1 Cryptages « naïfs »

• Cryptage de PolybeP = {a,b, … z}

les 25 lettres de l’alphabet latin (i et j identiques)C = {1,2,3,4,5}2

suite de 2 chiffres de 1 à 5K = Ø

pas de clefE : P CD : C P D = E-1

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

Polybe(-205 -126)

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

1.1.2 Cryptages additifs

• Cryptage de César– Principe

P = C = K = {a,b, … z} = Z26

x P y C k,k’ K k = k’

Ek(x) = x + k mod 26 décalage de k lettres

Dk(y) = y - k mod 26 décalage inverse

Jules César n’utilisait que la clef k = 3 !

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

Jules César(-100 -44)

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

Exemple

x = message 12-4-18-18-0-6-4

k = 3

y = phvvdjh 15-7-21-21-3-9-7

1.1.3 Cryptages généraux par substitution

• PrincipeP = C = {a,b, … z} = Z26

K = ∏ : Z26 Z26

ensemble des fonctions bijectives (permutations)

x P y C π,π’ ∏ π’ = π-1

Eπ(x) = π (x)

Dπ’(y) = π’ (x)

Il y a 26! clefs possibles considérable !

Exemple

x = message 12-4-18-18-0-6-4

k = z y x … c b a

y = nvhhztv 13-21-7-7-25-19-21

1.1.4 Cryptages affines

• PrincipeP = C = {a,b, … z} = Z26

K = {(a,b) Z262 | pgcd (a,26)=1 }

x P y C (a,b) K

Ek(x) = a x + b mod 26

Dk(y) = (y-b)/a mod 26 pour a=1, le cryptage est additif

Ek doit être injective pgcd (a,26) = 1

Zp pour p premier est un corps

a Zp pgcd (a,p) = 1

Exemple

x = message 12-4-18-18-0-6-4

k = (7, 3)

y = 7x + 3 mod 26

y = jfzzdtf 9-5-25-25-3-19-5 Pour décrypter :

x = (y-3)/7 mod 26 = (y-3) 7-1 mod 26

7-1 mod 26 = 15 (7.15 = 105 = 1 mod 26 )

x = 15 (y-3) mod 26 = 15y - 45 mod 26 =

15y - 19 mod 26

1.1.5 Cryptanalyse

• Analyse des fréquencesAl-Kindi philosophe, mathématicien, astronome, médecin, musicologue et … linguiste, auteur de 290 livres

Manuscrit sur le déchiffrement des messages cryptographiques (découvert en 1987 dans les archives ottomanes d’Istambul)

– Principe • La fréquence des lettres reste invariante entre le texte en clair et le cryptogramme• On classe les lettres du cryptogramme selon leur fréquence• On établit une corrélation des lettres les plus fréquentes avec une table de fréquence type du langage à crypter

QuickTime™ et undécompresseur TIFF (non compressé)

sont requis pour visionner cette image.

الكندي إسحاق ابن يعقوب يوسف أبو

Abu Yusuf Ya’qub ibn Is-haq ibn as-Sabbah

ibn Oòmran ibn Ismaïl Al-Kindi

(801-873)

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

QuickTime™ et undécompresseur TIFF (non compressé)

sont requis pour visionner cette image.

1.2 Cryptages polyalphabétiques

1.2.1 Cryptages par blocs

1.2.2 Cryptage matriciel

1.2.3 Cryptage à confidentialité parfaite

1.2.4 Cryptanalyse

1.2.1 Cryptages par blocs

• Origines XVième siècle• Principe

P = C = K = {a,b, … z} m = Z26

m

cryptage par blocs de m lettres avec une clef alphabétique de longueur m (x1, x2, … xm) P (y1, y2, … ym) C

(k1, k2, … km) K

Ek (x1, x2, … xm ) = (x1+k1, x2+k2, … xm+km)

Dk (y1, y2, … ym ) = (y1-k1, y2-k2, … ym-km) cryptage additif par blocs + & - sont définis mod 26

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

Leon Batista Alberti(1404 - 1472)

QuickTime™ et undécompresseur TIFF (non compressé)

sont requis pour visionner cette image.

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

Jean Trithème(1462 - 1516)

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

Giovanni Battista Della Porta

(1535 - 1615)

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

Blaise de Vigenère(1523 - 1596)

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

Exemple

x = message 12-4-18-18-0-6-4

k = cle 2-11-4

y = opwulkg 14-15-22-20-11-10-6

des lettres identiques de x donnent des lettres différentes de y

l’analyse des fréquences brutes est inapplicable

du fil à retordre pour le cryptanalyste

1.2.2 Cryptage matriciel

• PrincipeP = C = {a,b, … z}

m = Z26m

K = {M (m,m) | M matrice inversible dans Z26}

x = (x1, x2, … xm) P y = (y1, y2, … ym) C

k = (k1, k2, … kn) K

Ek (x) = x . k

Dk (y) = y . k-1

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

Lester S. Hill(1891-1961)

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

Exemple

€

k = 11 8

3 7

⎛

⎝ ⎜

⎞

⎠ ⎟

€

x = et = 4 19( )

€

y = 4 19( ) • 11 8

3 7

⎛

⎝ ⎜

⎞

⎠ ⎟ = 23 9( )

€

k−1 = 7 18

23 11

⎛

⎝ ⎜

⎞

⎠ ⎟

€

k • k−1 = 1 0

0 1

⎛

⎝ ⎜

⎞

⎠ ⎟

€

x = 23 9( ) • 7 18

23 11

⎛

⎝ ⎜

⎞

⎠ ⎟ = 4 19( )

1.2.3 Cryptage à confidentialité parfaite

• PrincipeP = C = K = {0, 1}n = Z2

n

x = (x1, x2, … xn) P y = (y1, y2, … yn) C

k = (k1, k2, … kn) K

Ek (x) = x k

Dk (y) = y k = x k k = x

cryptage du téléphone rouge (Washington - Moscou) confidentialité parfaite pour une clef jetable aussi longue que

le message

Gilbert Vernam(1890-1960)

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

Exemple

x = message code telex (Emile Baudot)

11100 00001 00101 00101 00011 11010 00001

k = richard

01010 00110 01110 10100 00011 01010 01001

y = pujz-t10110 00111 01011 10001 00000 10000 01000

1.2.4 Cryptanalyse

• Historique– Les cryptages monoalphabétiques ont résisté à la

cryptanalyse pendant près de 10 siècles (de Jules César à Al Kindi)

– Il a fallu attendre 5 siècles pour que les nouveaux cryptages polyalphabétiques prennent le relais

– Il faudra encore 4 siècles pour les cryptanalystes en viennent à bout grâce à deux techniques

Le test de Kasisky souvent attribué à BabbageLe test de Friedman

• Idée un cryptage polyalphabétique est équivalent à m cryptages

monoalphabétiques avec une répétition périodique de période m– Recherche de la longueur de la clef m

• recherche de séquences identiques de longueur 3 dans le cryptogramme

les séquences identiques de longueur 2 ont une probabilité trop forte d’apparaître au hasard

• distances de ces séquences : d1, d2, …• m divise pgcd (d1, d2, …) estimation

– Cryptanalyse des m cryptages monoalphabétiques

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

Charles Babbage(1791-1871)

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

Le test de Kasisky 1863

Le test de Friedman 1920

• Idée– P = C = {a, b,…z} = {a1, a2,…a26 }

– Indice de coïncidence d’un texte x : Ic (x) • probabilité que 2 caractères de x (de longueur n) soient égaux

nombre de choix possibles de 2 caractères quelconques dans x

nombre de caractères ai dans x

nombre de choix possibles de 2 caractères ai dans x

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

Wolfe Frederick Friedman(1891-1969)

QuickTime™ et undécompresseur TIFF (non compressé)

sont requis pour visionner cette image.

C2nC2n

€

C2n i

€

C2n i

€

ni

€

ni

Ic (x) =C2

ni

i=1

26

∑C2

n =ni (ni −1)

i=1

26

∑n(n−1)

Ic (x) =C2

ni

i=1

26

∑C2

n =ni (ni −1)

i=1

26

∑n(n−1)

• Indice de coïncidence d’un langagepi probabilité de ai issue

de la table des fréquences

– exemples français 0,074

anglais 0,065

• Indice de coïncidence d’une chaîne de caractère aléatoire

€

Ic (L) ≈ pi2

i=1

26

∑

€

Ic (L) ≈ pi2

i=1

26

∑

€

Ic (t) = 1

26 ≈ 0,038

€

Ic (t) = 1

26 ≈ 0,038

n = |y| longueur du cryptogramme y– estimation de la longueur de la clef m

test de Kasiski

– partition du cryptogramme en sous-chaînes y1, y2, … de longueur n/m colonnes d’un tableau en écrivant y en lignes de m lettres

– calcul de Ic (yi)

Méthode de cryptanalyse

2. Cryptages par transpositions et permutations

2.1 La scytale spartiate

2.2 Cryptage par transposition

2.3 Cryptage par permutation

2.4 Cryptages mixtes

2.5 Cryptanalyse

2.1 La scytale spartiate

• La scytale σκυτάλη (bâton)– Principe

P = C = {a, b, …z }n = Z26n

K =N

x P y C k K

Ek (xij) = xji j [1..k]

Dk (yij) = yji i [1..k] le texte en clair est écrit en lignes de k colonnes le cryptogramme est relevé en colonnes ce cryptage est utilisé par Jules Verne dans voyage au centre de la

terre

QuickTime™ et undécompresseur TIFF (non compressé)

sont requis pour visionner cette image.

(environ -500)

2.2 Cryptage par transposition

• Exemple

x = ceci.est.un.message.

k = 4

y =

€

c e c i

. e s t

. u n .

m e s s

a g e .c..ma eeueg csnse it.s.

2.3 Cryptage par permutation

• PrincipeP = C = {a, b, …z }n = Z26

n

K = ∏ : {1..n} {1..n}

ensemble des fonctions bijectives (permutations)

x P y C π,π’ ∏ π’ = π-1

Eπ (x1, x2, …xn ) = (x π(1), xπ(2), …xπ(n) )

Dπ’ (y1, y2, …yn ) = (yπ’(1), yπ’(2), …yπ’(n) ) équivalent à un cryptage de Hill avec une matrice K

(n,n) telle que ki,j = 1 si i = π(j) = 0 sinon

Exemple

x = c e c i . e s t . u n . m e s s a g e .

k = (4, 2, 1, 3)

y = i e c c t e . s . u . n s e m s . g a e

2.4 Cryptages mixtes

• PrincipeP = C = {a, b, …z }n = Z26

n

K = {a, b, …z }m = Z26m

le texte clef k définit une permutation π et sa longueur m définit une transposition

x P y C k K

Ek (xij) = x(πj)i j [1..m]

Dk (yij) = yj(π’i) i [1..m] π’ = π-1

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

Giovanni Battista Della Porta

(1535 - 1615)

QuickTime™ et undécompresseur TIFF (non compressé)sont requis pour visionner cette image.

Transposition suivi de permutation

x = c e c i . e s t . u n . m e s s a g e .

k = s o i r

π(k) = (4, 2, 1, 3) m(k) = 4

1. transposition

2. permutation

y = i t . s . e e u e g c . . m a c s n s e

€

c e c i

. e s t

. u n .

m e s s

a g e .

€

s o i r

Permutation suivi de transposition

x = c e c i . e s t . u n . m e s s a g e .

k = s o i r

π(k) = (4, 2, 1, 3) m(k) = 4

1. Permutation

y1 = i e c c t e . s . u . n s e m s . g a e

2. transposition

y = i t . s . e e u e g c . . m a c s n s e€

i e c c

t e . s

. u . n

s e m s

. g a e

Propriétés

– Le cryptage par transposition T est idempotent

– Le cryptage par permutation P est idempotent

– Les cryptages P et T sont commutatifs

– Donc : le cryptage P x T est idempotent

en fait une transposition est une permutation particulière

2.5 Cryptanalyse

• Principe– Retrouver la permutation par « recollement »

– Analyse de la distribution des bi-grammes, tri-grammes,…n-grammes

3. Autres cryptages

• Il y en a des centaines– Code Da Vinci– Code Playfair– Code Pigpen(l’enclos des cochons)– Code « la Bible » (Michael Drosnin)– Code ADFGVX– et bien d’autres encore …