
% 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


\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'éméteur
et décrypté parle récepteur.
Dans le cas où l'on utilise une clef de cryptage, on a le schéma présenté 
à la figure~\ref{Fig:schemageneral}.
\begin{figure}[ht]
\includegraphics[scale=0.3]{schemacrypto.eps}
\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 clef 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 clef et la  mise 
en {\oe}uvre de celle-ci 
surtout lorsque le nombre de destinataires est grand: 
il faut une cle 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 clef 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 : \Nat^* \rightarrow \Nat^* $ est la \emph{fonction d'Euler} 
définie par $\varph(n)$  est le nombre d'entiers dans $\{1, 2, \dots , n -1 \}$ 
qui sont premiers avec $n$.
\paragraph{Deuxième  étape: choix de la clef publique.} 
Le receveur choisit $e \in 
\{1, \dots , n-1\}$  premier avec $\varphi(n)$.
La clef publique est la paire $(e,n)$. L'expéditeur
va s'en servir pour encoder son message.
\paragraph{Troisième  étape: construction de la clef 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 clef privée de décryptage. Elle
est secrète et permet au receveur de décrypter tous les messages recus
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 $me$ par $n$. 
On a donc $me \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 $ad$ (c.-à-d. $ad [n]$). C'est précisément 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 clef publique.
\item Trouver la clef privée associée.
\item Montrer que  l'expéditeur a la possibilité de crypter le message $m=59$.
\item Construire le message codé $a$ à l'aide de la clé publique.
\item Décoder 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 Bezout;
\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{Arithmétique modulaire}

\section{Coefficients de Bézout}

\section{Puissance de grands nombres}

\section{Génération de grands nombres premiers}

\section{Factorisation}


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