Cryptographie/Cryptographie à clef publique

Principe

Le destinataire d'un message crypté génère deux clés à partir de nombres (en général deux grands nombres premiers) :

• Une clé privée, qu’il garde secrète, lui servant à décoder les messages qu’il reçoit,
• Une clé publique qu’il publie afin que ceux qui lui envoient des messages puissent les coder.

L'algorithme utilisé ne doit pas permettre de déduire la clé privée à partir de la clé publique et vice versa.

Un exemple : RSA

RSA repose sur l'hypothèse qu’il est très difficile de décomposer un grand nombre (de l’ordre de 200 chiffres minimum) en facteurs premiers.

L'algorithme pour générer les deux clés est le suivant :

1. Choisir deux grands nombres premiers différents : $p$ et $q$,
2. Leur produit détermine $n$ : $n=p\times q$
3. Choisir un nombre entier $e$ premier (aucun facteur commun) avec $(p-1)\times (q-1)$
4. Déterminer, par l'algorithme d'Euclide, $d$ tel que $e\times d\equiv 1mod(p-1)\times (q-1)$
5. Le couple $(n,e)$ constitue la clé publique,
6. Le couple $(n,d)$ constitue la clé privée.

Une fois les deux clés créées, le codage s'effectue de la manière suivante :

1. Le message est représenté sous la forme de plusieurs entiers $M$ entre $0$ et $n-1$,
2. Chaque entier $M$ est codé en un entier $C$ en utilisant la clé publique $(n,e)$ : $C\equiv M^{e}modn$

Le décodage s'effectue de la manière suivante :

1. Chaque entier $C$ est décodé en utilisant la clé privée $(n,d)$ : $D\equiv C^{d}modn$

   D'après un théorème du mathématicien Euler, $D\equiv M^{de}\equiv Mmodn$.