td.tex

   1
   2 % Objectifs pédagogiques :
   3 % arithmétique classique (pgcd, diviseur)
   4 % algorithme RSA
   5 % calculs modulo
   6 % Théorème de Bezout,  petit Fermat
   7 % Nombres premiers : tests simples, avancés, disctribution
   8 % Multiplications rapides:
   9 % Puissance rapides
  10 % Factorisation
  11
  12 % Cryptographie RSA : comprendre et approfondir
  13
  14
  15 \section{Introduction}
  16
  17 La \emph{cryptographie}, où l'art d'écrire avec une clé,
  18 est apparue en même temps que l'écriture.
  19 Dès qu'une information doit être transmise de manière sure,
  20 le message doit être protégé de toute interception: il est crypté par l'éméteur
  21 et décrypté parle récepteur.
  22 Dans le cas où l'on utilise une clef de cryptage, on a le schéma présenté
  23 à la figure~\ref{Fig:schemageneral}.
  24 \begin{figure}[ht]
  25 \includegraphics[scale=0.3]{schemacrypto.eps}
  26 \caption{Schéma général d'une méthode de cryptage/décryptage}\label{Fig:schemageneral}
  27 \end{figure}
  28 Dans cette figure, rien ne précise cependant que la clef de
  29 cryptage est la même que celle de décryptage.
  30 Lorsqu'une méthode se fondent sur une clé unique pour chiffrer et déchiffrer
  31 un message on emploie le terme de cryptographie \emph{symétrique}.
  32 Se pose immédiatement  le problème de confidentialité de la clef et la  mise
  33 en {\oe}uvre de celle-ci
  34 surtout lorsque le nombre de destinataires est grand:
  35 il faut une cle pour chacun d'entre eux.
  36
  37 Pour résoudre ce problème d'échange de clés, la cryptographie
  38 \emph{asymétrique} a été mise au point dans les années 1970.
  39 Elle se base sur le principe d'une clé publique pour le chiffrement et
  40 d'une clef privée pour le déchiffrement.
  41 Chaque destinataire (receveur)
  42 diffuse sa clé publique à quiconque désire chiffrer
  43 un message. Le message crypté  ne pourra être déchiffré qu'avec la clé privée,
  44 qui elle reste confidentielle.
  45
  46 RSA est un algorithme de cette famille. Son étude d'un point de vue mathématique
  47  est l'objectif de ce TD.
  48 Il s'inspire largement de~\cite{RSA09}
  49
  50 % Annonce plan
  51
  52
  53
  54 \section{L'algorithme RSA}
  55
  56 \subsection{Les étapes détaillées de l'algorithme}
  57
  58 On rappelle qu'un système cryptographique à clé publique est
  59 initialisé par le receveur, c.-à-d. celui qui veut recevoir des messages de
  60 manière sure.
  61
  62 \paragraph{Première étape: choix des deux nombres $p$ et $q$.}
  63 Le receveur choisit deux grands nombres premiers
  64 $p$ et $q$ et calcule $n = pq$. Puis il calcule $\varphi(n)$,
  65 où $\varphi : \Nat^* \rightarrow \Nat^* $ est la \emph{fonction d'Euler}
  66 définie par $\varph(n)$  est le nombre d'entiers dans $\{1, 2, \dots , n -1 \}$
  67 qui sont premiers avec $n$.
  68 \paragraph{Deuxième  étape: choix de la clef publique.}
  69 Le receveur choisit $e \in
  70 \{1, \dots , n-1\}$  premier avec $\varphi(n)$.
  71 La clef publique est la paire $(e,n)$. L'expéditeur
  72 va s'en servir pour encoder son message.
  73 \paragraph{Troisième  étape: construction de la clef privée.}
  74 Le receveur calcule l'entier $d \in \{1,\dots, n-1\}$
  75 tel que le reste de la division de $ed$ par $\varphi(n)$ est 1.
  76 Ceci se note aussi $ed \equiv 1 [\varphi(n)]$ qui se lie $ed$ est congru
  77 à 1 modulo $\varphi(n)$.
  78 La paire $(d,n)$ est la clef privée de décryptage. Elle
  79 est secrète et permet au receveur de décrypter tous les messages recus
  80 et cryptés avec $(e,n)$.
  81 \paragraph{Quatrième  étape: cryptage du message.}
  82 L’expéditeur peut crypter tout message écrit sous la forme
  83 d'un nombre $m$ appartenant à $\{1, \dots , n-1\}$ et qui est
  84 premier avec $n$.
  85 Le message codé est le reste $a$ de la division de $me$ par $n$.
  86 On a donc $me \equiv a [n]$, où $a \in \{1, \dots , n - 1\}$.
  87 \paragraph{Cinquième  étape:  décryptage du message.}
  88 Le receveur dispose de $a$ et de sa clé privée $(d,n)$.
  89 Pour décrypter $a$, il calcule le reste dans la division par $n$
  90 de $ad$ (c.-à-d. $ad [n]$). C'est précisément le message initial $m$.
  91
  92
  93 \subsection{Sur un exemple très petit}
  94 Le receveur choisit $p=7$, $q=13$.
  95 \begin{enumerate}
  96 \item Construire l'ensemble des entiers qui sont premiers avec $n=pq$
  97   et en déduire que $\varphi(91)=72$.
  98 \item Montrer que $(29,91)$ est un candidat acceptable de clef publique.
  99 \item Trouver la clef privée associée.
 100 \item Montrer que  l'expéditeur a la possibilité de crypter le message $m=59$.
 101 \item Construire le message codé $a$ à l'aide de la clé publique.
 102 \item Décoder le message $a$ à l'aide de la clé privée. Il doit s'agir de $m$.
 103 \end{enumerate}
 104
 105
 106 \subsection{Les points clés}
 107 L'algorithme RSA repose sur plusieurs points clés rencontrés successivement:
 108 \begin{itemize}
 109 \item la génération de deux grands nombres premiers $p$ et $q$ ;
 110 \item la multiplication de grands nombres : $pq$, $ed$,
 111 \item l'arithmétique modulaire;
 112 \item l'algorithme d'Euclide de génération de PGCD et son corollaire de Bezout;
 113 \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.
 114 \end{itemize}
 115
 116 \section{Arithmétique modulaire}
 117
 118 \section{Coefficients de Bézout}
 119
 120 \section{Puissance de grands nombres}
 121
 122 \section{Génération de grands nombres premiers}
 123
 124 \section{Factorisation}
 125
 126
 127 \section{Conclusion}
 128 cf SMATH paragraphe applications p 223.