\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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} } \)

La méthode de César

Principe

Nous voulons crypter le mot BONJOUR. La première étape, comme souvent avant de crypter, est de coder ce message. Dans notre cas, coder signifie transformer le message dans le langage des mathématiques par des associations triviales : $ A=0$ , $ B=1$ etc. \[ \begin{array}{*{6}{c|}c} B&O&N&J&O&U&R\\\hline 1&14&13&9&14&20&17 \end{array} \] Le mot BONJOUR est ainsi codé en 1-14-13-9-14-20-17. Le principe du codage de César consiste à modifier chaque caractère (du texte codé) en lui ajoutant un certain nombre ; par exemple $ 3$ . \[ \begin{array}{*{6}{c|}c} B&O&N&J&O&U&R\\\hline 1&14&13&9&14&20&17\\\hline 4&17&16&12&17&23&20 \end{array} \] Ainsi BONJOUR est crypté en 4-17-16-12-17-23-20. On peut ensuite décoder ce message par les associations inverses $ 0=A$ , $ 1=B$ etc. \[ \begin{array}{*{6}{c|}c} B&O&N&J&O&U&R\\\hline 1&14&13&9&14&20&17\\\hline 4&17&16&12&17&23&20\\\hline E&R&Q&M&R&X&U \end{array} \] Le mot BONJOUR est crypté en ERQMRXU. La clef de cryptage est le nombre utilisé pour le décalage ; dans notre exemple c'est le nombre $ 3$ . Recommençons un exemple et cryptons le mot ZAKARIA avec $ 4$ comme clef de cryptage. \[ \begin{array}{*{6}{c|}c} Z&A&K&A&R&I&A\\\hline 25&0&10&0&17&8&0\\\hline 29&4&14&4&21&12&4\\\hline ?&E&O&E&V&M&E \end{array} \]

Problème :: quelle est la lettre $ 29$ ?
Solution :: l'alphabet latin va de $ A=0$ à $ Z=25$ , mais on peut revenir à $ A$ à partir de $ 26$ . Ainsi $ A=26$ , $ B=27$ , $ C=28$ et donc $ D=29$ .

Ainsi le mot ZAKARIA est crypté en DEOEVME. En fait $ 29=26+3$ et $ D=3$ donc $ D=29$ . Puisque $ A=0$ et que $ A=26$ , on aimerai dire que $ 26=0$ ¹. Nous allons donner un cadre à cette égalité : les congruences.

Le calcul modulaire

Théorème [(Division euclidienne)]

