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 = 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
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).
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!".
Outil de calcul des clés RSA
Deutsche Übersetzung
Sie haben gebeten, diese Seite auf Deutsch zu besuchen. Momentan ist nur die Oberfläche übersetzt, aber noch nicht der gesamte Inhalt.Wenn Sie mir bei Übersetzungen helfen wollen, ist Ihr Beitrag willkommen. Alles, was Sie tun müssen, ist, sich auf der Website zu registrieren und mir eine Nachricht zu schicken, in der Sie gebeten werden, Sie der Gruppe der Übersetzer hinzuzufügen, die Ihnen die Möglichkeit gibt, die gewünschten Seiten zu übersetzen. Ein Link am Ende jeder übersetzten Seite zeigt an, dass Sie der Übersetzer sind und einen Link zu Ihrem Profil haben.
Vielen Dank im Voraus.
Dokument erstellt 24/06/2005, zuletzt geändert 26/10/2018
Quelle des gedruckten Dokuments:https://www.gaudry.be/de/crypto-rsa.html
Die Infobro ist eine persönliche Seite, deren Inhalt in meiner alleinigen Verantwortung liegt. Der Text ist unter der CreativeCommons-Lizenz (BY-NC-SA) verfügbar. Weitere Informationen auf die Nutzungsbedingungen und dem Autor.
