arithmetique/cryptologie.tex

   1
   2
   3 \section{Méthodes de cryptage \og à clé publique\fg{} }
   4 \subsection{Principe}
   5 Supposons qu'un individu $A$ soit obligé de transmettre à un autre individu $B$ un message $M$ en utilisant un réseau de communication public, par exemple les ondes hertziennes. N'importe quel individu peut se mettre à l'écoute et intercepter le message.\\
   6
   7
   8 Le problème est donc :
   9 \begin{itemize}
  10 \item le message doit être inintelligible pour tout individu autre que $A$ et $B$.
  11 \item $B$ doit pouvoir le comprendre.
  12 \item $B$ doit pouvoir s'assurer que le message provient bien de $A$ (et non d'un plaisantin quelconque).\\
  13 \end{itemize}
  14
  15
  16 L'idée est de doter tous les participants de la même méthode de cryptage. Les résultats du cryptage d'un même message par divers individus sont cependant différents, car chacun d'entre eux emploie une \og clé\fg{} qui lui est propre.
  17
  18 \begin{Ex}
  19 Lorsque l'on remplace 'a' par 'c', 'b' par 'd', etc\ldots, la méthode de cryptage est \og décalage des lettres de l'alphabet\fg{} et la clé est la longueur du décalage, ici 2.
  20 \end{Ex}
  21
  22
  23
  24 La méthode de cryptage est fondée sur l'existence de fonctions $f$, dépendant d'un paramètre (la \og clé\fg{} ), inversibles, mais pour lesquelles la détermination de l'inverse est matériellement impossible, en l'état actuel des connaissances humaines.\\
  25
  26
  27 Soit $f_A$ la fonction de cryptage qui utilise la clé propre à
  28 l'individu $A$.
  29 \begin{itemize}
  30  \item La clé de A est publique, ainsi n'importe qui est en mesure d'appliquer la fonction $f_A$ à un message $M$ quelconque.
  31 \item Par contre, seul $A$ connaît la fonction inverse $f_A^{-1}$ qui permet de retrouver le message initial.\\
  32 \end{itemize}
  33
  34
  35
  36 Au message $M$ , $A$ applique en fait $f_A^{-1}$ (il est le seul à
  37 pouvoir le faire).
  38
  39
  40
  41 Puis, à ce message $f_A^{-1}(M)$, il applique la fonction de cryptage de $B$, soit $f_B$ (il peut le faire, la clé de $B$ est publique), pour obtenir $f_B\circ f_A^{-1}(M)$, incompréhensible car les clés sont évidemment uniques, et donc $f_B\circ f_A^{-1}$ n'est pas l'identité.\\
  42
  43
  44
  45 C'est ce message \og doublement\fg{} crypté qui est envoyé. $B$ le reçoit et lui applique aussitôt $f_B^{-1}$, ce qu'il est le seul à pouvoir faire, pour obtenir $f_A^{-1}(M)$, auquel il applique $f_A$ : si le résultat est compréhensible, $B$ est sûr que le message lui était bien destiné, et qu'il a bien été envoyé par $A$.
  46
  47
  48
  49 \subsection{Utilisation de l'indicatrice d'Euler}
  50
  51 \begin{Exo}[Fonction indicatrice d'Euler]
  52 Soit $n$ un entier strictement positif; on note $\varphi(n)$ le nombre des entiers inférieurs à $n$ qui sont premiers avec $n$.
  53
  54 L'application de $\Net$ dans $\Net$ ainsi définie est appelée \emph{fonction indicatrice d'Euler}.
  55 \begin{enumerate}
  56 \item Montrer que, pour $p$ premier, $\varphi(p) = p - 1$
  57 \item Montrer que, pour $p$ premier, $\varphi(p^{\alpha}) = p^\alpha-p^{\alpha-1}$
  58 \item On considère les nombres de la
  59 forme $ap+bq$, pour $p$ et $q$ premiers entre eux et l'application de
  60 $(\Z/q\Z)\times(\Z/p\Z)$ dans $(\Z/pq\Z)$
  61 définie par $(a,b)\fc ap+bq\ [pq]$; montrer que cette application est injective et surjective.
  62 \item En déduire (en utilisant les nombres de la forme $ap+bq\ [pq]$) que, pour $p$ et $q$
  63 premiers entre eux, $\varphi(pq)=\varphi(p)\varphi(q)$. \item
  64 Utiliser le résultat précédent et le théorème de Fermat ci-dessus pour prouver que, pour tout entier $a$ premier avec $n$, et
  65 pour tout entier positif $n$ dépourvu de facteur carré, $a^{\varphi(n)}\equiv 1\ [n]$.
  66 \end{enumerate}
  67 \end{Exo}
  68
  69 \subsubsection{Résultat de base}
  70
  71 Diverses fonctions \og à inverse difficile à déterminer\fg{} ont été
  72 proposées. Les plus satisfaisantes sont celles qui utilisent le
  73 résultat suivant :
  74
  75 \begin{Th}
  76 s'il est très facile d'obtenir un très grand nombre entier composé par produit de deux nombres premiers eux-mêmes grands, la décomposition en facteurs premiers d'un nombre composé est très difficile.
  77 \end{Th}
  78
  79 \subsubsection{Méthode de cryptage}
  80
  81 La méthode de cryptage est la suivante :
  82
  83 \begin{enumerate}
  84  \item Soit donc $n = pq$ un entier, produit de deux nombres entiers premiers, par exemple tels que $p \equiv q \equiv 2 [3]$.
  85  \item Soit $M$ le message, préalablement chiffré (sans précautions particulières, par exemple en remplaçant les lettres par leurs codes ASCII).
  86 \item Si $M\geqslant n$, on décompose $M$ en plusieurs sous-messages, ses \og chiffres\fg{} en base $n$, par exemple.
  87 \item Si $n$ est la clé choisie par $A$, et pour $M<n$, $f_A(M)=C$, avec $C\equiv M^3\ [n]$. Comme $n$ est connu de tous, n'importe qui peut calculer $C$ très rapidement. Par contre, les facteurs premiers $p$ et $q$ de $n$ sont soigneusement tenus secrets par $A$.
  88 \item Un résultat (élémentaire) d'arithmétique indique que, comme $n$ n'a pas de facteur carré, si $M$ est premier avec $n$, alors $M^{\varphi(n)}\equiv 1\ [n]$ (dans cette expression, $\phi$ est la fonction indicatrice d'Euler, c'est-à-dire que $\varphi(n)$ est le nombre de nombres strictement positifs inférieurs à $n$ qui sont premiers avec $n$).
  89 \item Un autre résultat (élémentaire) d'arithmétique dit que, comme $n=pq$, avec $p$ et $q$ premiers, $\varphi(n)=\varphi(pq)=\varphi(p)\varphi(q)=(p-1)(q-1)$.
  90 \item On a donc, en combinant ces deux résultats,
  91 $M^{(p-1)(q-1)}\equiv 1\ [n]$, donc $M^{2(p-1)(q-1)}\equiv 1\ [n]$, et
  92 finalement $M^{2(p-1)(q-1)+1}\equiv M\ [n]$.
  93 \item Comme on a choisi $p\equiv q\equiv 2\ [3]$, $(p-1)(q-1)\equiv 1\ [3]$, $2(p-1)(q-1)\equiv 2\ [3]$ et $2(p-1)(q-1)+1\equiv 0\ [3]$. Il s'agit donc d'un multiple de 3, on peut poser $2(p-1)(q-1)+1=3k$, et on a $M^{3k}\equiv M\ [n]$.
  94 \item Or $M^{3k}=(M^3)^k$, donc, si le message crypté est $C\equiv M^3\ [n]$, $C^k\equiv M\ [n]$ et la connaissance de $k=\fr{2(p-1)(q-1)+1}3$ permet de retrouver le message original.
  95 \end{enumerate}
  96
  97 \begin{Ex}
  98 Avec $p=5$, $q=11$, $n=pq=55$.
  99
 100 Le message à envoyer est chiffré $M=7$.
 101
 102 Alors $7^2\equiv 49\ [55]$, $7^3\equiv 13\ [55]$.
 103
 104 Le message crypté est $C=13$.
 105
 106 Ici $k=\fr{2\times 4\times 10+1}3=27$, donc $M\equiv 13^{27}\ [55]$.
 107
 108 On a $13^{27}=13^{16+8+2+1}$, or $13^2\equiv 4\ [55]$, $13^4\equiv 4\times 4\equiv 16\ [55] $, $13^8\equiv 16\times 16\equiv 256\equiv 36\ [55] $ $13^{16}\equiv 36\times 36\equiv 1296\equiv 21\ [55]$, donc $13^3\equiv 4\times 13\equiv 52\ [55]$ , $13^{11}\equiv 52\times 36\equiv 37\ [55]$, $13^{27}\equiv 37\times 21\equiv 7\ [55]$.
 109 \end{Ex}
 110
 111
 112 Si, par malchance, $M$ est un multiple de $p$ ou de $q$, il suffit
 113 de modifier légèrement le premier chiffrage, par exemple en introduisant un espace supplémentaire dans les caractères du message d'origine, ce qui ne modifie pas son sens. Ne pas oublier cette précaution indispensable.
 114
 115
 116 \section{Choix d'un nombre n}
 117
 118 Dans l'exemple ci-dessus, le cryptage est immédiatement percé à jour, puisque la décomposition de 55 en ses facteurs premiers 5 et 11 est immédiate. On peut en dire autant de tout entier représentable sur 32 bits.\\
 119
 120 Il faut aller chercher bien plus loin pour assurer un minimum de sécurité. Pour fixer les idées, les clés utilisées sont à l'heure actuelle le produit de deux nombres qui ont entre 100 et 200 chiffres dans leur représentation décimale.
 121
 122
 123 \subsection{Nombres premiers}
 124
 125 Pour produire un nombre $n$ utilisable, il faut tout d'abord trouver deux
 126 nombres $p$ et $q$ premiers, suffisamment grands.\\
 127
 128 On choisit deux nombres se terminant par 1, 3, 7 ou 9 dans leur représentation décimale et de longueurs comparables (mais pas trop proches : il existe un algorithme de décomposition qui est capable de décomposer rapidement un nombre qui est le produit de deux nombres de
 129 longueurs très proches).\\
 130
 131 Il faut vérifier qu'ils sont premiers et, pour cela, disposer d'un critère de primalité (voir plus loin).\\
 132
 133 Lorsque le nombre produit au hasard n'est pas premier, il suffit de lui ajouter 2 , puis encore 2 etc., jusqu'à obtenir un nombre premier, ce qui interviendra très rapidement.\\
 134
 135 Avec ces deux nombres premiers $p$ et $q$ ainsi obtenus, on obtient la clé $n$.
 136
 137
 138 \subsection{Décomposition en facteurs premiers}
 139
 140 Théoriquement, bien sûr, la décomposition d'un nombre composé (non premier) est un problème résolu : il suffit de tenter de le diviser par tous les nombres premiers jusqu'à sa racine carrée.\\
 141
 142
 143 Pratiquement, cet algorithme est totalement impraticable dès que la longueur du nombre dépasse une vingtaine de chiffres décimaux (durée d'exécution trop élevée).\\
 144
 145 La durée d'exécution d'un algorithme de décomposition en facteurs premiers dé\-pend, bien sûr, de la longueur du nombre à décomposer. Mais il n'y a pas proportionnalité stricte : cela dépend aussi de l'algorithme utilisé. Pour prendre un exemple limite, 1000!, qui est un nombre dont la représentation décimale occupe plus de 4000 chiffres, est décomposé en quelques fractions de seconde par le plus rudimentaire des algorithmes.\\
 146
 147 Le seul moyen, donc, pour savoir si un nombre $n$ obtenu comme ci-dessus est une \og bonne\fg{} clé, est de tenter de le décomposer par tous les algorithmes connus. S'il résiste vaillamment, on peut l'adopter, sinon, il faut en changer.\\
 148
 149 La conclusion de cette présentation est qu'il est donc nécessaire de disposer d'un test de primalité et d'algorithmes de décomposition en facteurs premiers, questions que nous allons aborder dans les paragraphes suivants.