\[\forall a\in \Z,\ \forall b\in \N_{{>}0},\ \exists ! q\in \Z,\ \exists ! r\in \N,\quad \left\{\begin{array}{c} a=bq+r\\ 0\leqslant r {<} b \end{array} \right. \] On nomme $ a$ le dividende, $ b$ le diviseur, $ q$ le quotient et $ r$ le reste.

Démonstration

Existence.: Posons $ q=E\left(\dfrac{a}{b}\right)$ la partie entière de la division réelle de $ a$ par $ b$ et $ r=a-bq$ . Par construction $ a=bq+r$ . De plus, par définition de la fonction partie entière, $ q\leqslant \frac{a}{b}{<}q+1$ soit en multipliant par $ b$ (que nous avons supposé positif) $ bq\leqslant a{<}bq+b$ et en soustrayant finalement par $ bq$ on obtient $ 0\leqslant a-bq{<}b$ et donc $ 0\leqslant r{<}b$ .
Unicité.: Supposons que $ a=bq+r$ et $ a=bq'+r'$ avec $ 0\leqslant r{<}b$ et $ 0\leqslant r'{<}b$ . Alors $ bq+r=bq'+r'$ soit encore $ b(q-q')=r'-r$ or $ -b{<}r'-r{<}b$ soit $ -b{<}b(q-q'){<}b$ . En simplifiant par $ b$ : $ -1{<} q-q'{<}1$ . Or $ q-q'$ est un nombre entier et le seul nombre entier strictement compris entre $ -1$ et $ 1$ est $ 0$ d'où $ q-q'=0$ et donc $ q=q'$ . Pour finir $ r=a-bq=a-bq'=r'$ .

Remarque

$ \bullet$: $ 522=7\times 74+4$ est la division euclidienne de $ 522$ par $ 7$ ; le quotient est $ 74$ et le reste $ 4$ .
$ \bullet$: $ 2015=7\times 286+13$ n'est pas la division euclidienne de $ 2015$ par $ 7$ car ce qui jouerai le rôle du reste, à savoir $ 13$ ne satisfait pas $ 0\leqslant 13 {<} 7$ .
$ \bullet$: $ 2015=286\times7+13$ est la division euclidienne de $ 2015$ par $ 286$ ; le quotient est $ 7$ et le reste $ 13$ .

Définition

Soient $ a$ et $ b$ des entiers, $ b$ étant non nul. On dira que

$ \bullet$: $ b$ divise $ a$
$ \bullet$: $ a$ est un multiple de $ b$
$ \bullet$: $ b$ est un diviseur de $ a$

noté $ b\mid a$ , si le reste de la division euclidienne de $ a$ par $ b$ est nul.

Le nombre $ 666$ divise $ 1998$ .
Le nombre $ 522$ est un multiple de $ 3$ .
Le nombre $ 2$ est un diviseur de $ 6$ .

Proposition

Soient $ a$ et $ b$ des entiers, $ b$ étant non nul. Le nombre $ b$ divise $ a$ si et seulement si il existe un entier $ k$ tel que $ a=bk$ .

Démonstration

D'après le théorème de la division euclidienne, il existe $ k$ et $ r$ tel que $ a=bk+r$ . Par définition de "$ a$ divise $ b$ ", le reste est nul donc, $ a=bk+0=bk$ .

Définition

Soient $ a$ , $ b$ et $ n$ des entiers relatifs tels que $ n\geqslant 2$ . On dira que $ a$ est congru à $ b$ modulo $ n$ si $ a$ et $ b$ ont le même reste dans leur division euclidienne par $ n$ . On note \[a\equiv_n b\]

Proposition

Soient $ a$ , $ b$ et $ n$ des entiers relatifs tels que $ n\geqslant 2$ tels que $ a\equiv_n b$ . Alors $ n$ divise $ a-b$ .

Démonstration

Par définition, puisque $ a\equiv_n b$ , il existe $ q$ , $ q'$ et $ r$ tel que $ a=nq+r$ et $ b=nq'+r$ . En effectuant la différence de ces deux égalités, on obtient $ a-b=nq-nq'$ soit encore en factorisant $ a-b=n(q-q')$ ce qui prouve que $ a-b$ est un multiple de $ n$ .

Autrement dit : $ a\equiv_n b$ si et seulement si il existe un $ k\in \Z$ tel que $ a-b=kn$ . Par exemple :

$ \bullet$: $ 500\equiv_{11}5$ car $ 500-5=495=11\times 45$ .
$ \bullet$: $ 6\equiv_{123456} 6$ car $ 6-6=0=123456\times 0$ .
$ \bullet$: $ 253\equiv_{7} 1$ car $ 253-1=252=7\times 36$ .
$ \bullet$: $ -1\equiv_{2} 1$ car $ -1-1=-2=2\times (-1)$ .

Théorème [(Opérations)]

