RSA

En 1976 DIFFIE et HELLMAN ont posé le problème suivant :

Soit \({( {{A}_{i}} )}_{i=1..n}\: ,\: n\) individus qui veulent communiquer entre eux de façon secrète et simple.

Pour chaque \(i\) soit \({C}_{i}\) et \({D}_{i}\) deux procédures. Les procédures \({D}_{i}\) de déchiffrement sont secrètes et connues d’un seul individu \({A}_{i}\).

Si \({A}_{j}\) veut envoyer un message \(M\) à \({A}_{i}\) , il consulte l’annuaire et envoie \(M'=C_{i}( M )\) à \({A}_{i}\) ; la personne \({A}_{i}\) déchiffre le message reçu en calculant \(D_{i}( M')\) . Il retrouve \(M\) si \(D_{i} \circ C_{i}\) est l’identité.

.

Le groupe \(( \mathbb{Z}/n\mathbb{Z} )^{*}\)

.

L’ensemble des éléments inversibles de \(\mathbb{Z}/n\mathbb{Z}\) sera noté \(( \mathbb{Z}/n\mathbb{Z} )^{*}\) ou \({E}_{n}\) . C’est un groupe multiplicatif. Le nombre d’éléments de \({E}_{n}\) est \(\phi (n)\) , \(\phi\) étant la fonction d’Euler.

• \(\phi\) est multiplicative, c’est-à-dire si \(pgcd( m,n )=1\) alors \(\phi (m\times n)=\phi (m)\times \phi (n)\) .
• Si \(p\) est un nombre premier, alors \(\phi (p)=p-1\) .
• Si \(n=\prod \limits_{i=1}^{k} p_{i}\) alors, \(\phi (n)=n \prod \limits_{i=1}^{k} ( 1-\frac{1}{p_{i}} )\)

\(m=2\) et \(n=5\) , \(\phi (2)=1\) \(\phi (5)=4\) et \(E_{2}= 1\) , \(E_{5}=\{ 1;2;3;4\}\) .

En effet : \(1\times 1=1\) et pour \(( \mathbb{Z}/5 \mathbb{Z} )^{*}=E_{5}\), on a : \(2\times 3=6\) et \(6\equiv 1\text{ }( \bmod 5 )\) pour le nombre \(4\) : \(4\times 4=16\) et \(16\equiv 1\text{ }( \bmod 5 )\) .

Donc les entiers \(1\) ; \(2\) ; \(3\) et \(4\) sont des éléments inversibles de \(\mathbb{Z}/5\mathbb{Z}\)

\(n=10\) et \(10=2\times 5\).

On utilise la fonction d’Euler \(\phi (10)=\phi (2)\times \phi (5)\) d’où \(\phi (10)=\phi (2)\times \phi (5)=1\times 4=4\) . \(\phi (10)=10\times ( 1-\frac{1}{2} )\times ( 1-\frac{1}{5} )=10\times ( 1-\frac{1}{2}-\frac{1}{5}+\frac{1}{10} )=10-5-2+1=4\)

On vérifie \(\mathbb{Z}/10 \mathbb{Z}=\{ 0;1;2;3;4;5;6;7;8;9 \}\)

• L’entier \(2\) ne peut pas être inversible car tous les multiples de deux sont pairs et la différence entre un entier pair et un multiple de \(10\) ne peut pas être égale à \(1\). D’où les entiers pairs \(4\) ; \(6\) et \(8\) ne sont pas inversibles.
• De même l’entier \(5\) a des multiples qui sont multiples de \(10\) ou qui ont une différence de \(5\) avec les multiples de \(10\). Il reste donc \(3\) ; \(7\) et \(9\) :

\(3\times 7=21\text{ et }21\equiv 1\text{ }( \bmod 10 )\) et \(9\times 9=81\text{ et }81\equiv 1\text{ }( \bmod 10 )\) , il y a donc \(4\) entiers dans \({E}_{5}\).

\(a^{\phi (n)} \bmod =1 (mod \: n)\) si \(pgcd (a,n)=1\)

.

La méthode RSA :

.

La méthode de cryptographie RSA a été inventée en 1977 par Ron RIVEST, Adi SHAMIR et Len ADLEMAN, à la suite de la découverte de la cryptographie à la clé publique par DIFFIE et HELLMAN. Le RSA est un système cryptographique à clé publique très utilisé.

Principe de fonctionnement :

On utilise la méthode d’exponentiation avec \(n=q\times p\) ou q et p sont des nombres premiers distincts. Chaque individu \({A}_{i}\) choisit deux nombres premiers distincts \({q}_{i}\) et \({p}_{i}\) qu’il garde secrets, puis il choisit \(e_{i}\in E_{\phi ni}\) avec \(n_{i}=q_{i} \times p_{i}\) et calcule l’inverse de \(e_{i} \bmod \phi (n_{i})\) qui doit avoir comme propriété : \(pgcd (e_{i},(p-1) \times (q-1))=1\) .

• Sont rendus publics \(n_{i}\) et \(e_{i}\) .
• Bob veut envoyer un message à Alice, elle a rendu public n et e et a gardé secret d avec \(d\times e\equiv 1\text{ }( \bmod \phi (n) )\) . Le message M est un entier tel que \(0\le M\le n-1\) .

Protocole :

1. Bob envoie à Alice \(M'=C(M)={{M}^{e}}\text{ }\bmod n\)
2. Alice déchiffre en calculant \(D(M')={{( M' )}^{d}}\text{ }\bmod n\)

rsa.py

.

Pour crypter :

.

chiffre.py

.

Pour déchiffrer :

.

dechiffre.py