Cryptographie/Cryptographie à clef publique

Début de la boite de navigation du chapitre
Cryptographie à clef publique
Icône de la faculté
Chapitre no 4
Leçon : Cryptographie
Chap. préc. :Cryptographie à clef secrète
Chap. suiv. :Fonctions de hachage
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Cryptographie : Cryptographie à clef publique
Cryptographie/Cryptographie à clef publique
 », n'a pu être restituée correctement ci-dessus.

PrincipeModifier

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 : RSAModifier

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 :   et  ,
  2. Leur produit détermine   :  
  3. Choisir un nombre entier   premier (aucun facteur commun) avec  
  4. Déterminer, par l'algorithme d'Euclide,   tel que  
  5. Le couple   constitue la clé publique,
  6. Le couple   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   entre   et  ,
  2. Chaque entier   est codé en un entier   en utilisant la clé publique   :  

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

  1. Chaque entier   est décodé en utilisant la clé privée   :  
    D'après un théorème du mathématicien Euler,  .