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
|
%% 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{Fr}}
\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$.
%
%
%
\end{document}
|