Soient $ a$ , $ b$ , $ \alpha$ , $ \beta$ et $ n$ des entiers relatifs tels que $ n\geqslant 2$ . \[(a\equiv_n\alpha)\wedge(b\equiv_n\beta) \Longrightarrow \left\{ \begin{array}{ll} (i)&a+b\equiv_n\alpha+\beta\\ (ii)&ab\equiv_n\alpha\beta \end{array} \right. \]

Démonstration

Par définition, il existe des entiers relatifs $ k_a$ et $ k_b$ tels que $ a=\alpha+nk_a$ et $ b=\beta+nk_b$

$ (i)$: $ a+b=(\alpha+nk_a)+(\beta+nk_b)=\alpha+\beta+nk_a+nk_b=(\alpha+\beta)+n(k_a+k_b)$ ce qui traduit que $ a+b\equiv_n\alpha+\beta$ .
$ (ii)$: $ a+b=(\alpha+nk_a)(\beta+nk_b)=\alpha\beta+nk_a\beta+nk_b\alpha+n^2k_ak_b=(\alpha\beta)+n(k_a\beta+k_b\alpha+nk_ak_b)$ ce qui traduit que $ ab\equiv_n\alpha\beta$ .

Corollaire

Soient $ a$ , $ b$ , $ n$ et $ k$ des entiers relatifs tels que $ n\geqslant 2$ et $ k\in \N$ . \[(a\equiv_n b)\Longrightarrow (a^k\equiv_nb^k)\]

Démonstration

On raisonne par récurrence sur $ k\in \N$ , la propriété étant triviale pour $ k=0$ . \begin{eqnarray*} a^{k+1}&\equiv_n&a\times a^k\\ &\equiv_n&a\times b^k\qquad \text{par hypothèse de récurrence}\\ &\equiv_n&b\times b^k \qquad \text{car } a\equiv_nb \text{ ; en utilisant le théorème précédent}\\ &\equiv_n&b^{k+1} \end{eqnarray*} Ce qui achève la récurrence.

$ \bullet$: $ 25\equiv_4 1$ et $ 10\equiv_4 2$ donc $ 35\equiv_4 3$
$ \bullet$: $ 5\equiv_3 2$ et $ 11\equiv_3-1$ donc $ 55\equiv_3-2$
$ \bullet$: $ 10\equiv_91$ donc $ 10^{2016}\equiv_91$

Corollaire

Soient $ a$ , $ b$ , $ c$ , $ \alpha$ , $ \beta$ , $ \gamma$ et $ n$ des entiers relatifs tels que $ n\geqslant 2$ .

Commutativité.: $ a+b\equiv_nb+a$ , $ ab\equiv_nba$
Associativité.: $ (a+b)+c\equiv_na+(b+c)$ , $ (ab)c\equiv_na(bc)$
Element neutre.: $ a+0\equiv_na$ , $ a1\equiv_n a$
Symétrie.: $ a+(-a)\equiv_n 0$
Distributivité.: $ a(b+c)\equiv_n(ab)+(ac)$

Démonstration

Il suffit de revenir à la définition.

Dans la pratique, lorsque l'on veut travailler modulo un entier $ n$ , on a tendance à choisir un représentant dans l'intervalle $ [\![0; n-1]\!]$ ² ce qui est toujours possible d'après le théorème de la division euclidienne.

Proposition

Soient $ a$ et $ n$ des entiers relatifs tels que $ n\geqslant 2$ . Il existe un unique $ \alpha\in[\![0;n-1]\!]$ tel que $ a\equiv_n \alpha$ . On note $ \Z/n\Z$ l'ensemble $ [\![0;n-1]\!]$ munis des opérations d'addition et de multiplication.

Démonstration

Ceci est une conséquence du théorème de la division euclidienne.

Remarque

Avec la "Rigueur" on peut construire $ \Z/n\Z$ plus proprement comme le quotient de $ \Z$ par une certaine relation d'équivalence. Nous n'approfondirons pas ce point de vue mais il faudra garder en tête que les "nombres" que l'on manipulent dans $ \Z/n\Z$ sont en fait des ensembles. Par exemple dans $ \Z/5\Z$ , le nombre $ 1$ cache en fait $ 1$ , $ 6$ , $ 11$ , $ 16$ etc (de $ 5$ en $ 5)$ . C'est pour cela que l'on parle davantage de représentant. Dans ce cas $ 6$ existe dans $ Z/5\Z$ , il est représenté par $ 1$ .

Remarque

Lorsque l'on est amené a effectuer des opérations modulo $ n$ il peut être utile de dessiner les tables de multiplications et d'addition de $ \Z/n\Z$ . Par exemple si $ n=6$ on a \[ \begin{array}{c|cccccc} +&0&1&2&3&4&5\\\hline 0&0&1&2&3&4&5\\ 1&1&2&3&4&5&0\\ 2&2&3&4&5&0&1\\ 3&3&4&5&0&1&2\\ 4&4&5&0&1&2&3\\ 5&5&0&1&2&3&4 \end{array} \] \[ \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} \]

