Algorithme de cryptage RSA

Contents

RSA est un algorithme de cryptage qui a vu le jour en 1977, et qui doit son nom à ses trois inventeurs Rivest-Shamir-Adleman (Ron Rivest, Adi Shamir, et Leonard Adleman).

RSA est un algorithme à clé publique très sur, qui est devenu un standard de facto.

Le brevet de cet algorithme appartenait jusqu'au 6 Septembre 2000 à la société américaine RSA Data Security, qui fait maintenant partie de Security Dynamics et aux Public Key Partners, (PKP à Sunnyvale, Californie, états-Unis).

Le principe de l'algorithme RSA repose sur le fait qu'il est très difficile et très long de factoriser un très grand nombre en deux facteurs premiers. Nous devrons donc générer un nombre à partir de deux grands nombres premiers (plus de cent chiffres pour le représenter en système décimal) que nous garderons secrets.

Formules de l'algorithme RSA

Terminologie :

  • m = message en clair (plain text)
  • c = message crypté (cipher text)
  • p = grand nombre premier
  • q = grand nombre premier
  • n = produit des deux grands nombres premiers p et q
  • (e,n) = clé publique
  • (d,n) = clé privée
  • mod = modulo (reste de la division entière)

Déterminer φ(n) :

φ(n) = (p - 1) * (q - 1)

Déterminer e :

p,q < e < φ(n)

Déterminer d :

ed mod φ(n) = 1
p,q < d < φ(n)

Chiffrer un fichier :

c = me mod n

Déchiffrer un fichier :

Le déchiffrement repose sur le théorème d'Euler stipulant que si m et n sont premiers entre eux, alors :

m phi(n) = 1 mod(n)

m = c d mod n

Contents Haut

Principes de l'algorithme RSA

Comme RSA repose sur la difficulté de factoriser un très grand nombre en deux facteurs premiers, nous allons procéder de la manière inverse : générer les deux nombres premiers (p et q), puis les multiplier pour générer le nombre n.

p et q sont générés de manière aléatoire. Comme il est extrêmement difficile d'obtenir quelque chose de totalement aléatoire en informatique, certains programmes se basent sur des facteurs de temps système, d'autres sur l'intervention de l'utilisateur (générer les nombres depuis une série de mouvements effectués par l'utilisateur à l'aide de la souris, etc.).

Lorsque nous avons généré p et q, il est facile de trouver n, car n = p * q.

Nous pouvons aussi déterminer φ(n), car φ(n) = (p - 1) * (q - 1).

Déterminer la clé publique (e,n)

Nous sommes en possession de n, mais nous devons à présent générer e, en sachant qu'il doit être premier avec φ(n), et en respectant p,q < e < φ(n).

Remarque

être premier avec... ne signifie pas que le nombre e doit être un nombre premier, mais signifie qu'il ne doit pas avoir de diviseur entier commun (à part le nombre 1). Par exemple, les nombres 4 et 15 sont premiers entre eux, car ils n'ont pas de diviseur entier commun (à part le nombre 1), mais ils ne sont pas des nombres premiers.

Nous sommes donc en possession de la clé publique (e,n).

Déterminer la clé privée (d,n)

Comme nous sommes en possession de p et de q, nous pouvons facilement déterminer d.

ed mod φ(n)= 1, c'est à dire que le reste de la division entière du produit ed par φ(n) doit être égal à 1.

Sachant que φ(n)= (p-1)*(q-1), nous trouvons que ed mod( (p-1)*(q-1) ) = 1,

Seulement, nous travaillons avec un modulo pour rester dans un nombre de bits gérables par le système, mais cela entraîne un certain nombre de possibilités de clés (en ajoutant tous les multiples de φ(n)). Pour restreindre le nombre de possibilités à une seule, nous ajoutons cette condition : p,q < d < φ(n).

Contents Haut

Exemple d'application de RSA :

