AATA Cryptographie à clé privée

Section 7.1 Cryptographie à clé privée

Dans les cryptosystèmes à clé unique ou à clé privée, la même clé est utilisée à la fois pour chiffrer et déchiffrer les messages. Pour chiffrer un message en clair, nous appliquons au message une fonction gardée secrète, disons \(f\text{.}\) Cette fonction produit un message chiffré. Étant donné la forme chiffrée du message, nous pouvons retrouver le message original en appliquant la transformation inverse \(f^{-1}\text{.}\) La transformation \(f\) doit être relativement facile à calculer, tout comme \(f^{-1}\) ; cependant, \(f\) doit être extrêmement difficile à deviner à partir d’exemples disponibles de messages codés.

🔗

Exemple 7.1.1.

L’un des premiers et plus célèbres cryptosystèmes à clé privée était le code par décalage utilisé par Jules César. Nous commençons par numériser l’alphabet en posant \(\text{A} = 00, \text{B} = 01, \ldots, \text{Z} = 25\text{.}\) La fonction de codage sera

\begin{equation*} f(p) = p + 3 \bmod 26; \end{equation*}

c’est-à-dire \(A \mapsto D, B \mapsto E, \ldots, Z \mapsto C\text{.}\) La fonction de décodage est alors

\begin{equation*} f^{-1}(p) = p - 3 \bmod 26 = p + 23 \bmod 26\text{.} \end{equation*}

Supposons que nous recevions le message codé DOJHEUD. Pour décoder ce message, nous le numérisons d’abord :

\begin{equation*} 3, 14, 9, 7, 4, 20, 3\text{.} \end{equation*}

Ensuite nous appliquons la transformation inverse pour obtenir

\begin{equation*} 0, 11, 6, 4, 1, 17, 0\text{,} \end{equation*}

soit ALGEBRA. Remarquons ici qu’il n’y a rien de particulier aux nombres \(3\) ou \(26\text{.}\) Nous aurions pu utiliser un alphabet plus grand ou un décalage différent.

🔗

La cryptanalyse s’intéresse au déchiffrement d’un message reçu ou intercepté. Les méthodes issues des probabilités et des statistiques sont d’une grande aide pour déchiffrer un message intercepté ; par exemple, l’analyse des fréquences des caractères apparaissant dans le message intercepté permet souvent de le déchiffrer.

🔗

Exemple 7.1.2.

Supposons que nous recevions un message dont nous savons qu’il a été chiffré par une transformation par décalage appliquée aux lettres individuelles de l’alphabet à \(26\) lettres. Pour déterminer exactement quelle transformation par décalage a été utilisée, nous devons calculer \(b\) dans l’équation \(f(p) = p + b \bmod 26\text{.}\) Nous pouvons le faire par analyse des fréquences. La lettre \(\text{E} = 04\) est la lettre la plus fréquemment utilisée en anglais. Supposons que \(\text{S} = 18\) soit la lettre la plus fréquente dans le texte chiffré. Nous avons alors de bonnes raisons de supposer que \(18 = 4 + b \bmod 26\text{,}\) soit \(b= 14\text{.}\) Par conséquent, la fonction de chiffrement la plus probable est

\begin{equation*} f(p) = p + 14 \bmod 26\text{.} \end{equation*}

La fonction de déchiffrement correspondante est

\begin{equation*} f^{-1}(p) = p + 12 \bmod 26\text{.} \end{equation*}

Il est maintenant facile de vérifier si notre hypothèse est correcte.

🔗

Les codes par décalage simples sont des exemples de cryptosystèmes monoalphabétiques. Dans ces chiffres, un caractère du message chiffré représente exactement un caractère du message original. De tels cryptosystèmes ne sont pas très sophistiqués et sont assez faciles à déchiffrer. En fait, dans un simple décalage tel que décrit dans l’Exemple 7.1.1, il n’y a que \(26\) clés possibles. Il serait assez facile de toutes les essayer plutôt que d’utiliser l’analyse des fréquences.

🔗

Examinons un cryptosystème légèrement plus sophistiqué. Supposons que la fonction de codage soit donnée par

\begin{equation*} f(p) = ap + b \bmod 26\text{.} \end{equation*}

