RSA

Chiffrement à clé publique :
Chiffrement à clé publique :

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} )^{*}\)
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.

Propriétés de \(\phi\) :
  • \(\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}} )\)
Exemple n°1 :

\(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}\)

Exemple n°2 :

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

Identité d’Euler :

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

La méthode RSA :
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é.

_a/rsaimg.PNG

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

Exemple de programmes en Python :

Pour calculer les couples (e ; d) :

Pour calculer les couples (e ; d) :

rsa.py

_a/r001.PNG _a/r002.PNG _a/r003.PNG

Pour crypter :

Pour crypter :

chiffre.py

_a/r004.PNG

Pour déchiffrer :

Pour déchiffrer :

dechiffre.py

_a/r005.PNG