RSA
Les cryptosystèmes que nous avons introduit jusque là ont tous une "grande faille" : dès que l'on connait la clef de chiffrement on peut trouver la clef de déchiffrement (et inversement). On parle de cryptosystème
symétrique.
Le problème c'est que deux individus voulant échanger des informations secrètes doivent avant tout convenir de la méthode de chiffrement ainsi que la clef.
Si un pirate intercepte l'échange de clef, le cryptage devient inutile.
A l'opposé des cryptosystèmes symétrique il y a les cryptosystème
asymétrique : il est difficile de déterminer la clef de déchiffrement même en connaissant la clef de chiffrement. L'exemple fameux de tel cryptosystème est la méthode RSA, initiales des inventeurs Rivest, Shamir et Adleman. Pour arriver à comprendre son fonctionnement nous avons besoin des nombres premiers.
Les nombres premiers
Définition
Un nombre premier est un nombre qui n'a que deux diviseurs positifs.
On note \( \P\) , l'ensemble des nombres premiers.
Ainsi un nombre premier est un nombre qui n'est divisible que par 1 et par lui-même sauf \( 1\) .
Par exemple \( 2\) , \( 13\) , \( 101\) .
Proposition [Lemme d'Euclide]
Soient \( a\) , \( b\) des entiers et \( p\in \P\) .
\[p|ab\Longrightarrow (p|a)\vee(p|b)\]
Démonstration
Supposons que \( p\) ne divise pas \( a\) . Les seuls diviseurs de \( p\) et donc du \( PGCD(p,a)\) sont \( 1\) et \( p\) et puisque \( p\) ne divise pas \( a\) on a nécessairement \( PGCD(p,a)=1\) . Le lemme de Gauss permet de conclure que \( p|b\) .
Les nombres premiers sont au cœur de l'arithmétique. Ils forment les atomes de tous les nombres.
Théorème [Théorème fondamental de l'arithmétique - Gauss]
Tout nombre entier non nul se décompose de manière unique, à l'ordre des facteur près, en produit fini de nombre premier.
Démonstration
Montrons l'existence par récurrence sur \( n\) .
Le nombre \( 1\) est produit d'un nombre fini de nombre premier : aucun (produit sur l'ensemble vide) ce qui prouve le cas initial.
Supposons que tout entier \( n{<}N\) s'écrit comme produit fini de nombre premier et montrons qu'il en est de même pour \( N\) . Considérons le plus petit \( p\in D(N)\) strictement supérieur à \( 1\) qui existe car cet ensemble est une partie non vide de \( \N\) et admet donc un plus petit élément.
Nécessairement \( p\) est un nombre premier par minimalité. Mais \( N=N'p\) et puisque \( N'{<}N\) il s'écrit comme produit de nombre premier et il en va donc de même pour \( N\) .
L'unicité se déduit du lemme d'Euclide.
Théorème
\[\Card(\P)=+\infty\]
Démonstration
Raisonnons par l'absurde et supposons que \( p_1{<}p_2{<}\cdots{<}p_n\) sont les seuls premier. Considérons \( N=1+p_1\cdot p_2 \cdots p_n\) . Le nombre \( N\) n'est pas un nombre premier (puisque strictement plus grand que le plus grand des nombres premiers). D'après le théorème fondamental de l'arithmétique, \( N\) est divisible par un nombre premier, \( p_k\) . Mais puisque \( p_1\cdot p_2 \cdots p_n\) est également divisible par \( p_k\) on en déduit que \( 1=N-p_1\cdot p_2 \cdots p_n\) est divisible par \( p_k\) et nécessairement \( p_k=1\) qui n'est pas un nombre premier. Absurde.
Définition
Soit \( p\in \P\) et \( n\in \N_{{>}0}\) . On appelle valuation \( p\) -adique de \( n\) la plus grande puissance de \( p\) qui apparait dans la décomposition en facteur premier de \( n\) . On la note \( v_p(n)\) .
Par exemple \( v_2(12)=2\) , \( v_3(12)=1\) et \( v_5(12)=0\) .
Corollaire
Soit \( n\in \N_{{>}0}\) . La famille \( \{v_p(n)\}_{p\in \P}\) est une famille d'entier presque tous nul et
\[n=\prod_{p\in \P}p^{v_p(n)}\]
Démonstration
Cela se déduit du théorème fondamental de l'arithmétique.
Proposition
Soient \( a\) et \( b\) des éléments de \( \N_{{>}0}\) et \( p\in \P\) .
- \( (i)\) .
- \( v_p(ab)=v_p(a)+v_p(b)\) .
- \( (ii)\) .
- \( a|b \Longleftrightarrow \Big(\forall p\in \P,\ v_p(a)\leqslant v_p(b)\Big)\) .
- \( (iii)\) .
- \( v_p(a^b)=bv_p(a)\) .
- \( (iv)\) .
- \( v_p(PGCD(a,b))=min(v_p(a), v_p(b))\) .
Démonstration
- \( (i)\) .
- On a \( \dpl{a=\prod_{p\in \P}p^{v_p(a)}}\) et \( \dpl{b=\prod_{p\in \P}p^{v_p(b)}}\) d'où \( \dpl{ab=\prod_{p\in \P}p^{v_p(a)+v_p(b)}}\) .
- \( (ii)\) .
- Si \( a|b\) alors il existe \( k\neq0\) tel que \( b=ka\) ce qui implique d'après le premier point que \( v_p(b)=v_p(k)+v_p(a)\) pour tout \( p\in \P\) . En particulier \( v_p(b)\geqslant v_p(a)\) . Réciproquement : posons \( \dpl{k=\prod_{p\in \P}p^{v_p(b)-v_p(a)}}\) . Alors \( b=ka\) .
- \( (iii)\) .
- Beaucoup trop triviale.
- \( (iv)\) .
- C'est une conséquence de la construction du \( PGCD\) .
Théorème [Formule de Legendre]
Soient \( n\in \N_{{>}0}\) et \( p\in \P\) .
\[v_p(n!)=\sum_{i=1}^\infty\left[\dfrac{n}{p^i}\right]\]
où \( [x]\) désigne la partie entière du réel \( x\) .
Démonstration
Soit \( \alpha_i\in \N\) le plus grand entier tel que \( \alpha_ip^i\leqslant n\) . Dans ce cas le nombre d'entier inférieur ou égaux à \( n\) et divisible par \( p^i\) est \( \alpha_i=\dpl{\left[\dfrac{n}{p^i}\right]}\) .
Soit \( n_i\) le nombre d'entier entre \( 1\) et \( n\) de valuation \( p\) -adique exactement égale à \( i\) . Naturellement \( v_p(n!)=n_1+2n_2+3n_3\) etc...
Pour finir on observe que \( \dpl{\left[\dfrac{n}{p^i}\right]}=n_i+n_{i+1}.\cdots\) .
Les nombres premiers bien que centraux en arithmétiques sont très peu connu. Voici une petite brochette de conjecture lié aux nombres premiers.
- Goldbach.
- Tout nombre paire strictement supérieur à 2 s'écrit comme la somme de deux nombres premiers.
- Legendre.
- Pour tout entier \( n{>}1\) , il existe toujours un nombre premier entre \( n^2\) et \( (n+1)^2\) .
- Sophie Germain.
- Il existe une infinité de nombre premier \( p\) tel que \( 2p+1\) est également premier1.
- Mersenne.
- Il existe une infinité de nombre premier de la forme \( 2^n-1\) .
- Fermat.
- Il existe une infinité de nombre premier de la forme \( 2^{2^n}+1\)
- Fibonacci.
- Il existe une infinité de nombre premier qui apparaissent dans la suite de Fibonacci.
- Riemann.
- ...
Malgré les mystères qui entourent ces nombres nous disposons de puissant résultat.
Lemme
Soit \( p\in \P\) et \( 0 {<} k {<} p\)
\[\left(
\begin{array}{c}
p\\ k
\end{array}\right)
=\dfrac{p!}{k!(p-k)!}
\text{ est divisible par } p\]
Démonstration
On observe que
\[
k\left(
\begin{array}{c}
p\\ k
\end{array}\right)=p\left(
\begin{array}{c}
p-1\\ k-1
\end{array}\right)
\]
Ainsi \(
p|k\left(
\begin{array}{c}
p\\ k
\end{array}\right)
\) et puisque \( k\) est premier à \( p\) le lemme de Gauss prouve que \( p|\left(
\begin{array}{c}
p\\ k
\end{array}\right)\) .
Théorème [Petit théorème de Fermat]
Soit \( p\in \P\) et \( x\in \N\) .
\[x^{p}\equiv_px\]
Démonstration
On raisonne par récurrence sur \( x\) le cas initial étant trivial.
Supposons que pour un \( x\) quelconque fixé, \( x^{p}\equiv_p x\) . En developpant par le binôme de Newton on a
\[(x+1)^{p}=\sum_{k=0}^{p}
\left(
\begin{array}{c}
p\\ k
\end{array}\right)
x^k=1+x^p+\sum_{k=1}^{p-1}
\left(
\begin{array}{c}
p\\ k
\end{array}\right)\]
Or entre \( 1\) et \( p-1\) tous les coefficients binomiaux sont multiples de \( p\) c'est à dire nuls modulo \( p\) . En conclusion \( (x+1)^p\equiv_p x^p+1\) . Par hypothèse de récurrence, \( (x+1)^p\equiv_px+1\) .
Corollaire
Soit \( p\in \P\) et \( x\in \N\) non multiple de \( p\) .
\[x^{p-1}\equiv_p1\]
Démonstration
Le petit théorème de Fermat affirme que \( x^p\equiv_px\) c'est à dire qu'il existe \( k\in \Z\) tel que \( x^p-x=kp\) soit encore \( x(x^{p-1}-1)=kp\) . Cette dernière égalité implique que \( p|(x(x^{p-1}-x))\) or \( p\) et \( x\) sont premiers entre eux puisque \( p\) est premier et \( x\) non multiple de \( p\) . Le lemme de Gauss permet de conclure que \( x^{p-1}-1\) est multiple de \( p\) .
Principe de chiffrement
Proposition
Soient \( p{<}q\) deux nombres premier, \( e\) un nombre premier avec \( \varphi = (p-1)(q-1)\) et \( d\) l'inverse de \( e\) modulo \( \varphi\) . Pour tout \( x\in \Z\) ,
\[x^{de}\equiv_{pq}x\]
Démonstration
Puisque \( d\) est l'inverse de \( e\) modulo \( \varphi\) on en déduit \( de\equiv_\varphi1\) . D'une autre manière, il existe \( k\in \Z\) tel que \( de=1+k(p-1)(q-1)\) . Dans ce cas \( x^{de}=x\times \left(x^{(p-1)(q-1)}\right)^k\) .
Si \( x\) n'est pas multiple de \( p\) et de \( q\) alors le corollaire du petit théorème Fermat implique que \( x^{p-1}\equiv_p1\) soit encore \( x^{(p-1)(q-1)}\equiv_p1\) . De même \( x^{(p-1)(q-1)}\equiv_q1\) . Le lemme chinois implique alors que \( x^{(p-1)(q-1)}\equiv_{pq}1\) et donc \( x^{de}\equiv_{pq}x\) .
Si \( x\) est multiple de \( p\) mais pas de \( q\) alors le corollaire au petit théorème de Fermat implique que \( x^{q-1}\equiv_q1\) et donc \( x^{k(p-1)(q-1)}\equiv_q1\) . Par définition il existe \( \alpha\in \Z\) tel que \( x^{k(p-1)(q-1)}=\alpha q+1\) . En multipliant par \( x\) on a \( x^{1+k(p-1)(q-1)}=\alpha xq+x\) mais \( xq\equiv_{pq}0\) car \( x\) est multiple de \( p\) . Dans ce cas \( x^{de}\equiv_{pq}x\) .
Si \( x\) est multiple de \( q\) mais pas de \( p\) c'est le même raisonnement.
Si \( x\) est multiple de \( p\) et de \( q\) alors il est nul modulo \( pq\) et trivialement \( x^{de}\equiv_{pq}x(\equiv_{pq}0)\) .
Définition
Soient \( p{<}q\) deux nombres premiers. Notons \( n=pq\) et \( \varphi(n)=(p-1)(q-1)\)
Les données suivantes définissent le cryptosystème de RSA de base \( n\) .
- Espace de clefs.
- \( \mathcal{K}_{p,q}=\left(\Z/\varphi(n)\Z\right)^\times\)
- Fonction de chiffrement.
- Quelque soit \( e\in \mathcal{K}_{p,q}\) et \( x\in \Z\) , \( C_e(x)\equiv_{n}x^e\)
- Fonction de déchiffrement.
- Quelque soit \( e\in \mathcal{K}_{p,q}\) et \( x\in \Z\) , \( D_e(x)\equiv_{n}x^{e^{-1}}\) où \( e^{-1}\) désigne l'inverse de \( e\) modulo \( \varphi(n)\) .
La proposition précédente justifie que la propriété de déchiffrement est satisfaite.
Dans la pratique la clef de chiffrement, la donnée \( (n,e)\) , est appelé la
clef publique et la clef de déchiffrement, la donnée \( (n,e^{-1})\) est appelé la
clef privée.
Prenons par exemple \( p=3\) et \( q=11\) . Dans ce cas, \( n=33\) et \( \varphi(33)=20\) .
Le nombre \( e=13\) est un entier premier à \( 20\) donc \( (33,13)\) est une clef publique. Chiffrons le message
PIKACHU
\[
\begin{array}{c||ccccccc}
\text{Message}&P&I&K&A&C&H&U\\\hline
\text{Codage}&15&08&10&00&02&07&20\\\hline
x^{13}\ mod\ 33&9&17&10&0&8&13&14
\end{array}
\]
Ainsi le message chiffré est \( 9-17-10-0-8-13-14\) .
Imaginons avoir reçu le message \( 8-0-29-0-14-8-31\) avec la même clef de chiffrement. L'inverse de \( 13\) modulo \( 20\) s'obtient en appliquant l'algorithme d'Euclide étendue. On trouve \( 13^{-1}\equiv_{20}17\)
Déchiffrons alors le message.
\(
\begin{array}{c||cccccccc}
\text{Message} &08&00&29&00&09&14&08&31\\\hline
x^{17}\ mod\ 33&02&00&17&00&15&20&02&04\\\hline
\text{Décodage}&C&A&R&A&P&U&C&E
\end{array}
\)
La sécurité de ce cryptosystème réside dans le fait que même si on connait la clef publique \( (n,e)\) il est difficile de trouver l'inverse de \( e\) car on ne connait pas \( \varphi\) (\( p\) et \( q\) en fait). Bien sur ce cryptosystème sera sûre avec de grande valeur pour \( p\) et \( q\) . Ainsi si vous savez qu'un message a été codé avec \( (9068370463, 17)\) il sera difficile (du moins sans ordinateur) de trouver la clef privée.
Le paquetage est "automatique" avec cette méthode.
Si l'entier \( n\) est compris entre \( 26\) et \( 2525\) on travaillera par paquet de \( 2\) , s'il est entre \( 252526\) et \( 25252525\) on travaillera par paquet de \( 3\) etc.
Prenons par exemple \( p=509\) et \( q=691\) alors \( n=351719\) : on chiffrera par paquet de \( 3\) . Prenons \( e=7\) qui est bien premier avec
\( \varphi(351719)=350520\) .
\[
\begin{array}{c||ccccccccccccccc}
\text{Message}&A&T&T&R&A&P&E&Z&L&E&S&T&O&U&S\\\hline
\text{Codage}&00&19&19&17&00&15&04&25&11&04&18&19&14&20&18\\\hline
\text{Paquetage}&
&&{1919}&
&&{170015}&
&&{42511}&
&&{41819}&
&&{142018}\\\hline
x^{7}\ mod\ 351719&
&&{27519}&
&&{87444}&
&&{106946}&
&&{327923}&
&&{329813}
\end{array}
\]
et le message chiffré est \( 27519-87444-106946-327923-329813\) .
Échange et signature
Madame A souhaite transmettre un message suivant le protocole RSA à monsieur B. Monsieur B a crié sur tous les toits que sa clef publique est \( (n_B, e_B)\) et a secrètement gardé sa clef privée \( (n_B, d_B)\) . D'ailleurs madame A a fait la même chose avec sa clef publique \( (n_A, e_A)\) et privée \( (n_A, d_A)\) .
Madame A code son message claire \( M\) avec la clef publique de monsieur B et publie sur son mur FB le message crypté. Tout le monde peut le voir mais seul monsieur B qui dispose de la clef de déchiffrement peut retrouver le message initial \( M\) .
Monsieur B voudrait être sûre que le message qu'il reçoit provient bien de madame A et pas d'un pirate qui se ferait passer pour elle.
Madame A va alors signer son message avant de le chiffrer et de l'envoyer.
Elle applique au message claire \( M\) sa clef privée \( (n_A, d_A)\) puis ensuite la clef publique \( (n_B, e_B)\) de monsieur B. En recevant le message, monsieur B va appliquer sa clef privée et obtenir un message encore chiffré. Il va alors appliquer la clef publique \( (n_A, e_A)\) de A qui est à la seule qui a pu utiliser sa clef privée pour signer ce message, pour retrouver le message claire \( M\) .
Exponentiation modulaire rapide
Bien que cette méthode de chiffrement soit sûre elle est soumise à une contrainte : le calcul des puissances modulaires, communément appelé
exponentiation modulaire.
Reprenons l'exemple du déchiffrement introduit plus tôt. Avec une calculatrice on a \( 1919^7=9.5835149e+22\) . Cet arrondi rend le déchiffrement impossible
2. Il existe cependant une méthode rapide pour réaliser ces calculs sans arrondi ni problème du à la gestion de mémoire de la machine.
L'élément centrale de l'exponentiation modulaire rapide est le changement de base.
Théorème
Soient \( n\) et \( b\) des entiers tels que \( b{>}0\) .
Il existe un famille finie \( \{a_0, a_1, \dots, a_k\}\in[\![0,b[\![\) pour un certain \( k\in \N\) tel que
\( \dpl{n=\sum_{i=0}^ka_ib^i}\)
Démonstration
On raisonne par récurrence sur \( n\) , le cas initial \( n=0\) étant trivial.
D'après le théorème de la division euclidienne \( n=bq+r\) où \( 0\leqslant r {<}b\) . Naturellement \( q{<}n\) . Par hypothèse de récurrence \( \dpl{q=\sum_{i=0}^ka_ib^i}\) pour un certain \( k\) . Ainsi \( \dpl{n=\sum_{i=0}^ka_ib^{i+1}+rb^0}\) ce qui prouve le résultat.
Définition
Soit \( b\in \N_{{>}0}\) . L'écriture en base \( b\) d'un entier \( n\in \N\) est la donnée de la famille \( \{a_0, a_1, \dots, a_k\}\) du théorème précédent.
On note
\[n=(a_k\dots a_1a_0)_b\]
La manière usuelle d'écrire les nombres est l'écriture en base 10 ou base décimale. Lorsque l'on ne précise pas la base, il s'agira de l'écriture décimale du nombre, c'est à dire \( 123=(123)_{10}\)
En observant la preuve du théorème précédent, on obtient un algorithme permettant d'écrire en base \( b\) quelconque : il suffit de réaliser des divisions euclidienne successives. Écrivons par exemple l'entier \( 123\) en base \( 7\) .
- \( \bullet\)
- \( 123=7\times17+\boxed{4}\)
- \( \bullet\)
- \( 17=7\times2+\boxed{3}\)
- \( \bullet\)
- \( 2=7\times0+\boxed{2}\)
On a alors \( 123=(234)_{7}\) .
Définition
- \( \bullet\)
- L'écriture en base \( 2\) est appelé le binaire.
- \( \bullet\)
- L'écriture en base \( 3\) est appelé le trinaire.
- \( \bullet\)
- L'écriture en base \( 8\) est appelé l'octal.
- \( \bullet\)
- L'écriture en base \( 16\) est appelé l'hexadécimal.
- \( \bullet\)
- L'écriture en base \( 60\) est appelé le sexagésimal.
- \( \bullet\)
- L'écriture en base \( 150\) est appelé l'indienne.
Lorsque la base dépasse les 10 caractères usuelles de la numération, on ajoute des caractères. Par exemple, en hexadécimal, on l'habitude de compléter les chiffres de \( 0\) à \( 9\) par les lettres, \( A\) , \( B\) , \( C\) , \( D\) et \( E\) . Ainsi \( (ABC)_{16}=\underbrace{10}_{A}\times16^2+\underbrace{11}_{B}\times16^1+\underbrace{12}_C = 2748\) .
Algorithme d'exponentiation modulaire rapide
Cet algorithme permet de calculer très rapidement \( x^n\) modulo \( m\) . L'idée est d'écrire l'entier \( n\) en binaire (base \( 2\) ).
Écrivons \( n=\sum_{i=0}^ka_i2^i\) où pour tout \( i\) , \( a_i\in \{0,1\}\) . Dans ce cas, \( x^n=\prod_{i=0}^kx^{2^i}\) . L'avantage est que \( (x^{2^i})^2=x^{2^{i+1}}\) . D'où l'algorithme.
§
Écrire n en binaire : \( n=\sum_{i=0}^ka_i2^i\)
Pour i de 0 à k
Si i=0
poser x[0] = x modulo m
Sinon
x[i] = x[i-1]*x[i-1] modulo m
Fin Si
Fin pour
res = 1
Pour i de 0 à k
Si \( a_i\) =1
res = res*x[i] modulo m
Fin Si
Fin pour
Renvoyer res
Par exemple calculons \( 19^{19}\) modulo \( 2017\) .
- Ecriture binaire.
-
La première étape consiste à écrire \( 19\) en binaire ce qui se fait par division euclidienne successive. On trouve \( 19=(10011)_2\) .
- Calcul des puissances de puissance de \( 2\) .
-
On représente la situation dans un tableau
\[\begin{array}{|c||c|c|c|c|c|}
\hline
k&0&1&2&3&4\\\hline
{}^2&&&&&\\\hline
mod&&&&&\\\hline
\end{array}
\]
où la dernière ligne est la seconde ligne modulo \( m=2017\) .
Le tableau va jusqu'à \( k=4\) car c'est la plus grande puissance de \( 2\) qui apparait dans l'écriture binaire de \( 19\) . On l'initialise de la sorte
\[\begin{array}{|c||c|c|c|c|c|}
\hline
k&0&1&2&3&4\\\hline
{}^2&19&&&&\\\hline
mod&19&&&&\\\hline
\end{array}
\]
On prend la valeur de la dernière ligne de la colonne \( k\) que l'on met au carré et que l'on inscrit dans à la seconde ligne de la colonne \( k+1\) et on calcul la réduction modulo \( m\) à la dernière ligne.
\[\begin{array}{|c||c|c|c|c|c|}
\hline
k&0&1&2&3&4\\\hline
{}^2&19&361&&&\\\hline
mod&19&361&&&\\\hline
\end{array}
\]
On itère le processus.
\[\begin{array}{|c||c|c|c|c|c|}
\hline
k&0&1&2&3&4\\\hline
{}^2&19&361&130321&&\\\hline
mod&19&361&1233&&\\\hline
\end{array}
\]
\[\begin{array}{|c||c|c|c|c|c|}
\hline
k&0&1&2&3&4\\\hline
{}^2&19&361&130321&1520289&\\\hline
mod&19&361&1233&1488&\\\hline
\end{array}
\]
\[\begin{array}{|c||c|c|c|c|c|}
\hline
k&0&1&2&3&4\\\hline
{}^2&19&361&130321&1520289&2214144\\\hline
mod&19&361&1233&1488&1495\\\hline
\end{array}
\]
- Conclusion.
- Les puissances de \( 2\) apparaissant dans l'écriture binaire de \( 19\) sont \( 0\) , \( 1\) et \( 4\) on a donc \( 19^{19}\equiv_{2017}19\times361\times1495\equiv_{2017}808\times1495\equiv_{2017}1794\)
1Monsieur Le Blanc
2Et il s'agit d'un cas très simple
