Upload
marquite-poisson
View
110
Download
1
Embed Size (px)
Citation preview
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 …