Cryptologie de César

Cryptosystème

Proposition

Soient $ n$ et $ k$ des entiers tels que $ n\geqslant 2$ . \[\forall x\in \Z,\ (x+k)-k\equiv_n x\]

Démonstration

Ceci est une conséquence triviale de l'associativité de la congruence.

Définition

Les données suivantes définissent le cryptosystème de César.

Espace de clefs.: $ \mathcal{K}=\Z/26\Z$
Fonction de chiffrement.: Quelque soit $ k\in \mathcal{K}$ et $ x\in \Z$ , $ C_k(x)\equiv_{26}x+k$
Fonction de déchiffrement.: Quelque soit $ k\in \mathcal{K}$ et $ x\in \Z$ , $ D_k(x)\equiv_{26}x-k$

La proposition précédente justifie que la propriété de déchiffrement est satisfaite.

Remarque

On aurait put définir l'espace de clefs par $ \mathcal{K}=\Z$ mais, puisque les fonctions sont définies modulo $ 26$ , la clef $ 26$ et la clef $ 0$ donnent la même chose.

Si par exemple le message crypté est RTTFIUVFE avec $ 17$ comme clef, on décrypte de la manière suivante. \[ \begin{array}{c|c|c|c|c|c|c|c|cl} R&T&T&F&I&U&V&F&E&\\\hline 17&19&19&5&8&20&21&5&4&\text{Codage (} A=0\text{ , } B=1 \text{ , ...)}\\\hline 0&2&2&-12&-9&3&4&-12&-13&\text{Fonction de déchiffrement }x-17\\\hline 0&2&2&14&17&3&4&14&13&\text{On se place dans }\Z/26\Z \\\hline A&C&C&O&R&D&E&O&N& \end{array} \]

Cryptanalyse

Une attaque en force brute permet en général de casser le cryptage par la méthode de César. Le principe d'une attaque en force brute consiste a essayer toutes les clefs. Par exemple, nous savons qu'un message codé avec la méthode de César est LEDVJJRXVUVTVJRI. On teste toutes les clefs. \[ \begin{array}{c||p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}} Clef&L&E&D&V&J&J&R&X&V&U&V&T&V&J&R&I\\\hline\hline 0 &L&E&D&V&J&J&R&X&V&U&V&T&V&J&R&I\\\hline 1 &K&D&C&U&I&I&Q&W&U&T&U&S&U&I&Q&H\\\hline 2 &J&C&B&T&H&H&P&V&T&S&T&R&T&H&P&G\\\hline 3 &I&B&A&S&G&G&O&U&S&R&S&Q&S&G&O&F\\\hline 4 &H&A&Z&R&F&F&N&T&R&Q&R&P&R&F&N&E\\\hline 5 &G&Z&Y&Q&E&E&M&S&Q&P&Q&O&Q&E&M&D\\\hline 6 &F&Y&X&P&D&D&L&R&P&O&P&N&P&D&L&C\\\hline 7 &E&X&W&O&C&C&K&Q&O&N&O&M&O&C&K&B\\\hline 8 &D&W&V&N&B&B&J&P&N&M&N&L&N&B&J&A\\\hline 9 &C&V&U&M&A&A&I&O&M&L&M&K&M&A&I&Z\\\hline 10 &B&U&T&L&Z&Z&H&N&L&K&L&J&L&Z&H&Y\\\hline 11 &A&T&S&K&Y&Y&G&M&K&J&K&I&K&Y&G&X\\\hline 12 &Z&S&R&J&X&X&F&L&J&I&J&H&J&X&F&W \end{array} \qquad \begin{array}{c||p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}p{0.1cm}} Clef&L&E&D&V&J&J&R&X&V&U&V&T&V&J&R&I\\\hline\hline 13 &Y&R&Q&I&W&W&E&K&I&H&I&G&I&W&E&V\\\hline 14 &X&Q&P&H&V&V&D&J&H&G&H&F&H&V&D&U\\\hline 15 &W&P&O&G&U&U&C&I&G&F&G&E&G&U&C&T\\\hline 16 &V&O&N&F&T&T&B&H&F&E&F&D&F&T&B&S\\\hline 17 &U&N&M&E&S&S&A&G&E&D&E&C&E&S&A&R\\\hline 18 &T&M&L&D&R&R&Z&F&D&C&D&B&D&R&Z&Q\\\hline 19 &S&L&K&C&Q&Q&Y&E&C&B&C&A&C&Q&Y&P\\\hline 20 &R&K&J&B&P&P&X&D&B&A&B&Z&B&P&X&O\\\hline 21 &Q&J&I&A&O&O&W&C&A&Z&A&Y&A&O&W&N\\\hline 22 &P&I&H&Z&N&N&V&B&Z&Y&Z&X&Z&N&V&M\\\hline 23 &O&H&G&Y&M&M&U&A&Y&X&Y&W&Y&M&U&L\\\hline 24 &N&G&F&X&L&L&T&Z&X&W&X&V&X&L&T&K\\\hline 25 &M&F&E&W&K&K&S&Y&W&V&W&U&W&K&S&J \end{array} \] On voit apparaitre, pour la clef $ 17$ , un message de César.

