Chiffrement DES
Le système de chiffrement DES, aujourd'hui désuet, est un algorithme de chiffrement par bloc qui a longtemps été utilisé pour le chiffrement des mot de passe UNIX. Il est aussi utilisé dans (d'ancien) décodeur de HBO
1.
- 1970 :
- Horst Feistel et ses collègues d'IBM, travaillant avec un système d'exploitation appelé DEMONSTRATION, propose un système de chiffrement par bloc pour la banque en ligne. Le Système DEMONSTRATION ne supportant pas les noms long est communément appelé DEMON. D'où le nom de cette méthode de chiffrement : lucifer.
- 1973 :
- le bureau des standards américain (NBS) lance un appel à la création d'un algorithme de chiffrement utilisable par les entreprises.
- 1976 :
- après quelques "modifications" de la part de l'agence de sécurité nationale américaine (NSA), le système lucifer rebaptisé DES pour data encryption system, est sélectionné par le NBS.
- 1994 :
- Don Coppersmith avoue qu'en 1974, les concepteurs d'IBM avaient trouvé avant l'heure une méthode d'attaque (appelée attaque-T, genre d'attaque différentielle), permettant de casser DES.
- 1998 :
- la machine deep crack (ayant couté environ 200 000€) permet de casser DES en force brute en 56h.
- 1999 :
- par l'intermédiaire de calcul distribué à travers le réseau, il a suffit de 22h pour casser DES en force brute (environ 100 000 machines connectées sur internet).
Dans tout ce chapitre nous ne travaillerons qu'en binaire.
Clef
La clef de DES est un nombre binaire sur 64 bits (8 octets) mais seul 56 bits sont actifs. En effet pour chaque octet un bit, le dernier, est réservé au contrôle de la clef. Il va permettre de s'assurer que l'octet comporte un nombre impaire de 1.
\[
\begin{array}{ccccccc|c}
0&1&0&1&1&1&1&X\\
0&1&0&1&1&0&1&X\\
0&1&0&1&0&0&1&X\\
0&1&1&1&1&1&1&X\\
0&1&0&1&0&0&0&X\\
0&0&0&1&1&0&1&X\\
1&0&1&1&1&1&0&X\\
1&0&0&1&0&0&0&X
\end{array}
\qquad
\Longrightarrow
\qquad
\begin{array}{ccccccc|c}
0&1&0&1&1&1&1&0\\
0&1&0&1&1&0&1&1\\
0&1&0&1&0&0&1&0\\
0&1&1&1&1&1&1&1\\
0&1&0&1&0&0&0&1\\
0&0&0&1&1&0&1&0\\
1&0&1&1&1&1&0&0\\
1&0&0&1&0&0&0&1
\end{array}
\]
Il n'y a donc que \( 56\) bits de choix, ce que signifie, puisqu'un bit ne peut prendre que deux valeurs, qu'il y a \( 2^{56}\) clefs différentes. Ce qui représente environ \( 72\) millions de milliard de clefs possible. Un ordinateur avec un algorithme permettant de tester une clef par seconde mettra donc environ 2 milliards d'année a tout tester.
Constante du chiffrement DES
La méthode de chiffrement DES peut être programmée dans une boite noire (dont on ne voit pas le code) avec un certain nombre de constate. Une attaque différentielle permet de ne pas prendre en compte la valeur des constantes utilisées dans cette boite. C'est pour cette raison que dans la pratique elles sont connues. Il y en a de trois natures : les fonctions de permutations, la fonction d'expansion et les matrices de substitutions.
- Les fonctions de permutations.
- Ces fonctions que le notes dans un tableau vont permettre de mélanger les bits dans le mot.
Par exemple la permutation \( P=(4\ 1\ 3\ 2)\) se comprend par le placement en première position du quatrième bit, en seconde position du premier en troisième du troisième et en quatrième du second.
Si par exemple le message est \( M="1010"\) alors après application de la permutation \( P\) le nouveau message est \( M'="0110"\) .
Cinq permutations interviennent dans le système DES. Nous les notons en matrices bien qu'il faille les lire en ligne, nous n'avons simplement pas la place autrement.
- La permutation initiale
- \( PI =
\begin{pmatrix}
58&50&42&34&26&18&10&2\\
60&52&44&36&28&20&12&4\\
62&54&46&38&30&22&14&6\\
64&56&48&40&32&24&16&8\\
57&49&41&33&25&17&9&1\\
59&51&43&35&27&19&11&3\\
61&53&45&37&29&21&13&5\\
63&55&47&39&31&23&15&7
\end{pmatrix}
\)
- La permutation initiale inverse
- qui fait simplement les association inverse de \( PI\) :
\( PI^{-1} =
\begin{pmatrix}
40&8&48&16&56&24&64&32\\
39&7&47&15&55&23&63&31\\
38&6&46&14&54&22&62&30\\
37&5&45&13&53&21&61&29\\
36&4&44&12&52&20&60&28\\
35&3&43&11&51&19&59&27\\
34&2&42&10&50&18&58&26\\
33&1&41&9&49&17&57&25
\end{pmatrix}
\)
- La permutation des rondes
-
\( P=\begin{pmatrix}
16&7&20&21&29&12&28&17\\
1&15&23&26&5&18&31&10\\
2&8&24&14&32&27&3&9\\
19&13&30&6&22&11&4&25
\end{pmatrix}\)
- La première permutation des clefs
- \[CP_1=\left(
\begin{array}{*{14}{c}}
57&49&41&33&25&17&9&1&58&50&42&34&26&18\\
10&2&59&51&43&35&27&19&11&3&60&52&44&36\\
63&55&47&39&31&23&15&7&62&54&46&38&30&22\\
14&6&61&53&45&37&29&21&13&5&28&20&12&4\\
\end{array}
\right)
\]
- La seconde permutation des clefs
- \[CP_2=
\left(
\begin{array}{*{12}{c}}
14&17&11&24&1&5&3&28&15&6&21&10\\
23&19&12&4&26&8&16&7&27&20&13&2\\
41&52&31&37&47&55&30&40&51&45&33&48\\
44&49&39&56&34&53&46&42&50&36&29&32
\end{array}
\right)
\]
- La fonction d'expansion
- va permettre de transformer un bloc de 32 bits en un bloc de 48 bits. Elle s'utilise comme les fonctions de permutation mais dupliquent en plus 16 bits.
\[E=
\begin{pmatrix}
32&1&2&3&4&5\\
4&5&6&7&8&9\\
8&9&10&11&12&13\\
12&13&14&15&16&17\\
16&17&18&19&20&21\\
20&21&22&23&24&25\\
24&25&26&27&28&29\\
28&29&30&31&32&1
\end{pmatrix}
\]
- Les matrices de substitution
- sont aux nombres de 8 et sont des matrices de 4 lignes et 16 colonnes dont nous détaillerons l'utilisation le moment venu :
\[
S1=\left(
\begin{array}{*{16}{c}}
14 &4 &13 &1 &2 &15 &11 &8 &3 &10 &6 &12 &5 &9 &0 &7 \\
0 &15 &7 &4 &14 &2 &13 &1 &10 &6 &12 &11 &9 &5 &3 &8 \\
4 &1 &14 &8 &13 &6 &2 &11 &15 &12 &9 &7 &3 &10 &5 &0 \\
15 &12 &8 &2 &4 &9 &1 &7 &5 &11 &3 &14 &10 &0 &6 &13
\end{array}
\right)
\]
\[
S2 =\left(
\begin{array}{*{16}{c}}
15&1&8&14&6&11&3&4&9&7&2&13&12&0&5&10\\
3&13&4&7&15&2&8&14&12&0&1&10&6&9&11&5\\
0&14&7&11&10&4&13&1&5&8&12&6&9&3&2&15\\
13&8&10&1&3&15&4&2&11&6&7&12&0&5&14&9
\end{array}
\right)
\]
\[
S3 =\left(
\begin{array}{*{16}{c}}
10&0&9&14&6&3&15&5&1&13&12&7&11&4&2&8\\
13&7&0&9&3&4&6&10&2&8&5&14&12&11&15&1\\
13&6&4&9&8&15&3&0&11&1&2&12&5&10&14&7\\
1&10&13&0&6&9&8&7&4&15&14&3&11&5&2&12
\end{array}
\right)
\]
\[
S4 =\left(
\begin{array}{*{16}{c}}
7&13&14&3&0&6&9&10&1&2&8&5&11&12&4&15\\
13&8&11&5&6&15&0&3&4&7&2&12&1&10&14&9\\
10&6&9&0&12&11&7&13&15&1&3&14&5&2&8&4\\
3&15&0&6&10&1&13&8&9&4&5&11&12&7&2&14
\end{array}
\right)
\]
\[
S5 =\left(
\begin{array}{*{16}{c}}
2&12&4&1&7&10&11&6&8&5&3&15&13&0&14&9\\
14&11&2&12&4&7&13&1&5&0&15&10&3&9&8&6\\
4&2&1&11&10&13&7&8&15&9&12&5&6&3&0&14\\
11&8&12&7&1&14&2&13&6&15&0&9&10&4&5&3
\end{array}
\right)
\]
\[
S6 =\left(
\begin{array}{*{16}{c}}
12&1&10&15&9&2&6&8&0&13&3&4&14&7&5&11\\
10&15&4&2&7&12&9&5&6&1&13&14&0&11&3&8\\
9&14&15&5&2&8&12&3&7&0&4&10&1&13&11&6\\
4&3&2&12&9&5&15&10&11&14&1&7&6&0&8&13
\end{array}
\right)
\]
\[
S7 =\left(
\begin{array}{*{16}{c}}
4&11&2&14&15&0&8&13&3&12&9&7&5&10&6&1\\
13&0&11&7&4&9&1&10&14&3&5&12&2&15&8&6\\
1&4&11&13&12&3&7&14&10&15&6&8&0&5&9&2\\
6&11&13&8&1&4&10&7&9&5&0&15&14&2&3&12
\end{array}
\right)
\]
\[
S8 =\left(
\begin{array}{*{16}{c}}
13&2&8&4&6&15&11&1&10&9&3&14&5&0&12&7\\
1&15&13&8&10&3&7&4&12&5&6&11&0&14&9&2\\
7&11&4&1&9&12&14&2&0&6&10&13&15&3&5&8\\
2&1&14&7&4&10&8&13&15&12&9&0&3&5&6&11
\end{array}
\right)
\]
Logique propositionnelle
Le principe de chiffrement DES est très faible en terme de ressource de temps de calcul. Il n'y a que des substitutions, des conversions en binaire et des opérations de logique.
Revenons sur les opérations de la logique.
Les trois opérations logiques élémentaires
- Le non de la logique
- que l'on note \( \neg p\) et dont la table est
\[
\begin{array}{c||c}
p&\neg p\\\hline\hline
0&1\\
1&0
\end{array}
\]
- Le ou de la logique
- que l'on note \( p+q\) et dont la table est
\[
\begin{array}{cc||c}
p&q&p+q\\\hline\hline
0&0&0\\
0&1&1\\
1&0&1\\
1&1&1
\end{array}
\]
- Le et de la logique
- que l'on note \( p\times q\) ou plus simplement \( p.q\) et dont la table est
\[
\begin{array}{cc||c}
p&q&p.q\\\hline\hline
0&0&0\\
0&1&0\\
1&0&0\\
1&1&1
\end{array}
\]
On note \( 0\) la proposition qui est toujours fausse, on l'appel la
contradiction.
On note \( 1\) la proposition qui est toujours vrai, on l'appel la
tautologie.
Candimatica
Ces trois opérations satisfont certaines lois :
Proposition
Soient \( p\) , \( q\) et \( r\) des propositions
- Commutativité.
- \( p+q=q+p\) , \( p.q=q.p\)
- Associativité.
- \( (p+q)+r=p+(q+r)\) , \( (p.q).r=p.(q.r)\)
- Neutralité.
- \( p+0=p\) , \( p.1=p\)
- Distributivité.
- \( p.(q+r)=(p.q)+(p.r)\) , \( p+(q.r)=(p+q).(p+r)\)
- Idempotence.
- \( p+p=p\) , \( p.p=p\)
- de Morgan
- \( \neg(p+q)=(\neg p).(\neg q)\) , \( \neg(p.q)=(\neg p)+(\neg q)\)
- Absorption 1.
- \( p+1=1\) , \( p.0=0\)
- Tiers exclu.
- \( p+(\neg p)=1\)
- Involution.
- \( \neg(\neg p)=p\)
- Contradiction.
- \( p.(\neg p)=0\)
- Absorption 2.
- \( p+(p.q)=p\) , \( p.(p+q)=p\)
Cette proposition se démontre en comparant par exemple les tables de vérité
Ou exclusif
Le
ou exclusif, qui sera l'outil de la cryptographie DES, se comporte comme le
ou classique à ceci près qu'il renvoie faux si les deux propositions sont vrais. On le note \( p\oplus q\) et sa table de vérité est
\[
\begin{array}{cc||c}
p&q&p\oplus q\\\hline\hline
0&0&0\\
0&1&1\\
1&0&1\\
1&1&0
\end{array}
\]
Théorème
- \( p\oplus q=(p+q).\neg(p.q)\)
- \( p\oplus p=0\)
- \( p\oplus 0=p\)
- \( p\oplus 1=\neg p\)
- \( p\oplus \neg p=1\)
- \( p\oplus q=q\oplus p\)
- \( p\oplus(q\oplus r)=(p\oplus q)\oplus r\)
- \( \left(p\oplus q =0\right)\Leftrightarrow (p=q)\)
- \( \neg(p\oplus q)=(\neg p)\oplus q=p\oplus (\neg q)=(\neg p)\oplus (\neg q)\)
- \( \left(p\oplus q = r\right)\Rightarrow\left(q\oplus r=p\right)\)
Démonstration
Exercice
Méthode de chiffrement
- Création de 16 sous-clefs.
- La clef \( K\) est donnée sur 64 bits. On commence par supprimer les 8 bits de contrôle pour ne garder que les 56 bits utiles
\[
\begin{array}{cccccccc}
0&1&0&1&1&1&1&0\\
0&1&0&1&1&0&1&1\\
0&1&0&1&0&0&1&0\\
0&1&1&1&1&1&1&1\\
0&1&0&1&0&0&0&1\\
0&0&0&1&1&0&1&0\\
1&0&1&1&1&1&0&0\\
1&0&0&1&0&0&0&1
\end{array}\Rightarrow
\begin{array}{ccccccc|c}
0&1&0&1&1&1&1&0\\
0&1&0&1&1&0&1&1\\
0&1&0&1&0&0&1&0\\
0&1&1&1&1&1&1&1\\
0&1&0&1&0&0&0&1\\
0&0&0&1&1&0&1&0\\
1&0&1&1&1&1&0&0\\
1&0&0&1&0&0&0&1
\end{array}
\]
On considère donc la clef de 56 bits \( K=
0101111
0101101
0101001
0111111
0101000
0001101
1011110
1001000\)
On va appliquer la première permutation \( CP_1\) :
\[CLEF = \left\{
\begin{array}{r||*{15}{c}}
\text{Position}&1&2&3&4&5&6&7&8&9&10&11&12&13&14\\\hline
\text{bit}&0&1&0&1&1&1&1&0&1&0&1&1&0&1\\\hline\hline
\text{Position}&15&16&17&18&19&20&21&22&23&24&25&26&27&28\\\hline
\text{bit}&0&1&0&1&0&0&1&0&1&1&1&1&1&1\\\hline\hline
\text{Position}&29&30&31&32&33&34&35&36&37&38&39&40&41&42\\\hline
\text{bit}&0&1&0&1&0&0&0&0&0&0&1&1&0&1\\\hline\hline
\text{Position}&43&44&45&46&47&48&49&50&51&52&53&54&55&56\\\hline
\text{bit}&1&0&1&1&1&1&0&1&0&0&1&0&0&0
\end{array}
\right.
\]
\[
CP_1=
\left(
\begin{array}{*{14}{c}}
57&49&41&33&25&17&9&1&58&50&42&34&26&18\\
10&2&59&51&43&35&27&19&11&3&60&52&44&36\\
63&55&47&39&31&23&15&7&62&54&46&38&30&22\\
14&6&61&53&45&37&29&21&13&5&28&20&12&4\\
\end{array}
\right)
\]
\[
CP_1[CLEF]=\left\{
\begin{array}{r||*{15}{c}}
\text{Position}
&\underset{57}{1}
&\underset{49}{2}
&\underset{41}{3}
&\underset{33}{4}
&\underset{25}{5}
&\underset{17}{6}
&\underset{9}{7}
&\underset{1}{8}
&\underset{58}{9}
&\underset{50}{10}
&\underset{42}{11}
&\underset{34}{12}
&\underset{26}{13}
&\underset{18}{14}
\\\hline
\text{bit}&1&1&0&0&0&0&0&0&0&0&0&1&1&1\\\hline\hline
\text{Position}
&\underset{10}{15}
&\underset{2}{16}
&\underset{59}{17}
&\underset{51}{18}
&\underset{43}{19}
&\underset{35}{20}
&\underset{27}{21}
&\underset{19}{22}
&\underset{11}{23}
&\underset{3}{24}
&\underset{60}{25}
&\underset{52}{26}
&\underset{44}{27}
&\underset{36}{28}
\\\hline
\text{bit}&1&1&0&1&0&0&1&0&0&0&1&1&1&1\\\hline\hline
\text{Position}
&\underset{63}{29}
&\underset{55}{30}
&\underset{47}{31}
&\underset{39}{32}
&\underset{31}{33}
&\underset{23}{34}
&\underset{15}{35}
&\underset{7}{36}
&\underset{62}{37}
&\underset{54}{38}
&\underset{46}{39}
&\underset{38}{40}
&\underset{30}{41}
&\underset{22}{42}
\\\hline
\text{bit}&0&0&1&0&1&1&1&1&0&1&0&0&1&0\\\hline\hline
\text{Position}
&\underset{14}{43}
&\underset{6}{44}
&\underset{61}{45}
&\underset{53}{46}
&\underset{45}{47}
&\underset{37}{48}
&\underset{29}{49}
&\underset{21}{50}
&\underset{13}{51}
&\underset{5}{52}
&\underset{28}{53}
&\underset{20}{54}
&\underset{12}{55}
&\underset{4}{56}
\\\hline
\text{bit}&0&1&0&1&1&0&1&0&1&1&1&1&1&1
\end{array}
\right.
\]
On obtient alors le mélange : \(
11000000000111110100100011110010111101001001011010111111
\)
On sépare la clef en deux partie de 28 bits :
\[
G = 1100000000011111010010001111\qquad
D = 0010111101001001011010111111
\]
On va alors réaliser le processus suivant pour obtenir 16 sous-clefs :
- Écraser \( G\) et \( D\) par leur décaler de 1 bit vers la gauche (le premier bit devenant le dernier).
- La clef \( K_1\) est le résultat de la permutation par \( CP_2\) de la concaténation de \( G\) et \( D\) .
- Écraser \( G\) et \( D\) par leur décaler de 1 bit vers la gauche.
- La clef \( K_2\) est le résultat de la permutation par \( CP_2\) de la concaténation de \( G\) et \( D\) .
- Écraser \( G\) et \( D\) par leur décaler de 1 bit vers la gauche.
- La clef \( K_3\) est le résultat de la permutation par \( CP_2\) de la concaténation de \( G\) et \( D\) .
- ...
- Écraser \( G\) et \( D\) par leur décaler de 1 bit vers la gauche.
- La clef \( K_16\) est le résultat de la permutation par \( CP_2\) de la concaténation de \( G\) et \( D\) .
La propriété de la permutation \( CP_2\) est qu'elle supprime les bits 9, 18, 22, 25, 35, 38, 43 et 54 transformant le bloc de 56 bits en un bloc de 48 octets.
Dans notre exemple :
- Décalage de 1 bit à gauche :
\[
G = 1100000000011111010010001111 \quad \text{deviens}\quad
G = 1000000000111110100100011111
\]
\[
D = 0010111101001001011010111111 \quad \text{deviens}\quad
D = 0101111010010010110101111110
\]
On concatène \( G\) et \( D\)
et on applique le mélange \( CP_2\) (comme nous l'avons fait pour \( CP_1\) ) pour obtenir :
\[K_1=111110011000001010001110010101111111000011101001\]
- Décalage de 1 bit à gauche :
\[
G = 1000000000111110100100011111 \quad \text{deviens}\quad
G = 0000000001111101001000111111
\]
\[
D = 0101111010010010110101111110 \quad \text{deviens}\quad
D = 1011110100100101101011111100
\]
On concatène \( G\) et \( D\)
et on applique le mélange \( CP_2\) pour obtenir :
\[K_2 = 101100010001111010101010011010001110111011011111\]
- etc
- Paquetage.
- On divise le message en paquet de 64 bits en complétant éventuellement les bits manquant par des 0 à la fin.
Si par exemple le message est
\[M=
\begin{array}{l}
11011100101110111100010011010101\\
11100110111101111100001000110010\\
10011101001010110110101111100011\\
0011101011011111
\end{array}\]
Alors on le découpe en deux blocs :
\[M_1=
\begin{array}{l}
11011100101110111100010011010101\\
11100110111101111100001000110010
\end{array}
\qquad
M_2=
\begin{array}{l}
10011101001010110110101111100011\\
00111010110111110000000000000000
\end{array}\]
Les opérations qui suivent se font sur chacun des blocs, nous ne les illustreront qu'avec le bloc de 64 bits \( M_1\) .
- Permutation initiale.
- On applique au bloc la permutation initiale \( PI\) donnée plus haut. On rappel que cette permutation initiale correspond à un mélange des bits :
\[
\begin{array}{r||*{16}{c}}
\text{Position}&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\\hline
\text{bit}&1&1&0&1&1&1&0&0&1&0&1&1&1&0&1&1\\\hline\hline
\text{Position}&17&18&19&20&21&22&23&24&25&26&27&28&29&30&31&32\\\hline
\text{bit}&1&1&0&0&0&1&0&0&1&1&0&1&0&1&0&1\\\hline\hline
\text{Position}&33&34&35&36&37&38&39&40&41&42&43&44&45&46&47&48\\\hline
\text{bit}&1&1&1&0&0&1&1&0&1&1&1&1&0&1&1&1\\\hline\hline
\text{Position}&49&50&51&52&53&54&55&56&57&58&59&60&61&62&63&64\\\hline
\text{bit}&1&1&0&0&0&0&1&0&0&0&1&1&0&0&1&0
\end{array}
\qquad
\begin{pmatrix}
58&50&42&34&26&18&10&2\\
60&52&44&36&28&20&12&4\\
62&54&46&38&30&22&14&6\\
64&56&48&40&32&24&16&8\\
57&49&41&33&25&17&9&1\\
59&51&43&35&27&19&11&3\\
61&53&45&37&29&21&13&5\\
63&55&47&39&31&23&15&7
\end{pmatrix}
\]
Ainsi, avec cette matrice de permutation, le premier bit du nouveau message est le bit 58, le second est le bit 50, le troisième le 42 et ainsi de suite. Le nouveau message deviens alors
\[
\begin{array}{r||*{16}{c}}
\text{Position}
&\underset{58}{1}
&\underset{50}{2}
&\underset{42}{3}
&\underset{34}{4}
&\underset{26}{5}
&\underset{18}{6}
&\underset{10}{7}
&\underset{2}{8}
&\underset{60}{9}
&\underset{52}{10}
&\underset{44}{11}
&\underset{36}{12}
&\underset{28}{13}
&\underset{20}{14}
&\underset{12}{15}
&\underset{4}{16}\\\hline
\text{bit}&0&1&1&1&1&1&0&1&1&0&1&0&1&0&1&1\\\hline\hline
\text{Position}
&\underset{62}{17}
&\underset{54}{18}
&\underset{46}{19}
&\underset{38}{20}
&\underset{30}{21}
&\underset{22}{22}
&\underset{14}{23}
&\underset{6}{24}
&\underset{64}{25}
&\underset{56}{26}
&\underset{48}{27}
&\underset{40}{28}
&\underset{32}{29}
&\underset{24}{30}
&\underset{16}{31}
&\underset{8}{32}\\\hline
\text{bit}&0&0&1&1&1&1&0&1&0&0&1&0&1&0&1&0\\\hline\hline
\text{Position}
&\underset{57}{33}
&\underset{49}{34}
&\underset{41}{35}
&\underset{33}{36}
&\underset{25}{37}
&\underset{17}{38}
&\underset{9}{39}
&\underset{1}{40}
&\underset{59}{41}
&\underset{51}{42}
&\underset{43}{43}
&\underset{35}{44}
&\underset{27}{45}
&\underset{19}{46}
&\underset{11}{47}
&\underset{3}{48}\\\hline
\text{bit}&0&1&1&1&1&1&1&1&1&0&1&1&0&0&1&0\\\hline\hline
\text{Position}
&\underset{61}{49}
&\underset{53}{50}
&\underset{45}{51}
&\underset{37}{52}
&\underset{29}{53}
&\underset{21}{54}
&\underset{13}{55}
&\underset{5}{56}
&\underset{63}{57}
&\underset{55}{58}
&\underset{47}{59}
&\underset{39}{60}
&\underset{31}{61}
&\underset{23}{62}
&\underset{15}{63}
&\underset{7}{64}\\\hline
\text{bit}&0&0&0&0&0&0&1&1&1&1&1&1&0&0&1&0
\end{array}
\]
Soit encore \( PI[M_1]=
0111110110101011001111010010101001111111101100100000001111110010
\)
- Gauche et droite.
- On note \( G\) la partie gauche de \( PI[M_1]\) correspondant aux 32 premiers bits et \( D\) la partie droite correspondant aux 32 derniers.
\[
G = 01111101101010110011110100101010\qquad
D = 01111111101100100000001111110010
\]
- Rondes.
- On va effectuer 16 rondes. Chacune de ces rondes suit le même schéma à ceci près qu'à la ronde \( k\) on utilisera le morceau \( K_k\) de la clef. Le schéma des rondes est le suivant :
- On applique la fonction d'expansion au bloc D. On obtient un message \( E[D]\) non plus sur 32 mais sur 48 bits que l'on regarde comme 12 blocs de 4 bits.
- On calcul \( E[D]\oplus K_k\) (lors de la ronde \( k\) ) en additionnant (exclusivement) avec le morceau de clef.
- On découpe ensuite \( E[D]\oplus K_k\) en 8 blocs de 6 bits. Notons \( B_1, \dots, B_8\) ces 8 blocs. Le bloc \( B_i=x_1x_2x_3x_4x_5x_6\) où les \( x_{machin}\) sont soit \( 0\) soit \( 1\) . On considère l'entier \( n\) dont l'écriture binaire est \( x_1x_6\) . Il s'agit donc d'un entier entre \( 0\) et \( 3\) . On considère \( m\) l'entier dont l'écriture binaire est \( x_2x_3x_4x_5\) ce qui correspond à un entier entre \( 0\) et \( 15\) . On va remplacer \( B_i\) par le nombre, que l'on écrira en binaire, à l'intersection de la \( (n+1)\) -ième ligne et \( (m+1)\) -ième colonne de la matrice de substitution \( S_i\) . Il s'agit, par construction d'un bloc de 4 bits.
- Notons \( \mathbb{S}\) l'application successive des matrices de substitution, de sorte que l'on note \( \mathbb{S}[E[D]\oplus K_k]\) le message issue de l'itération précédente (en regroupant les 8 blocs de 4 bits). On applique alors la permutation des rondes. On note \( P[\mathbb{S}[E[D]\oplus K_k]]\) le résultat
- On remplace \( D\) par \( P[\mathbb{S}[E[D]\oplus K_k]]\oplus G\) et \( G\) par \( D\) .
Réalisation la première ronde.
-
\[
\begin{array}{r||*{16}{c}}
\text{Position}&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\\hline
\text{bit}&0&1&1&1&1&1&1&1&1&0&1&1&0&0&1&0\\\hline\hline
\text{Position}&17&18&19&20&21&22&23&24&25&26&27&28&29&30&31&32\\\hline
\text{bit}&0&0&0&0&0&0&1&1&1&1&1&1&0&0&1&0
\end{array}
\qquad
\begin{pmatrix}
32&1&2&3&4&5\\
4&5&6&7&8&9\\
8&9&10&11&12&13\\
12&13&14&15&16&17\\
16&17&18&19&20&21\\
20&21&22&23&24&25\\
24&25&26&27&28&29\\
28&29&30&31&32&1
\end{pmatrix}
\]
\[
\begin{array}{r|*{16}{c}}
\text{Position}
&\underset{32}{1}
&\underset{1}{2}
&\underset{2}{3}
&\underset{3}{4}
&\underset{4}{5}
&\underset{5}{6}
&\underset{4}{7}
&\underset{5}{8}
&\underset{6}{9}
&\underset{7}{10}
&\underset{8}{11}
&\underset{9}{12}
&\underset{8}{13}
&\underset{9}{14}
&\underset{10}{15}
&\underset{11}{16}\\\hline
\text{bit}&0&0&1&1&1&1&1&1&1&1&1&1&1&1&0&1\\\hline\hline
\text{Position}
&\underset{12}{17}
&\underset{13}{18}
&\underset{12}{19}
&\underset{13}{20}
&\underset{14}{21}
&\underset{15}{22}
&\underset{16}{23}
&\underset{17}{24}
&\underset{16}{25}
&\underset{17}{26}
&\underset{18}{27}
&\underset{19}{28}
&\underset{20}{29}
&\underset{21}{30}
&\underset{20}{31}
&\underset{21}{32}\\\hline
\text{bit}&1&0&1&0&0&1&0&0&0&0&0&0&0&0&0&0\\\hline\hline
\text{Position}
&\underset{22}{33}
&\underset{23}{34}
&\underset{24}{35}
&\underset{25}{36}
&\underset{24}{37}
&\underset{25}{38}
&\underset{26}{39}
&\underset{27}{40}
&\underset{28}{41}
&\underset{29}{42}
&\underset{28}{43}
&\underset{29}{44}
&\underset{30}{45}
&\underset{31}{46}
&\underset{32}{47}
&\underset{1}{48}\\\hline
\text{bit}&0&1&1&1&1&1&1&1&1&0&1&0&0&1&0&0
\end{array}
\]
Ainsi \( E[D]=001111111111110110100100000000000111111110100100\)
- On réalise le ou exclusif avec la clef \( K_1\) :
\[
\begin{array}{rc}
&001111111111110110100100000000000111111110100100\\
\oplus &111110011000001010001110010101111111000011101001\\\hline
&110001100111111100101010010101111000111101001101
\end{array}
\]
Ainsi \( E[D]\oplus K_1=
110001100111111100101010010101111000111101001101
\)
- On regarde \( E[D]\oplus K_1\) en 8 blocs de 6 bits.
\[E[D]\oplus K_1=
110001\ 100111\ 111100\ 101010\ 010101\ 111000\ 111101\ 001101
\]
- On va remplacer le bloc \( 110001\) à l'aide \( S_1\) .
-
- Pour la ligne : le premier et dernier caractère forment \( {1}{1} \) soit \( {3} \) en base 10.
- Pour la colonne : les autres caractères du bloc forment \( {1000} \) soit \( {8} \) en base 10.
- A l'intersection de la ligne \( {3}+1\) et de la colonne \( {8}+1\) de \( S_{{1}}\) se trouve l'entier \( {5} \) qui, codé sur \( 4 \) bits, est \( {0101} \) .
- On va remplacer le bloc \( 100111\) à l'aide \( S_2\) .
-
- Pour la ligne : le premier et dernier caractère forment \( {1}{1} \) soit \( {3} \) en base 10.
- Pour la colonne : les autres caractères du bloc forment \( {0011} \) soit \( {3} \) en base 10.
- A l'intersection de la ligne \( {3}+1\) et de la colonne \( {3}+1\) de \( S_{{2}}\) se trouve l'entier \( {1} \) qui, codé sur \( 4 \) bits, est \( {0001} \) .
- On va remplacer le bloc \( 111100\) à l'aide \( S_3\) .
-
- Pour la ligne : le premier et dernier caractère forment \( {1}{0} \) soit \( {2} \) en base 10.
- Pour la colonne : les autres caractères du bloc forment \( {1110} \) soit \( {14} \) en base 10.
- A l'intersection de la ligne \( {2}+1\) et de la colonne \( {14}+1\) de \( S_{{3}}\) se trouve l'entier \( {14} \) qui, codé sur \( 4 \) bits, est \( {1110} \) .
- On va remplacer le bloc \( 101010\) à l'aide \( S_4\) .
-
- Pour la ligne : le premier et dernier caractère forment \( {1}{0} \) soit \( {2} \) en base 10.
- Pour la colonne : les autres caractères du bloc forment \( {0101} \) soit \( {5} \) en base 10.
- A l'intersection de la ligne \( {2}+1\) et de la colonne \( {5}+1\) de \( S_{{4}}\) se trouve l'entier \( {11} \) qui, codé sur \( 4 \) bits, est \( {1011} \) .
- On va remplacer le bloc \( 010101\) à l'aide \( S_5\) .
-
- Pour la ligne : le premier et dernier caractère forment \( {0}{1} \) soit \( {1} \) en base 10.
- Pour la colonne : les autres caractères du bloc forment \( {1010} \) soit \( {10} \) en base 10.
- A l'intersection de la ligne \( {1}+1\) et de la colonne \( {10}+1\) de \( S_{{5}}\) se trouve l'entier \( {15} \) qui, codé sur \( 4 \) bits, est \( {1111} \) .
- On va remplacer le bloc \( 111000\) à l'aide \( S_6\) .
-
- Pour la ligne : le premier et dernier caractère forment \( {1}{0} \) soit \( {2} \) en base 10.
- Pour la colonne : les autres caractères du bloc forment \( {1100} \) soit \( {12} \) en base 10.
- A l'intersection de la ligne \( {2}+1\) et de la colonne \( {12}+1\) de \( S_{{6}}\) se trouve l'entier \( {1} \) qui, codé sur \( 4 \) bits, est \( {0001} \) .
- On va remplacer le bloc \( 111101\) à l'aide \( S_7\) .
-
- Pour la ligne : le premier et dernier caractère forment \( {1}{1} \) soit \( {3} \) en base 10.
- Pour la colonne : les autres caractères du bloc forment \( {1110} \) soit \( {14} \) en base 10.
- A l'intersection de la ligne \( {3}+1\) et de la colonne \( {14}+1\) de \( S_{{7}}\) se trouve l'entier \( {3} \) qui, codé sur \( 4 \) bits, est \( {0011} \) .
- On va remplacer le bloc \( 001101\) à l'aide \( S_8\) .
-
- Pour la ligne : le premier et dernier caractère forment \( {0}{1} \) soit \( {1} \) en base 10.
- Pour la colonne : les autres caractères du bloc forment \( {0110} \) soit \( {6} \) en base 10.
- A l'intersection de la ligne \( {1}+1\) et de la colonne \( {6}+1\) de \( S_{{8}}\) se trouve l'entier \( {7} \) qui, codé sur \( 4 \) bits, est \( {0111} \) .
- En conclusion
- nous obtenons le message :
\[\mathbb{S}[E[D]\oplus K_1] = 0101\ 0001\ 1110\ 1011\ 1111\ 0001\ 0011\ 0111\]
On applique la permutation des rondes \( \mathbb{S}[E[D]\oplus K_1]\) :
\[
\begin{array}{r||*{16}{c}}
\text{Position}&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\\hline
\text{bit}&0&1&0&1&0&0&0&1&1&1&1&0&1&0&1&1\\\hline\hline
\text{Position}&17&18&19&20&21&22&23&24&25&26&27&28&29&30&31&32\\\hline
\text{bit}&1&1&1&1&0&0&0&1&0&0&1&1&0&1&1&1
\end{array}
\quad
\begin{pmatrix}
16&7&20&21&29&12&28&17\\
1&15&23&26&5&18&31&10\\
2&8&24&14&32&27&3&9\\
19&13&30&6&22&11&4&25
\end{pmatrix}
\]
\[
\begin{array}{r||*{16}{c}}
\text{Position}
&\underset{16}{1}
&\underset{7}{2}
&\underset{20}{3}
&\underset{21}{4}
&\underset{29}{5}
&\underset{12}{6}
&\underset{28}{7}
&\underset{17}{8}
&\underset{1}{9}
&\underset{15}{10}
&\underset{23}{11}
&\underset{26}{12}
&\underset{5}{13}
&\underset{18}{14}
&\underset{31}{15}
&\underset{10}{16}
\\\hline
\text{bit}&1&0&1&0&0&0&1&1&0&1&0&0&0&1&1&1\\\hline\hline
\text{Position}
&\underset{2}{17}
&\underset{8}{18}
&\underset{24}{19}
&\underset{14}{20}
&\underset{32}{21}
&\underset{27}{22}
&\underset{3}{23}
&\underset{9}{24}
&\underset{19}{25}
&\underset{13}{26}
&\underset{30}{27}
&\underset{6}{28}
&\underset{22}{29}
&\underset{11}{30}
&\underset{4}{31}
&\underset{25}{32}
\\\hline
\text{bit}&1&1&1&0&1&1&0&1&1&1&1&0&0&1&1&0
\end{array}
\]
Au final \[P[\mathbb{S}[E[D]\oplus K_1]]=10100011010001111110110111100110\]
Pour finir on réalise l'opération \( P[\mathbb{S}[E[D]\oplus K_1]]\oplus G\) qui deviendra le nouveau \( D\) et le nouveau \( G\) sera l'ancien \( D\) .
\[
\begin{array}{*{33}{c}}
&1&0&1&0&0&0&1&1&0&1&0&0&0&1&1&1&1&1&1&0&1&1&0&1&1&1&1&0&0&1&1&0\\
\oplus
&0&1&1&1&1&1&0&1&1&0&1&0&1&0&1&1&0&0&1&1&1&1&0&1&0&0&1&0&1&0&1&0\\\hline
&1&1&0&1&1&1&1&0&1&1&1&0&1&1&0&0&1&1&0&1&0&0&0&0&1&1&0&0&1&1&0&0
\end{array}
\]
Et
\[
G = 01111111101100100000001111110010\qquad
D = 11011110111011001101000011001100
\]
On réitère alors ces rondes en changeant la clef à chaque tour.
- Initialement.
- \[
G = 01111101101010110011110100101010\qquad
D = 01111111101100100000001111110010
\]
- A la fin de la ronde 1.
- \[
G = 01111111101100100000001111110010\qquad
D = 11011110111011001101000011001100
\]
- A la fin de la ronde 2.
- \[
G = 11011110111011001101000011001100\qquad
D = 01101111000010101101000101000010
\]
- A la fin de la ronde 3.
- \[
G = 01101111000010101101000101000010\qquad
D = 00010110110001011111000000000101
\]
- A la fin de la ronde 4.
- \[
G = 00010110110001011111000000000101\qquad
D = 11000010011110110010001010100101
\]
- A la fin de la ronde 5.
- \[
G = 11000010011110110010001010100101\qquad
D = 11011110001100011000100010010110
\]
- A la fin de la ronde 6.
- \[
G = 11011110001100011000100010010110\qquad
D = 00110000100011100000011111011101
\]
- A la fin de la ronde 7.
- \[
G = 00110000100011100000011111011101\qquad
D = 11011000000101101110110100111101
\]
- A la fin de la ronde 8.
- \[
G = 11011000000101101110110100111101\qquad
D = 10110001110000011011010001001001
\]
- A la fin de la ronde 9.
- \[
G = 10110001110000011011010001001001\qquad
D = 01100001011001111100011111101100
\]
- A la fin de la ronde 10.
- \[
G = 01100001011001111100011111101100\qquad
D = 00101111001001110101000100100100
\]
- A la fin de la ronde 11.
- \[
G = 00101111001001110101000100100100\qquad
D = 01000110000011010111100010111011
\]
- A la fin de la ronde 12.
- \[
G = 01000110000011010111100010111011\qquad
D = 00010111101001110010010111110111
\]
- A la fin de la ronde 13.
- \[
G = 00010111101001110010010111110111\qquad
D = 00101111100101010111011000111111
\]
- A la fin de la ronde 14.
- \[
G = 00101111100101010111011000111111\qquad
D = 01100111100101000101100001000001
\]
- A la fin de la ronde 15.
- \[
G = 01100111100101000101100001000001\qquad
D = 00110000110010100100001000011100
\]
- A la fin de la ronde 16.
- \[
G = 00110000110010100100001000011100\qquad
D = 11010101001001100001000100011010
\]
Pour finir on recolle la partie gauche et droite et on fini avec le message
\[
M_1'=
0011000011001010010000100001110011010101001001100001000100011010
\]
Permutation initiale inverse. On applique finalement à ce message \( M_1'\) la permutation initiale inverse qui fini alors par
\[
PI^{-1}[M_1']=
1000100000110110101000010001001111001011011000001001010010010000
\]
Qui correspond donc au message chiffré. On réitère ensuite l'intégralité de ce processus à tous les blocs du message.
1Valar Morgulis
