La méthode affine
Principe
La fonction de chiffrement par la méthode affine est une généralisation de la méthode de César.
Au lieu de prendre comme fonction de chiffrement une fonction
linéaire de la forme \( C(x)\equiv_{26}x+k\) on va considérer une fonction
affine comme par exemple \( C(x)\equiv_{26} 2x+3\) .
Chiffrons le message
BONJOUR.
\[
\begin{array}{*{6}{c|}c}
B&O&N&J&O&U&R\\\hline
1&14&13&9&14&20&17\\\hline
5&5&3&21&5&17&11\\\hline
F&F&D&V&F&R&L
\end{array}
\]
La première observation que nous pouvons faire est que la lettre
B est cryptée en
F et que la lettre
O est également cryptée en
F. Si nous recevons ce message comment pourrons-nous faire la différence entre le
F qui est le cryptogramme de la lettre
B et celui qui est le cryptogramme de la lettre
O ?
Quelle est la fonction de déchiffrement ? Si nous travaillions avec nombres réels (on "oublie" le modulo \( 26\) ), on vérifierai rapidement que la fonction \( D(x)=\dfrac{1}{2}(x-3)\) satisfait la propriété de déchiffrement \( D(C(x))=x\) . Quel est l'équivalent du \( \dfrac{1}{2}\) modulo \( 26\) ? Pour répondre à cette question nous allons avoir besoin de définir l'inverse modulaire.
L'inverse modulaire
Définition
Soit \( a\in \Z\) . On note \( D(a)\) l'ensemble des diviseurs positifs de \( a\) .
\[D(a)=\Big\{x\in \N\Big|\ x\mid a\Big\}\]
Par exemple \( D(132)=\{1,2,3,4,6,12,11,22,33,44,66,132\}\) .
Proposition
Soient \( a\) et \( b\) deux diviseurs positifs d'un entier \( n\) tel que \( n=ab\) .
\[(a\leqslant\sqrt{n})\ \vee\ (b\leqslant \sqrt{n})\]
Démonstration
Raisonnons par l'absurde. S'il existe deux diviseurs \( a\) et \( b\) de \( n\) tel que \( a{>}\sqrt{n}\) et \( b{>}\sqrt{n}\) alors \( ab{>}\sqrt{n}^2=n\) et \( n{>}n\) ce qui est impossible.
Dans la pratique, pour la recherche des diviseurs d'un entiers, on va chercher à le factoriser par des entiers allant de \( 1\) jusqu'à sa racine carré (sa partie entière précisement).
Par exemple déterminons \( D(108)\) . Puisque \( \sqrt{108}\simeq 10.3923\) . On va chercher à factoriser \( 108\) par des entiers entre \( 1\) et \( 10\) .
\begin{eqnarray*}
108&=&1\times 108\\
&=&2\times 54\\
&=&3\times 36\\
&=&4\times 27\\
&=&6\times 18\\
&=&9\times 12
\end{eqnarray*}
Ainsi \( D(108)=\{1,2,3,4,6,9,12,18,27,36,54,108\}\) .
Définition
Le plus grand commun diviseur entre deux entiers \( a\) et \( b\) , noté \( PGCD(a,b)\) , est le plus grand entier de l'ensemble \( D(a)\cap D(b)\) .
Par exemple \( PGCD(132,108)=12\) car \( D(132)\cap D(108)=\{1,2,3,4,6,12\}\) .
Lemme
Soient \( a\) et \( b\) des entiers non nuls.
\[D\big(PGCD(a,b)\big)=D(a)\cap D(b)\]
Démonstration
Ceci est une conséquence de la construction du \( PGCD\) .
Théorème [Caractérisation du PGCD]
Soient \( a\) , \( b\) et \( d\) des entiers non nuls.
\[\Big((d\mid a)\wedge (d\mid b)\Big)\Longleftrightarrow \Big(d\mid PGCD(a,b)\Big)\]
Démonstration
Il s'agit d'une reformulation du lemme précédent.
Corollaire [Algorithme d'Euclide]
Soit \( a=bq+r\) une division euclidienne de deux entiers \( a\) et \( b\) .
\[PGCD(a,b)=PGCD(b,r)\]
Démonstration
Notons \( d=PGCD(a,b)\) et \( d'=PGCD(b,r)\) .
Puisque \( d\) est un diviseur de \( a\) et \( b\) , il est nécessairement un diviseur de \( r=a-bq\) . Ainsi \( d\) est un diviseur de \( b\) et de \( r\) donc de leur \( PGCD\) à savoir \( d'\) .
De la même manière, puisque \( d'\) est un diviseur de \( b\) et \( r\) , c'est aussi un diviseur de \( a=bq+r\) . Ainsi \( d'\) est un diviseur de \( b\) et de \( a\) donc de leur \( PGCD\) à savoir \( d\) .
Nous venons de montrer que \( d\) est un diviseur de \( d'\) qui est lui même un diviseur de \( d\) . Nécessairement \( d=d'\) .
Remarque
Dans la pratique, lorsque l'on veut déterminer le \( PGCD\) entre deux entiers, on va réaliser des divisions euclidiennes successives en remplaçant à chaque fois, dividende et diviseur par diviseur et reste jusqu'à obtenir un reste nul, ce qui sera toujours possible par la construction de \( \N\) (toute partie non vide de \( \N\) admet un plus petit élément). Le \( PGCD\) est le dernier reste non nul.
Pour ordonner les idées, on place ces données dans un tableau, chaque ligne représentant une division euclidienne \( a=bq+r\) .
\[
\begin{array}{c|c|c|c}
a&b&r&q\\\hline\hline
132&108&24&1\\
108&24&\boxed{12}&4\\
24&12&0&2
\end{array}
\]
Ainsi le \( PGCD\) est \( 12\) .
Définition
Soient \( a\) , \( b\) et \( n\) des entiers tels que \( n\geqslant 2\) . On dira que \( b\) est l'inverse de \( a\) modulo \( n\) si \( ab\equiv_n 1\)
Par exemple \( 3\) est l'inverse de \( 7\) modulo \( 20\) car \( 7\times3=21\equiv_{20}1\) .
La question naturelle est de savoir si tous les nombres modulaires ont un inverse et accessoirement comment le trouver.
Définition
On dira que deux entiers \( a\) et \( b\) sont premiers entre eux si \( PGCD(a,b)=1\) .
Par exemple \( 24\) et \( 25\) sont premiers entre eux.
Théorème [Identité de Bachet-Bézout]
Deux entiers \( a\) et \( b\) sont premiers entre eux si et seulement si il existe \( u\in \Z\) et \( v\in \Z\) tel que \( au+bv=1\) .
Démonstration
Si \( d\) est le \( PGCD\) de \( a\) et \( b\) alors puisque \( au+bv=1\) , on en déduit que \( d\) est un diviseur de \( 1\) et le seul diviseur positif de \( 1\) est \( 1\) et donc \( a\) et \( b\) sont premiers entre eux.
La réciproque se déduit de l'algorithme d'Euclide étendue que nous détaillerons par la suite.
Corollaire
Soient \( a\) et \( n\) des entiers tels que \( n\geqslant 2\) . L'entier \( a\) admet un inverse modulo \( n\) si et seulement si \( a\) et \( n\) sont premiers entre eux.
Démonstration
D'après l'identité de Bachet-Bézout, les entiers \( a\) et \( n\) sont premiers entre eux si et seulement s'il existe \( u\in \Z\) et \( v\in \Z\) tel que \( au+nv=1\) , ce qui équivaut à dire que \( au\equiv_n1\) (puisque \( n\equiv_n0\) ) et \( u\) est l'inverse modulaire de \( a\) .
§
Pour déterminer l'inverse modulaire d'un entier, on applique l'algorithme d'Euclide étendue. Détaillons un exemple et cherchons l'inverse de \( 382\) modulo \( 2365\) . Pour que cela soit au moins possible, nous devons déterminer le \( PGCD\) de ces deux entiers. Appliquons l'algorithme d'Euclide.
\[
\begin{array}{c|c|c|c}
a&b&r&q\\\hline\hline
2365&382&73&6\\
382&73&17&5\\
73&17&5&4\\
17&5&2&3\\
5&2&1&2\\
2&1&0&2
\end{array}
\]
Puisque le dernier reste non nul est \( 1\) , on en déduit que \( 2365\) et \( 382\) sont premiers entre eux. D'après le corollaire précédent, il existe un inverse modulaire. Pour le trouver, il faut déterminer \( u\) et \( v\) tels que \( 2365u+382v=1\) . Pur cela nous allons rajouter au tableau de l'algorithme d'Euclide deux colonnes \( u\) et \( v\) .
On va remplir ce tableau par le bas en initialisant \( u\) et \( v\) par des valeurs évidentes \( 0\) et \( 1\) respectivement.
On peut vérifier, qu'à cette dernière ligne, on a bien \( au+bv=1\) (\( 2\times0+1\times1=1\) ).
\[
\begin{array}{c|c|c|c|c|c}
a&b&r&q&u&v\\\hline\hline
2365&382&73&6&&\\
382&73&17&5&&\\
73&17&5&4&&\\
17&5&2&3&&\\
5&2&1&2&&\\
2&1&0&2&0&1
\end{array}
\]
On va remplir la ligne du dessus. On va mettre la valeur de \( v\) dans la nouvelle case de \( u\) .
Pour la nouvelle valeur de \( v\) on va mettre \( -q\times\underset{NEW}{u}+\underset{OLD}{u}\) où \( \underset{NEW}{u}\) représente le nouveau \( u\) (ici \( 1\) ) et \( \underset{OLD}{u}\) l'ancienne valeur (ici \( 0\) ).
\[
\begin{array}{c|c|c|c|c|c}
a&b&r&q&u&v\\\hline\hline
2365&382&73&6&&\\
382&73&17&5&&\\
73&17&5&4&&\\
17&5&2&3&&\\
5&2&1&2&1&-2\\
2&1&0&2&0&1
\end{array}
\]
On recommence : à la ligne de dessus, on place l'ancienne valeur de \( v\) comme nouvelle valeur de \( u\) et pour la nouvelle valeur de \( v\) le résultat de \( -q\times\underset{NEW}{u}+\underset{OLD}{u}\) . Ici \( \underset{NEW}{u}=-2\) et \( \underset{OLD}{u}=1\) .
\[
\begin{array}{c|c|c|c|c|c}
a&b&r&q&u&v\\\hline\hline
2365&382&73&6&&\\
382&73&17&5&&\\
73&17&5&4&&\\
17&5&2&3&-2&7\\
5&2&1&2&1&-2\\
2&1&0&2&0&1
\end{array}
\]
On peut vérifier qu'à chaque ligne \( au+bv=1\) (par exemple, notre dernier calcul permet d'aboutir à \( 17\times(-2)+5\times7=1\) ).
On réitère pour aboutir à :
\[
\begin{array}{c|c|c|c|c|c}
a&b&r&q&u&v\\\hline\hline
2365&382&73&6&157&-972\\
382&73&17&5&-30&157\\
73&17&5&4&7&-30\\
17&5&2&3&-2&7\\
5&2&1&2&1&-2\\
2&1&0&2&0&1
\end{array}
\]
Nous avons donc trouvé : \( 2365\times157+382\times(-972)=1\) .
Pour finir (la question de départ était de trouver l'inverse de \( 382\) modulo \( 2365\) ), regardons cette égalité modulo \( 2365\) (on rappel que \( 2365\equiv_{2365}0\) ) : \( 382\times(-972)\equiv_{2365}1\) et \( -972\) est l'inverse modulaire de \( 382\) . On peut choisir un représentant positif : \( -972\equiv_{2365}-972+2365=1393\) et on peut donc conclure que l'inverse de \( 382\) modulo \( 2365\) est \( 1393\) .
Définition
Soit \( n\) un entier supérieur ou égal à \( 2\) . On note \( \big(\Z/n\Z\big)^\times\) l'ensemble des éléments de \( \Z/n\Z\) qui admette un inverse modulaire.
De manière équivalente (d'après l'identité de Bachet-Bézout), les éléments inversibles de \( \big(\Z/n\Z\big)^\times\) sont les éléments de \( \Z/n\Z\) premiers avec \( n\) .
On peut repérer les inverses modulaires dans la table de multiplication
1. Prenons par exemple \( n=6\) .
En détectant les \( 1\) , on identifie les éléments inversibles.
\( 1\times 1\equiv_6 1\) et \( 5\times 5 \equiv_6 1\) . Les seuls éléments inversibles modulo \( 6\) sont \( 1\) et \( 5\) qui sont par le même occasion, les seuls éléments de \( \Z/6\Z\) premiers avec \( 6\) .
\[
\begin{array}{c|cccccc}
\times&0&1&2&3&4&5\\\hline
0&0&0&0&0&0&0\\
1&0&1&2&3&4&5\\
2&0&2&4&0&2&4\\
3&0&3&0&3&0&3\\
4&0&4&2&0&4&2\\
5&0&5&4&3&2&1
\end{array}
\]
On peut alors grossièrement écrire \( \big(\Z/n\Z\big)^\times=\{1,5\}\) .
Digression : équations modulaires
Équations diophantiennes
Définition
Une équation diophantienne est une équation polynomiale à une ou plusieurs inconnues dont les solutions sont cherchées parmi les nombres entiers.
Nous nous intéressons aux équations linéaire de degrés 1, c'est à dire de la forme \( ax+by=c\) . L'identité de Bachet-Bézout, l'algorithme d'Euclide étendu et le lemme de Gauss sont les ingrédients de sa résolution.
Lemme
(Gauss)
Soient \( a\) , \( b\) et \( c\) des entiers.
\[\Big(a|bc \wedge PGCD(a,b)=1\Big)\Rightarrow a|c\]
Démonstration
Par définition \( a|bc\) se traduit par l'existence d'un entier \( k\) tel que \( bc=ak\) . L'identité de Bachet-Bézout permet de trouver \( u\) et \( v\) tel que \( au+bv=1\) ce qui donne en multipliant par \( c\) , \( acu+bcv=c\) soit encore \( acu+akv=c\) . Le terme de gauche est multiple de \( a\) donc \( c\) est multiple de \( a\) .
Théorème [Résolution des équations diophantiennes linéaire d'ordre 1]
Considérons l'équation diophantienne d'inconnues \( x\) et \( y\)
\[ax+by=c\]
Notons \( d=PGCD(a,b)\) , \( a'=\dfrac{a}{d}\) , \( b'=\dfrac{b}{d}\) et \( (u,v)\in \Z^2\) tel que \( a'u+b'v=1\) , ce qui est possible puisque \( a'\) et \( b'\) sont premiers entre eux.
- \( \bullet\)
- Si \( c\) ne divise pas \( d\) alors il n'existe aucune solution entière.
- \( \bullet\)
- Si \( d|c\) , notons \( c'=\dfrac{c}{d}\) . Toutes les solutions entières sont de la forme
\[
\begin{array}{rcl}
x&=&c'u-b'k\\
y&=&c'v+a'k
\end{array}
\]
pour \( k\in \Z\) .
Démonstration
Vérifions tout d'abord que les données sont solutions.
\begin{eqnarray*}
ax+by
&=& da'(c'u-b'k) + db'(c'v+a'k)\\
&=& da'c'u-da'b'k + db'c'v+db'a'k\\
&=& da'c'u + db'c'v\\
&=& dc'(a'u + b'v)\\
&=& c
\end{eqnarray*}
Réciproquement. En simplifiant par \( d\) , l'équation donne \( a'x+b'y=c'\) où \( a'\) et \( b'\) sont premiers entre eux. L'identité de Bachet-Bézout permet de trouver \( u\) et \( v\) tel que \( a'u+b'v=1\) . En multipliant cette égalité par \( c'\) on arrive à \( a'(c'u)+b'(c'v)=c'\) ce qui implique que \( a'(x-c'u)+b'(y-c'v)=0\) . Cette égalité nous informe qu \( a'|b'(y-c'v)\) mais puisque \( a'\) et \( b'\) sont premier entre eux, le lemme de Gauss permet d'affirmer que \( a'|(y-c'v)\) . C'est à dire qu'il existe \( k\in \Z\) tel que \( y-c'v=a'k\) c'est à dire \( y=c'v+a'k\) . En substituant cette valeur de \( y\) dans \( a'(x-c'u)+b'(y-c'v)=0\) on trouve que \( x=c'u-b'k\) .
Par exemple \( 6x+4y=19\) n'admet pas de solution entière.
Autre exemple, \( 6x+4y=18\) admet des solutions entières de la forme
\[
\begin{array}{rcl}
x&=&9+2k\\
y&=&-9-3k
\end{array}
\]
pour \( k\in \Z\) .
Lemme chinois
On s'intéresse à résoudre des systèmes d'équations modulaires de la forme
\[
\left\{
\begin{array}{rcl}
x&\equiv_n&a\\
x&\equiv_m&b
\end{array}
\right.
\]
L'outil fondamentale est le lemme chinois.
Théorème [Lemme chinois]
Soient \( n\) et \( m\) deux entiers premiers entre eux.
\[\Z/n\Z\times\Z/m\Z=\Z/nm\Z\]
Démonstration
Considérons l'application bien définie suivante
\begin{eqnarray*}
\varphi : \Z/nm\Z&\longrightarrow&\Z/n\Z\times\Z/m\Z\\
x&\longmapsto&(x_n, x_m)
\end{eqnarray*}
où \( x_n\) représente \( x\) modulo \( n\) et \( x_m\) modulo \( m\) .
Pour prouver le théorème il faut prouver que ce morphisme est une bijection, ce qui se résume à trouver l'application inverse. Si on se donne \( (a,b)\in \Z/n\Z\times\Z/m\Z\) on cherche un \( x\in \Z/nm\Z\) tel que \( x_n\equiv_na\) et \( x_m\equiv_mb\) .
D'après l'identité de Bachet-Bézout, puisque \( n\) et \( m\) sont premiers entre eux, il existe \( u\) et \( v\) dans \( \Z\) tel que \( nu+mv=1\) . En particulier \( mv\equiv_n1\) et \( nu\equiv_m1\) . On pose alors \( x\equiv_{nm}nub+mva\) . On observe alors que \( x\equiv_{n}\underbrace{nub}_{\equiv_n0}+\underbrace{mv}_{\equiv_n1}a\equiv_na\) . De même \( x\equiv_{m}\underbrace{nu}_{\equiv_m1}b+\underbrace{mva}_{\equiv_m0}\equiv_mb\) .
Corollaire
Soient \( n\) et \( m\) des entiers premiers entre eux et \( a\) et \( b\) dans \( \Z\) . Soient \( (u,v)\in \Z^{2}\) une solution de l'équation diophantienne \( nx+my=1\) .
\[
\left\{
\begin{array}{rcl}
x&\equiv_n&a\\
x&\equiv_m&b
\end{array}
\right. \Longleftrightarrow x \equiv_{nm} nub+mva
\]
Considérons par exemple le système
\(
\left\{
\begin{array}{rcl}
x&\equiv_3&1\\
x&\equiv_4&2
\end{array}
\right.
\)
Sans besoin d'appliquer l'algorithme d'Euclide étendu, on observe que \( 3\) et \( 4\) sont premiers entre eux et \( 3\times(-1)+4\times(1)=1\) . Alors les solutions de ce système sont de la forme \( x\equiv_{12}3\times(-1)\times 2+4\times(1)\times 1\equiv_{12}-2\equiv_{12}10\) .
Ainsi toutes les solutions sont de la forme \( x=10+12k\) pour \( k\in \Z\) .
Cryptologie affine
Cryptosystème
Proposition
Soit \( a\) , \( b\) et \( n\) des entiers tel que \( n\geqslant 2\) et \( PGCD(a,n)=1\) . Notons \( a^{-1}\) l'inverse de \( a\) modulo \( n\)
\[\forall x\in \Z,\ a^{-1}\big((ax+b)-b\big)\equiv_n x\]
Démonstration
Cela est une conséquence de la distributivité.
Définition
Les données suivantes définissent le
cryptosystème affine.
- Espace des clefs.
- \( \mathcal{K}=\big(\Z/26\Z\big)^\times\times \big(\Z/26\Z\big)\)
- Fonction de chiffrement.
- Quelque soit \( (a,b)\in \mathcal{K}\) et \( x\in \Z\) , \( C_{(a,b)}(x)\equiv_{26}ax+b\) .
- Fonction de déchiffrement.
- Quelque soit \( (a,b)\in \mathcal{K}\) et \( x\in \Z\) , \( D_{(a,b)}(x)\equiv_{26}a^{-1}(x-b)\) où \( a^{-1}\) désigne l'inverse de \( a\) modulo \( 26\) .
La proposition précédente justifie que la propriété de déchiffrement est satisfaite.
Dans l'exemple d'introduction de ce chapitre nous avions crypté le message
BONJOUR avec \( 2x+3\) comme fonction de chiffrement. Nous avions obtenue le message
FFDVFRL et nous avions d'ailleurs remarqué qu'il allait être difficile de distinguer le
F qui est un
B du
F qui est un
O. En fait la méthode de chiffrement utilisée n'est pas bonne car \( 2\) n'est pas inversible modulo \( 26\) (car \( PGCD(26,2)=2\) ).
Le message suivant est chiffré par la méthode affine avec \( (3,2)\) comme clef (cette clef est valide puisque \( 3\) est premier avec \( 26\) et admet donc un inverse modulaire) :
NSAIAKPMOEECUOCRRAPO.
Pour déchiffrer ce message, déterminons l'inverse modulaire de \( 3\) .
\[
\begin{array}{c|c|c|c|c|c}
a&b&r&q&u&v\\\hline\hline
26&3&2&8&-1&9\\
3&2&1&1&1&-1\\
2&1&0&2&0&1
\end{array}
\]
Ainsi, \( 26\times(-1)+3\times 9=1\) . En regardant cette égalité modulo \( 26\) , on arrive à \( 3\times 9\equiv_{26}1\) et \( 9\) est l'inverse modulaire de \( 3\) . La fonction de déchiffrement est alors \( D_{(3,2)}(x)\equiv_{26}9(x-2)\) . Déchiffrons le message.
\[
\begin{array}{c|*{20}{|c}}
&N&S&A&I&A&K&P&M&O&E&E&C&U&O&C&R&R&A&P&O\\\hline
&13&18 &0 & 8& 0&10&15&12&14&4&4&2&20&14&2&17&17& 0&15&14\\\hline
-2 &11&16 &-2& 6 &-2& 8 &13 &10& 12&2 & 2&0&18 &12 &0&15& 15& -2&13&12\\\hline
\times 9 &99&144&-18&54&-18&72&117&90&108&18&18&0&162&108&0&135&135&-18&117&108\\\hline
\equiv_{26}&21&14 &8 &2 &8&20&13 &12& 4&18&18&0& 6& 4&0& 5& 5& 8& 13& 4\\\hline
&V&O&I&C&I&U&N&M&E&S&S&A&G&E&A&F&F&I&N&E
\end{array}
\]
Et
VOICI UN MESSAGE AFFINE
Cryptanalyse
Dans le cas de la méthode affine, une attaque en force brute permet en général de casser le message crypté.
On peut montrer qu'il y a \( 12\) éléments de \( Z/26\Z\) qui sont inversibles. La cardinalité de l'espace des clefs pour la méthode affine est donc de \( 12\times 26=312\) . C'est un nombre important sur le papier mais dérisoire du point de vu de l'informatique.
Voici un exemple (nous ne présentons pas les \( 312\) clefs possibles). Le message reçu est
TNCYGA.
\[\begin{array}{c|c||cccccc}
(a,b) & a^{-1} && & & & &\\\hline\hline
(17,0) & 23 &V&N&U&G&I&A\\\hline
(17,1) & 23 &Y&Q&X&J&L&D\\\hline
(17,2) & 23 &B&T&A&M&O&G\\\hline
(17,3) & 23 &E&W&D&P&R&J\\\hline
(17,4) & 23 &H&Z&G&S&U&M\\\hline
(17,5) & 23 &K&C&J&V&X&P\\\hline
(17,6) & 23 &N&F&M&Y&A&S\\\hline
(17,7) & 23 &Q&I&P&B&D&V\\\hline
(17,8) & 23 &T&L&S&E&G&Y\\\hline
(17,9) & 23 &W&O&V&H&J&B\\\hline
(17,10) & 23 &Z&R&Y&K&M&E\\\hline
(17,11) & 23 &C&U&B&N&P&H\\\hline
(17,12) & 23 &F&X&E&Q&S&K\\\hline
(17,13) & 23 &I&A&H&T&V&N\\\hline
(17,14) & 23 &L&D&K&W&Y&Q\\\hline
(17,15) & 23 &O&G&N&Z&B&T\\\hline
(17,16) & 23 &R&J&Q&C&E&W\\\hline
(17,17) & 23 &U&M&T&F&H&Z\\\hline
(17,18) & 23 &X&P&W&I&K&C\\\hline
(17,19) & 23 &A&S&Z&L&N&F\\\hline
(17,20) & 23 &D&V&C&O&Q&I\\\hline
(17,21) & 23 &G&Y&F&R&T&L\\\hline
(17,22) & 23 &J&B&I&U&W&O\\\hline
(17,23) & 23 &M&E&L&X&Z&R\\\hline
(17,24) & 23 &P&H&O&A&C&U\\\hline
(17,25) & 23 &S&K&R&D&F&X
\end{array}\]
\[\begin{array}{c|c||cccccc}
(a,b) & a^{-1} && & & & &\\\hline\hline
(19,0) & 11 &B&N&W&E&O&A\\\hline
(19,1) & 11 &Q&C&L&T&D&P\\\hline
(19,2) & 11 &F&R&A&I&S&E\\\hline
(19,3) & 11 &U&G&P&X&H&T\\\hline
(19,4) & 11 &J&V&E&M&W&I\\\hline
(19,5) & 11 &Y&K&T&B&L&X\\\hline
(19,6) & 11 &N&Z&I&Q&A&M\\\hline
(19,7) & 11 &C&O&X&F&P&B\\\hline
(19,8) & 11 &R&D&M&U&E&Q\\\hline
(19,9) & 11 &G&S&B&J&T&F\\\hline
(19,10) & 11 &V&H&Q&Y&I&U\\\hline
(19,11) & 11 &K&W&F&N&X&J\\\hline
(19,12) & 11 &Z&L&U&C&M&Y\\\hline
(19,13) & 11 &O&A&J&R&B&N\\\hline
(19,14) & 11 &D&P&Y&G&Q&C\\\hline
(19,15) & 11 &S&E&N&V&F&R\\\hline
(19,16) & 11 &H&T&C&K&U&G\\\hline
(19,17) & 11 &W&I&R&Z&J&V\\\hline
(19,18) & 11 &L&X&G&O&Y&K\\\hline
(19,19) & 11 &A&M&V&D&N&Z\\\hline
(19,20) & 11 &P&B&K&S&C&O\\\hline
(19,21) & 11 &E&Q&Z&H&R&D\\\hline
(19,22) & 11 &T&F&O&W&G&S\\\hline
(19,23) & 11 &I&U&D&L&V&H\\\hline
(19,24) & 11 &X&J&S&A&K&W\\\hline
(19,25) & 11 &M&Y&H&P&Z&L
\end{array}\]
Et on gagne une bonne chose avec la fonction de chiffrement \( 19x+2\) qui admet \( 11(x-2)\) comme fonction de déchiffrement.
Pour compliquer un peu
Exactement de la même manière que pour la méthode de César, on peut raisonner en paquet.
Définition
Soit \( n\geqslant 1\) un entier. Posons \( \dpl{N=\left(\sum_{i=0}^{n-1}25\times10^{2i}\right)+1=\underbrace{25...2525}_{n \times}+1=25...2526}\) . Le
cryptosystème affine par paquet de \( n\) est défini par les données suivantes.
- Espace de clefs.
- \( \mathcal{K}=\Big(\Z/N\Z\Big)^\times\times\Big(\Z/N\Z\Big)\)
- Fonction de chiffrement.
- Quelque soit \( (a,b)\in \mathcal{K}\) et \( x\in \Z\) , \( C_{(a,b)}(x)\equiv_{N}ax+b\)
- Fonction de déchiffrement.
- Quelque soit \( (a,b)\in \mathcal{K}\) et \( x\in \Z\) , \( D_{(a,b)}(x)\equiv_{N}a^{-1}(x-b)\) où \( a^{-1}\) désigne l'inverse de \( a\) modulo \( N\) .
Considérons par exemple, la clef \( (2017,123)\) . Il faut d'abord s'assurer que \( 2017\) est bien inversible modulo \( 2526\) . Pour ce faire, on applique l'algorithme d'Euclide étendu.
\[
\begin{array}{|c|c|c|c|c|c|}
\hline
a&b&r&q&u&v\\\hline
2526&2017&509&1&531&-665\\\hline
2017&509&490&3&-134&531\\\hline
509&490&19&1&129&-134\\\hline
490&19&15&25&-5&129\\\hline
19&15&4&1&4&-5\\\hline
15&4&3&3&-1&4\\\hline
4&3&1&1&1&-1\\\hline
3&1&0&3&0&1\\\hline
\end{array}
\]
Ainsi \( 2526\times531+2017\times(-665)=1\) . En regardant cette égalité modulo \( 2526\) , on arrive à \( 2017\times(-665)\equiv_{2526}1\) et \( -665\equiv_{2526}1861\) est l'inverse de \( 2017\) modulo \( 2526\) .
Ceci prouve que \( (2017, 123)\) est bien une clef du cryptosystème affine. On obtient de plus que la fonction de déchiffrement est \( D_{(2017,123)}(x)\equiv_{2526}1861(x-123)\) .
Déchiffrons le message
701-211-1485-2369-1306-1215-852-816-861 obtenu en appliquant la méthode affine par paquet de \( 2\) avec \( (2017, 123)\) comme clef.
\[
\begin{array}{l*{18}{|c}}
\text{Message chiffré}&&{701}&&{211}&&{1485}&&{2369}&&{1306}&&{1215}&&{852}&&{816}&&{861}\\\hline
\text{Déchiffrement}&&{2108}&&{2104}&&{1104}&&{1802}&&{1417}&&{1308}&&{207}&&{1413}&&{1800}\\\hline
\text{Paquettage}&21&08&21&04&11&04&18&02&14&17&13&08&02&07&14&13&18&00\\\hline
\text{Décodage}&V&I&V&E&L&E&S&C&O&R&N&I&C&H&O&N&S&A
\end{array}
\]
1Si l'entier \( n\) n'est pas trop grand ! A ne pas faire pour \( n=2365\) !
