\documentclass[11pt]{article} \usepackage{fullpage,french,epsf,fancyheadings} \pagestyle{fancy} \lhead{Arithmétique et cryptographie} \rhead{Jean-Christophe Filliâtre} \newcommand{\IN}{\mbox{I\!N}} \newcommand{\bi}{big\_int} \newtheorem{theoreme}{Théorème} \renewcommand{\pmod}[1]{~(\mbox{mod}~#1)} \newcommand\point{{\noindent$\bullet$~}} \begin{document} \begin{center} \LARGE\bf Arithmétique et cryptographie \end{center} \bigskip Dans ce TP, nous utiliserons le module \verb!big_int! de Caml Light qui implémente des entiers en précision arbitraire. Ce module définit un type abstrait \verb!big_int! des entiers. Afin d'afficher convenablement les valeurs de ce type, on commencera par installer le ``pretty-printer'' correspondant : \begin{verbatim} #open "big_int";; let pprinter b = format__print_string (string_of_big_int b);; install_printer "pprinter";; \end{verbatim} \noindent Les fonctions de ce module nécessaires à ce TP sont données à la fin de ce sujet. \section{Algorithme d'Euclide} \subsection{Algorithme d'Euclide originel} Soient $u,v \in \IN$. L'algorithme suivant, dit {\em algorithme d'Euclide}, calcule le pgcd de $u$ et $v$ : \begin{center}\begin{minipage}{10cm}\begin{description} \item[A1] Si $v=0$ alors la réponse est $u$. \item[A2] Faire $(u,v) \leftarrow (v,u \bmod v)$. Retourner en {\bf A1}. \end{description}\end{minipage}\end{center} \point Justifier cet algorithme (on posera $0\wedge0=0$ par convention). Ecrire une fonction {\tt euclide : \bi\ ->~\bi\ ->~\bi} implémentant l'algorithme d'Euclide. \paragraph{Complexité.} La complexité de l'algorithme d'Euclide est donnée par le résultat suivant : \begin{theoreme}[G. Lamé, 1845] Si $0 \leq u,v < N$, le nombre de divisions dans l'algorithme d'Euclide appliqué à $u$ et $v$ est au plus $\lceil\log_\phi(\sqrt{5}N)\rceil-2$, où $\phi$ est le nombre d'or $\frac{1+\sqrt{5}}{2}$. \end{theoreme} \subsection{Algorithme d'Euclide étendu} Soient $u,v \in \IN$. L'algorithme d'Euclide peut-être adapté pour calculer, en même temps que le pgcd de $u$ et $v$, les coefficients de Bezout. L'algorithme suivant calcule un vecteur $(u_1,u_2,u_3)$ tel que $uu_1 + vu_2 = u_3 = u\wedge v$. \newcommand{\vu}{(u_1,u_2,u_3)} \newcommand{\vv}{(v_1,v_2,v_3)} \newcommand{\vt}{(t_1,t_2,t_3)} \begin{center}\begin{minipage}{10cm}\begin{description} \item[B1] $\vu \leftarrow (1,0,u)$, $\vv \leftarrow (0,1,v)$. \item[B2] Si $v_3=0$ alors la réponse est $\vu$. \item[B3] Soit $q = \lfloor u_3/v_3 \rfloor$. Faire \par $\vt \leftarrow \vu - q\vv$, \par $\vu \leftarrow \vv$ \par $\vv \leftarrow \vt$. \par Retourner en {\bf B2}. \end{description}\end{minipage}\end{center} \point Justifier cet algorithme (on déterminera l'invariant de boucle). Ecrire une fonction {\tt bezout : \bi\ ->~\bi\ ->~\bi~*~\bi~*~\bi} qui implémente cet algorithme. \subsection{Application : division modulo $m$} Soient $u,v,m \in \IN^\star$ tels que $v\wedge m = 1$. On appelle quotient de $u$ par $v$ modulo $m$ tout entier $w$ tel que $0 \leq w < m$ et $u \equiv vw\pmod{m}$. \medskip \point Ecrire une fonction calculant le quotient de $u$ et $v$ modulo $m$. \section{Décomposition en facteurs premiers} Etant donné $n \in \IN$, $n$ s'écrit de manière unique sous la forme \begin{equation}\label{decomposition} n = p_1p_2\ldots p_k \qquad\mbox{avec}\quad p_1\leq p_2\leq\ldots\leq p_k \quad\mbox{et}\quad p_i\mbox{ premier} \end{equation} On se propose ici de déterminer les facteurs $p_i$. \subsection{Méthode par division} La méthode la plus simple est la suivante : si $n>1$ on teste la divisibilité de $n$ par les nombres premiers successifs $p=2,3,5,\ldots$ jusqu'à ce que $n \equiv 0\pmod{p}$. On remplace alors $n$ par $n/p$ et on reprend à $p$. Lorsque $n\not\equiv 0\pmod{p}$ avec $\lfloor n/p\rfloor \leq p$ on s'arrête, avec $n$ premier. Cette méthode a l'inconvénient qu'il faut déterminer la séquence des nombres permiers. Mais on peut simplifier cette méthode de la fa\c con suivante : Soit $n \in \IN^\star$ dont on souhaite déterminer la décomposition en facteurs premiers. Soit $(d_i)$ une séquence d'entiers $$2=d_0 < d_1 < d_2 < \ldots$$ qui inclut tous les nombres premiers $\leq \sqrt{n}$ et au moins un élément $d_k \geq \sqrt{n}$. Alors l'algorithme suivant détermine la décomposition de $n$ en facteurs premiers : \begin{center}\begin{minipage}{10cm}\begin{description} \item[A1] $t \leftarrow 0$, $k \leftarrow 0$. \item[A2] Si $n=1$ c'est terminé. \item[A3] On divise $n$ par $d_k$ : $n = qd_k+r$ avec ($0 \leq rd_k$ alors $k \leftarrow k+1$ et aller en {\bf A3}. \item[A6] $t \leftarrow t+1$, $p_t \leftarrow n$. C'est terminé. \end{description}\end{minipage}\end{center} \point Justifier cet algorithme. Ecrire une fonction {\tt decomp : \bi~list ->~ \bi\ ->~\bi\ list} prenant en argument une séquence $(d_k$) pour $n$, $n$ et rendant la séquence des $p_i$ telle que (\ref{decomposition}). \medskip On pourrait prendre pour $(d_k$) la séquence $2,3,5,7,\ldots$, c'est-à-dire 2 puis tous les impairs à partir de 3. Mais on peut prendre plutôt la séquence $2,3,5,7,11,13,17,19,23,25,\ldots$, c'est-à-dire ajouter alternativement 2 et 4 à partir de 5 (on supprime ainsi tous les multiples de 2 et 3). \medskip \point Ecrire une fonction \verb!dk! prenant $n$ en argument et renvoyant une telle séquence $d_0, \ldots, d_k$ avec $d_k \geq \sqrt{n}$. \medskip On peut gagner encore 20\% sur cette séquence en supprimant les entiers de la forme $30m\pm5$, et encore 14\% en supprimant les multiples de 7, etc. Si $n$ est petit on peut utiliser une table des nombres premiers (pour $n \leq 10^6$ il n'y a que 168 nombres premiers dans une telle table). \paragraph{Complexité.} La complexité de cet algorithme est un problème très difficile, mais en pratique l'algorithme n'est plus guère utilisable au delà de $10^6$. \subsection{Méthode de Fermat} On se propose ici d'implémenter un autre algorithme de décomposition en facteurs premiers dû à Pierre de Fermat (1643), plus adapté à la recherche de grands facteurs premiers. Soit $N$ impair s'écrivant sous la forme $uv$, avec $u \leq v$. On définit alors $$x = (u+v)/2, \qquad y = (v-u)/2$$ et on a \begin{equation}\label{eqfermat} N = x^2 - y^2, \qquad 0 \leq y < x \leq N \end{equation} La méthode de Fermat consiste à rechercher des valeurs de $x$ et $y$ satisfaisant (\ref{eqfermat}). Etant donné $N$ impair, l'algorithme suivant détermine le plus grand facteur de $N$ inférieur ou égal à $\sqrt{N}$. \begin{center}\begin{minipage}{13cm}\begin{description} \item[A1] Initialiser : $x' \leftarrow 2\lfloor\sqrt{N}\rfloor+1$, $y' \leftarrow 1$ et $r \leftarrow \lfloor\sqrt{N}\rfloor^2 - N$ (dans les étapes suivantes, $x'$ correspond à $2x+1$, $y'$ à $2y+1$ et $r$ à $x^2+y^2-N$). \item[A2] Si $r > 0$ alors faire $r \leftarrow r - y'$, $y' \leftarrow y'+2$. Aller en {\bf A2}. \item[A3] Si $r < 0$ alors faire $r \leftarrow r + x'$, $x' \leftarrow x'+2$. Aller en {\bf A2}. \item[A4] Si $r = 0$ alors c'est terminé : on a $$N = ((x'-y')/2) ((x'+y'-2)/2)$$ et $(x'-y')/2$ est le plus grand facteur de $N$ inférieur ou égal à $\sqrt{N}$. \end{description}\end{minipage}\end{center} \point Justifier cet algorithme. Ecrire une fonction {\tt fermat : \bi\ ->\ \bi~*~\bi} implémentant l'algorithme ci-dessus et renvoyant la décomposition en deux facteurs obtenue. En déduire une nouvelle fonction {\tt decomp2} de décomposition en facteurs premiers. %\section{Tests de primalité} \section{Application à la cryptographie : la méthode RSA} Parmi les procédés cryptographiques, la méthode RSA, découverte par R.~Rivest, A.~Shamir et L.~Adleman en 1978, est l'une des plus utilisée actuellement. Elle fait partie des méthodes dite {\em à clé publique} : chaque personne possède une clé $P$ {\em publique} que dont tout le monde peut avoir connaissance (par exemple dans un annuaire), et une clé {\em secrète} $S$ qu'elle seule connait. Lorsque que je veux envoyer un message $M$ à une personne $A$ je le code avec sa clé publique $P_A$. Le receveur $A$ le décode alors avec sa clé secrète $S_A$ et peut le lire. Un tel système fonctionne donc si on a les propriétés suivantes : \begin{enumerate} \item $S(P(M)) = M$ pour tout message $M$ ; \item Les paires $(S,P)$ sont toutes distinctes ; \item Découvrir la clé secrète $S$ à partir de la clé publique $P$ est aussi difficile que déchiffrer le message codé ; \item Une paire $(S,P)$ peut se calculer facilement. \end{enumerate} La méthode RSA fonctionne de la manière suivante : soient $x$, $y$ et $s$ trois grands nombres premiers, tels que $x,y \leq s$. Soit $N = xy$, et $p$ tel que $ps \bmod{(x-1)(y-1)} = 1$. On peut alors montrer que pour tout $M$ on a $M^{ps} = M \pmod{N}$. La clé publique est alors le couple $(N,p)$ et la clé secrète le couple $(N,s)$. Pour coder un message on commence par le découper en entiers inférieurs à $N$, et on élève alors ces entiers à la puissance $p$ modulo $N$. Pour le décoder on élève les entiers composant le message à la puissance $s$ modulo $N$. \medskip \point En supposant que l'on dispose d'un générateur de grands nombres premiers, comment engendrer un couple clé publique-clé secrète pour la méthode RSA ? \medskip \point J'ai codé un message en le découpant par groupes de 3 caractères, lesquels sont représentés par leur code ASCII sur 2 chiffres. (Exemple : le groupe de trois caractères TAS est représenté par l'entier 846583). Le message est ensuite codé en utilisant la clé publique $(N,p)$ où $N = 49808911 $ et $p = 5685669$, et le résultat est \begin{verbatim} 41021358 1169160 31809925 17484908 32136910 30925474 22255997 48565640 37770004 48144453 6582428 39919725 \end{verbatim} ``Craquer'' ce codage RSA pour découvrir le message en clair. \section*{Références} \noindent {\sc D.~E.~Knuth}. {\em The art of computer programming, Volume 2: Seminumerical Algorithms}, Addison-Wesley, 1981. \medskip \noindent {\sc R.~Sedgewick}. {\em Algorithms}, Addison-Wesley, 1988. \section*{Annexe : le module {\tt big\_int}} Le module {\tt big\_int} fournit, entre autres, les valeurs et fonctions suivantes : \begin{verbatim} (* 0 et 1 : *) value zero_big_int : big_int value unit_big_int : big_int (* conversions : *) value big_int_of_int : int -> big_int value string_of_big_int : big_int -> string value big_int_of_string : string -> big_int (* égalité et comparaisons : *) value eq_big_int : big_int -> big_int -> bool value le_big_int : big_int -> big_int -> bool value ge_big_int : big_int -> big_int -> bool value lt_big_int : big_int -> big_int -> bool value gt_big_int : big_int -> big_int -> bool (* opérations + - x / et modulo : *) value add_big_int : big_int -> big_int -> big_int value sub_big_int : big_int -> big_int -> big_int value mult_big_int : big_int -> big_int -> big_int value quomod_big_int : big_int -> big_int -> big_int * big_int value div_big_int : big_int -> big_int -> big_int value mod_big_int : big_int -> big_int -> big_int value power_big_int_positive_big_int: big_int -> big_int -> big_int \end{verbatim} \end{document}