\documentclass[12pt]{article}
\usepackage{kbexo}
\course{MHT633 -- Arithmétique et Cryptologie}
\num{2}
\begin{document}
\exotitle[Systèmes de chiffrement symétriques anciens]
\medskip

\noindent On rappelle que dans le cas de l'alphabet usuel à 26 lettres on
utilise la numérotation des lettres de l'alphabet suivante:
\begin{center}
\begin{tabular*}{0.95\textwidth}{@{\extracolsep{\fill}}|*{26}{@{}c}|}
\;\,a & b & c & d & e & f & g & h & i & j & k & l & m & n & o & p & q & r & s & t & u & v & w & x & y & z \\
\hline
\;\,0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25
\end{tabular*}
\end{center}

\exo[Chiffrement affine]
\noindent Étant donnés deux entiers $a$ et $b$,  une
lettre de l'alphabet est identifiée à un élément $x$ de l'anneau $\ZM/26\ZM$
et est chiffrée en $ax+b$. 
\Q Montrez que la fonction de chiffrement est inversible ssi $a
  \mod 26 \in (\ZM/26\ZM)^*$ et calculez son inverse. Précisez les données
$(\mathcal P, \mathcal C,\mathcal K,\mathcal E,\mathcal D)$ de ce
  système de chiffrement. Quel est le cardinal de $\mathcal K$?

\Q Un chiffrement affine dont vous ne connaissez pas la clé a
  chiffré le texte clair \kbd{hahaha} en \kbd{nonono}. Retrouvez la
  clé. (Il s'agit d'une attaque à texte clair connu). Calculez la
  clé de déchiffrement.

\Q Montrez que la composée de deux chiffrements affines est
  encore un chiffrement affine.

\Q Montrez qu'un chiffrement par décalage est un cas particulier
  de chiffrement affine. Montrez qu'un chiffrement affine est un cas
  particulier de chiffrement de substitution.

\Q Généralisez la définition d'un système de chiffrement affine sur l'anneau
  $A=\ZM/m\ZM$. Généralisez l'attaque précédente: que doit avoir en sa
  possession un attaquant pour calculer la clé ?


\exo[Matrices à coefficients dans un anneau]
\noindent Soit $(A,+,\cdot)$ un anneau commutatif et unitaire. 
\Q Montrez que l'ensemble des matrices à $n$ lignes et $n$
  colonnes, à coefficients dans $A$, est un anneau pour l'addition
  et la multiplication des matrices. On le note $M_n(A)$.

\Q Montrez que $M\in M_n(A)$ est inversible si et seulement si $\det(A)$ est
  inversible dans $A$. 

\Q Pour $n=2$, montrez que 
$M=\smallmat{a & b \\c&d}$
est inversible dans $M_2(A)$ si et seulement si $ad-bc \in A^*$ et que 
dans ce cas 
$$
M^{-1}=(ad-bc)^{-1}\begin{pmatrix} d & -b \\-c&a\end{pmatrix}.
$$

