\documentclass[10pt,a4paper]{article}

\usepackage[utf8]{inputenc}
\usepackage{amssymb,amsmath,fullpage}
\usepackage{supertabular}
\usepackage[french]{babel}

\DeclareMathSymbol{\gena}{\mathord}{letters}{"3C}
\DeclareMathSymbol{\genb}{\mathord}{letters}{"3E}
\newcommand{\scal}[2]{\gena{#1},{#2}\genb}

\newcommand{\ra}{\rightarrow}
\newcommand{\trib}{\mathcal{M}}
\newcommand{\Rr}{\mathbf{R}}
\newcommand{\Nn}{\mathbf{N}}
\newcommand{\Cc}{\mathbf{C}}
\newcommand{\Zz}{\mathbf{Z}}
\newcommand{\Si} {\Sigma}
\newcommand{\si} {\sigma}
\newcommand{\Qq}{\mathbf{Q}}
\newcommand{\ord}{\mathrm{ord}}
\newcommand{\tq}{\,\mid\,}
\newcommand{\eps}{\varepsilon}
\newcommand{\Parts}{\mathcal{P}}
\newcommand{\mods}[1]{\, (\mathrm{mod}\, {#1})}
\newcommand{\norm}[1]{\vert\vert{#1}\vert\vert}
\def\stacksum#1#2{{\stackrel{{\scriptstyle #1}}
{{\scriptstyle #2}}}}
\newcommand{\Cic}{C_c^{\infty}}
\newcommand{\ppartial}{\tilde{\partial}}
\newcommand{\indic}[1]{[\underline{Indication}~:\ {#1}]}

\newcommand{\implique}{\Rightarrow}
\newcommand{\ssi}{\Leftrightarrow}

\newcommand{\bareme}[1]{\marginpar{(\small{\textsf{{#1}}})}}
\newcommand{\baremeg}[1]{\marginpar{\framebox{\textsf{{#1}}}}}



\newcounter{exercices}
\newcounter{etape}

\newenvironment{exo}{\par\setcounter{etape}{0}\stepcounter{exercices}
\medskip\textbf{Exercice {\arabic{exercices}}.}\ }

\newcommand{\etap}{\stepcounter{etape}(\arabic{etape})\ }

\begin{document}

\selectlanguage{french}

\begin{flushleft}
\textbf{Université Bordeaux I -- 2009/2010}\hfill
\textbf{Master 1 Cryptologie et Sécurité Informatique}
\par
\textbf{Courbes elliptiques}\hfill\textbf{K. Belabas - F. Pazuki}
\end{flushleft}

\bigskip
\bigskip

\begin{center}
\textbf{TD 1}
\end{center}

\par
\bigskip

%% \noindent
%% \textsf{\underline{Barême indicatif} : $???$}

\underline{Nomenclature officielle}\newline
\begin{equation*}
\begin{array}{ll}
\text{PARI/GP} & \text{le système complet,} \\
\text{PARI ou libpari} & \text{la bibliothèque,} \\
\text{gp} & \text{le calculateur i.e. ce que vous utilisez,} \\
\text{GP} & \text{le langage utilisé pour programmer le calculateur.}
\end{array}
\end{equation*}


\begin{exo}
L'objectif de cet exercice est de rappeler la méthode d'exponentiation binaire.  
\begin{enumerate}
\item 
Étant donné $n\in\mathbb{N}^*$, écrire une procédure renvoyant la liste des chiffres de $n$ dans son écriture en base $2$ i.e. $n=\sum_{i=0}^k\varepsilon_i2^i$ où $\varepsilon_i\in\{0,1\}$ pour tout entier naturel $i$ compris entre $0$ et $k$.
\item 
En déduire un algorithme d'exponentiation efficace dans tout ensemble $E$ muni d'une multiplication.
\item
Le programmer pour $E=\mathbb{N}^*$ et pour $E=\left(\mathbb{Z}/ n\mathbb{Z}\right)^\times$ où $n\geqslant 1$.
\end{enumerate}
\end{exo}

\begin{exo} L'objectif de cet exercice est de rafraîchir votre mémoire arithmétique. Le petit théorème de Fermat affirme que si $p$ est un nombre premier alors
\begin{equation*}
\forall b\in\mathbb{Z},\quad\left(b^{p}\equiv b\mod(p)\right).
\end{equation*}
\begin{enumerate}
\item
Justifier ce théorème.
\item
Montrer en utilisant le théorème de Fermat que $n=10^5+7$ n'est pas un nombre premier.
\item
Retrouver ce résultat en utilisant la commande \textit{isprime} et la commande $\textit{ispseudoprime}$. Comparer ces deux commandes à l'aide de la documentation.
\item
Trouver la décomposition de $n$ en facteurs premiers à l'aide de la commande \textit{factor}.
\item
Les entiers naturels apparaissant dans le résultat précédent sont-ils réellement premiers?
\item
Étudier expérimentalement la réciproque du petit théorème de Fermat i.e. si
\begin{equation*}
\forall b\in\mathbb{Z},\quad\left(b^{n}\equiv b\mod(n)\right)
\end{equation*}
alors $n$ est un nombre premier.
\item
Un entier impair $n$ est dit \textit{pseudo-premier de base $b$} si $n$ et $b$ sont premiers entre eux et si $b^{n-1}\equiv 1\mod(n)$. Un \textit{entier de Carmichael} est un entier $n$ non premier mais pseudo-premier pour toute base.
\item
Dresser la liste de tous les nombres de Carmichael inférieurs à $10000$ à l'aide de gp.
\end{enumerate}
\end{exo}

\begin{exo}
La \emph{méthode de cryptographie} R.S.A est très difficile à attaquer. Elle est devenue un standard dans le monde. Les lettres R.S.A. signifient Rivest-Shamir-Adleman du nom de ses inventeurs, qui l'ont mis au point en 1977.
RSA est un algorithme dit \og à clef publique \fg qui sert aussi bien au chiffrement de documents qu'à l'identification.

Le principe d'un algorithme à clef publique est que la méthode pour chiffrer  le message est connue de tout le monde, mais qu'une seule personne sait déchiffrer.
Dans le cas du codage RSA, tous les agents reçoivent la clef publique, un couple $(n,d)$ tel que $n$ est un nombre (très grand en général, et qui est le produit de deux facteurs premiers $p$ et $q$), et $d$ choisi tel que $d$ et $(p-1)(q-1)$ sont premiers entre eux.
La clé privée du décodeur est l'entier $e$ tel que $1< e < (p-1)(q-1) $ et 
$$ed \equiv \, 1 \, \mod (p-1)(q-1).$$
La sécurité de ce code vient du fait qu'il est très difficile de trouver la décomposition en facteurs premiers $ n = pq$ du nombre $n$.\\

Le message est exprimé à l'aide des entiers choisis dans $\Si = \{ 0, 1, \dots, n-1\}$. Pour le chiffrer un caractère, on utilise l'application
$$ \Theta :  \si \in \Si \mapsto \si^d \mod n.$$
Pour déchiffrer, on effectue
$$\Xi : \si \in \Si \mapsto \si^e \mod n.$$

Cette technique est justifiée par le petit théorème de Fermat, qui dans notre cas s'écrit : pour tout entier $x$ et pour tout entier $\ell$, 
$$x^{\ell (p-1)(q-1) + 1} \equiv x \mod n.$$
Ainsi la propriété $ed \equiv \, 1 \mod  (p-1)(q-1)$ garantit que $\Xi \circ \Theta = \textrm{Id}$.

\vspace{2mm}

\begin{enumerate}
\item Écrivez une procédure de chiffrement \texttt{RSA} qui chiffre l'entier $s$ avec la clef publique $(n,d)$. 
\item Chiffrez le message $1234567890$ en utilisant la clef publique $n = 21556703041$ et $d = 7$. 
\item Déchiffrez le message $8509780874$ en utilisant la clef privée $n = 34675796329$ et $e = 30595937633$.
\item Dans les deux cas précédents, cassez le cryptosystème, i.e. retrouvez les valeurs $\{p, q\}$, $d$ et $e$.
\item Écrivez une procédure \texttt{GenClef} qui génère aléatoirement une clef publique $(n,d)$ et une clef privée $(n,e)$ où $n$ est le produit de deux nombres premiers $p$, $q$ choisis au hasard parmi les $10^7$ premiers nombres premiers et $e$ est choisi uniformément entre $2$ et $(p-1)(q-1)-2$. 
\end{enumerate}

\end{exo}


\begin{exo}
L'objectif de cet exercice est de pouvoir manipuler de façon pratique les corps finis et les polynômes à coefficients dans les corps finis.
\begin{enumerate}
\item
Soit $p$ un nombre premier.
\begin{enumerate}
\item
Soit $\mathbb{F}_p$ «le" corps fini à $p$ éléments. Donner un modèle simple de ce corps fini.
\item
Montrer que pour tout $x$ dans $\mathbb{F}_p$,
\begin{equation*}
x^p=x.
\end{equation*}
\item
Écrire les tables d'addition et de multiplication de $\mathbb{F}_7$ en s'aidant de gp.
\end{enumerate}
\item
Soit $P(X)=X^5+X^4+2X^3-2X^2-4X-3$.
\begin{enumerate}
\item
Factoriser $P$ à l'aide de gp dans $\mathbb{C}[X]$ puis dans $\mathbb{Z}[X]$. 
\item
Calculer à l'aide de gp le discriminant de $P$.
\item
Factoriser à l'aide de gp ce polynôme dans $\mathbb{F}_2[X]$, $\mathbb{F}_{11}[X]$, $\mathbb{F}_{13}[X]$, $\mathbb{F}_{23}[X]$, $\mathbb{F}_{31}[X]$, $\mathbb{F}_{37}[X]$. Que remarquez-vous?
\end{enumerate}
\item
Soit $\mathbb{F}_4$ «le" corps fini à $4$ éléments. Montrer que $\mathbb{F}_4$ est isomorphe en tant que corps à
\begin{equation*}
\mathbb{F}_2[X]/(X^2+X+1).
\end{equation*}
Écrire les tables d'addition et de multiplication de ce corps en s'aidant de gp.
\item
On cherche à décrire explicitement $\mathbb{F}_8$.
\begin{enumerate}
\item
Soit $x$ dans $\mathbb{F}_8\setminus\mathbb{F}_2$. Montrer que $\mathbb{F}_8=\mathbb{F}_2[x]$.
\item
En déduire que $\mathbb{F}_8$ est isomorphe en tant que corps à $\mathbb{F}_2[X]/(Q(X))$
où $Q(X)$ est le polynôme minimal de $x$ sur $\mathbb{F}_2$. Rappelez les propriétés d'un tel polynôme.
\item
Combien existe-t-il de polynômes de degré $3$ à coefficients dans $\mathbb{F}_2$? Dressez la liste des polynômes de degré $3$ à coefficients dans $\mathbb{F}_2$ et $\mathbb{F}_2$-irréductibles en s'aidant de gp.
\item
En déduire que $\mathbb{F}_8$ est isomorphe en tant que corps à
\begin{equation*}
\mathbb{F}_2[X]/(X^3+X+1)=\mathbb{F}_{8,1}
\end{equation*}
et à
\begin{equation*}
\mathbb{F}_2[X]/(X^3+X^2+1)=\mathbb{F}_{8,2}.
\end{equation*}
\item
Écrire les tables d'addition et de multiplication de $\mathbb{F}_{8,1}$ et $\mathbb{F}_{8,2}$ en s'aidant de gp.
\item
Soit $\alpha$ une racine de $X^3+X+1$. Montrer à l'aide de gp que $\alpha^2$ et $\alpha^4$ sont les autres racines de $X^3+X+1$. Montrer également à l'aide de gp que $\alpha^3$, $\alpha^5$ et $\alpha^6$ sont les racines de $X^3+X^2+1$.
\item
En déduire que les tables de lois de $\mathbb{F}_{8,1}$ et de $\mathbb{F}_{8,2}$ sont équivalentes.
\item
écrire un isomorphisme explicite entre $\mathbb{F}_{8,1}$ et $\mathbb{F}_{8,2}$.
\item
Vérifier à l'aide de gp que si $x$ et $y$ sont dans $\mathbb{F}_{8,1}$ alors
\begin{equation*}
(x+y)^2=x^2+y^2, \quad (x+y)^4=x^4+y^4, \quad (x+y)^8=x^8+y^8.
\end{equation*}
Généralisation?
\end{enumerate}
\item
Soient $p$ un nombre premier et $Q(X)$ un polynôme à coefficients dans $\mathbb{F}_p$, de degré $n\geqslant 1$ et $\mathbb{F}_p$-irréductible.
\begin{enumerate}
\item
Montrer que $\mathbb{F}_p[X]/(Q(X))$ est «le" corps fini de cardinal $q=p^n$ noté $\mathbb{F}_q$.
\item
Montrer que pour tous $x$ et $y$ dans $\mathbb{F}_q$ et pour tout entier naturel $t$,
\begin{equation*}
(x+y)^{p^t}=x^{p^{t}}+y^{p^{t}}.
\end{equation*}
\item
En déduire que l'application
\begin{eqnarray*}
\text{Frob}_p: \mathbb{F}_q & \rightarrow & \mathbb{F}_q \\
x & \mapsto & x^p
\end{eqnarray*}
est un automorphisme\footnote{$\text{Frob}_p$ est le \textbf{morphisme de Frobenius} de $\mathbb{F}_q$} de $\mathbb{F}_q$ dont les points fixes sont exactement les éléments de $\mathbb{Z}/p\mathbb{Z}$.
\item
En déduire que pour tout élément $x$ de $\mathbb{F}_q$ et tout entier naturel $t$,
\begin{equation*}
\left(Q(x)\right)^{p^t}=Q\left(x^{p^t}\right).
\end{equation*}
\item
En déduire également que si $\alpha$ est une racine de $Q(X)$ alors les autres racines de $Q(X)$ sont $\alpha^p, \alpha^{p^2},\cdots, \alpha^{p^{n-1}}$. 
\end{enumerate}
\item
Comment trouver un polynôme à coefficients dans $\mathbb{F}_p$, de degré $n\geqslant 1$ et $\mathbb{F}_p$-irréductible?
\begin{enumerate}
\item
Écrire une procédure permettant de tirer aléatoirement un polynôme de degré $n$ à coeffcients dans $\mathbb{F}_p$.
\item
Tester l'irréductibilité d'un tel polynôme de plusieurs façons.
\item
Donner une estimation du nombre d'essais à faire par rapport à $n$ pour que le polynôme aléatoire fourni par la procédure précédente soit $\mathbb{F}_p$-irréductible.
\end{enumerate}
\item
Tester sur des gros exemples tout ce qui a été vu dans cet exercice i.e. $n>10^3$ et/ou $p>10^{10}, 10^{100}$. Qu'en pensez-vous?
\end{enumerate}
\end{exo}

\end{document}
