path: root/exercices2b.tex

%% 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{\trace}{\operatorname{tr}}
\newcommand{\Norm}{\operatorname{N}}
\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 $\trace
\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 $\trace(x+y) = \trace(x) + \trace(y)$
pour tous $x,y \in \mathbb{F}_q$ et que $\trace(cx) =
c\,\trace(x)$ si $c \in \mathbb{F}_p$ et $x \in \mathbb{F}_q$.

\begin{corrige}
On rappelle que $\Frob(x+y) = \Frob(x) + \Frob(y)$, et par conséquent
$\Frob^i(x+y) = \Frob^i(x) + \Frob^i(y)$ pour n'importe quel $i$ ; a
donc $\trace(x+y) = \sum_{i=0}^{d-1} \Frob^i(x+y) = \sum_{i=0}^{d-1}
(\Frob^i(x) + \Frob^i(y)) = \sum_{i=0}^{d-1} \Frob^i(x) +
\sum_{i=0}^{d-1} \Frob^i(y) = \trace(x) + \trace(y)$.

Pour la seconde égalité, lorsque $c\in \mathbb{F}_p$ on a $\Frob(cx) =
\Frob(c)\,\Frob(x) = c\,\Frob(x)$, et par conséquent $\Frob^i(cx) =
c\,\Frob^i(x)$ pour tout $i$.  On peut donc écrire $\trace(cx) =
\sum_{i=0}^{d-1} \Frob^i(cx) = \sum_{i=0}^{d-1} (c \Frob^i(x)) = c
\sum_{i=0}^{d-1} \Frob^i(x) = c\,\trace(x)$.
\end{corrige}

(1) Montrer que $\trace$ prend en fait des valeurs dans
$\mathbb{F}_p$.  (On pourra pour cela chercher à calculer
$\Frob(\trace(x))$.)

\begin{corrige}
On a $\Frob(\trace(x)) = \Frob(\sum_{i=0}^{d-1} \Frob^i(x)) =
\sum_{i=0}^{d-1} \Frob^{i+1}(x) = \sum_{i=1}^{d} \Frob^i(x)$.  Or
$\Frob^d(x) = x$ pour tout $x \in \mathbb{F}_q$ (où $q = p^d$) d'après
le petit théorème de Fermat.  La somme se réécrit donc bien comme
$\sum_{i=0}^{d-1} \Frob^i(x) = \trace(x)$.  Ceci montre que
$\trace(x)$ est stable par le Frobenius, i.e., vérifie $\trace(x)^p =
\trace(x)$, donc $\trace(x) \in \mathbb{F}_p$.
\end{corrige}

(2) Expliquer pourquoi $\trace(x)$ est un polynôme de $x$ (dont
on calculera le degré).

\begin{corrige}
On a $\trace(x) = x + x^p + x^{p^2} + \cdots + x^{p^{d-1}}$, qui est
manifestement un polynôme de degré $p^{d-1}$ (remarquons que ceci est
strictement plus petit que $p^d$).
\end{corrige}

(3) Montrer qu'il existe $x \in \mathbb{F}_q$ tel que $\trace(x)
\neq 0$.

\begin{corrige}
Le polynôme $\trace$ étant de degré $p^{d-1} < p^d$ non identiquement
nul, il ne peut pas s'annuler en les $p^d$ points de $\mathbb{F}_q$.
Il existe donc $x \in \mathbb{F}_q$ tel que $\trace(x) \neq 0$.
\end{corrige}

(4) En déduire que $\trace$ 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$).

