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

diff --git a/rsa.tex b/rsa.tex
index 0316be6..eee81e5 100644
--- a/rsa.tex
+++ b/rsa.tex
@@ -55,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$)
@@ -132,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
@@ -178,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$. 
@@ -214,6 +155,16 @@ r_{n}  & = & r_{n-2} - r_{n-1} \times q_{n}  \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]
@@ -221,7 +172,108 @@ 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 
@@ -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]
@@ -305,67 +358,7 @@ d'inconnues $x$ et $y$.
 \end{enumerate}
 \end{Exo}
 
-\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{Exo}[Sujet du bac S Liban 2005]
-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$.}
-\begin{enumerate}
-\item  On considÃ¨re lâÃ©quation $(E)$ : $109x-226y=1$ oÃ¹ $x$ et $y$
-  sont des entiers relatifs.
-\begin{enumerate}
-\item  DÃ©terminer $109\land 226$. 
-  Que peut-on en conclure pour l'Ã©quation $(E)$? 
-\item  Montrer que l'ensemble des solutions de $(E)$  
-  est l'ensemble des couples de la forme 
-  $(141+226k ;68+109k)$, oÃ¹ $k$ appartient Ã  $\Z$.
-  En dÃ©duire qu'il existe un unique entier naturel non nul $d$ 
-  infÃ©rieur ou Ã©gal Ã  226 et un unique entier naturel non nul $e$ tels que
-  $109d =1+226 e$ (on prÃ©cisera les valeurs des entiers $d$ et $e$).
-\end{enumerate}
-\item DÃ©montrer que 227 est un nombre premier.
-\item  On note $A=\{0,1,2,\dots,226\}$. On considÃ¨re les deux fonctions 
-  $f$ et $g$ de $A$ dans $A$ dÃ©finies de la maniÃ¨re suivante: 
-\begin{itemize}
-\item  A tout entier $a\in A$, $f$ associe le reste de
-  la division euclidienne de $a^{109}$ par 227.
-\item A tout entier $a\in A$, $g$ associe le reste de la
-  division euclidienne de $a^{141}$ par 227.
-\end{itemize}
-\begin{enumerate}
-\item VÃ©rifier que $g(f(0))=0$ .
-\item Montrer que, quel que soit l'entier non nul $a$ de $A$ , $a^{226}-1$ est multiple de 227.
-\item En dÃ©duire que, quel que soit l'entier non nul $a$ de $A$, 
-$g(f(a))=a$ . Que peut-on dire de $f(g(a))=a$?
-\end{enumerate}
-\end{enumerate}
-\end{Exo}
 
 
 
@@ -444,15 +437,22 @@ $261x +2$ soit multiple de 305.
 
 \begin{Exo}
 \begin{enumerate}
-\item DÃ©monter que $35 \equiv 1 [11]$
+\item DÃ©monter que $3^5 \equiv 1 [11]$
 \item En dÃ©duire que pour tous entiers naturels $k$ et $r$ on a 
-                                        $35k +r \equiv 3r [11]$.
+                                        $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}
 
 
 
@@ -492,6 +492,32 @@ a^d & \equiv &   (m^e)^d [n]\\
 \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]$.
@@ -526,6 +552,46 @@ $p$ divise $a^{p} - a = a (a^{p-1}-1)$. Or $p$ est premier avec  $a$ d'aprÃ¨s le
 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Ã© 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$.}
+\begin{enumerate}
+\item  On considÃ¨re lâÃ©quation $(E)$ : $109x-226y=1$ oÃ¹ $x$ et $y$
+  sont des entiers relatifs.
+\begin{enumerate}
+\item  DÃ©terminer $109\land 226$. 
+  Que peut-on en conclure pour l'Ã©quation $(E)$? 
+\item  Montrer que l'ensemble des solutions de $(E)$  
+  est l'ensemble des couples de la forme 
+  $(141+226k ;68+109k)$, oÃ¹ $k$ appartient Ã  $\Z$.
+  En dÃ©duire qu'il existe un unique entier naturel non nul $d$ 
+  infÃ©rieur ou Ã©gal Ã  226 et un unique entier naturel non nul $e$ tels que
+  $109d =1+226 e$ (on prÃ©cisera les valeurs des entiers $d$ et $e$).
+\end{enumerate}
+\item DÃ©montrer que 227 est un nombre premier.
+\item  On note $A=\{0,1,2,\dots,226\}$. On considÃ¨re les deux fonctions 
+  $f$ et $g$ de $A$ dans $A$ dÃ©finies de la maniÃ¨re suivante: 
+\begin{itemize}
+\item  A tout entier $a\in A$, $f$ associe le reste de
+  la division euclidienne de $a^{109}$ par 227.
+\item A tout entier $a\in A$, $g$ associe le reste de la
+  division euclidienne de $a^{141}$ par 227.
+\end{itemize}
+\begin{enumerate}
+\item VÃ©rifier que $g(f(0))=0$ .
+\item Montrer que, quel que soit l'entier non nul $a$ de $A$ , $a^{226}-1$ est multiple de 227.
+\item En dÃ©duire que, quel que soit l'entier non nul $a$ de $A$, 
+$g(f(a))=a$ . Que peut-on dire de $f(g(a))=a$?
+\end{enumerate}
+\end{enumerate}
+\end{Exo}
+
+
+
 \subsection{Puissance de grands nombres}
 
 \begin{Exp}
@@ -549,10 +615,13 @@ Calculer $2^{500} [13]$ et $26^{1000} [17]$.
 \end{Exo}
 
 
-\begin{Exo}
-Montrer que l'entier naturel $n$ est premier si et seulement si 
-$$(x +1) ^n \equiv x ^n +1[n].$$
-\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}
 
 
 
@@ -580,7 +649,7 @@ $N$  qui sont 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:
+Lorsque $N$ est grand, on a:
 \begin{eqnarray}
 \pi(N) &\approx& \dfrac{N}{\ln(N)}
 \end{eqnarray}
@@ -589,7 +658,7 @@ 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 $n$ dans $\N_{N}^{*}$,
+$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&
@@ -667,15 +736,15 @@ il suffit de vÃ©rifier  qu'il n'est pas multiple d'un nombre premiers infÃ©rieur
 
 \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}
+% \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.}
@@ -694,7 +763,7 @@ 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{p}-1}$ on retournÃ© $ 1 [\texttt{p}]$ 
+\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}
 
@@ -737,15 +806,86 @@ 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$ tels que $p>q$. On dÃ©finit  $t = \frac{p+q}{2}$ et $s = \frac{p-q}{2}$.
+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 9623827 et  343570291. % res=2953*3259     res = 17729*19379
+\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