Pour compliquer un peu

Au lieu de chiffrer lettre par lettre, on peut le faire par paquet de deux lettres. Supposons, par exemple, que nous souhaitons chiffrer ONCOMPLIQUECESAR. On commence comme d'habitude par coder ce message. \[ \begin{array}{cc|cc|cc|cc|cc|cc|cc|cc} O &N &C &O &M &P &L &I &Q &U &E &C &E &S &A &R \\\hline 14&13&02&14&12&15&11&08&16&20&04&02&04&18&00&17 \end{array} \] Attention, il est important de mettre les $ 0$ devant les chiffres de $ 0$ à $ 9$ pour que l'on obtienne des nombres à 4 chiffres (avec éventuellement des $ 0$ à gauche). On forme des nombres à 4 chiffres. \[ \begin{array}{cc|cc|cc|cc|cc|cc|cc|cc} O &N &C &O &M &P &L &I &Q &U &E &C &E &S &A &R \\\hline 14&13&02&14&12&15&11&08&16&20&04&02&04&18&00&17\\\hline &{1413}&&{214}&&{1215}&&{1108}&&{1620}&&{402}&&{418}&&{17} \end{array} \] Ainsi le codage de ONCOMPLIQUECESAR est $ 1413$ -$ 214$ -$ 1215$ -$ 1108$ -$ 1620$ -$ 402$ -$ 518$ -$ 17$ (on choisit de mettre des "-" entre les nombres). On ajoute ensuite la clef. On prend $ 2016$ comme clef. \[ \begin{array}{cc|cc|cc|cc|cc|cc|cc|cc} O &N &C &O &M &P &L &I &Q &U &E &C &E &S &A &R \\\hline 14&13&02&14&12&15&11&08&16&20&04&02&04&18&00&17\\\hline &{1413}&&{214}&&{1215}&&{1108}&&{1620}&&{402}&&{418}&&{17}\\\hline &{3429}&&{2230}&&{3231}&&{3124}&&{3636}&&{2418}&&{2434}&&{2033} \end{array} \] Ainsi le message chiffrer est $ 3429$ -$ 2230$ -$ 3231$ -$ 3124$ -$ 3636$ -$ 2418$ -$ 2434$ -$ 2033$ . Bien sur on ne va pas (et surtout on ne peut pas) décoder ce message. Le message crypté est cette suite de nombre. On peut cependant simplifier cette expression. En effet, lorsque l'on chiffrait lettre par lettre on allait de $ A=0$ à $ Z=25$ c'est pour cette raison que l'on travaillait modulo $ 26$ . Dans cet exemple, on code par paquet de $ 2$ ; c'est à dire que l'on va de $ AA=0000$ à $ ZZ=2525$ . Certes il y a des nombres qui ne correspondent à aucune paire de lettre (comme $ 0999$ ) mais le plus grand entier de ce système de chiffrement est $ 2525$ . On va donc travailler modulo $ 2526$ . \[ \begin{array}{cc|cc|cc|cc|cc|cc|cc|cc} O &N &C &O &M &P &L &I &Q &U &E &C &E &S &A &R \\\hline 14&13&02&14&12&15&11&08&16&20&04&02&04&18&00&17\\\hline &{1413}&&{214}&&{1215}&&{1108}&&{1620}&&{402}&&{418}&&{17}\\\hline &{3429}&&{2230}&&{3231}&&{3124}&&{3636}&&{2418}&&{2434}&&{2033}\\\hline &{903}&&{2230}&&{705}&&{598}&&{1110}&&{2418}&&{2434}&&{2033} \end{array} \] Le chiffrement de César ONCOMPLIQUECESAR par paquet de $ 2$ avec $ 2016$ comme clef est $ 903$ -$ 2230$ -$ 705$ -$ 598$ -$ 1110$ -$ 2418$ -$ 2434$ -$ 2033$ . Ce que nous venons de faire par paquet de $ 2$ peut aussi être fait par paquet de $ 3$ , $ 4$ etc... Formalisons.

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 de César par paquet de $ n$ est défini par les données suivantes.

