debut premiers

[modelisationMathS3.git] / rsa.tex

% Objectifs pédagogiques :
% arithmétique classique (pgcd, diviseur)
% algorithme RSA
% calculs modulo 
% Théorème de Bezout,  petit Fermat
% Nombres premiers : tests simples, avancés, disctribution
% Multiplications rapides:  
% Puissance rapides 
% Factorisation 

% Cryptographie RSA : comprendre et approfondir
% on doit discuter de la taille des nombres premier pour pouvoir coder tout mot.
% on doit pouvoir déduire  de l'unicité de la clé d pour une cle e

\section{Introduction}

La \emph{cryptographie}, où l'art d'écrire avec une clé, 
est apparue en même temps que l'écriture.
Dès qu'une information doit être transmise de manière sure,
le message doit être protégé de toute interception: il est crypté par l'émetteur
et décrypté par le récepteur.
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}
\end{figure}
Dans cette figure, rien ne précise cependant que la clé de
cryptage est la même que celle de décryptage.
Lorsqu'une méthode se fondent sur une clé unique pour chiffrer et déchiffrer
un message on emploie le terme de cryptographie \emph{symétrique}. 
Se pose immédiatement  le problème de confidentialité de la clé et la  mise 
en {\oe}uvre de celle-ci 
surtout lorsque le nombre de destinataires est grand: 
il faut une clé pour chacun d'entre eux.

Pour résoudre ce problème d'échange de clés, la cryptographie 
\emph{asymétrique} a été mise au point dans les années 1970.
Elle se base sur le principe d'une clé publique pour le chiffrement et 
d'une clé privée pour le déchiffrement.
Chaque destinataire (receveur)
diffuse sa clé publique à quiconque désire chiffrer 
un message. Le message crypté  ne pourra être déchiffré qu'avec la clé privée,
qui elle reste confidentielle.

RSA est un algorithme de cette famille. Son étude d'un point de vue mathématique
 est l'objectif de ce TD.
Il s'inspire largement de~\cite{RSA09} 

% Annonce plan



\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}

