X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/modelisationMathS3.git/blobdiff_plain/ffce293ccbd93a8d34365b009c246eead8d3b0be..refs/heads/master:/rsa.tex

diff --git a/rsa.tex b/rsa.tex
index 541d3c2..eee81e5 100644
--- a/rsa.tex
+++ b/rsa.tex
@@ -24,6 +24,7 @@ Dans le cas où l'on utilise une clé de cryptage, on a le schéma présenté
 à la figure~\ref{Fig:schemageneral}.
 \begin{figure}[ht]
 \begin{center}
+%\includegraphics[scale=0.5]{schemacrypto.pdf}
 \includegraphics[scale=0.5]{schemacrypto.eps}
 \end{center}
 \caption{Schéma général d'une méthode de cryptage/décryptage}\label{Fig:schemageneral}
@@ -54,71 +55,7 @@ Il s'inspire largement de~\cite{RSA09}
 
 
 
-\section{L'algorithme RSA}
-
-\subsection{Les étapes détaillées de l'algorithme}
-
-On rappelle qu'un système cryptographique à clé publique est
-initialisé par le receveur, c.-à-d. celui qui veut recevoir des messages de
-manière sure. 
-
-\paragraph{Première étape: choix des deux nombres $p$ et $q$.} 
-Le receveur choisit deux grands nombres premiers
-$p$ et $q$ et calcule $n = pq$. Puis il calcule $\varphi(n)$, 
-où $\varphi : \N^* \rightarrow \N^* $ est la \emph{fonction d'Euler} 
-définie par $\varphi(n)$  est le nombre d'entiers dans $\{1, 2, \dots , n -1 \}$ 
-qui sont premiers avec $n$.
-\paragraph{Deuxième  étape: choix de la clé publique.} 
-Le receveur choisit $e \in 
-\{1, \dots , n-1\}$  premier avec $\varphi(n)$.
-La clé publique est la paire $(e,n)$. L'expéditeur
-va s'en servir pour crypter son message à la quatrième étape ci-dessous.
-\paragraph{Troisième  étape: construction de la clé privée.}
-Le receveur calcule l'entier $d \in \{1,\dots, n-1\}$
-tel que le reste de la division de $ed$ par $\varphi(n)$ est 1. 
-Ceci se note aussi $ed \equiv 1 [\varphi(n)]$ qui se lie $ed$ est congru 
-à 1 modulo $\varphi(n)$.
-La paire $(d,n)$ est la clé privée de décryptage. Elle
-est secrète et permet au receveur de décrypter tous les messages reçus
-et cryptés avec $(e,n)$. 
-\paragraph{Quatrième  étape: cryptage du message.}
-L’expéditeur peut crypter tout message écrit sous la forme 
-d'un nombre $m$ appartenant à $\{1, \dots , n-1\}$ et qui est 
-premier avec $n$. 
-Le message codé est le reste $a$ de la division de $m^e$ par $n$. 
-On a donc $m^e \equiv a [n]$, où $a \in \{1, \dots , n - 1\}$.
-\paragraph{Cinquième  étape:  décryptage du message.} 
-Le receveur dispose de $a$ et de sa clé privée $(d,n)$. 
-Pour décrypter $a$, il calcule le reste dans la division par $n$
-de $a^d$ (c.-à-d. $a^d [n]$). 
-Si aucune erreur de calcul n'a été effectuée, c'est le message initial $m$.
-
-
-\subsection{Sur un exemple très petit}
-Le receveur choisit $p=7$, $q=13$.
-\begin{enumerate}
-\item Construire l'ensemble des entiers qui sont premiers avec $n=pq$ 
-  et en déduire que $\varphi(91)=72$.
-\item Montrer que $(29,91)$ est un candidat acceptable de clé publique.
-\item Trouver la clé privée associée.
-\item Montrer que  l'expéditeur a la possibilité de crypter le message $m=59$.
-\item Construire le message crypté $a$ à l'aide de la clé publique.
-\item Décrypter
- le message $a$ à l'aide de la clé privée. Il doit s'agir de $m$. 
-\end{enumerate} 
-
-
-\subsection{Les points clés}
-L'algorithme RSA repose sur plusieurs points clés rencontrés successivement:
-\begin{itemize}
-\item la génération de deux grands nombres premiers $p$ et $q$ ;
-\item la multiplication de grands nombres : $pq$, $ed$,   
-\item l'arithmétique modulaire;
-\item l'algorithme d'Euclide de génération de PGCD et son corollaire de Bézout;
-\item la factorisation, qui tant qu'elle n'est pas réalisable sur des grands nombres, garantit la sécurité du cryptage des données.
-\end{itemize}
-
-\section{Rappels d'arithmétique}
+\section{Rappels d'arithmétique jusqu'au PGCD} 
 
 Soit deux entiers $a$ et $b$ dans $\Z$.
 On dit que $a$ divise $b$ (que l'on note $a | b$)
@@ -131,7 +68,13 @@ $a$ et $b$, noté $a\land b$ est l'entier naturel qui vérifie
 \item Si $d | a$ et $d | b$, alors $d | a\land b$.
 \end{itemize}
 
-\subsection{Algorithme d'Euclide de calcul de PGCD}
+
+\begin{Exo}
+Déterminer $550 \land 1540$.
+\end{Exo}
+
+
+%\subsection{Algorithme d'Euclide de calcul de PGCD}
 
 Par définition, le PGCD de $a$ non nul avec
 0 est $a$ (définition raisonnable, car 0
@@ -177,7 +120,6 @@ Donner le code d'un programme qui prend en entrée deux entiers naturels $a$
 et $b$ tels que $a>b \ge 0$ et qui retourne leur PGCD 
 \end{Exo}
 
-\subsection{Les incontournables Bézout et Gau{\ss}}
 
 \begin{Prop}[Identite   de Bézout]
 On considère deux nombres entiers strictement positifs $a$ et $b$. 
@@ -190,13 +132,13 @@ Dans la preuve de la proposition précédente, on avait successivement
 
 \begin{eqnarray}
 a &=& b \times q_1 +r_1 \label{eq:def:r1} \\
-b &=& r_1 \times q_2 +r_2 \\
-r_1 &=& r_2 \times q_3 +r_3 \\
+b &=& r_1 \times q_2 +r_2 \nonumber \\
+r_1 &=& r_2 \times q_3 +r_3 \nonumber\\
 & \vdots & \nonumber\\
 r_{n-4} & = & r_{n-3} \times q_{n-2} + r_{n-2} \label{eq:def:rnm4} \\
 r_{n-3} & = & r_{n-2} \times q_{n-1} + r_{n-1} \label{eq:def:rnm3} \\
 r_{n-2} & = & r_{n-1} \times q_{n} + r_{n} \label{eq:def:rnm2}\\
-r_{n-1} & = & r_{n} \times q_{n+1} + 0 
+r_{n-1} & = & r_{n} \times q_{n+1} + 0 \nonumber 
 \end{eqnarray}
 
 
@@ -204,25 +146,135 @@ On sait que $a\land b$ est $r_n$ le dernier reste non nul.
 On remonte les équations une à une en démarrant de (\ref{eq:def:rnm2}).
 \begin{eqnarray}
 r_{n}  & = & r_{n-2} - r_{n-1} \times q_{n}  \nonumber \\
-  & = & r_{n-2} - (r_{n-3} - r_{n-2} \times q_{n-1}) \times q_{n} (\textrm{on remplace $r_{n-1}$ par sa def dans (\ref{eq:def:rnm3})}) \nonumber\\
-  & = & r_{n-2}. (1 + q_{n-1}. q_{n}) - r_{n-3}. q_{n} (\textrm{factorisation})\nonumber \\
-   & = & (r_{n-4} - r_{n-3} \times q_{n-2}). (1 + q_{n-1}. q_{n}) - r_{n-3}. q_{n}(\textrm{on remplace $r_{n-2}$ par sa def dans (\ref{eq:def:rnm4})}) \nonumber \\
+  & = & r_{n-2} - (r_{n-3} - r_{n-2} \times q_{n-1}) \times q_{n} \textrm{ (on remplace $r_{n-1}$ par son expression tirée de  (\ref{eq:def:rnm3})}) \nonumber\\
+  & = & r_{n-2}. (1 + q_{n-1}. q_{n}) - r_{n-3}. q_{n} \textrm{ (factorisation)}\nonumber \\
+   & = & (r_{n-4} - r_{n-3} \times q_{n-2}). (1 + q_{n-1}. q_{n}) - r_{n-3}. q_{n}\textrm{ (on remplace $r_{n-2}$ par son expression tirée de (\ref{eq:def:rnm4})}) \nonumber \\
 & \vdots & \nonumber \\
-& = & \ldots (\textrm{on remplace $r_{1}$ par sa def dans (\ref{eq:def:r1})}) \nonumber\\ 
-& = ax + by \nonumber
+& = & \ldots \textrm{ (on remplace $r_{1}$ par son expression tirée de (\ref{eq:def:r1})}) \nonumber\\ 
+& = &ax + by \nonumber
 \end{eqnarray}
-
 \end{Proof}
 
+\begin{Exo}
+Montrer qu'il existe $x$ et $y$ tels que 
+$29x + 72y=1$ puis trouver une valeur pour  $x$ et $y$.
+\end{Exo}
+
+
+\begin{Exo}
+Montrer que les propriétés $ a \land m = 1 $
+et $ b \land m = 1 $ impliquent $ ab \land m = 1 $.
+\end{Exo}
 
 
 \begin{Def}[Nombres premiers entre eux]
-Les deux entiers relatifs $a$ et $b$ sont premiers entre eux s 
+Les deux entiers relatifs $a$ et $b$ sont premiers entre eux si 
 leur plus grand commun diviseur est égal à 1.
 \end{Def}
 
+\begin{Exo}
+Montrer que 55 et 21 sont premiers entre eux.
+\end{Exo}
+
+
+
 
 
+
+
+\section{L'algorithme RSA}
+
+\subsection{Les étapes détaillées de l'algorithme}
+
+On rappelle qu'un système cryptographique à clé publique est
+initialisé par le receveur, c.-à-d. celui qui veut recevoir des messages de
+manière sure. 
+
+\paragraph{Première étape: choix des deux nombres $p$ et $q$.} 
+Le receveur choisit deux grands nombres premiers
+$p$ et $q$ et calcule $n = pq$. Puis il calcule $\varphi(n)$, 
+où $\varphi : \N^* \rightarrow \N^* $ est la \emph{fonction d'Euler} 
+L'entier $\varphi(n)$  est le nombre d'entiers 
+dans $\{1, 2, \dots , n -1 \}$ qui sont premiers avec $n$.
+
+\begin{Exo}
+Le receveur choisit $p=7$, $q=13$.
+Construire l'ensemble des entiers qui sont premiers avec $n=pq$ 
+et en déduire que $\varphi(91)=72$.
+\end{Exo}
+
+
+\paragraph{Deuxième  étape: choix de la clé publique.} 
+Le receveur choisit $e \in 
+\{1, \dots , n-1\}$  premier avec $\varphi(n)$.
+La clé publique est la paire $(e,n)$. 
+Chaque expéditeur
+va s'en servir pour crypter son message à destination de ce receveur.
+Le cryptage est détaillé 
+ à la quatrième étape ci-dessous.
+
+\begin{Exo}
+Montrer que $(29,91)$ est un candidat acceptable de clé publique.
+\end{Exo}
+
+\paragraph{Troisième  étape: construction de la clé privée.}
+Le receveur calcule l'entier $d \in \{1,\dots, n-1\}$
+tel que le reste de la division de $ed$ par $\varphi(n)$ est 1. 
+Ceci se note aussi $ed \equiv 1 [\varphi(n)]$ qui se lie $ed$ est congru 
+à 1 modulo $\varphi(n)$.
+La paire $(d,n)$ est la clé privée de décryptage. 
+Elle est secrète et permet au receveur de décrypter tous les messages reçus
+et cryptés avec $(e,n)$. 
+
+\begin{Exo}
+ Trouver la clé privée associée.
+\end{Exo}
+
+
+\paragraph{Quatrième  étape: cryptage du message.}
+L’expéditeur peut crypter tout message écrit sous la forme 
+d'un nombre $m$ appartenant à $\{1, \dots , n-1\}$ et qui est 
+premier avec $n$. 
+Le message codé est le reste $a$ de la division de $m^e$ par $n$. 
+On a donc $m^e \equiv a [n]$, où $a \in \{1, \dots , n - 1\}$.
+
+\begin{Exo}
+\begin{enumerate}
+\item Montrer que  l'expéditeur a la possibilité de crypter le message $m=59$.
+\item Construire le message crypté $a$ à l'aide de la clé publique.
+\end{enumerate}
+\end{Exo}
+
+\paragraph{Cinquième  étape:  décryptage du message.} 
+Le receveur dispose de $a$ et de sa clé privée $(d,n)$. 
+Pour décrypter $a$, il calcule le reste dans la division par $n$
+de $a^d$ (c.-à-d. $a^d [n]$). 
+Si aucune erreur de calcul n'a été effectuée, c'est le message initial $m$.
+
+
+\begin{Exo}
+Décrypter
+ le message $a$ à l'aide de la clé privée. Il doit s'agir de $m$. 
+\end{Exo}
+
+
+\subsection{Les points clés}
+L'algorithme RSA repose sur plusieurs points clés rencontrés successivement:
+\begin{itemize}
+\item la génération de deux grands nombres premiers $p$ et $q$ ;
+\item la multiplication de grands nombres : $pq$, $ed$,   
+\item l'arithmétique modulaire;
+\item l'algorithme d'Euclide de génération de PGCD et son corollaire de Bézout;
+\item la factorisation, qui tant qu'elle n'est pas réalisable sur des grands nombres, garantit la sécurité du cryptage des données.
+\end{itemize}
+
+
+
+%\subsection{L'algorithme de RSA est correct}
+
+\section{Les incontournables théorèmes de Bézout et de 
+  Gau{\ss}}
+
 \begin{Prop}[Théorème de Bézout]
 Deux entiers strictement positifs 
 $a$ et $b$ sont premiers entre eux, si et seulement s'il
@@ -237,7 +289,7 @@ car 1 est le PGCD de $a$ et de $b$.
 \item[\textbf{Si.}] 
   Supposons qu'il existe un couple $(x,y)$ 
   d'entiers relatifs vérifiant $ax + by = 1$ et $d = a \land b$.
-  Le $d$ divise $ax$ et $d$ divise $by$. Donc $d$ divise 
+  L'entier $d$ divise les produits $ax$ et $by$. Donc $d$ divise 
   $ax + by$ et donc $d$ est 1.   
 \end{itemize}
 \end{Proof}
@@ -248,8 +300,9 @@ Si $a$ divise le produit $bc$
 et s'il est premier avec $b$, alors il divise $c$.
 \end{Prop}
 
+
 \begin{Exo}
-Faire la preuve de ce théorème
+Faire la preuve du  théorème de Gau{\ss}.
 \end{Exo}
 
 \begin{Prop}[Fonction d'Euler]
@@ -257,9 +310,10 @@ Si $p$ et $q$ sont deux nombres premiers distincts alors l'égalité
 suivante permet de trouver le valeur de la fonction d'Euler en un seul 
 produit:
 \begin{equation}
-\varphi(pq)=(p-1)(q-1) \label{FEuler}
+\varphi(pq)=(p-1)(q-1). \label{FEuler}
 \end{equation} 
 \end{Prop}
+
 \begin{Exo}[Preuve de l'expression d'Euler]
 On doit compter le cardinal des nombres de $\{1, 2, . . . , pq -1\}$ qui sont 
 premiers avec $pq$.
@@ -277,28 +331,234 @@ premiers avec $pq$.
 
 
 
+
+
+
 %Refaire cet exo avec 27x +8y = 1
 \begin{Exo}
-L'objectif est de résoudre l'équation $(E)$ d'inconnues $x$ et $y$ 
-$405x -120y =15$.
+L'objectif est de résoudre l'équation $(E)$ $405x -120y =15$ 
+d'inconnues $x$ et $y$.
 \begin{enumerate}
 \item Trouver le PGCD de 405 et 120  à l'aide de l'algorithme d'Euclide.
 \item En déduire une solution particulière de cette équation.
 \item En utilisant la solution particulière, montrer que $(E)$ est 
   équivalente à $27(x-3) = 8(y-10)$.
-\item Utiliser le théorème de Gauss pour montrer que 
-  l'ensemble solution de $(E)$ est $\{(8k+3;27k+10)| k \in \Z\}$. 
+\item Utiliser le théorème de Gau{\ss} pour montrer que 
+  l'ensemble des solutions de $(E)$ est $\{(8k+3;27k+10)| k \in \Z\}$. 
 \end{enumerate}
 \end{Exo}
 
 
 
+\begin{Exo}
+  Soit $p$ un nombre premier.
+\begin{enumerate}
+\item Calculer $\varphi(p^2)$.
+\item Est-ce que RSA  fonctionnerait aussi avec l'entier $n = p^2$ à la place de $n=pq$?
+\end{enumerate}
+\end{Exo}
+
+
+
+
+
+\section{Congruence modulo}
+
+\begin{Def}[Congruence modulo]
+Soit $a$ et $b$ deux entiers relatifs.
+On dit que $a$ est congru $b$ modulo $n$ si $n$ divise $a-b$, c'est-à-dire
+s'il existe $x \in \Z$ tel que $(a-b) = nx$.
+On note    $a \equiv b [n]$. 
+La relation \og $\equiv [n]$ \fg{}
+est une relation d'équivalence appelée congruence modulo $n$.
+\end{Def}
+
+\begin{Prop}
+Soit $a$, $b$, $c$, $d$, $x$ et $y$ dans $\Z$. 
+Si $a \equiv c[n]$ et  $b \equiv d[n]$, alors
+\begin{enumerate}
+\item $a +b \equiv c + d [n]$;
+\item $ab \equiv cd [n]$;
+\item $ax +by \equiv cx +dy [n]$.
+\end{enumerate}
+\end{Prop}
+
+\begin{Exo}
+Démontrer la proposition précédente.
+\end{Exo}
+
+\begin{Prop}
+Soit deux entiers naturels $a$ et $n$ tels que $1< a< n$.
+Si $a$ et $n$ sont premier entre eux, 
+alors il existe un unique $x \in \{1, \dots, n-1\}$ tel 
+que $ax \equiv 1[n]$.
+\end{Prop}
+
+\begin{Proof}
+\begin{itemize}
+\item[\textbf{Existence.}]
+Comme $a$ et $n$ sont premiers entre eux, d'après le théorème de Bézout,
+il existe $x$ et $y$ entiers tels que $ax+ny = 1$, soit encore $ax \equiv 1[n]$.
+\item [\textbf{Unicité.}]
+Supposons qu'il existe une seconde solution $x'\in \{1, \dots, n-1\}$ telle que 
+$ax' \equiv 1[n]$. Donc $a(x-x') \equiv 0[n]$. Or $n$ est premier avec  $a$.
+D'après le théorème de Gau{\ss}, $n$ divise donc $x-x'$.
+Or $x-x'\in \{-n+2,-n+3,\dots,-1,0,1, \dots, n-2\}$. Le seul nombre divisible par $n$ est 0 et donc $x=x'$.
+\end{itemize} 
+\end{Proof}
+
+\begin{Exp}
+Trouvons les nombres $x$ tels que $7x+11$ soit multiple de 36. Dit autrement, 
+résoudre l'équation $7x \equiv -11 [36]$. 
+
+On cherche un \og inverse \fg{} de 7 c.-à-d. un nombre $t$, $1 < t < 35$ 
+tel que $7t \equiv 1 [36]$. 
+Soit à résoudre $7t \equiv 1 [36]$ qui revient à trouver $t$ et $u$ tels
+que  $7t -36u = 1$, soit encore les coefficient de Bézout relatifs à 
+(7 et 36). On trouve successivement 
+\begin{eqnarray*}
+36 & = & 7  \times 5 +1 \\ 
+7 & = & 7 \times 1 + 0 \\
+& \textrm{et donc}&\\
+1 & = & 36 - 7 \times 5
+\end{eqnarray*}
+et donc $t = -5$ (et $u=-1$). 
+On en déduit $7x \equiv -11 [36]$ est équivalent à 
+$(-5).7x \equiv (-5).-11 [36]$ soit encore 
+$x \equiv 55 [36] \equiv 19 [36]$.
+\end{Exp}
+
+\begin{Exo}
+Trouver les entiers relatif $x$ tels que 
+$261x +2$ soit multiple de 305.
+\end{Exo}
+
+
+
+\begin{Exo}
+\begin{enumerate}
+\item Démonter que $3^5 \equiv 1 [11]$
+\item En déduire que pour tous entiers naturels $k$ et $r$ on a 
+                                        $3^{5k +r} \equiv 3^r [11]$.
+\item  $n$ étant un entier naturel, quels sont les restes possibles
+  dans la division de $3^n$ par 11?
+\item  Trouvez pour quelles valeurs de $n$, $3^n + 7$ est divisible par 11.
+\end{enumerate}
+\end{Exo}
+
+\begin{Exo}
+Soit $p$ un nombre premier tel que $p \equiv 3 [4]$. 
+Soit $a$  un entier qui est un carré, modulo $p$:
+il existe $b$ tel que $a \equiv b^2 [p]$.
+Montrer que 
+$a^{(p+1)/4}$ est une racine carré de $a$, modulo $p$.  
+\end{Exo}
+
+
+
+\begin{Exo}
+On se place dans le contexte de cryptographie par RSA.
+Démontrer que si la clé d'encryptage est $e < \varphi(n)$, alors 
+il existe une unique clé de décodage entre 1 et $\varphi(n)$.
+\end{Exo}
+
+\begin{Prop}[Théorème d'Euler]\label{th:Euler}
+Soit $n \in \N^*$ et $m$, $m<n$ un entier relativement premier avec $n$.
+Alors 
+\begin{equation}
+m^{\varphi(n)}\equiv1 [n].
+\end{equation}
+\end{Prop}
+On laisse de côté la démonstration.
+
+\begin{Prop}[Correction de RSA]
+Le cryptage-décryptage du code RSA est correct: 
+on crypte un message $m$ tel que 
+$m\land n= 1$ en $a$ avec  
+$ m^e  \equiv a [n]$ selon la clé $(e,n)$.
+Alors le décryptage selon la clé $(d,n)$ redonne
+le message initial : $a^d \equiv m [n]$.
+\end{Prop} 
+\begin{Proof}
+\begin{eqnarray*}
+a^d & \equiv &   (m^e)^d [n]\\
+& \equiv &   m^{ed} [n] \textrm{ (réécriture)}\\
+& \equiv &   m^{k.\varphi(n)+1} [n] \textrm{ (définition de $d$)}\\
+& \equiv &   m^{k.\varphi(n)}m [n] \textrm{ (réécriture)}\\
+& \equiv &   (m^{\varphi(n)})^km [n] \textrm{ (réécriture)}\\
+& \equiv &   (1)^km [n] \textrm{ (théorème d'Euler)}\\
+& \equiv &   m [n] \textrm{ (réécriture)}\\
+\end{eqnarray*}
+\end{Proof}
+
+
+\begin{Exo}
+On considère l'algorithme suivant: 
+on choisit deux nombres premiers $p$ et $q$
+distincts tels que 
+$p \equiv 2 [3]$ et $s \equiv 2 [3]$.
+Soit $n = pq$. 
+Alice veut envoyer un message  à Bob. 
+Comme dans RSA, son message est un nombre $m \in \ \{1, . . . , n - 1\}$ 
+tel que $m \land  n = 1$
+Le message codé d'Alice est le résultat $a= m^3[n]$.
+Bob décode $a$ en calculant 
+\[
+m' \equiv a^{d} [n] \textrm{ où $d=\dfrac{2(p-1)(q-1)+1}{3}$} 
+\]
+Normalement $m$ doit être égal à $m'$.
+
+\begin{enumerate}
+\item Choisir $p=11$, $q=17$, $m=4$ puis construire le message codé ainsi que le message décodé.
+\item  Montrer que $d$ est toujours un entier.
+\item Expliquer pourquoi $a$ et $m'$ ne sont pas divisibles par $n$.
+\item Montrer que Bob a bien décodé le message d’Alice.
+\end{enumerate}
+
+\end{Exo}
+
+
+\begin{Prop}[Petit théorème de Fermat]
+Si $p$ est un nombre premier et $a$ un entier 
+alors $a^{p} \equiv a [p]$.
+\end{Prop}
+
+\begin{Proof}
+La preuve se fait par récurrence sur $a$. 
+\begin{itemize}
+\item Pour $a=0$, c'est trivial.
+\item Supposons la formule établie pour $k=a$ et montrons qu'elle l'est aussi
+pour $k=a+1$. 
+On remarque tout d'abord que pour chaque $k$, $0 < k < p$, le coefficient 
+binomial $\binom{p}{k} = \dfrac{p!}{k!(p-k)!}$ est divisible par $p$, c.-à-d.
+$\binom{p}{k} \equiv 0 [p]$.
+On a alors successivement:
+\begin{eqnarray*}
+(k+1)^p &=& a^p + 
+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\dots +\binom{p}{p-1}a^{1}+1\\
+&\equiv& a^p +1 [p]\textrm{ (d'après la remarque sur les coeff. binomiaux)}\\\
+&\equiv& a +1 [p]\textrm{ (par hypothèse de récurrence).}\\\
+\end{eqnarray*}
+\end{itemize}
+\end{Proof}
+
+\begin{Prop}[Corrolaire du petit théorème de Fermat]
+Si $p$ est un nombre premier et $a$ un entier non divisible par $p$,
+alors $a^{p-1}-1$ est un multiple de $p$.
+\end{Prop}
+\begin{Proof}
+D'après le petit théorème de Fermat, $a^{p}  \equiv a [p]$. Dit Autrement
+$p$ divise $a^{p} - a = a (a^{p-1}-1)$. Or $p$ est premier avec  $a$ d'après les 
+hypothèses. D'après le théorème de Gau{\ss}, $p$ divise $a^{p-1}-1$.
+\end{Proof}
+
 
 \begin{Exo}[Sujet du bac S Liban 2005]
-On rappelle le résultat suivant appelé petit théorème de Fermat.
+% On rappelle le résultat suivant appelé le corollaire du 
+% petit théorème de Fermat.
 
-\emph{Si $p$ est un nombre premier et $a$ un entier non divisible par $p$,
- alors $a^{p-1}-1$ est un multiple de $p$.}
+% \emph{Si $p$ est un nombre premier et $a$ un entier non divisible par $p$,
+%  alors $a^{p-1}-1$ est un multiple de $p$.}
 \begin{enumerate}
 \item  On considère l’équation $(E)$ : $109x-226y=1$ où $x$ et $y$
   sont des entiers relatifs.
@@ -329,18 +589,303 @@ $g(f(a))=a$ . Que peut-on dire de $f(g(a))=a$?
 \end{enumerate}
 \end{enumerate}
 \end{Exo}
-\section{Arithmétique modulaire}
-% cf TD maths discrète; 
-% Corollaire 7.6 du chap RSA
-% unicité de la clef de décodage
+
 
 
 \subsection{Puissance de grands nombres}
 
+\begin{Exp}
+Calculons $666^{999}[13]$.
+On a successivement:
+\begin{eqnarray*}
+666^{999} & \equiv & (13\times 51 + 3)^{999} [13]\\ 
+ & \equiv & 3^{999} [13]\\ 
+ & \equiv & 3^{12\times83 +3} [13] \\
+ & \equiv & 3^3 \times (3^{12})^{83} [13] \\
+ & \equiv & 3^3 \times (1)^{83} [13] \textrm{(car $3^{12}\equiv 1 [13]$ d'après le corollaire du petit théorème de Fermat)}\\ 
+ & \equiv & 27 [13]\\
+ & \equiv & 1 [13]
+\end{eqnarray*} 
+\end{Exp}
+
+
+
+\begin{Exo}
+Calculer $2^{500} [13]$ et $26^{1000} [17]$.
+\end{Exo}
+
+
+% \begin{Exo}
+% Montrer que si l'entier naturel $n$ est premier alors
+% $$(x +1)^n \equiv x^n +1[n].$$
+
+% On a même l'équivalence, cependant, l'autre sens est plus technique à démontrer.
+
+% \end{Exo}
+
+
+
+
+
 \section{Génération de grands nombres premiers}
+Dans ce qui suit, on nomme $\Prem$ l'ensemble des nombres premiers.
+Depuis Euclide, on sait que $\Prem$ est de taille infinie.
+Fermat avait cru donner une formule ne générant que des nombres premiers.
+Il affirmait que pour tout $n \in \N$, le nombre 
+\begin{eqnarray}
+F_n &= & 2^{2^n} +1 
+\end{eqnarray}
+était premier. Or 641 divise $F_5$. Aujourd'hui, on pense que seuls 
+les nombres de $F_0$ à $F_4$ sont premiers.
+
+\subsection{Distribution des nombres premiers parmi les entiers}
+
+Même si on ne connaît pas de formule permettant de construire tous les 
+nombres premiers, tout n'est pas perdu puisque les nombres premiers 
+ne sont pas si rares que cela. Le théorème suivant donne même 
+la proportion approximative des entiers inférieurs ou égaux à
+$N$  qui sont premiers.
+\begin{Prop}[Théorème des nombres premiers]
+La fonction $\pi:\N \rightarrow \N$  associe 
+à chaque nombre $N$ le nombre d'entiers inférieurs ou égaux à $N$ qui sont 
+premiers, soit $\pi(N) = |\{p \le N | p \textrm{ premier}\}|$.
+Lorsque $N$ est grand, on a:
+\begin{eqnarray}
+\pi(N) &\approx& \dfrac{N}{\ln(N)}
+\end{eqnarray}
+\end{Prop}
+La preuve de ce théorème est d'un niveau très avancé et n'est pas reproduite 
+ici.
+
+Pour obtenir un  entier de 100 chiffres, il suffit de considérer 
+$N= 10^{100}$. Si on choisit au hasard un nombre dans $\N_{N}^{*}$,
+la probabilité qu'il soit premier est: 
+\begin{eqnarray*}
+\textrm{Prob}(n \textrm{ premier}) &\approx&
+ \dfrac{\dfrac{N}{\ln(N)}}{N} \\
+ &\approx&
+ \dfrac{1}{\ln(N)}
+\end{eqnarray*}
+Le tableau~\ref{Table:propPrem} donne une valeur approchée de 
+cette probabilité pour quelques nombres de chiffres. 
+Dans celui-ci:
+\begin{itemize}
+\item la seconde ligne n'impose aucune restriction sur le dernier chiffre;
+\item la troisième ligne impose que le dernier chiffre soit dans 
+  $\{1,3,5,7,9\}$: il est  inutile de vérifier que les
+  multiples de 2 sont premiers!
+\item la quatrième ligne impose que le dernier chiffre soit dans $\{1,3,7,9\}$:
+  les multiples de 5 ne sont pas premiers!
+\end{itemize}
+On constate que si l'on tire au hasard un nombre (même de 100 chiffres), 
+parmi ceux qui se terminent par $\{1,3,7,9\}$ (ensemble noté $B$ par la suite) 
+la probabilité qu'il soit premier n'est pas infime. La solution au problème 
+de génération de nombres premiers repose sur la capacité ou non a disposer 
+d'un test efficace de primalité pour des grands nombres.
+
+%% Attention ce tableau est généré par ailleurs 
+\begin{table}[ht]
+\begin{center}
+\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|}
+ \hline 
+Nombre de chiffres & \textbf{75}& \textbf{100}& \textbf{125}& \textbf{150}& \textbf{175}& \textbf{200}& \textbf{225}& \textbf{250}& \textbf{275}& \textbf{300}\\
+\hline 
+Dernier chiffre quelconque & 172& 230& 287& 345& 402& 460& 518& 575& 633& 690\\
+\hline 
+Dernier chiffre impair & 86& 115& 143& 172& 201& 230& 259& 287& 316& 345\\
+\hline 
+Dernier chiffre dans $\{1,3,7,9\}$& 69& 92& 115& 138& 161& 184& 207& 230& 253& 276\\
+\hline
+ \end{tabular}
+\end{center}
+\caption{Probabilités inverse d'obtenir un nombre premier \label{Table:propPrem}}
+\end{table}
+
+
+On considère comme expérience aléatoire le fait de tirer un nombre au hasard 
+dans $B$. On a une probabilité $p$ que le nombre soit premier.
+Soit $X$ la variable aléatoire qui compte le nombre 
+de fois où l'on a réalisé cette expérience avant d'obtenir un nombre premier.
+$X$ suit une loi géométrique de paramètre $p$:
+\[
+P(X=k) = (1-p)^{k-1}p.
+\]
+Or l'espérance d'une variable aléatoire
+suivant une loi géométrique de paramètre $p$ est $\frac{1}{p}$.
+Pour 100 chiffres, il faudra en moyenne 92 tirages pour générer un 
+nombre premier. 
+
+Il \og reste \fg{} à fournir une méthode efficace pour décider 
+de la primalité d'un entier, ce que présente la section suivante.
+
+
+\subsection{Tests de primalité}
+Chaque section donne un algorithme permettant de décider si un entier $p$ fourni
+en entrée est premier ou non.
+
+\subsubsection{Méthode naïve}
+On vérifie s'il est divisible par l'un des entiers pairs compris entre 2 et 
+$\sqrt{p}$. Si la réponse est négative, alors $p$ est premier, 
+sinon il est composé. Pour améliorer la performance de cette méthode, on peut 
+calculer à l'avance une liste des nombres premiers inférieurs à $\sqrt{p}$
+(avec un crible d'Ératosthène), pour ne tester que ceux-ci.
+
+Par exemple, pour tester un nombre inférieur à 39 000, 
+il suffit de vérifier  qu'il n'est pas multiple d'un nombre premiers inférieur
+à 198 (car $198^2 = 39 204$); on doit faire au maximum 45 divisions.
+
+\subsubsection{Tests probabilistes}
+
+% \begin{Prop}[Corrolaire du petit théorème de Fermat]
+% Si $p$ est un nombre premier et $a$ un entier non divisible par $p$,
+% alors $a^{p-1}-1$ est un multiple de $p$, c'est-à-dire:
+% \begin{equation}
+%  \forall a\in \N \forall p \in \N (   p \in \Prem \textrm{ et }   a \not\equiv  0[p] 
+%   \Rightarrow a^{p-1}\equiv 1 [p]).
+% \label{petittheremeFermat}
+% \end{equation}
+% \end{Prop}
+
+
+\paragraph{Test de Fermat.}
+Le petit théorème de Fermat est une implication et non pas une équivalence:
+\begin{itemize}
+\item si on prend un $p\in \N$ et un $a \in\N$ quelconque, 
+  alors si $p$ est premier et $a$ non divisible par $p$, alors on peut en déduire que $a^{p-1}\equiv 1 [p]$;
+\item rien ne dit que si on a  $a^{p-1}\equiv 1 [p]$, alors $p$ est premier et $a$ non divisible par $p$.
+\item rien ne dit non plus que que si on a  $a^{p-1}\equiv 1 [p]$ et que $a$ non divisible par $p$, alors $p$ est premier.
+\end{itemize}
+Cependant si on effectue un grand nombre de fois l'expérience de choisir 
+$a \in \N_{n-1}^{*}$ et qu'à chaque fois on établit $a^{p-1}\equiv 1 [p]$, 
+alors $p$ est probablement premier.
+Cependant ce n'est pas toujours le cas: par exemple $2^{340} \equiv 1 [341]$ et 
+pourtant $341 =  11 \times 31$.
+
+\begin{Exo}
+Donner le code de la fonction \verb+testPrimaliteFermat(n,t)+ qui retourne 
+\verb+True+ si \verb+t+ evaluations de $\texttt{a}^{\texttt{n}-1}$ ont retourné $ 1 [\texttt{n}]$ 
+pour un $a \in \N_{n-1}^{*}$ et \verb+False+ sinon.
+\end{Exo}
+
+
+
+\paragraph{Test de Miller-Rabin}
+
+Soit $n$ un nombre premier impair,
+alors nous pouvons écrire $n - 1$ comme $2^s \times d$, 
+où $s$ est un entier et $d$ est impair.
+Alors, pour tout entier naturel $a \in \N_{n-1}^*$
+tel que $a$ est premier avec $n$, 
+une des conditions suivantes doit être vérifiée:
+\begin{enumerate}
+\item $a^{d} \equiv 1 [n]$, ou bien  
+\item $a^{2^r\cdot d} \equiv -1 [n]$ pour un certain $0 \le r \le s-1$.
+\end{enumerate} 
+La preuve de cette propriété est admise
+
+Le test de primalité de Miller-Rabin est basé sur les équations précédentes.
+Si on choisit un grand nombre $t$ de fois $a \in \N_{n-1}^*$
+et qu'on obtienne à chaque fois 
+\begin{itemize}
+\item $a^{d} \equiv 1 [n]$ ou 
+\item $a^{2^r\cdot d} \equiv -1 [n]$ pour un certain $0 \le r \le s-1$,
+\end{itemize}
+alors le nombre $n$ est probablement premier.
+Dans le cas contraire ($a^{d} \not\equiv 1 [n]$ et 
+$a^{2^r \cdot d} \not\equiv -1 [n]$ pour tous les  $0 \le r \le s-1$),
+$n$ n'est pas premier.
+
+\begin{Exo}
+Donner le code de la fonction \verb+testPrimaliteMillerRabin(n,t)+.
+\end{Exo}
+
 
 \section{Factorisation}
+L'objectif de cette partie est de montrer qu'on peut factoriser $n$ 
+sous la forme de $p\times q$ si ces deux derniers nombres ont été mal choisis.
+
+
+\begin{Exo}
+On considère que l'étape 1 de l'algorithme RSA a généré deux nombre premiers $p$ et $q$ proches tels que $p>q$. On définit  $t = \frac{p+q}{2}$ et $s = \frac{p-q}{2}$.
+Montrer que
+\begin{enumerate}
+\item le produit $n = pq = t^2 - s^2$;
+\item l'entier $t$ est légèrement supérieur à la racine carrée de $n$ et que $s $ est petit;
+\item l'on peut utiliser ces informations pour factoriser $n$ c.-à-d. retrouver $p$ et $q$;
+\item Factoriser 896861 et  318040531. % res=2953*3037     res = 17729*17939
+\item Factoriser 9623827 et 343570291. % res=(3259, 2953)     res = (19379, 17729)
+\end{enumerate}
+\end{Exo}
+
+\begin{TP}
+L'objectif de ce TP est d'implanter toute la démarche RSA 
+avec les éléments vus en TD. 
+% Tout ceci est à synthétiser dans un document 
+% libreoffice à renvoyer à l'adresse \url{couchot@femto-st.fr} avec pour sujet 
+% RSA-NOM1-NOM2-TDX.
+\begin{enumerate}
+\item Quel est le plus petit nombre à trois chiffres? 
+  Quel est le plus grand nombre à trois chiffres? 
+  Comment générer aléatoirement un nombre qui a trois chiffres en utilisant 
+  \verb+randint+?
+\item Même question que la question précédente, en remplaçant \og trois\fg{}
+  par $M$.  
+\item On a vu qu'un nombre se terminant par 0,2,4,5,6,8 n'est jamais premier.
+  Comment générer un nombre qui a $N$ chiffres, dont le dernier chiffre 
+  n'est pas  dans la liste précédente.
+\item Pour affirmer qu'un nombre de 100 chiffres 
+  est premier, on invoquera le test de Miller-Rabin avec 50
+  valeurs testées  différentes $a$. Si toutes retournent qu'il est 
+  probablement premier, on considérera qu'il l'est.
+  Construire la fonction \verb+genereUnNombrePremier(N)+ qui retourne 
+  un nombre probablement premier selon cette méthode.
+  %Copier-coller cette fonction dans votre synthèse.
+\item A l'aide de l'agorithme précédent, générer deux nombres premiers 
+  $p$ et $q$ de 100 chiffres.
+  %Copier et coller ces deux nombres dans votre synthèse.
+  Calculer $n=pq$ puis \verb+phi+ telle 
+  que \verb+phi=(p-1)*(q-1)+.
+
+\item Contruire la partie $e$ de la clé publique $(e,n)$
+  comme un nombre premier de trente chiffres par exemple. 
+  Si elle est première avec \verb+phi+, c'est une bonne clé, sinon on 
+  regénere un nombre premier de trente chiffres.
+  %Copier et coller $e$ dans votre synthèse.
+
+\item Donner le code la fonction \verb+bezout(+$a$,$b$\verb+)+ 
+qui retourne $x$ et $y$ tels que $x.a + y.b = a \land b$.
+
+%  \begin{verbatim}
+% def bezout(a,b):
+%   if b==0: return [1,0]
+%   else:
+%     uv= bezout(b,a%b)
+%     return [uv[1],uv[0]-uv[1]*(a/b)]
+% \end{verbatim}
+
+Se servir de cette fonction pour générer la partie $d$ de 
+la clé privée $(d,n)$. Attention, faire en sorte que $0 \le d \le$\verb+phi+.
+%Copier-coller les instructions permettant d'obtenir $d$.
+%Copier-coller la valeur de $d$.
+
+\item Chiffrer à l'aide de la clé publique $(e,n)$
+  le message $m=3402752281514000316845$  
+  qui est un numéro de carte bancaire comprenant les 16 chiffres, 
+  la date de validité et le code de sécurité. Le mesage chiffré est $a$.
+  %Copier-coller l'instructions permettant d'obtenir $a$.
+  %Copier-coller la valeur de $a$.
+  
+
+\item Déchiffrer $a$ à l'aide de la clé privée. 
+  Vérifier que vous obtenez bien $m$ à nouveau.
+  %Copier-coller l'instructions permettant de déchiffrer $a$.
+\end{enumerate} 
+
+
+ 
+\end{TP}
+
 
 
-\section{Conclusion}
-cf SMATH paragraphe applications p 223.
\ No newline at end of file
+% \section{Conclusion}
+% cf SMATH paragraphe applications p 223.
\ No newline at end of file