diff options
| -rw-r--r-- | exercices2b.tex | 103 |
1 files changed, 103 insertions, 0 deletions
diff --git a/exercices2b.tex b/exercices2b.tex new file mode 100644 index 0000000..656c670 --- /dev/null +++ b/exercices2b.tex @@ -0,0 +1,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} |