\documentclass[12pt]{amsart}
\usepackage{kb}
\title{RIJNDAEL -- AES}
\author{}

\def\TABgen#1{
  \begin{array}{|c|c|c|c|} \hline
  #1_{0,0} & #1_{0,1} & #1_{0,2} & #1_{0,3} \\ \hline
  #1_{1,0} & #1_{1,1} & #1_{1,2} & #1_{1,3} \\ \hline
  #1_{2,0} & #1_{2,1} & #1_{2,2} & #1_{2,3} \\ \hline
  #1_{3,0} & #1_{3,1} & #1_{3,2} & #1_{3,3} \\ \hline
  \end{array}
}
\def\MATgen#1{
  \begin{pmatrix}
  #1_{0,0} & #1_{0,1} & #1_{0,2} & #1_{0,2} \\
  #1_{1,0} & #1_{1,1} & #1_{1,2} & #1_{1,3} \\
  #1_{2,0} & #1_{2,1} & #1_{2,2} & #1_{2,3} \\
  #1_{3,0} & #1_{3,1} & #1_{3,2} & #1_{3,3} 
  \end{pmatrix}
}

\begin{document}
\maketitle

Nous décrivons les grandes lignes de l'algorithme de chiffrement
symétrique \textsc{rijndael}, utilisé comme \emph{Advanced Encryption
Standard} (\textsc{aes}) depuis 2002, en remplacement de \textsc{des} et
\textsc{Triple des}. C'est un chiffrement itératif par bloc, qui admet des
clés de 128, 192 ou 256 bits; le nombre \texttt{Nb} de tours est
respectivement de 10, 12 ou 14 pour chacune des tailles de clé.

Chaque bloc contient $16 \times 8 = 128$ bits et est constitué de $16$
octets, rangés dans un tableau $4 \times 4$ :
$$ \TABgen{a} $$
On considère le corps fini $\FM_{256} = \FM_{2}[X]/(T)$, défini par le
polynôme irréductible $T(X) = X^8+X^4+X^3+X+1\in \FM_2[X]$; on note $\alpha$
la classe de $X$ dans $\FM_{256}$. Chaque octet
$(b_7,\dots,b_0)\in(\FM_{2})^8$ est identifié avec l'élément $\sum_{i=0}^7
b_i \alpha^i\in \FM_{256}$.

\textsc{Rijndael} utilise 4 opérations élémentaires, agissant successivement
sur un bloc donné; elles sont spécifiées plus loin:
\begin{itemize}
\item \texttt{SubBytes} ($S$-box),
\item \texttt{ShiftRows},
\item \texttt{MixColumns},
\item \texttt{AddRoundKey}.
\end{itemize}
Un algorithme de \emph{cadencement de clé} calcule à partir de la clé $K$
une suite de $\texttt{Nb} + 1$ sous-clés de tour
$(K_0,\dots,K_{\texttt{Nb}})$, comportant toutes $16$ octets. Le texte à
chiffrer est découpé en blocs de 16 octets et, pour chaque bloc clair, on
effectue les opérations suivantes pour produire un bloc chiffré de même
longueur:
\begin{enumerate}
\item On initialise un tableau $4\times 4$ avec 16 octets de texte clair; on
applique successivement sur ce tableau les opérations suivantes.
\item \texttt{AddRoundKey}$(K_0)$.
\item On effectue $\texttt{Nb}-1$ tours comportant les 4 étapes
\texttt{SubBytes}, \texttt{ShiftRows}, \texttt{MixColumns},
\texttt{AddRoundKey}$(K_i)$ dans cet ordre, pour $i = 1,\dots, \texttt{Nb} - 1$;
\item Un dernier tour ne comporte plus que 3 étapes: \texttt{SubBytes},
\texttt{ShiftRows}, \texttt{AddRoundKey}$(K_{\texttt{Nb}})$.
\item Le contenu actuel du tableau donne les 16 octets du texte chiffré.
\end{enumerate}

\misctitle{SubBytes ($S$-box)} opère indépendamment sur chacun des $16$
octets. C'est la composée $S=f\circ I$ des applications
\begin{align*}
\begin{array}{rcl}
   I: \FM_{256} & \to & \FM_{256}\\
%
      x & \mapsto &
  \begin{cases}
     x^{-1} & \text{si $x\neq 0$},\\
     0 & \text{si $x = 0$},\\
   \end{cases}
\end{array}
&
%
\quad\text{et}\quad
%
&
\begin{array}{rcl}
    f:  \FM_{256}\simeq (\FM_2)^8 &\to& (\FM_2)^8 \simeq \FM_{256}\\
      x &\mapsto& Ax+B\\[0.9cm]
\end{array}
\end{align*}
où $A$ est une matrice $8\times 8$ à coefficients dans $\FM_2$ et $B\in
(\FM_2)^8$:
\begin{small}
$$
A=\begin{pmatrix}
1&0&0&0&1&1&1&1\\
1&1&0&0&0&1&1&1\\
1&1&1&0&0&0&1&1\\
1&1&1&1&0&0&0&1\\
1&1&1&1&1&0&0&0\\
0&1&1&1&1&1&0&0\\
0&0&1&1&1&1&1&0\\
0&0&0&1&1&1&1&1\\
\end{pmatrix}\quad\text{et}\quad
B=\begin{pmatrix}
1\\
1\\
0\\
0\\
0\\
1\\
1\\
0
\end{pmatrix}.
$$
\end{small}

\misctitle{ShiftRows}
  fait subir une permutation circulaire vers la gauche aux lignes du
tableau, respectivement de 0, 1, 2, 3 cases:
$$ \TABgen{a} \quad \longrightarrow \quad \TABgen{b} $$

\misctitle{MixColumns} s'interprète comme une multiplication matricielle:
$$ \TABgen{a} \quad \longrightarrow \quad \TABgen{b} $$
où
$$
\MATgen{b}
=
\begin{pmatrix}
\alpha & \alpha+1 & 1 & 1 \\
 1 & \alpha & \alpha+1 & 1  \\
1 & 1 & \alpha & \alpha+1  \\
\alpha+1 & 1 & 1 & \alpha
\end{pmatrix}
\MATgen{a}
$$
est le produit des matrices à coefficients dans $\FM_{256}$.

\misctitle{AddRoundKey$(K_i)$} addition bit à bit (\textsc{xor}) de la clé de
tour $K_i$, case par case.
\end{document}