Espace de clefs.: $ \mathcal{K}=\Z/N\Z$
Fonction de chiffrement.: Quelque soit $ k\in \mathcal{K}$ et $ x\in \Z$ , $ C_k(x)\equiv_{N}x+k$
Fonction de déchiffrement.: Quelque soit $ k\in \mathcal{K}$ et $ x\in \Z$ , $ D_k(x)\equiv_{N}x-k$

La propriété de déchiffrement est encore une conséquence de l'associativité. Une attaque en force brute permet de casser la méthode de César par paquet de $ n$ . Par exemple le message suivant est codé avec la méthode de César : $ 212407$ -$ 21819$ -$ 132903$ -$ 232903$ -$ 31804$ -$ 51801$ -$ 82110$ -$ 41002$ -$ 41216$ -$ 242518$ -$ 42699$ . On va donc décrypter ce message pour toutes les clefs et nous afficherons le message claire lorsque nous reconnaitrons des lettres de l'alphabet (entre $ 0$ et $ 25$ ). Mais quel est le nombre de paquet ? Le message crypté contient des nombres tous plus petit que $ 242518$ . Ainsi l'entier $ N$ ne peut pas être $ 26$ ou $ 2526$ . Le premier candidat est $ 252526$ ³ et donc le cryptage se fait par paquet de $ 3$ . Finalement $ 999$ est la clef de cryptage. \[ \begin{array}{p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}|p{0.19cm}} &&{212407} & &&{21819} & &&{132903} & &&{232903} & &&{31804} & &&{51801} & &&{82110} & &&{41002} & &&{41216} & &&{242518} & &&{42699} \\\hline &&{211408}& &&{20820}& &&{131904}& &&{231904}& &&{30805}& &&{50802}& &&{81111}& &&{40003}& &&{40217}& &&{241519}& &&{41700}\\\hline 21&14&08& 02&08&20& 13&19&04& 23&19&04& 03&08&05& 05&08&02& 08&11&11& 04&00&03& 04&02&17& 24&15&19& 04&17&00\\\hline V&O&I& C&I&U& N&T&E& X&T&E& D&I&F& F&I&C& I&L&L& E&A&D& E&C&R& Y&P&T& E&R&A \end{array} \] Et VOICI UN TEXTE DIFFICILLE A DECRYPTER⁴

¹Oui ! Ca fait mal aux yeux.
²L'intervalle noté $ [\![a;b]\!]$ désigne l'ensemble des nombres entiers compris entre $ a$ et $ b$
³"Premier candidat" car si nous n'arrivons pas à déchiffrer le message, on poursuivra avec le "second candidat" : $ 25252526$ . S'il ne fonctionne pas on essayera avec $ 2525252526$ etc.
⁴Avec une belle faute d'orthographe ! A noter qu'il manquait un caractère pour faire 11 paquets de 3. On a rajouté un caractère (en l'occurrence A) à la fin du texte.