<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">

\section{MÃ©thodes de cryptage \og Ã&nbsp; clÃ© publique\fg{} }
\subsection{Principe}
Supposons qu'un individu $A$ soit obligÃ© de transmettre Ã&nbsp; 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 Ã&nbsp; l'Ã©coute et intercepter le message.\\


Le problÃ¨me est donc :
\begin{itemize}
\item le message doit Ãªtre inintelligible pour tout individu autre que $A$ et $B$.
\item $B$ doit pouvoir le comprendre.
\item $B$ doit pouvoir s'assurer que le message provient bien de $A$ (et non d'un plaisantin quelconque).\\
\end{itemize}


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.

\begin{Ex}
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. 
\end{Ex}



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


Soit $f_A$ la fonction de cryptage qui utilise la clÃ© propre Ã&nbsp;
l'individu $A$.
\begin{itemize}
 \item La clÃ© de A est publique, ainsi n'importe qui est en mesure d'appliquer la fonction $f_A$ Ã&nbsp; un message $M$ quelconque.
\item Par contre, seul $A$ connaÃ®t la fonction inverse $f_A^{-1}$ qui permet de retrouver le message initial.\\
\end{itemize}

 

Au message $M$ , $A$ applique en fait $f_A^{-1}$ (il est le seul Ã&nbsp;
pouvoir le faire).



Puis, Ã&nbsp; 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Ã©.\\



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 Ã&nbsp; 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$.



\subsection{Utilisation de l'indicatrice d'Euler}

\begin{Exo}[Fonction indicatrice d'Euler]
Soit $n$ un entier strictement positif; on note $\varphi(n)$ le nombre des entiers infÃ©rieurs Ã&nbsp; $n$ qui sont premiers avec $n$.

L'application de $\Net$ dans $\Net$ ainsi dÃ©finie est appelÃ©e \emph{fonction indicatrice d'Euler}.
\begin{enumerate}
\item Montrer que, pour $p$ premier, $\varphi(p) = p - 1$
\item Montrer que, pour $p$ premier, $\varphi(p^{\alpha}) = p^\alpha-p^{\alpha-1}$
\item On considÃ¨re les nombres de la
forme $ap+bq$, pour $p$ et $q$ premiers entre eux et l'application de
$(\Z/q\Z)\times(\Z/p\Z)$ dans $(\Z/pq\Z)$
dÃ©finie par $(a,b)\fc ap+bq\ [pq]$; montrer que cette application est injective et surjective. 
\item En dÃ©duire (en utilisant les nombres de la forme $ap+bq\ [pq]$) que, pour $p$ et $q$
premiers entre eux, $\varphi(pq)=\varphi(p)\varphi(q)$. \item
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
pour tout entier positif $n$ dÃ©pourvu de facteur carrÃ©, $a^{\varphi(n)}\equiv 1\ [n]$.
\end{enumerate}
\end{Exo}

\subsubsection{RÃ©sultat de base}

Diverses fonctions \og Ã&nbsp; inverse difficile Ã&nbsp; dÃ©terminer\fg{} ont Ã©tÃ©
proposÃ©es. Les plus satisfaisantes sont celles qui utilisent le
rÃ©sultat suivant :

\begin{Th}
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.
\end{Th}

\subsubsection{MÃ©thode de cryptage}

La mÃ©thode de cryptage est la suivante :

\begin{enumerate}
 \item Soit donc $n = pq$ un entier, produit de deux nombres entiers premiers, par exemple tels que $p \equiv q \equiv 2 [3]$.
 \item Soit $M$ le message, prÃ©alablement chiffrÃ© (sans prÃ©cautions particuliÃ¨res, par exemple en remplaÃ§ant les lettres par leurs codes ASCII).
\item Si $M\geqslant n$, on dÃ©compose $M$ en plusieurs sous-messages, ses \og chiffres\fg{} en base $n$, par exemple.
\item Si $n$ est la clÃ© choisie par $A$, et pour $M&lt;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$.
\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-Ã&nbsp;-dire que $\varphi(n)$ est le nombre de nombres strictement positifs infÃ©rieurs Ã&nbsp; $n$ qui sont premiers avec $n$).
\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)$.
\item On a donc, en combinant ces deux rÃ©sultats,
$M^{(p-1)(q-1)}\equiv 1\ [n]$, donc $M^{2(p-1)(q-1)}\equiv 1\ [n]$, et
finalement $M^{2(p-1)(q-1)+1}\equiv M\ [n]$.
\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]$.
\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.
\end{enumerate}

\begin{Ex}
Avec $p=5$, $q=11$, $n=pq=55$.

Le message Ã&nbsp; envoyer est chiffrÃ© $M=7$.

Alors $7^2\equiv 49\ [55]$, $7^3\equiv 13\ [55]$.

Le message cryptÃ© est $C=13$.

Ici $k=\fr{2\times 4\times 10+1}3=27$, donc $M\equiv 13^{27}\ [55]$.

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]$.
\end{Ex}


Si, par malchance, $M$ est un multiple de $p$ ou de $q$, il suffit
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.


\section{Choix d'un nombre n}

Dans l'exemple ci-dessus, le cryptage est immÃ©diatement percÃ© Ã&nbsp; 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.\\

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 Ã&nbsp; l'heure actuelle le produit de deux nombres qui ont entre 100 et 200 chiffres dans leur reprÃ©sentation dÃ©cimale.


\subsection{Nombres premiers}

Pour produire un nombre $n$ utilisable, il faut tout d'abord trouver deux
nombres $p$ et $q$ premiers, suffisamment grands.\\

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
longueurs trÃ¨s proches).\\

Il faut vÃ©rifier qu'ils sont premiers et, pour cela, disposer d'un critÃ¨re de primalitÃ© (voir plus loin).\\

Lorsque le nombre produit au hasard n'est pas premier, il suffit de lui ajouter 2 , puis encore 2 etc., jusqu'Ã&nbsp; obtenir un nombre premier, ce qui interviendra trÃ¨s rapidement.\\

Avec ces deux nombres premiers $p$ et $q$ ainsi obtenus, on obtient la clÃ© $n$.


\subsection{DÃ©composition en facteurs premiers}

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'Ã&nbsp; sa racine carrÃ©e.\\


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).\\

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 Ã&nbsp; 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.\\

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

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.
</pre></body></html>