Soit deux entiers $a$ et $b$ dans $\Z$.
On dit que $a$ divise $b$ (que l'on note $a | b$)
s'il existe un entier $q \in \Z$ tel que $b = aq$. 

Le plus grand diviseur commun (PGCD) de 
$a$ et $b$, noté $a\land b$ est l'entier naturel qui vérifie 
\begin{itemize}
\item $a \land b | a$ et $a \land  b | b$;
\item Si $d | a$ et $d | b$, alors $d | a\land b$.
\end{itemize}

\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
est divisible par tout entier non nul, donc par $a$, qui l'est aussi par $a$) 
et enfin le PGCD de 0 et de 0 n'est pas
défini.

On se limite ici au cas de deux entiers $a$ et $b$ strictement positifs. Supposons par exemple $a>b$

\begin{enumerate}
\item La division euclidienne de $a$ par $b$ peut s'écrire $a=bq+r$ avec $0\infeg r<b$.

\item Montrons que \og $d$ est un diviseur commun à $a$ et $b$ \fg{}
  est équivalent à  \og $d$ est un diviseur commun à $b$ et $r$ \fg{}.
\begin{itemize}
\item  Soit $d$ un diviseur commun à $a$ et $b$, qui peuvent alors s'écrire $a=da'$ et $b=db'$. L'égalité $a=bq+r$ devient $da'=db'q+r$ ou encore $r=d(a'-b'q)$, donc $d$ est aussi un diviseur commun à $b$ et $r$.

\item Réciproquement, soit $d$ un diviseur commun à $b$ et $r$, qui peuvent alors s'écrire $b=db'$ et $r=dr'$ et l'égalité $a=bq+r$ devient $a=d(b'q+r')$.
Donc $d$ est un diviseur commun à $a$ et $b$.
\end{itemize}

Ainsi, les ensembles des diviseurs communs à $a$ et $b$ 
d'une part et à $b$ et $r$ d'autre part sont identiques.
En particulier $a\et b=b\et r$.

\item Si $r=0$ on a $a\et b= b\et 0$ qui est égal à $b$.

\item Sinon,  $r$ est différent de $0$ et on peut donc effectuer la
  division euclidienne de $b$ par $r$, qui donne un reste $r_{1}$, 
  tel que $0 \le r_{1}<r$ et $b\et r=r\et r_{1}$.

\item Cet algorithme est itéré jusqu'à l'obtention d'un reste nul, ce qui se produit obligatoirement puisqu'il s'agit d'entiers et que la suite des restes ainsi construite est strictement décroissante.
  Le PGCD est alors l'avant-dernier reste (le dernier non nul).
\end{enumerate}

\begin{Exo}
Déterminer $154 \land 35$ par l'algorithme d'Euclide.
\end{Exo}


\begin{Exo}
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$. 
Il existe un couple d'entiers $x$ et $y$ tels que $ax+by=d$, 
où $d$ est le PGCD de $a$ et de $b$. 
\end{Prop}

\begin{Proof}
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 \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 \nonumber 
\end{eqnarray}


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 \\
& \vdots & \nonumber \\
& = & \ldots (\textrm{on remplace $r_{1}$ par sa def dans (\ref{eq:def:r1})}) \nonumber\\ 
& = &ax + by \nonumber
\end{eqnarray}
\end{Proof}



\begin{Def}[Nombres premiers entre eux]
Les deux entiers relatifs $a$ et $b$ sont premiers entre eux si 
leur plus grand commun diviseur est égal à 1.
\end{Def}



\begin{Prop}[Théorème de Bézout]
Deux entiers strictement positifs 
$a$ et $b$ sont premiers entre eux, si et seulement s'il
existe un couple $(x,y)$ d'entiers relatifs vérifiant $ax + by = 1$.
\end{Prop}
\begin{Proof}
\begin{itemize}
\item[\textbf{Seulement si.}] Supposons $a$ et $b$ premiers entre eux. 
D'après l'identité de Bézout, 
il existe donc un couple d'entiers $x$ et $y$ tels que $ax+by=1$, 
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$.
  L'entier $d$ divise les produits $ax$ et $by$. Donc $d$ divise 
  $ax + by$ et donc $d$ est 1.   
\end{itemize}
\end{Proof}

\begin{Prop}[Théorème de Gau{\ss}]
Soient $a$, $b$ et $c$ trois entiers naturels. 
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
\end{Exo}

\begin{Prop}[Fonction d'Euler]
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}
\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$.
\begin{enumerate}
\item Construire l'ensemble $P$ des entiers naturels multiples de $p$ inférieurs à $pq -1$. Combien en a-t-on?
\item Construire l'ensemble $Q$ des entiers naturels multiples de $q$ inférieurs à $pq -1$. Combien en a-t-on?
\item Supposons qu'un élément $k$ appartienne à la fois à $P$ et à $Q$.
  Montrer que cela implique qu'il existe deux entiers naturels 
  $m_1$ et $m_2$ tels que $m_1.p = m_2.q$.
\item En utilisant le théorème de Gau{\ss}, montrer que cela est absurde.
\item En déduire l'équation (\ref{FEuler}).
\end{enumerate}
\end{Exo}




%Refaire cet exo avec 27x +8y = 1
\begin{Exo}
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 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}[Sujet du bac S Liban 2005]
On rappelle le résultat suivant appelé 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}



\section{Arithmétique modulaire}

\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 $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 exite $x$ et $y$ entiers tels que 
\end{itemize} 
\end{Proof}


\begin{Exo}
\begin{enumerate}
\item Démonter que $35 \equiv 1 [11]$
\item En déduire que pour tous entiers naturels $k$ et $r$ on a 
                                        $35k +r \equiv 3r [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$, $3n + 7$ est divisible par 11
\end{enumerate}
\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]
  Si $m<n$ est  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}

\subsection{Puissance de grands nombres}


\begin{Exo}
Montrer que l'entier naturel $n$ est premier si et seulement si 
$$(x +1) ^n \equiv x ^n +1[n].$$
\end{Exo}


\section{Génération de grands nombres premiers}
Depuis Euclide, on sait qu'il y a une infinité de nombres premiers.
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, les qutres étant composés.

\subsection{Distribution des nombres premier 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 distribution 
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$ 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 $n$ 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), 
et que ce nombre se termine par$\{1,3,7,9\}$, 
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.

Pour peut qu'on dispose d'un test de primalité rapide,
 

il \og suffit \fg{}
de tirer quelques nombres au hasard pour avoir  

%% 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 \label{Table:propPrem}}
\end{table}

\subsection{Tests de primalité}



\section{Factorisation}


\section{Conclusion}
cf SMATH paragraphe applications p 223.