Algorithme de chiffrement RSA

Décembre 2016

Algorithme de chiffrement Rivest, Shamir, Adleman (RSA)



Usages


RSA, du nom de ces inventeurs, est un algorithme de chiffrement appartenant à la grande famille "Cryptographie asymétrique".

RSA peut être utilisé pour assurer :
  • la confidentialité : seul le propriétaire de la clé privée pourra lire le message chiffré avec la clé publique correspondante.
  • la non-altération et la non-répudiation : seul le propriétaire de la clé privée peut signer un message (avec la clé privée). Une signature déchiffrée avec la clé publique prouvera donc l'authenticité du message.

Sa robustesse réside dans la difficulté à factoriser un grand nombre.

Évènements clés


Mise en oeuvre de RSA


Avertissement : cet article énonce le principe de base de l'algorithme publié en 1978.
Pour une implémentation rigoureuse, un certain nombres de précautions sont à prendre en compte afin d'éviter certaines vulnérabilités (se référer aux standards les plus récents).

Alice et Bob

  • Bob possède un message confidentiel qu'il souhaite transmettre à Alice.
  • Alice construit deux clés :
    • une clé de chiffrement publique qu'elle transmet à Bob.
    • une clé de déchiffrement privée qu'elle conserve soigneusement.
  • Bob utilise la clé publique pour chiffrer le message, et le transmets à Alice.
  • Alice utilise la clé privée pour déchiffrer le message reçu.

Génération des clés

  • Soient deux grands nombres premiers « aléatoirement » choisis : p et q.
  • Notons : n = p*q et φ = (p-1)*(q-1)
  • Soient d un grand entier « aléatoirement » choisi, premier avec φ. Et e l'inverse de d modulo φ.
  • La clé publique de chiffrement est le couple (n,e), la clé privée de déchiffrement le couple (n,d).

Chiffrement/Déchiffrement

Chiffrement

  • Avant d'être chiffré, le message original doit être décomposé en une série d'entiers M de valeurs comprises entre 0 et n-1.
  • Pour chaque entier M il faut calculer C≡M^e [n].
  • Le message chiffré est constitué de la succession des entiers C.

Déchiffrement

  • Conformément à la manière dont il a été chiffré, le message reçu doit être composé d'une succession d'entiers C de valeurs comprises entre 0 et n-1.
  • Pour chaque entier C il faut calculer M≡C^d [n].
  • Le message original peut alors être reconstitué à partir de la série d'entiers M.

Fiabilité


La sécurité de l'algorithme RSA repose sur la difficulté à factoriser n.
Pour décrypter le message, il est nécessaire de trouver d connaissant e, ce qui nécessite de recalculer φ, et donc de connaître p et q, les deux facteurs premiers de n.

Or, la factorisation d'un entier (de très grande taille) en facteurs premiers est extrêmement difficile, cette opération nécessitant une capacité de calcul très importante.
Pour exemple : en 2010, l'INRIA et ses partenaires ont réussi à factoriser une clé de 768 bits. Il leur a fallu deux ans et demi de recherche, et plus de 10^20 calculs. C'est à ce jour le meilleur résultat connu de factorisation.

Afin de se prémunir contre les puissances de calculs grandissantes, il est régulièrement recommandé d'utiliser des tailles de clés de plus en plus grandes (actuellement de 2048 bits).

A voir également :


Encryption with RSA
Encryption with RSA
Cifrado por medio de RSA
Cifrado por medio de RSA
La codificazione con RSA
La codificazione con RSA
A codificação com RSA
A codificação com RSA
Ce document intitulé «  Algorithme de chiffrement RSA  » issu de CommentCaMarche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.