Algorithme de cryptage RSA

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 = m^e 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

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).

Application de RSA : exemple

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

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

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)₂ = (72)₁₀

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 = m^e mod n avec pour valeur (e,n) de la clé publique (73,1073) :

• 72⁷³mod 1073 = 997
• 101⁷³mod 1073 = 1026
• 108⁷³mod 1073 = 367
• 108⁷³mod 1073 = 367
• 111⁷³mod 1073 = 629
• 32⁷³mod 1073 = 698
• 119⁷³mod 1073 = 785
• 111⁷³mod 1073 = 629
• 114⁷³mod 1073 = 965
• 108⁷³mod 1073 = 367
• 100⁷³mod 1073 = 544
• 33⁷³mod 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

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

• 997⁶⁴⁹mod 1073 = 72
• 1026⁶⁴⁹mod 1073 = 101
• 367⁶⁴⁹mod 1073 = 108
• 367⁶⁴⁹mod 1073 = 108
• 629⁶⁴⁹mod 1073 = 111
• 698⁶⁴⁹mod 1073 = 32
• 785⁶⁴⁹mod 1073 = 119
• 629⁶⁴⁹mod 1073 = 111
• 965⁶⁴⁹mod 1073 = 114
• 367⁶⁴⁹mod 1073 = 108
• 544⁶⁴⁹mod 1073 = 100
• 847⁶⁴⁹mod 1073 = 33

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

Outil de calcul des clés RSA

Structure du document