1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
%% 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}{~}
%
%
%
\begin{document}
\title{INFMDI720\\Exercices\\{\normalsize Rappels mathématiques pour la cryptographie}}
\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]$
et 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.
\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$ ?
\dothis Inversement, quels éléments de $F$ sont représentés par les
entiers $31$ et $64$ ?
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$.
\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 ?
\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.
\dothis Écrire une fonction (dans un langage de programmation
quelconque) qui calcule $2 \otimes x$ en fonction de $x$.
\dothis Utiliser cette fonction, et notamment la distributivité
$\otimes$ sur $\oplus$, pour écrire une fonction calculant $x \otimes
y$ en général.
\dothis Calculer $250 \otimes 250$.
%
%
%
\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}
|
