Algorithme de cryptage RSA

Table des matières

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

Table des matières 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).

Table des matières 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!".

Table des matières Haut

Outil de calcul des clés RSA

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

Version en cache

21/11/2024 09:30:59 Cette version de la page est en cache (à la date du 21/11/2024 09:30:59) afin d'accélérer le traitement. Vous pouvez activer le mode utilisateur dans le menu en haut pour afficher la dernère version de la page.

Document créé le 24/06/2005, dernière modification le 26/10/2018
Source du document imprimé : https://www.gaudry.be/crypto-rsa.html

L'infobrol est un site personnel dont le contenu n'engage que moi. Le texte est mis à disposition sous licence CreativeCommons(BY-NC-SA). Plus d'info sur les conditions d'utilisation et sur l'auteur.