Answers to first exercise.

1 files changed, 154 insertions, 2 deletions

diff --git a/exercices2b.tex b/exercices2b.tex
index 546c295..17f032c 100644
--- a/exercices2b.tex
+++ b/exercices2b.tex
@@ -30,10 +30,22 @@
 \newcommand{\dothis}{\leavevmode\hbox to0pt{\hskip-\parindent\HandRight{}\hskip0ptplus1fil}}
 \DeclareUnicodeCharacter{00A0}{~}
 %
+\newif\ifcorrige
+\corrigetrue
+\newenvironment{corrige}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
+{{\hbox{}\nobreak\hfill\checkmark}%
+\ifcorrige\relax\else\egroup\fi\par}
+%
 %
 %
 \begin{document}
+\ifcorrige
+\title{INFMDI720\\Exercices --- Corrigé\\{\normalsize Rappels mathématiques pour la cryptographie}}
+\else
 \title{INFMDI720\\Exercices\\{\normalsize Rappels mathématiques pour la cryptographie}}
+\fi
 \author{}
 \date{}
 \maketitle
@@ -49,7 +61,7 @@
 \exercice
 
 On admet que le polynôme $P(t) = t^8+t^4+t^3+t+1 \in \mathbb{F}_2[t]$
-et irréductible.  On pose $F = \mathbb{F}_2[t]/(P)$.
+est irréductible.  On pose $F = \mathbb{F}_2[t]/(P)$.
 
 On fait la convention suivante : un élément $a_0 + a_1 \bar t + \cdots
 + a_7 \bar t^7$ de $F$, où $a_0,\ldots,a_7 \in \{0,1\}$ sera
@@ -59,13 +71,41 @@ On fait la convention suivante : un élément $a_0 + a_1 \bar t + \cdots
 \dothis Expliquer pourquoi cette convention a bien
 un sens.
 
+\begin{corrige}
+On a des bijections successives entre
+\begin{itemize}
+\item $F = \mathbb{F}_2[t]/(P)$,
+\item les polynômes de $\mathbb{F}_2[t]$ de degré $<8$ (via le reste
+  de la division euclidienne par $P$),
+\item les octuplets $(a_0,\ldots,a_7)$ d'éléments de $\mathbb{F}_2$
+  (coefficients du polynôme),
+\item les octuplets $(a_0,\ldots,a_7)$ d'éléments de $\{0,1\}$
+  (chiffres de la représentation binaire d'un entier de $8$ bits),
+\item les entiers entre $0$ et $255$,
+\end{itemize}
+qui se composent bien en une bijection comme indiqué.
+\end{corrige}
+
 \dothis Avec cette convention, quels sont par exemple les entiers
 représentant les éléments $\bar t$ et $\bar t^7 + \bar t^6 + \bar t^5
-+ \bar t^4 + \bar t^3 + \bar t$ ?
++ \bar t^4 + \bar t^3 + \bar t$ de $F$ ?
 
 \dothis Inversement, quels éléments de $F$ sont représentés par les
 entiers $31$ et $64$ ?
 
+\begin{corrige}
+L'élément $\bar t$ de $F$ est représenté par l'entier $2^1 = 2$, et
+$\bar t^7 + \bar t^6 + \bar t^5 + \bar t^4 + \bar t^3 + \bar t$ par
+$2^7 + 2^6 + 2^5 + 2^4 + 2^3 + 2 = 250$.
+
+Réciproquement, $31 = 2^4 + 2^3 + 2^2 + 2 + 1$ représente $\bar t^4 +
+\bar t^3 + \bar t^2 + \bar t + 1$, et $64 = 2^6$ représente $\bar
+t^6$.
+
+Remarquons par ailleurs que $0$ et $1$ représentent $0$ et $1$, ce qui
+épargne beaucoup de maux de tête.
+\end{corrige}
+
 On appelle $\oplus$ et $\otimes$ les opérations définies sur les
 entiers entre $0$ et $255$ qui correspond aux opérations $+$ et
 $\times$ sur $F$ (autrement dit : $a\oplus b$ est l'entier qui
@@ -77,26 +117,138 @@ d'une représentation différente de la même chose).
 \dothis Calculer par exemple $7\oplus 11$, puis $4\otimes 4$, et enfin
 $141 \otimes 2$.
 
+\begin{corrige}
+L'entier $7 = 2^2 + 2 + 1$ représente $\bar t^2 + \bar t + 1$ et $11 =
+2^3 + 2 + 1$ représente $\bar t^3 + \bar t + 1$, donc $7\oplus 11$ est
+l'entier qui représente $(\bar t^2 + \bar t + 1) + (\bar t^3 + \bar t
++ 1) = \bar t^3 + \bar t^2$, c'est-à-dire $2^3 + 2^2 = 12$.
+\end{corrige}
+
 \dothis Expliquer pourquoi l'opération $\oplus$ est, sur les entiers
 de 8 bits, l'opération \texttt{XOR} de « ou exclusif » (c'est-à-dire
 l'opération calculée bit à bit par les règles : $\mathtt{XOR}(0,0) =
 0$, $\mathtt{XOR}(0,1) = \mathtt{XOR}(1,0) = 1$ et $\mathtt{XOR}(1,1)
 = 0$).  Le polynôme $P$ a-t-il joué un rôle ici ?
 