\Q On note $\Gl_n(A)$ le groupe des matrices inversibles de
  $M_n(A)$. Montrez que l'ordre de $\Gl_2(\ZM/p\ZM)$ où $p$ est un
  nombre premier est $(p^2-1)(p^2-p)$. \hint{Cherchez quelles
  conditions les colonnes d'une matrice inversible doivent satisfaire.} 

\Q Généralisation: montrez que 
$$
\abs{\Gl_n(\ZM/p\ZM)} = (p^n-1)(p^n-p)(p^n-p^2)\dots (p^n-p^{n-1}).
$$

\exo[Chiffrement de Hill]
\noindent Soit $K\in \Gl_n(A)$, on définit
\begin{align*}
e_K : A^n &\to A^n\\
x &\mapsto xK 
\end{align*}

\Q Montrez qu'on définit ainsi un système de chiffrement symétrique dont on
  précisera les données 
$(\mathcal P, \mathcal C,\mathcal K,\mathcal E,\mathcal D)$.

\Q Exemple numérique: 
\kbd{YIFZMA} est un texte chiffré par un chiffrement de Hill avec
  $n=2$ et $A=\ZM/26\ZM$, de
matrice 
$K=\smallmat{9 & 13 \\ 2 & 3}$.
Retrouvez le clair.

\Q
Eve a volé la machine à chiffrer de Bob, qui utilise un chiffrement de Hill
avec une matrice $2\times 2$ sur $\ZM/26\ZM$. Elle tente une attaque à texte
choisi: le texte clair \kbd{ba} est chiffré en \kbd{HC} et le texte clair
\kbd{zz} est chiffré en \kbd{GT}. Quelle est la clé ? Quelle est la clé de
déchiffrement ? Que pensez-vous des choix de Eve ?

\Q Généralisez l'attaque de Eve (à clair choisi) à un système de chiffrement
de Hill quelconque. 

\Q Montrez que la composée de deux chiffrements de Hill est encore un
chiffrement de Hill. Vous considèrerez le cas de matrices de même taille,
puis de tailles différentes.

\Q Montrez qu'un chiffrement par permutation est un cas particulier d'un
  chiffrement de Hill.

\exo[Chiffrement de Hill affine]
\noindent Soit $K\in \Gl_n(A)$ et $b\in A^n$. On définit 
\begin{align*}
e_K : A^n &\to A^n\\
&x\mapsto xK  +b
\end{align*}

\Q Montrez qu'on définit ainsi un système de chiffrement symétrique dont on
  précisera   les données
$(\mathcal P, \mathcal C,\mathcal K,\mathcal E,\mathcal D)$.

\Q Généralisez l'attaque sur le chiffrement de Hill à ce système.

\exo
\kbd{GEZXDS} est un texte chiffré par un chiffrement de Hill de matrice 
$2\times 2$.
Le clair est \kbd{solved}. Trouvez la clé. Calculez ensuite la clé de
déchiffrement.

\exo (Extrait du DS 2007) Déchiffrer le texte suivant, chiffré avec le
chiffrement affine:
\begin{center}
  \kbd{JGMGJGUFEOVMHTGMENGVFEGJJGM}
\end{center}
On donnera la clef de chiffrement ainsi que la clef de déchiffrement.

%\exo{{\bf Chiffrement à flot par addition d'une suite    pseudo-aléatoire:} 

%Une suite de bits pseudo-aléatoire $s=s_0,s_1,s_2,\dots=(s_n)_{n\geq  0}$ est une suite obtenue à partir d'une clé $K$ et d'un
 % algorithme de génération public. Le chiffrement d'un message
  %clair binaire $m=m_0m_1m_2\dots$ est obtenu par ajout bits à bits
%  de $s$ à $m$, soit $c=e_K(m)=m+s$.
%\begin{enumerate}
%\item Quelle est la fonction de déchiffrement $d_K$ associée ?
%\item Montrez qu'on ne peut pas utiliser  la même sous
%  partie de $s$ pour chiffrer plusieurs messages.
%\item Exemple naïf: le registre à décalage linéaire. Soit $L$
%  un entier, $(c_1,\dots c_L)\in \F_2^L$ et $(s_o,s_1,\dots
%  s_{L-1})\in \F_2^L$. On définit $s_n$ pour tout $n\geq L$ par la
%  relation de récurrence:
%\begin{equation*}
%s_n=c_1s_{n-1}+c_2s_{n-2}+\dots +c_Ls_{n-L}.
%\end{equation*}
%\begin{enumerate}
%\item Montrez que le nombre de suites $s$ ainsi définies, lorsque
%  les coefficients $c_i$ sont fixés, est $2^L$.
%\item Montrez que, si $c_L=1$,  on peut calculer l'initialisation
%  $s_0\dots s_{L-1}$  à partir des coefficients $c_i$ et de $L$ bits
%  consécutifs de $s$.
%\item 
%\end{enumerate}
%\end{enumerate}
%}

\end{document}