Nous devons d’abord déterminer quand une fonction de décodage \(f^{-1}\) existe. Une telle fonction de décodage existe lorsque nous pouvons résoudre l’équation

\begin{equation*} c = ap + b \bmod 26 \end{equation*}

en \(p\text{.}\) D’après la Proposition 3.1.4, cela est possible exactement lorsque \(a\) est inversible, ou, de manière équivalente, lorsque \(\gcd( a, 26) =1\text{.}\) Dans ce cas

\begin{equation*} f^{-1}(p) = a^{-1} p - a^{-1} b \bmod 26\text{.} \end{equation*}

Un tel cryptosystème est appelé cryptosystème affine.

🔗

Exemple 7.1.3.

Considérons le cryptosystème affine \(f(p) = ap + b \bmod 26\text{.}\) Pour que ce cryptosystème fonctionne, nous devons choisir un \(a \in {\mathbb Z}_{26}\) qui soit inversible. Cela n’est possible que si \(\gcd(a, 26) = 1\text{.}\) En tenant compte de ce fait, nous prendrons \(a = 5\) puisque \(\gcd(5, 26) = 1\text{.}\) Il est facile de voir que \(a^{-1} = 21\text{.}\) Nous pouvons donc prendre comme fonction de chiffrement \(f(p) = 5p + 3 \bmod 26\text{.}\) Ainsi, ALGEBRA est codé comme \(3, 6, 7, 23, 8, 10, 3\text{,}\) soit DGHXIKD. La fonction de déchiffrement sera

\begin{equation*} f^{-1}(p) = 21 p - 21 \cdot 3 \bmod 26 = 21 p + 15 \bmod 26\text{.} \end{equation*}

🔗

Un cryptosystème serait plus sûr si une lettre du texte chiffré pouvait représenter plusieurs lettres du message en clair. Pour donner un exemple de ce type de cryptosystème, appelé cryptosystème polyalphabétique, nous allons généraliser les codes affines en utilisant des matrices. L’idée fonctionne à peu près de la même manière qu’avant ; cependant, au lieu de chiffrer une lettre à la fois, nous chiffrerons des paires de lettres. Nous pouvons stocker une paire de lettres \(p_1\) et \(p_2\) dans un vecteur

\begin{equation*} {\mathbf p} = \begin{pmatrix} p_1 \\ p_2 \end{pmatrix}\text{.} \end{equation*}

Soit \(A\) une matrice \(2 \times 2\) inversible à coefficients dans \({\mathbb Z}_{26}\text{.}\) Nous pouvons définir une fonction de codage par

\begin{equation*} f({\mathbf p}) = A {\mathbf p} + {\mathbf b}\text{,} \end{equation*}

où \({\mathbf b}\) est un vecteur colonne fixe et les opérations matricielles sont effectuées dans \({\mathbb Z}_{26}\text{.}\) La fonction de décodage doit être

\begin{equation*} f^{-1}({\mathbf p}) = A^{-1} {\mathbf p} - A^{-1} {\mathbf b}\text{.} \end{equation*}

🔗

Exemple 7.1.4.

Supposons que nous souhaitons coder le mot HELP. La chaîne de chiffres correspondante est \(7, 4, 11, 15\text{.}\) Si

\begin{equation*} A = \begin{pmatrix} 3 & 5 \\ 1 & 2 \end{pmatrix}\text{,} \end{equation*}

alors

\begin{equation*} A^{-1} = \begin{pmatrix} 2 & 21 \\ 25 & 3 \end{pmatrix}\text{.} \end{equation*}

Si \({\mathbf b} = ( 2, 2)^\transpose\text{,}\) alors notre message est chiffré comme RRGR. La lettre chiffrée R représente plus d’une lettre du message en clair.

🔗

L’analyse des fréquences peut toujours être effectuée sur un cryptosystème polyalphabétique, car nous comprenons bien comment les paires de lettres apparaissent en anglais. La paire th apparaît très souvent ; la paire qz n’apparaît jamais. Pour éviter le déchiffrement par un tiers, nous devons utiliser une matrice plus grande que celle utilisée dans l’Exemple 7.1.4.

🔗

Précédent Top Suivant