+\begin{corrige}
+L'addition dans $F$ se fait terme à terme sur les coefficients, comme
+le \texttt{XOR}, donc il s'agit simplement de constater que l'addition
+dans $\mathbb{F}_2$ est bien le \texttt{XOR} des bits, ce qui est
+clair.  Le polynôme $P$ (à part peut-être son degré, et bien sûr le
+fait qu'il est à coefficients dans $\mathbb{F}_2$) n'a joué aucun rôle
+ici.
+
+Remarquons au passage que $x \oplus x = 0$ pour tout $x$ (on a affaire
+à un corps de caractéristique $2$), ce qui est clair sur le
+\texttt{XOR}.
+\end{corrige}
+
 \dothis En distinguant les deux cas $x<128$ et $x\geq 128$, donner une
 expression générale de $2 \otimes x$ (qui pourra utiliser l'opération
 $\oplus$ de « ou exclusif »).  Expliquer où le polynôme $P$ a joué un
 rôle.
 
+\begin{corrige}
+Si $x<128$ alors le bit $a_7$ de poids fort de $x$ est nul,
+c'est-à-dire que l'élément de $F$ représenté par $x$ n'a pas de terme
+en $\bar t^7$.  Pour le multiplier par $\bar t$ (représenté par $2$),
+on décale simplement d'un cran tous les coefficients $a_0,\ldots,a_7$,
+et puisque $a_7=0$ on a encore affaire à un polynôme de degré $<8$.
+Ce décalage d'un cran correspond, sur l'écriture binaire, à une
+multiplication par $2$, donc : $2\otimes x = 2x$ (multiplication
+usuelle) lorsque $x<128$.
+
+Si au contraire $x \geq 128$, alors le bit $a_7$ de poids fort de $x$
+vaut $1$.  On peut écrire $x = x' \oplus 128$ où $x'$ (qui
+vaut $x\oplus 128$) est constitué des autres bits de $x$ et vérifie
+donc $x' < 128$.  On a donc $2 \otimes x = (2\otimes x') \oplus
+(2\otimes 128)$ (puisque $\otimes$ est distributive sur $\oplus$ comme
+$F$ est un corps), c'est-à-dire : $2\otimes x = 2(x\oplus 128) \oplus
+27$ lorsque $x\geq 128$.  Le nombre $27 = 2^4 + 2^3 + 2 + 1$ dans
+cette expression représente l'élément $\bar t^4+\bar t^3+\bar t+1$
+donné par le reste de la division euclidienne de $t^8$ par $t$ (i.e.,
+les termes de $P$ autres que le terme dominant $t^8$) : c'est le seul
+endroit où $P$ intervient.
+\end{corrige}
+
 \dothis Écrire une fonction (dans un langage de programmation
 quelconque) qui calcule $2 \otimes x$ en fonction de $x$.
 