Pour notre exemple, nous allons travailler avec des nombres à notre mesure, et non avec des nombres de plus de cent chiffres.

Génération des clés RSA

Les nombres premiers générés au hasard sont : p = 29, q = 37.

n = pq = 29 * 37 = 1073

φ(n) = (p-1)*(q-1) = (29-1)*(37-1) = 1008

Nous devons déterminer e tel qu'il soit premier avec φ(n), plus grand que p et q, et plus petit que φ(n)->e = 73

Déterminer d tel que 73 * d mod 1008 = 1 ->d = 649

Nous sommes en possession de nos deux clés :

  • Clé publique (73,1073)
  • Clé privée (649,1073)

Chiffrement RSA

Nous décidons de chiffrer le message "Hello world!" selon les caractères ASCII. Comme nous pouvons déterminer la taille des blocs en RSA, nous utilisons ici des blocs de 7 bits (ce qui nous suffit pour ASCII).

Valeur de la lettre H sur 7 bits = (1001000)2 = (72)10

Les valeurs des blocs sont les suivantes : 72, 101, 108, 108, 111, 32, 119, 111, 114, 108, 100, 33.

Chaque valeur est soumise à la formule c = me mod n avec pour valeur (e,n) de la clé publique (73,1073) :

  • 7273mod 1073 = 997
  • 10173mod 1073 = 1026
  • 10873mod 1073 = 367
  • 10873mod 1073 = 367
  • 11173mod 1073 = 629
  • 3273mod 1073 = 698
  • 11973mod 1073 = 785
  • 11173mod 1073 = 629
  • 11473mod 1073 = 965
  • 10873mod 1073 = 367
  • 10073mod 1073 = 544
  • 3373mod 1073 = 847

Le message chiffré est 997 1026 367 367 629 698 785 629 965 367 544 847.

Bien entendu, ceci est un très mauvais algorithme, car il prend les blocs tel quels, et nous pouvons "casser" le code sans même avoir accès à p et q, en utilisant simplement la fréquence d'apparition des lettres. Par exemple, nous pouvons utiliser 7 bits pour coder les caractères, mais travailler avec des blocs de 8 bits. L'emplacement libre à la fin du premier bloc contiendrait le premier bit de la deuxième lettre, et ainsi de suite.

Déchiffrement RSA

Nous recevons les blocs suivants : 997 1026 367 367 629 698 785 629 965 367 544 847.

Chaque bloc est soumis à la formule m = c d mod n avec pour valeur (d,n) de la clé privée (649,1073) :

  • 997649mod 1073 = 72
  • 1026649mod 1073 = 101
  • 367649mod 1073 = 108
  • 367649mod 1073 = 108
  • 629649mod 1073 = 111
  • 698649mod 1073 = 32
  • 785649mod 1073 = 119
  • 629649mod 1073 = 111
  • 965649mod 1073 = 114
  • 367649mod 1073 = 108
  • 544649mod 1073 = 100
  • 847649mod 1073 = 33

Les valeurs ASCII 72, 101, 108, 108, 111, 32, 119, 111, 114, 108, 100, 33 représentent "Hello world!".

Contents Haut

Outil de calcul des clés RSA

p : | |
q : | |
n = p*q : | |
φ(n) | |
e : | |
d : | |
Clé privée
Clé publique | |

English translation

You have asked to visit this site in English. For now, only the interface is translated, but not all the content yet.

If you want to help me in translations, your contribution is welcome. All you need to do is register on the site, and send me a message asking me to add you to the group of translators, which will give you the opportunity to translate the pages you want. A link at the bottom of each translated page indicates that you are the translator, and has a link to your profile.

Thank you in advance.

Document created the 24/06/2005, last modified the 26/10/2018
Source of the printed document:https://www.gaudry.be/en/crypto-rsa.html

The infobrol is a personal site whose content is my sole responsibility. The text is available under CreativeCommons license (BY-NC-SA). More info on the terms of use and the author.