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{\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}