-\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$)
\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
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$.
\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]
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
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]
\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}
\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}
\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]$.
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}
\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}
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}
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&
\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.}
\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}
\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