\begin{corrige}
Si $\trace(x) = c \neq 0$ (on vient de voir qu'un tel $x$ existe),
comme $c \in \mathbb{F}_p$ d'après la question (1), on a
$\trace(\frac{1}{c}x) = 1$.  Si $a \in \mathbb{F}_p$ est quelconque,
on a alors $\trace(\frac{a}{c}x) = a$.  Donc $\trace$ prend bien
toutes les valeurs de $\mathbb{F}_p$.
\end{corrige}

\smallbreak

(B) On appelle \emph{norme absolue} dans $\mathbb{F}_q$ (ou bien norme
dans $\mathbb{F}_q$ sur $\mathbb{F}_p$) l'application $\Norm
\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 $\Norm(xy) = \Norm(x)\,\Norm(y)$ pour
tous $x,y \in \mathbb{F}_q$.

\begin{corrige}
On rappelle que $\Frob(xy) = \Frob(x) \, \Frob(y)$, et par conséquent
$\Frob^i(xy) = \Frob^i(x) \, \Frob^i(y)$ pour n'importe quel $i$ ; a
donc $\Norm(xy) = \prod_{i=0}^{d-1} \Frob^i(xy) = \prod_{i=0}^{d-1}
(\Frob^i(x) \, \Frob^i(y)) = \prod_{i=0}^{d-1} \Frob^i(x) \times
\prod_{i=0}^{d-1} \Frob^i(y) = \Norm(x) \, \Norm(y)$.
\end{corrige}

(1) Montrer que $\Norm$ prend en fait des valeurs dans
$\mathbb{F}_p$.  (On pourra pour cela chercher à calculer
$\Frob(\Norm(x))$.)

\begin{corrige}
On a $\Frob(\Norm(x)) = \Frob(\prod_{i=0}^{d-1} \Frob^i(x)) =
\prod_{i=0}^{d-1} \Frob^{i+1}(x) = \prod_{i=1}^{d} \Frob^i(x)$.  Or
$\Frob^d(x) = x$ pour tout $x \in \mathbb{F}_q$ (où $q = p^d$) d'après
le petit théorème de Fermat.  Le produit se réécrit donc bien comme
$\prod_{i=0}^{d-1} \Frob^i(x) = \Norm(x)$.  Ceci montre que $\Norm(x)$
est stable par le Frobenius, i.e., vérifie $\Norm(x)^p = \Norm(x)$,
donc $\Norm(x) \in \mathbb{F}_p$.
\end{corrige}

(2) Exprimer $\Norm(x)$ comme une certaine puissance de $x$ (dont
on calculera l'exposant).

\begin{corrige}
On a $\Norm(x) = x \times x^p \times x^{p^2} \times \cdots \times
x^{p^{d-1}} = x^{1+p+p^2+\cdots+p^{d-1}}$.  L'exposant est la somme
d'une série géométrique et vaut $\frac{p^d-1}{p-1}$ (remarquer que
ceci est un entier).  On a peut donc écrire $\Norm(x) =
x^{\frac{p^d-1}{p-1}}$.
\end{corrige}

(3) Montrer que $\Norm(x) = 0$ si et seulement si $x=0$.

\begin{corrige}
Le fait que $\Norm(0) = 0$ est trivial.

Dans un corps (ou plus généralement, un anneau intègre), un produit
est nul si et seulement si un des facteurs est nul.  Si on a
$x^{\frac{p^d-1}{p-1}} = 0$, la seule possibilité est que $x=0$ (ou
bien directement sur la définition : si $\prod_{i=0}^{d-1} \Frob^i(x)
= 0$, c'est qu'un des facteurs $\Frob^i(x)$ est nul, ce qui en
appliquant $\Frob^{d-i}$ implique $x=0$).
\end{corrige}

(4) Montrer que $\Norm$ prend toutes les valeurs
de $\mathbb{F}_p$ (i.e., qu'il s'agit d'une fonction surjective ; on
pourra considérer $\Norm(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$).

\begin{corrige}
Soit $g$ un élément primitif de $\mathbb{F}_q^\times$ : il est donc
d'ordre exactement $q-1 = p^d-1$ (i.e., $g^j = 1$ si et seulement si
$j$ est multiple de $p^d-1$).  On a vu que $\Norm(g) =
g^{\frac{p^d-1}{p-1}}$.  On a donc $\Norm(g)^i = g^{\frac{p^d-1}{p-1}
  i}$.  On a donc $\Norm(g)^i = 1$ si et seulement si
$\frac{p^d-1}{p-1} i$ est multiple de $p^d-1$, c'est-à-dire si et
seulement si $\frac{p^d-1}{p-1} i = (p^d-1)k$ pour un certain
entier $k$, ce qui signifie $\frac{i}{p-1} = k$ pour un certain
entier $k$, autrement dit $i$ multiple de $p-1$.  On a donc bien
montré que $\Norm(g)$ est d'ordre $p-1$, i.e., primitif
dans $\mathbb{F}_p^\times$.

Si $a$ est un élément quelconque de $\mathbb{F}_p$, soit $a = 0$
auquel cas il est la norme de $0$, soit $a \neq 0$, auquel cas on peut
écrire $a = \Norm(g)^i$ pour un certain $i$ (puisqu'on vient de voir
que $\Norm(g)$ est primitif), et du coup $a = \Norm(g^i)$.  Donc
$\Norm$ prend bien toutes les valeurs de $\mathbb{F}_p$.
\end{corrige}

%
%
%
\end{document}