Cryptographie/Cryptographie à clef publique
Une page de Wikiversité.
Cryptographie/Cryptographie à clef publique est une ébauche concernant l'informatique. Vous pouvez aider le projet Wikiversité en l'améliorant.
|
|
|||
| Chapitre 4 | |||
| Leçon : Cryptographie | |||
|---|---|---|---|
| Chap. préc. : | La cryptographie à clef secrète | ||
| Chap. suiv. : | Les fonctions de hachage | ||
En raison de limitations techniques, la typographie souhaitable du titre, « Cryptographie : La cryptographie à clef publique
Cryptographie/Cryptographie à clef publique », n'a pu être restituée correctement ci-dessus.
[modifier] 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 envoie 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.
[modifier] 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 :
- Choisir deux grands nombres premiers différents : p et q,
- Leur produit détermine n :
- Choisir un nombre entier e premier (aucun facteur commun) avec
- Déterminer, par l'algorithme d'Euclide, d tel que
- Le couple (n,e) constitue la clé publique,
- 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 :
- Le message est représenté sous la forme de plusieurs entiers M entre 0 et n − 1,
- Chaque entier M est codé en un entier C en utilisant la clé publique (n,e) :
Le décodage s'effectue de la manière suivante :
- Chaque entier C est décodé en utilisant la clé privée (n,d) :
- D'après un théorème du mathématicien Euler,
.
- D'après un théorème du mathématicien Euler,
