\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Mes commandes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\multirows}[3]{\multirow{#1}{#2}{$#3$}}%pour rester en mode math \renewcommand{\arraystretch}{1.3}%pour augmenter la taille des case \newcommand{\point}[1]{\marginnote{\small\vspace*{-1em} #1}}%pour indiquer les points ou le temps \newcommand{\dpl}[1]{\displaystyle{#1}}%megamode \newcommand{\A}{\mathscr{A}} \newcommand{\LN}{\mathscr{N}} \newcommand{\LL}{\mathscr{L}} \newcommand{\K}{\mathbb{K}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\M}{\mathcal{M}} \newcommand{\D}{\mathbb{D}} \newcommand{\E}{\mathcal{E}} \renewcommand{\P}{\mathcal{P}} \newcommand{\G}{\mathcal{G}} \newcommand{\Kk}{\mathcal{K}} \newcommand{\Cc}{\mathcal{C}} \newcommand{\Zz}{\mathcal{Z}} \newcommand{\Ss}{\mathcal{S}} \newcommand{\B}{\mathbb{B}} \newcommand{\inde}{\bot\!\!\!\bot} \newcommand{\Proba}{\mathbb{P}} \newcommand{\Esp}[1]{\dpl{\mathbb{E}\left(#1\right)}} \newcommand{\Var}[1]{\dpl{\mathbb{V}\left(#1\right)}} \newcommand{\Cov}[1]{\dpl{Cov\left(#1\right)}} \newcommand{\base}{\mathcal{B}} \newcommand{\Som}{\textbf{Som}} \newcommand{\Chain}{\textbf{Chain}} \newcommand{\Ar}{\textbf{Ar}} \newcommand{\Arc}{\textbf{Arc}} \newcommand{\Min}{\text{Min}} \newcommand{\Max}{\text{Max}} \newcommand{\Ker}{\text{Ker}} \renewcommand{\Im}{\text{Im}} \newcommand{\Sup}{\text{Sup}} \newcommand{\Inf}{\text{Inf}} \renewcommand{\det}{\texttt{det}} \newcommand{\GL}{\text{GL}} \newcommand{\crossmark}{\text{\ding{55}}} \renewcommand{\checkmark}{\text{\ding{51}}} \newcommand{\Card}{\sharp} \newcommand{\Surligne}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\SurligneMM}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \renewcommand{\lim}[1]{\underset{#1}{lim}\,} \newcommand{\nonor}[1]{\left|#1\right|} \newcommand{\Un}{1\!\!1} \newcommand{\sepon}{\setlength{\columnseprule}{0.5pt}} \newcommand{\sepoff}{\setlength{\columnseprule}{0pt}} \newcommand{\flux}{Flux} \newcommand{\Cpp}{\texttt{C++\ }} \newcommand{\Python}{\texttt{Python\ }} %\newcommand{\comb}[2]{\begin{pmatrix} #1\\ #2\end{pmatrix}} \newcommand{\comb}[2]{C_{#1}^{#2}} \newcommand{\arrang}[2]{A_{#1}^{#2}} \newcommand{\supp}[1]{Supp\left(#1\right)} \newcommand{\BB}{\mathcal{B}} \newcommand{\arc}[1]{\overset{\rotatebox{90}{)}}{#1}} \newcommand{\modpi}{\equiv_{2\pi}} \renewcommand{\Re}{Re} \renewcommand{\Im}{Im} \renewcommand{\bar}[1]{\overline{#1}} \newcommand{\mat}{\mathcal{M}} \newcommand{\und}[1]{{\mathbf{\color{red}\underline{#1}}}} \newcommand{\rdots}{\text{\reflectbox{$\ddots$}}} \newcommand{\Compa}{Compa} \newcommand{\dint}{\dpl{\int}} \newcommand{\intEFF}[2]{\left[\!\left[#1 ; #2\right]\!\right]} \newcommand{\intEFO}[2]{\left[\!\left[#1 ; #2\right[\!\right[} \newcommand{\intEOF}[2]{\left]\!\left]#1 ; #2\right]\!\right]} \newcommand{\intEOO}[2]{\left]\!\left]#1 ; #2\right[\!\right[} \newcommand{\ou}{\vee} \newcommand{\et}{\wedge} \newcommand{\non}{\neg} \newcommand{\implique}{\Rightarrow} \newcommand{\equivalent}{\Leftrightarrow} \newcommand{\Ab}{\overline{A}} \newcommand{\Bb}{\overline{B}} \newcommand{\Cb}{\overline{C}} \newcommand{\Cl}{\texttt{Cl}} \newcommand{\ab}{\overline{a}} \newcommand{\bb}{\overline{b}} \newcommand{\cb}{\overline{c}} \newcommand{\Rel}{\mathcal{R}} \newcommand{\superepsilon}{\varepsilon\!\!\varepsilon} \newcommand{\supere}{e\!\!e} \makeatletter \newenvironment{console}{\noindent\color{white}\begin{lrbox}{\@tempboxa}\begin{minipage}{\columnwidth} \ttfamily \bfseries\vspace*{0.5cm}} {\vspace*{0.5cm}\end{minipage}\end{lrbox}\colorbox{black}{\usebox{\@tempboxa}} } \makeatother \def\ie{\textit{i.e. }} \def\cf{\textit{c.f. }} \def\vide{ { $ {\text{ }} $ } } %Commande pour les vecteurs \newcommand{\grad}{\overrightarrow{Grad}} \newcommand{\Vv}{\overrightarrow{v}} \newcommand{\Vu}{\overrightarrow{u}} \newcommand{\Vw}{\overrightarrow{w}} \newcommand{\Vup}{\overrightarrow{u'}} \newcommand{\Zero}{\overrightarrow{0}} \newcommand{\Vx}{\overrightarrow{x}} \newcommand{\Vy}{\overrightarrow{y}} \newcommand{\Vz}{\overrightarrow{z}} \newcommand{\Vt}{\overrightarrow{t}} \newcommand{\Va}{\overrightarrow{a}} \newcommand{\Vb}{\overrightarrow{b}} \newcommand{\Vc}{\overrightarrow{c}} \newcommand{\Vd}{\overrightarrow{d}} \newcommand{\Ve}[1]{\overrightarrow{e_{#1}}} \newcommand{\Vf}[1]{\overrightarrow{f_{#1}}} \newcommand{\Vn}{\overrightarrow{0}} \newcommand{\Mat}{Mat} \newcommand{\Pass}{Pass} \newcommand{\mkF}{\mathfrak{F}} \renewcommand{\sp}{Sp} \newcommand{\Co}{Co} \newcommand{\vect}[1]{\texttt{Vect}\dpl{\left( #1\right)}} \newcommand{\prodscal}[2]{\dpl{\left\langle #1\left|\vphantom{#1 #2}\right. #2\right\rangle}} \newcommand{\trans}[1]{{\vphantom{#1}}^{t}{#1}} \newcommand{\ortho}[1]{{#1}^{\bot}} \newcommand{\oplusbot}{\overset{\bot}{\oplus}} \SelectTips{cm}{12}%Change le bout des flèches dans un xymatrix \newcommand{\pourDES}[8]{ \begin{itemize} \item Pour la ligne : le premier et dernier caractère forment $#1#2$ soit $#4$ en base 10. \item Pour la colonne : les autres caractères du bloc forment $#3$ soit $#5$ en base 10. \item A l'intersection de la ligne $#4+1$ et de la colonne $#5+1$ de $S_{#8}$ se trouve l'entier $#6$ qui, codé sur $4$ bits, est \textbf{\texttt{$#7$}}. \end{itemize} } \)

Le chiffrement de Hill

Le principe du chiffrement de Hill est d'essayer de rendre l'analyse fréquentielle caduc (même avec un chiffrement mono alphabétique, c'est à dire par paquet de 1). L'idée est qu'au leu de chiffrer caractère par caractère, on va réunir les caractères par bloc. Ainsi tous les caractères du bloc "influeront" sur le chiffrement des autres. Pour y arriver nous avons besoin d'un outil mathématique : les matrices.

Les matrices

Dans la suite on fixe un entier $ n\geqslant 2$ .

Définition

Une matrice $ 2\times 2$ à coefficient dans $ \Z/n\Z$ est la donnée d'un tableau à deux lignes et deux colonnes. Chaque case du tableau étant remplie d'une valeur de $ \Z/n\Z$ . Si $ a$ , $ b$ , $ c$ et $ d$ sont des éléments de $ \Z/n\Z$ , on note une matrice \[\left( \begin{array}{cc} a&b\\ c&d \end{array} \right)\] On note $ \M_2(\Z/n\Z)$ l'ensemble des matrices $ 2\times 2$ à coefficient dans $ \Z/n\Z$ .

Remarque

On peut bien sur généraliser cette définition à des matrices à $ n$ lignes et $ m$ colonnes et changer également l'ensemble des coefficients pour définir $ \M_{n,m}(\K)$ . Cela ne sera pas nécessaire pour la suite.

Par exemple $ \left( \begin{array}{cc} 2&3\\ -8&7 \end{array} \right)\in \M_{2}(\Z/26\Z)$ L'ensemble des matrices porte une structure algébrique dit d'anneau. Cela signifie que l'on peut additionner et multiplier des matrices entre elles de manière cohérente.

Définition [Opérations]

Soient $ A=\left( \begin{array}{cc} a&b\\ c&d \end{array} \right)$ et $ B=\left( \begin{array}{cc} \alpha&\beta\\ \gamma&\delta \end{array} \right)$ des matrices de $ \M_2(\Z/n\Z)$ et $ \lambda\in \Z/n\Z$

Addition.: On pose : \[A+B\equiv_n \left( \begin{array}{cc} a&b\\ c&d \end{array} \right) + \left( \begin{array}{cc} \alpha&\beta\\ \gamma&\delta \end{array} \right) \equiv_n \left( \begin{array}{cc} a+\alpha&b+\beta\\ c+\gamma&d+\delta \end{array} \right) \]
Multiplication matricielle.: On pose \[A.B\equiv_n \left( \begin{array}{cc} a&b\\ c&d \end{array} \right) . \left( \begin{array}{cc} \alpha&\beta\\ \gamma&\delta \end{array} \right) \equiv_n \left( \begin{array}{cc} a\alpha+b\gamma&a\beta+b\delta\\ c\alpha+d\gamma&c\beta+d\delta \end{array} \right) \]
Multiplication scalaire.: On pose \[\lambda.A\equiv_n \lambda. \left( \begin{array}{cc} a&b\\ c&d \end{array} \right) \equiv_n \left( \begin{array}{cc} \lambda a&\lambda b\\ \lambda c&\lambda d \end{array} \right) \]

Les "cohérences" de ces deux opérations sont résumés dans la proposition suivante

Proposition [Structure algébrique]

Soient $ A$ , $ B$ et $ C$ des matrices de $ M_2(\Z/n\Z)$ .

Commutativité $ +$ .: $ A+B\equiv_nB+A$
Associativité $ +$ .: $ (A+B)+C\equiv_nA+(B+C)$
Neutralité $ +$ .: $ A+0\equiv_n0+A\equiv_nA$ où $ 0\equiv_n\left( \begin{array}{cc} 0&0\\ 0&0 \end{array} \right)$
Symétrie $ +$ .: $ A+(-A)\equiv_n(-A)+A\equiv_n0$ où $ -A$ est la matrice où tous les coefficients ont changé de signe.
Associativité $ \times$ .: $ (A.B).C\equiv_nA.(B.C)$
Neutralité $ \times$: $ A.Id\equiv_nId.A\equiv_nA$ où $ Id\equiv_n\left( \begin{array}{cc} 1&0\\ 0&1 \end{array} \right)$
Distributivité.: $ A(B+C)\equiv_nAB+AC$ et $ (A+B)C\equiv_nAC+BC$

Démonstration

Pour démontrer toutes ces propriétés, on se ramène à la définition
(#longetfastidieux).

Remarque

Il était nécessaire de donner la règle de la distributivité de la sorte (en précisant la distributivité à droite et a gauche) et cela pour la même raison qui fait que nous n'avons pas écrit la règle "Commutativité $ \times$ " : le produit des matrices n'est pas commutatif. Pour le voir, il suffit de traiter un exemple. Plaçons nous dans $ \Z/2\Z$ et considérons les matrices $ A=\left( \begin{array}{cc} 1&1\\ 0&1 \end{array} \right) $ et $ B=\left( \begin{array}{cc} 1&1\\ 1&0 \end{array} \right)$ Alors $ AB\equiv_2\left( \begin{array}{cc} 0&1\\ 1&0 \end{array} \right)$ et $ BA\equiv_2\left( \begin{array}{cc} 1&0\\ 1&1 \end{array} \right)$ Il faut donc prendre garde ! En général, le produit des matrices n'est pas commutatif ! Une autre règle n'est pas vérifiée : celle que nous aurions pu appeler "Symétrie $ \times$ " qui consisterai à écrire $ A.A^{-1}\equiv_nId\equiv_nA^{-1}.A$ . Le problème est que la multiplication étant "étrange" par définition, la division va aussi l'être.

Définition

Soit $ A=\left( \begin{array}{cc} a&b\\ c&d \end{array} \right)\in \M_2(\Z/n\Z)$ . On note $ \det(A)$ le nombre $ ad-bc$ que l'on appelle déterminant de $ A$ .

Par exemple si $ A\equiv_{26}\left( \begin{array}{cc} -5&2\\ 8&7 \end{array} \right)\in \M_2(\Z/26\Z)$ , alors $ \det(A)\equiv_{26}(-5)\times(7)-(8)\times(2)\equiv_{26}-35-16=-51\equiv_{26}1$ .

Proposition

Soient $ A$ , $ B$ des matrices de $ \M_2(\Z/n\Z)$ . \[\det(AB)\equiv_n\det(A)\det(B)\]

Démonstration

Écrivons $ A=\left( \begin{array}{cc} a&b\\ c&d \end{array} \right)$ et $ B=\left( \begin{array}{cc} \alpha&\beta\\ \gamma&\delta \end{array} \right)$ . Alors $ A.B\equiv_n \left( \begin{array}{cc} a\alpha+b\gamma&a\beta+b\delta\\ c\alpha+d\gamma&c\beta+d\delta \end{array} \right)$ . Par définition $ \det(A)=ad-bc$ et $ \det(B)=\alpha\delta-\beta\gamma$ . En multipliant ces résultats et en développant on arrive à \[\det(A)\det(B)=ad\alpha\delta-ad\beta\gamma-bc\alpha\delta+bc\beta\gamma\] D'autre par le déterminant de $ A.B$ se calcul : \begin{eqnarray*} \det(A.B)&=&(a\alpha+b\gamma)(c\beta+d\delta)-(c\alpha+d\gamma)(a\beta+b\delta)\\ &=&(ac\alpha\beta+ad\alpha\delta+bc\beta\gamma+bd\gamma\delta)\\ &-&(ac\alpha\beta+bc\alpha\delta+ad\beta\gamma+bd\gamma\delta)\\ &=& ad\alpha\delta+bc\beta\gamma-bc\alpha\delta-ad\beta\gamma \end{eqnarray*}

Théorème [Inverse matricielle modulaire]

Soit $ A=\left( \begin{array}{cc} a&b\\ c&d \end{array} \right)\in \M_2(\Z/n\Z)$ . La matrice $ A$ est inversible si et seulement si $ \det(A)=ad-bc \in \left(\Z/n\Z\right)^\times$ . Précisément, si on note $ A^{-1}$ cet inverse alors \[A^{-1}\equiv_{n}\det(A)^{-1}\left( \begin{array}{cc} d&-b\\ -c&a \end{array} \right)\] où $ \det(A)^{-1}$ désigne l'inverse de $ \det(A)$ modulo $ n$ .

Démonstration

Si $ \det(A)$ est inversible modulo $ n$ , on vérifie très facilement que $ A.A^{-1}\equiv_{n}A^{-1}.A\equiv_{n}Id$ pour le $ A^{-1}$ donné dans l'énoncé du théorème. Inversement si $ A$ est inversible alors il existe $ A^{-1}$ tel que $ A.A^{-1}=A^{-1}.A=Id$ . En passant au déterminant et en utilisant la proposition précédente, on arrive à $ \det(A)\det(A^{-1})\equiv_n\det(A^{-1})\det(A)\equiv_n\det(Id)\equiv_n1$ .

Par exemple $ A\equiv_{26}\left( \begin{array}{cc} 5&3\\ 4&2 \end{array} \right)\in \M_2(\Z/26\Z)$ . On a $ \det(A)\equiv_{26}10-12\equiv_{26}-2$ . Il faut voir si cet élément est inversible modulo $ 26$ . Il faut pour cela qu'il soit premier avec $ 26$ , ce qui n'est clairement pas le cas. Conclusion : la matrice $ A$ n'est pas inversible modulo $ 26$ . Autre exemple avec $ A\equiv_{26}\left( \begin{array}{cc} 5&3\\ -7&-2 \end{array} \right)\in \M_2(\Z/26\Z)$ . On a $ \det(A)\equiv_{26}(-10)-(-21)\equiv_{26}11$ . En appliquant l'algorithme d'Euclide étendue, on détermine que $ 26(3)+(11)(-7)=1$ soit encore $ 11(-7)\equiv_{26}$ et $ 11^{-1}\equiv_{26}-7$ . \[ \begin{array}{*{4}{c|}|c|c} a&b&r&q&u&v\\\hline 26&11&4&2&3&-7 \\ 11&4&3&2&-1&3\\ 4&3&1&1&1&-1\\ 3&1&0&3&0&1 \end{array} \] En appliquant la formule on arrive à \[\left( \begin{array}{cc} 5&3\\ -7&-2 \end{array} \right)^{-1}\equiv_{26}-7\left( \begin{array}{cc} -2&-3\\ 7&5 \end{array} \right)\equiv_{26}\left( \begin{array}{cc} 14&21\\ -49&-35 \end{array} \right) \equiv_{26}\left( \begin{array}{cc} 14&21\\ 3&17 \end{array} \right)\]

Définition

On note $ \GL_2(\Z/n\Z)$ l'ensemble des matrices inversibles de $ \M_{2}(\Z/n\Z)$ .

Proposition

$ \Card\left(GL_2(\Z/26\Z)\right)=(2^2-1)(2^2-2)(13^2-1)(13^2-13)=157248$

Démonstration

On peut démontrer un énoncé plus général : si $ p$ et $ q$ deux nombres premiers distincts alors $ \Card\left(GL_2(\Z/pq\Z)\right)=(p^2-1)(p^2-p)(q^2-1)(q^2-q)$ . On montre en adaptant la preuve du lemme chinois que l'application \begin{eqnarray*} \varphi : \GL_2(\Z/pq\Z)&\longrightarrow&\GL_2(\Z/p\Z)\times\GL_2(\Z/q\Z)\\ M&\longmapsto&(M_p,M_q) \end{eqnarray*} où $ M_q\equiv_q M$ et $ M_p \equiv_pM$ est une bijection. Il y a donc autant d'élément dans $ \GL_2(\Z/pq\Z)$ que dans $ \GL_2(\Z/p\Z)\times\GL_2(\Z/q\Z)$ . Or la cardinalité de ce dernier ensemble est le produit des cardinalités de $ \GL_2(\Z/q\Z)$ et $ \GL_2(\Z/p\Z)$ . Pour conclure il suffit de montrer que la cardinalité de $ \GL_2(\Z/p\Z)$ est $ (p^2-1)(p^2-p)$ . Les éléments de $ \GL_2(\Z/p\Z)$ sont composés de $ 2$ vecteurs qui doivent être linéairement indépendant (car le déterminant de la matrice est non nul). Ainsi la première colonne (le premier vecteur) est n'importe quoi sauf $ 0$ : $ p^2-1$ possibilités. Le second vecteur ne doit pas être colinéaire au premier donc $ p^2-p$ possibilités.

Pour finir, définissons le produit matrice-vecteur.

Définition

On note $ (\Z/n\Z)^2$ l'ensemble des vecteurs en dimension 2 à coefficient dans $ \Z/n\Z$ . \[\left(\Z/n\Z\right)^2=\left\{\big(^a_b\big)\Big| (a\in \Z/n\Z) \wedge (b\in \Z/n\Z)\right\}\]

Définition [Produit matrice-vecteur]

Soient $ A=\left( \begin{array}{cc} a&b\\ c&d \end{array} \right)\in \M_2(\Z/n\Z)$ et $ X=\left(\begin{array}{c} x\\ y \end{array}\right)\in (\Z/n\Z)^2 $ . On pose \[A.X=\left( \begin{array}{c} ax+by\\ cx+dy \end{array} \right)\]

Par exemple pour $ A=\left( \begin{array}{cc} 4&3\\ 1&-2 \end{array} \right)$ et $ X=\left(\begin{array}{c} 2\\ -3 \end{array}\right) $ alors $ A.X=\left(\begin{array}{c} -1\\ 8 \end{array}\right) $

Principe du chiffrement

Cryptosystème

Définition

Les données suivantes définissent le cryptosystème de Hill de dimension 2 par paquet de 1.

Espace de clefs.: $ \mathcal{K}=\GL_2(\Z/26\Z)$
Fonction de chiffrement.: Quelque soit $ A\in \mathcal{K}$ et $ X\in (\Z/26\Z)^2$ , $ C_A(X)=A.X$ .
Fonction de déchiffrement.: Quelque soit $ A\in \mathcal{K}$ et $ X\in (\Z/26\Z)^2$ , $ D_A(X)=A^{-1}.X$ .

L'associativité du calcul matriciel justifie la propriété du déchiffrement. Prenons comme exemple la matrice $ A=\left( \begin{array}{cc} 5&3\\ -7&-2 \end{array} \right)$ qui est bien un élément de $ GL_2(\Z/26\Z)$ puisque $ \det(A)=11$ est un nombre premier avec $ 26$ . Chiffrons le message CHIFFREMENTDEHILL \[ \begin{array}{*{18}{c|}c} Texte &C&H&I&F&F&R&E&M&E&N&T&D&E&H&I&L&L&\\\hline Codage &2&7&8&5&5&17&4&12&4&13&19&3&4&7&8&11&11&\\\hline Vecteur\ X& &{(2,7)}&&{(8,5)}&&{(5,17)}&&{(4,12)}&&{(4,13)}&&{(19,3)}&&{(4,7)}&&{(8,11)}&&{(11,0)}\\\hline A.X& &{(31,-28)}&&{(55,-66)}&&{(76,-69)}&&{(56,-52)}&&{(59,-54)}&&{(104,-139)}&&{(41,-42)}&&{(73,-78)}&&{(55,-77)}\\\hline \equiv_{26}& &{(5,24)}&&{(3,12)}&&{(24,9)}&&{(4,0)}&&{(7,24)}&&{(0,17)}&&{(15,10)}&&{(21,0)}&&{(3,1)}\\\hline Dépaquetage&5&24&3&12&24&9&4&0&7&24&0&17&15&10&21&0&3&1\\\hline Décodage&F&Y&D&M&Y&J&A&E&H&Y&A&R&P&K&V&A&D&B \end{array} \] Ainsi le message chiffré est FYDMYJAEHYARPKVADB. Inversement : imaginons avoir reçu le DTQUCTEQGDAA obtenue par un chiffrement de Hill de matrice $ A= \left( \begin{array}{cc} 9&4\\ 5&7 \end{array} \right) $ . La première étape consiste à déterminer l'inverse de $ A$ et avant cela il faut calculer son déterminant et l'inverse de celui-ci.

Calcul du déterminant.: $ \det(A)=9\times7-5\times4=63-20=43\equiv_{26}17$
Calcul de l'inverse du déterminant.: \[\begin{array}{c|c|c|c||c|c} a&b&r&q&u&v\\\hline 26&17&9&1&2&-3\\ 17&9&8&1&-1&2\\ 9&8&1&1&1&-1\\ 8&1&0&8&0&1 \end{array} \] Ainsi $ 17^{-1}\equiv_{26}-3(\equiv_{26}23)$
Calcul de l'inverse de la matrice.: On applique la formule : \[A^{-1}\equiv_{26}-3 \left( \begin{array}{cc} 7&-4\\ -5&9 \end{array} \right)\equiv_{26} \left( \begin{array}{cc} -21&12\\ 15&-27 \end{array} \right)\equiv_{26} \left( \begin{array}{cc} 5&12\\ 15&-1 \end{array} \right) \]

Ceci étant on peut déchiffrer le message. \[ \begin{array}{c|*{12}{|c}} &D&T&Q&U&C&T&E&Q&G&D&A& \\\hline Codage &3&19&16&20&2&19&4&16&6&3&0& \\\hline Vecteur \ X &&{(3,19)}&&{(16,20)}&&{(2.19)}&&{(4,16)}&&{(6,3)}&&{(0,0)} \\\hline A^{-1}.X &&{(243,26)}&&{(320,220)}&&{(238,11)} &&{(212,44)}&&{(66,87)}&&{(0,0)} \\\hline \equiv_{26} &&{(9,0)}&&{(8,12)}&&{(4,11)} &&{(4,18)}&&{(14,9)}&&{(0,0)}\\\hline Dépaquetage &9&0&8&12&4&11&4&18&14&9&0&0\\\hline Décodage &J&A&I&M&E&L&E&S&O&J&A&A \end{array} \]

Cryptanalyse

Dans la précédente section nous avons vu que la cardinalité de $ \GL_2(\Z/26\Z)$ c'est à dire de l'espace des clefs du chiffrement de Hill par paquet de 1 en dimension 2 était de $ 157\,248$ . Ce nombre reste "raisonnable" et une attaque en force brute est suffisante dans ce cas. Il est également possible de raisonner par analyse fréquentielle mais de manière différente que celle que nous avons vu. En effet, comme nous pouvons l'observer dans l'exemple précédent, la lettre E avait été codée, une fois par un C et un autre fois par la même lettre E. Le chiffrement de Hill, ne permet aucune analyse fréquentielle mono alphabétique. Mais puisque nous travaillons par paquet de 2, on peut faire une analyse fréquentielle $ 2$ -alphabétique¹. Dans un texte en français, les blocs de 2 lettres les plus fréquents sont \[ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{Lettres} &ES&LE&EN&DE&RE&NT&ON&TE&ER&SE\\\hline \text{Fréquences}&3.15\%&2.46\%&2.42\%&2.15\%&2.09\%&1.97\%&1.64\%&1.63\%&1.63\%&1.55\%\\\hline \end{array} \] Ainsi, lorsque le texte est suffisamment long, une analyse fréquentielle peut aboutir au déchiffrement. Il existe une autre manière d'attaquer un problème de cryptographie, l'attaque à clair connu, que nous allons détailler dans le cas du chiffrement de Hill, mais qui s'applique pour tous les autres cryptosystèmes. Le principe de l'attaque à clair connu réside dans le fait que l'on ne possède pas seulement le message chiffré. On possède également un partie du texte claire². Imaginons que vous interceptiez un flux d'information entre enseignants qui ont pris la peine de chiffrer leurs communications et ne se sont pas retenus de dire à leurs étudiants "De toute manière nous utilisons un chiffrement de Hill pour toute nos communications.". Vous interceptez un document Exam_crypto.txt. En l'ouvrant, bien sur tout est codé :YXYIEZLD.... Vous savez, que comme tout examen qui se respecte, il est fort probable que les premiers mots soient EXAMENDECRYPTO. Sachant qu'il s'agit d'un chiffrement de Hill, la clef est une matrice $ A\equiv_{26} \left( \begin{array}{cc} a&b\\ c&d \end{array} \right) \in\GL_2(\Z/26\Z) $ . En comparant la chaine dans le document et la chaine supposé on en déduit que "$ A$ .EX=YX", "$ A$ .AM=YI", "$ A$ .EN=EZ" et "$ A$ .DE=LD". En replaçant par les valeurs numériques, on arrive à quatre équations :

1.: $ A\left(\begin{array}{c} E\\ X \end{array}\right)=\left(\begin{array}{c} Y\\ X \end{array}\right)\Leftrightarrow A\left(\begin{array}{c}4\\23\end{array}\right)\equiv_{26}\left(\begin{array}{c}24\\23\end{array}\right)$
2.: $ A\left(\begin{array}{c} A\\ M \end{array}\right)=\left(\begin{array}{c} Y\\ I \end{array}\right)\Leftrightarrow A\left(\begin{array}{c}0\\12\end{array}\right)\equiv_{26}\left(\begin{array}{c}24\\8\end{array}\right)$
3.: $ A\left(\begin{array}{c} E\\ N \end{array}\right)=\left(\begin{array}{c} E\\ Z \end{array}\right)\Leftrightarrow A\left(\begin{array}{c}4\\13\end{array}\right)\equiv_{26}\left(\begin{array}{c}4\\25\end{array}\right)$
4.: $ A\left(\begin{array}{c} D\\ E \end{array}\right)=\left(\begin{array}{c} L\\ D \end{array}\right)\Leftrightarrow A\left(\begin{array}{c}3\\4\end{array}\right)\equiv_{26}\left(\begin{array}{c}11\\3\end{array}\right)$

On peut, grâce aux définitions du calcul matricielle, "fusionner" deux équations. Par exemple l'équation 1 et l'équation 2 donnent l'équation 1.2 : $ A\left(\begin{array}{cc}4&0\\23&12\end{array}\right)=\left(\begin{array}{cc}24&24\\23&8\end{array}\right)$ qui se résout simplement en inversant la matrice à droite de $ A$ . Précisément : $ A=\left(\begin{array}{cc}24&24\\23&8\end{array}\right).\left(\begin{array}{cc}4&0\\23&12\end{array}\right)^{-1}$ . Pour pouvoir réaliser cette opération, il faut que la matrice soit inversible, c'est à dire que son déterminant, soit premier avec $ 26$ . Or $ \det\left(\begin{array}{cc}4&0\\23&12\end{array}\right)=48$ et $ PGCD(26,48)=2$ . La matrice n'est donc pas inversible. Il faut être capable de trouver une matrice inversible en combinant les équations. Plus on dispose de clair connu, plus on dispose d'équation et donc plus il va être facile de trouver une matrice inversible. Dans cet exemple, avec les 4 équations dont nous disposons, nous pouvons former six matrices :

Équation 1.2 :: $ A\left(\begin{array}{cc}4&0\\23&12\end{array}\right)\equiv_{26}\left(\begin{array}{cc}24&24\\23&8\end{array}\right)$ et $ \det\left(\begin{array}{cc}4&0\\23&12\end{array}\right)\equiv_{26}48$ qui n'est pas premier avec $ 26$ .
Équation 1.3 :: $ A\left(\begin{array}{cc}4&4\\23&13\end{array}\right)\equiv_{26}\left(\begin{array}{cc}24&4\\23&25\end{array}\right)$ et $ \det\left(\begin{array}{cc}4&4\\23&13\end{array}\right)\equiv_{26}-40$ qui n'est pas premier avec $ 26$
Équation 1.4 :: $ A\left(\begin{array}{cc}4&3\\23&4\end{array}\right)\equiv_{26}\left(\begin{array}{cc}24&11\\23&3\end{array}\right)$ et $ \det\left(\begin{array}{cc}4&3\\23&4\end{array}\right)\equiv_{26}-53\equiv_{26}-1$ qui est premier avec $ 26$ . Dans ce cas \[A \equiv_{26} \left(\begin{array}{cc}24&11\\23&3\end{array}\right)\cdot \left(\begin{array}{cc}4&3\\23&4\end{array}\right)^{-1}\equiv_{26} \left(\begin{array}{cc}24&11\\23&3\end{array}\right)\cdot \left(\begin{array}{cc}-4&3\\23&-4\end{array}\right)\equiv_{26} \left(\begin{array}{cc}1&2\\3&5\end{array}\right) \]
Équation 2.3 :: $ A\left(\begin{array}{cc}0&4\\12&13\end{array}\right)\equiv_{26}\left(\begin{array}{cc}24&4\\8&25\end{array}\right)$ et $ \det\left(\begin{array}{cc}0&4\\12&13\end{array}\right)\equiv_{26}-48$ qui n'est pas premier avec $ 26$
Équation 2.4 :: $ A\left(\begin{array}{cc}0&3\\12&4\end{array}\right)\equiv_{26}\left(\begin{array}{cc}24&11\\8&3\end{array}\right)$ et $ \det\left(\begin{array}{cc}0&3\\12&4\end{array}\right)\equiv_{26}-36$ qui n'est pas premier avec $ 26$
Équation 3.4 :: $ A\left(\begin{array}{cc}4&3\\13&4\end{array}\right)\equiv_{26}\left(\begin{array}{cc}4&11\\25&3\end{array}\right)$ et $ \det\left(\begin{array}{cc}4&3\\13&4\end{array}\right)\equiv_{26}-23\equiv_{26}3$ qui est premier avec $ 26$ . Dans ce cas \[ A \equiv_{26} \left(\begin{array}{cc}4&11\\25&3\end{array}\right)\cdot \left(\begin{array}{cc}4&3\\13&4\end{array}\right)^{-1}\equiv_{26} \left(\begin{array}{cc}4&11\\25&3\end{array}\right)\cdot \left(\begin{array}{cc}10&-1\\-13&10\end{array}\right)\equiv_{26} \left(\begin{array}{cc}1&2\\3&5\end{array}\right) \]

A chaque fois qu'il est possible d'inverser la matrice on trouve $ A\equiv_{26} \left(\begin{array}{cc}1&2\\3&5\end{array}\right)$ qui est donc la clef de chiffrement. Pour déchiffrer il faudra appliquer la matrice inverse $ A^{-1}\equiv_{26} \left(\begin{array}{cc}1&2\\3&5\end{array}\right)^{-1}\equiv_{26} \left(\begin{array}{cc}-5&2\\3&-1\end{array}\right)$

Lemme

Supposons que le clair connu d'un message obtenu par un chiffrement de Hill, soit composé de $ 2n$ caractères pour un certain entier $ n\in \N_{{>}0}$ . Alors il existe $ \dfrac{n(n-1)}{2}$ équations matricielles différentes permettant de déterminer la clef de chiffrement.

Démonstration

Se donner $ 2n$ caractères connus donne $ n$ équations matrices-vecteurs. Il y a $ (^n_2)=\dfrac{n!}{2!(n-2)!}=\dfrac{n(n-1)}{2}$ façon de coupler des équations matrice-vecteur pour obtenir des équations matrice-matrice (par définition du combinatoire).

Complication

Le chiffrement de Hill est déjà un principe de paquetage, mais rien n'empêche de compiler les paquetages. On sera dans ce cas amener à travailler avec des matrice de $ \GL_2(\Z/2526\Z)$ ou $ \GL_2(\Z/252526\Z)$ qui sont de cardinalités respective $ (2^2-1)(2^2-2)(3^2-1)(3^2-3)(421^2-1)(421^2-421)=9\,025\,798\,118\,400$ et $ (2^2-1)(2^2-2)(31^2-1)(31^2-31)(4073^2-1)(4073^2-4073)=1\,473\,860\,586\,963\,514\,982\,400$ . Nous n'entrerons pas plus dans le détail. Il est également possible de compliquer davantage en prenant des paquets de 3 ou 4 par exemple et donc être amené à travailler avec des matrices de $ \GL_3(\Z/26\Z)$ ou plus généralement $ \GL_n(\Z/26\Z)$ . Le principe est exactement le même. La seule difficulté réside dans le calcul du déterminant et de la détermination de l'inverse matricielle. Cela n'est pas le but de ce cours (mais ce n'est pas du tout or de portée).

¹C'est à dire par paquet de 2
²C'est par ce type d'attaque qu'Alan Türing a réussi à casser ENIGMA