%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt]{article} \usepackage[francais]{babel} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{times} % A tribute to the worthy AMS: \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} % \usepackage{mathrsfs} \usepackage{wasysym} \makeatletter\relax\let\Square\@undefined\relax\makeatother \usepackage{bbding} \usepackage{url} % \theoremstyle{definition} \newtheorem{comcnt}{Tout} \newcommand\exercice{% \refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}} \newcommand{\limp}{\mathrel{\Rightarrow}} \newcommand{\liff}{\mathrel{\Longleftrightarrow}} \newcommand{\pgcd}{\operatorname{pgcd}} \newcommand{\ppcm}{\operatorname{ppcm}} \newcommand{\signe}{\operatorname{signe}} \newcommand{\tee}{\mathbin{\top}} \newcommand{\Frob}{\operatorname{Frob}} \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 \pretolerance=10000 \tolerance=8000 % % % \setcounter{comcnt}{4} \exercice On admet que le polynôme $P(t) = t^8+t^4+t^3+t+1 \in \mathbb{F}_2[t]$ 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 « représenté » par l'entier $a_0 + a_1 \times 2 + \cdots + a_7 \times 2^7$ entre $0$ et $255$. \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$ 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 représente la somme dans $F$ des éléments représentés par $a$ et $b$, et de même $a\otimes b$ pour le produit ; ces opérations font donc de $\{0,\ldots,255\}$ un corps isomorphe à $F$, puisqu'il s'agit juste 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} % % % \exercice Soit $q = p^d$ une puissance d'un nombre premier $p$. (A) On appelle \emph{trace absolue} dans $\mathbb{F}_q$ (ou bien trace dans $\mathbb{F}_q$ sur $\mathbb{F}_p$) l'application $\mathrm{tr} \colon \mathbb{F}_q \to \mathbb{F}_q$ qui envoie un élément $x \in \mathbb{F}_q$ sur la somme $\sum_{i=0}^{d-1} \Frob^i(x)$ des $d$ itérées consécutives du Frobenius, où comme d'habitude $\Frob^i(x)$ désigne $x^{p^i}$. (0) Montrer que $\mathrm{tr}(x+y) = \mathrm{tr}(x) + \mathrm{tr}(y)$ pour tous $x,y \in \mathbb{F}_q$ et que $\mathrm{tr}(cx) = c\,\mathrm{tr}(x)$ si $c \in \mathbb{F}_p$ et $x \in \mathbb{F}_q$. (1) Montrer que $\mathrm{tr}$ prend en fait des valeurs dans $\mathbb{F}_p$. (On pourra pour cela chercher à calculer $\Frob(\mathrm{tr}(x))$.) (2) Expliquer pourquoi $\mathrm{tr}(x)$ est un polynôme de $x$ (dont on calculera le degré). (3) Montrer qu'il existe $x \in \mathbb{F}_q$ tel que $\mathrm{tr}(x) \neq 0$. (4) En déduire que $\mathrm{tr}$ prend toutes les valeurs de $\mathbb{F}_p$ (i.e., qu'il s'agit d'une fonction surjective ; on pourra par exemple commencer par montrer qu'elle prend la valeur $1$). \smallbreak (B) On appelle \emph{norme absolue} dans $\mathbb{F}_q$ (ou bien norme dans $\mathbb{F}_q$ sur $\mathbb{F}_p$) l'application $\mathrm{N} \colon \mathbb{F}_q \to \mathbb{F}_q$ qui envoie un élément $x \in \mathbb{F}_q$ sur le produit $\prod_{i=0}^{d-1} \Frob^i(x)$ des $d$ itérées consécutives du Frobenius, où comme d'habitude $\Frob^i(x)$ désigne $x^{p^i}$. (0) Montrer que $\mathrm{N}(xy) = \mathrm{N}(x)\,\mathrm{N}(y)$ pour tous $x,y \in \mathbb{F}_q$. (1) Montrer que $\mathrm{N}$ prend en fait des valeurs dans $\mathbb{F}_p$. (On pourra pour cela chercher à calculer $\Frob(\mathrm{N}(x))$.) (2) Exprimer $\mathrm{N}(x)$ comme une certaine puissance de $x$ (dont on calculera l'exposant). (3) Montrer que $\mathrm{N}(x) = 0$ si et seulement si $x=0$. (4) Montrer que $\mathrm{N}$ prend toutes les valeurs de $\mathbb{F}_p$ (i.e., qu'il s'agit d'une fonction surjective ; on pourra considérer $\mathrm{N}(g)$ pour $g$ un élément primitif de $\mathbb{F}_q^\times$, et montrer qu'il est d'ordre $p-1$ dans $\mathbb{F}_p^\times$). % % % \end{document}