diff options
Diffstat (limited to 'exercices2b.tex')
| -rw-r--r-- | exercices2b.tex | 156 |
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} + % % % |