+\begin{corrige}
+En C, par exemple :
+
+\noindent
+\texttt{uint8\_t multiplier\_par\_deux(uint8\_t x) \{\\\strut~~if (x\&0x80)
+  return (x<{}<1)\char`^{0x1b}; else return x<{}<1;\\\}}
+
+(On a écrit $27$ comme \texttt{0x1b}, le test à $128$ comme un « et
+  logique » avec \texttt{0x80}, et la multiplication par $2$ par un
+décalage vers la gauche de $1$ bit.  On a fait usage de types
+non-signés de 8 bits exactement (\texttt{uint8\_t}), pour pouvoir
+supposer que le décalage vers la gauche jetterait le bit débordant.)
+\end{corrige}
+
 \dothis Utiliser cette fonction, et notamment la distributivité
 $\otimes$ sur $\oplus$, pour écrire une fonction calculant $x \otimes
 y$ en général.
 
+\begin{corrige}
+Remarquons que si $y = b_0 + b_1 \times 2 + \cdots + b_7 \times 2^7$
+où $b_i \in \{0,1\}$ sont les bits de $y$, alors on a aussi $y = b_0
+\oplus (b_1 \otimes 2) \oplus \cdots \oplus (b_7 \otimes 2^{\otimes
+  7})$ (où $2^{\otimes i}$ désigne $2\otimes \cdots \otimes 2$ avec
+$i$ facteurs).  En effet, ceci est dû aux trois faits suivants :
+\begin{itemize}
+\item On a $2^{\otimes i} = 2^i$ si $0\leq i\leq 7$.  Ceci est dû au
+  fait que $2\otimes x = 2x$ si $x<128$.
+\item On a $b \otimes x = b x$ pour $b \in \{0,1\}$.  C'est évident
+  (pour $\otimes$ comme pour $\times$, multiplier par $0$ donne $0$ et
+  par $1$ donne l'identité).
+\item Une somme de puissances de $2$ distinctes est aussi leur
+  \texttt{XOR} (car il n'y a pas de retenues dans l'addition).
+\end{itemize}
+Dans ces conditions, on a donc $x \otimes y = (b_0 \otimes x) \oplus
+(b_1 \otimes x \otimes 2) \oplus \cdots \oplus (b_7 \otimes x \otimes
+2^{\otimes 7})$.  La fonction va donc calculer $x \otimes 2^{\otimes
+  i}$ en appliquant successivement la fonction de doublement déjà
+écrite, puis faire le \texttt{XOR} des différentes valeurs en question
+pour lesquelles le bit $b_i$ correspondant de $y$ vaut $1$.  Cela
+donne :
+
+\noindent
+\texttt{uint8\_t multiplier(uint8\_t x, uint8\_t y)
+  \{\\\strut~~uint8\_t z = 0;\\\strut~~while (y) \{\\\strut~~~~if
+  (y\&1) z \char`^= x;\\\strut~~~~x =
+  multiplier\_par\_deux(x);\\\strut~~~~y >{}>=
+  1;\\\strut~~\}\\\strut~~return z;\\\strut\}}
+\end{corrige}
+
 \dothis Calculer $250 \otimes 250$.
 
+\begin{corrige}
+Il faut écrire les quantités en binaire :
+
+\begin{tabular}{rcc@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}lc}
+$27$&$=$&\texttt{0}&\texttt{0}&\texttt{0}&\texttt{1}&\texttt{1}&\texttt{0}&\texttt{1}&\texttt{1}&${}_{(2)}$&\\\hline
+$250$&$=$&\texttt{1}&\texttt{1}&\texttt{1}&\texttt{1}&\texttt{1}&\texttt{0}&\texttt{1}&\texttt{0}&${}_{(2)}$&\\
+$250 \otimes 2$&$=$&\texttt{1}&\texttt{1}&\texttt{1}&\texttt{0}&\texttt{1}&\texttt{1}&\texttt{1}&\texttt{1}&${}_{(2)}$&$*$\\
+$250 \otimes 2^2$&$=$&\texttt{1}&\texttt{1}&\texttt{0}&\texttt{0}&\texttt{0}&\texttt{1}&\texttt{0}&\texttt{1}&${}_{(2)}$&\\
+$250 \otimes 2^3$&$=$&\texttt{1}&\texttt{0}&\texttt{0}&\texttt{1}&\texttt{0}&\texttt{0}&\texttt{0}&\texttt{1}&${}_{(2)}$&$*$\\
+$250 \otimes 2^4$&$=$&\texttt{0}&\texttt{0}&\texttt{1}&\texttt{1}&\texttt{1}&\texttt{0}&\texttt{0}&\texttt{1}&${}_{(2)}$&$*$\\
+$250 \otimes 2^5$&$=$&\texttt{0}&\texttt{1}&\texttt{1}&\texttt{1}&\texttt{0}&\texttt{0}&\texttt{1}&\texttt{0}&${}_{(2)}$&$*$\\
+$250 \otimes 2^6$&$=$&\texttt{1}&\texttt{1}&\texttt{1}&\texttt{0}&\texttt{0}&\texttt{1}&\texttt{0}&\texttt{0}&${}_{(2)}$&$*$\\
+$250 \otimes 2^7$&$=$&\texttt{1}&\texttt{1}&\texttt{0}&\texttt{1}&\texttt{0}&\texttt{0}&\texttt{1}&\texttt{1}&${}_{(2)}$&$*$\\\hline
+$250 \otimes 250$&$=$&\texttt{0}&\texttt{0}&\texttt{0}&\texttt{0}&\texttt{0}&\texttt{0}&\texttt{1}&\texttt{0}&${}_{(2)}$&\\
+\end{tabular}
+
+(La première ligne est là pour simplifier le calcul de $2x' \oplus 27$
+lorsqu'on en a besoin, et les $*$ indiquent les lignes dont le bit
+correspondant de $y=250$ vaut $1$, ce sont celles dont on fait le
+\texttt{XOR}.)
+
+Le résultat est donc $250 \otimes 250 = 2$.
+\end{corrige}
+
 %
 %
 %