L'algorithme de chiffrement RSA est un type d'algorithme de chiffrement à clé publique. Pour mieux comprendre RSA, comprenons d’abord ce qu’est l’algorithme de chiffrement à clé publique.
Algorithme de chiffrement à clé publique :
L’algorithme de chiffrement à clé publique est également appelé algorithme asymétrique. Les algorithmes asymétriques sont des algorithmes dans lesquels l'expéditeur et le destinataire utilisent des clés différentes pour le cryptage et le déchiffrement. Chaque expéditeur se voit attribuer une paire de clés :
Le Clé publique est utilisé pour le cryptage, et le Clé privée est utilisé pour le décryptage. Le décryptage ne peut pas être effectué à l'aide d'une clé publique. Les deux clés sont liées, mais la clé privée ne peut pas être dérivée de la clé publique. La clé publique est bien connue, mais la clé privée est secrète et n'est connue que de l'utilisateur qui possède la clé. Cela signifie que tout le monde peut envoyer un message à l'utilisateur en utilisant la clé publique de l'utilisateur. Mais seul l’utilisateur peut décrypter le message grâce à sa clé privée.
L'algorithme à clé publique fonctionne de la manière suivante :
- Les données à envoyer sont cryptées par l'expéditeur UN en utilisant la clé publique du destinataire prévu
- B déchiffre le texte chiffré reçu à l'aide de sa clé privée, connue uniquement de B. B répond à A en chiffrant son message à l'aide de la clé publique de A.
- A déchiffre le texte chiffré reçu à l'aide de sa clé privée, qui n'est connue que de lui.
Algorithme de cryptage RSA :
RSA est l'algorithme à clé publique le plus courant, du nom de ses inventeurs Rivest, Shamir et Adelman (RSA).
L'algorithme RSA utilise la procédure suivante pour générer des clés publiques et privées :
- Sélectionnez deux grands nombres premiers, p et q .
- Multipliez ces nombres pour trouver n = pxq, où n est appelé module de cryptage et de déchiffrement.
- Choisissez un numéro C'est moins que n , tel que n est premier par rapport à (p - 1) x (q -1). Cela signifie que C'est et (p - 1) x (q - 1) n'ont pas de facteur commun sauf 1. Choisissez 'e' tel que 1
pgcd (e,d(n)) =1 - Si n = pxq, alors la clé publique est . Un message en clair m est chiffré à l'aide d'une clé publique. Pour trouver le texte chiffré à partir du texte brut, la formule suivante est utilisée pour obtenir le texte chiffré C.
C = mC'estcontre m
Ici , m doit être inférieur à n . Un message plus volumineux (>n) est traité comme une concaténation de messages, chacun étant chiffré séparément. - Pour déterminer la clé privée, nous utilisons la formule suivante pour calculer le d tel que :
DC'estmod {(p - 1) x (q - 1)} = 1
Ou
DC'estmod φ (n) = 1 - La clé privée est . Un message chiffré c est déchiffré à l'aide d'une clé privée. Pour calculer du texte brut m à partir du texte chiffré c, la formule suivante est utilisée pour obtenir le texte brut m.
m = cdcontre m
Prenons un exemple d'algorithme de chiffrement RSA :
Exemple 1:
Cet exemple montre comment nous pouvons chiffrer le texte brut 9 à l'aide de l'algorithme de chiffrement à clé publique RSA. Cet exemple utilise les nombres premiers 7 et 11 pour générer les clés publiques et privées.
Explication:
Étape 1: Sélectionnez deux grands nombres premiers, p et q .
p = 7
q = 11
Étape 2: Multipliez ces nombres pour trouver n = p x q, où n est appelé module de cryptage et de déchiffrement.
Dans un premier temps, nous calculons
n = pxq
n = 7 x 11
n = 77
Étape 3: Choisissez un numéro C'est moins ça n , tel que n est premier par rapport à (p - 1) x (q -1). Cela signifie que C'est et (p - 1) x (q - 1) n'ont pas de facteur commun sauf 1. Choisissez 'e' tel que 1 Deuxièmement, nous calculons φ (n) = (p - 1) x (q-1) (n) = (7 - 1) x (11 - 1) (n) = 6 x 10 (n) = 60 Choisissons maintenant e relatif premier de 60 comme 7. Ainsi la clé publique est = (7, 77) Étape 4: Un message en clair m est chiffré à l'aide d'une clé publique. Pour trouver le texte chiffré à partir du texte brut, la formule suivante est utilisée pour obtenir le texte chiffré C. Pour trouver le texte chiffré à partir du texte brut, la formule suivante est utilisée pour obtenir le texte chiffré C. C = mC'estcontre m C = 97contre 77 C = 37 Étape 5 : La clé privée est . Pour déterminer la clé privée, on utilise la formule d suivante telle que : DC'estmod {(p - 1) x (q - 1)} = 1 7d mod 60 = 1, ce qui donne d = 43 La clé privée est = (43, 77) Étape 6 : Un message chiffré c est déchiffré à l'aide d'une clé privée. Pour calculer du texte brut m à partir du texte chiffré c, la formule suivante est utilisée pour obtenir le texte brut m. m = cdcontre m m = 3743contre 77 m = 9 Dans cet exemple, Texte brut = 9 et texte chiffré = 37 Dans un système de chiffrement RSA, un A particulier utilise deux nombres premiers, 13 et 17, pour générer les clés publique et privée. Si le public de A est 35. Alors la clé privée de A est …………… ?. Explication: Étape 1: dans un premier temps, sélectionnez deux grands nombres premiers, p et q . p = 13 q = 17 Étape 2: Multipliez ces nombres pour trouver n = pxq, où n est appelé module de cryptage et de déchiffrement. Dans un premier temps, nous calculons n = pxq n = 13 x 17 n = 221 Étape 3: Choisissez un numéro C'est moins ça n , tel que n est premier par rapport à (p - 1) x (q -1). Cela signifie que C'est et (p - 1) x (q - 1) n'ont pas de facteur commun sauf 1. Choisissez 'e' tel que 1 Deuxièmement, nous calculons φ (n) = (p - 1) x (q-1) (n) = (13 - 1) x (17 - 1) (n) = 12 x 16 (n) = 192 pgcd (35, 192) = 1 Étape 3: Pour déterminer la clé privée, nous utilisons la formule suivante pour calculer le d tel que : Calculer d = dC'estmod φ (n) = 1 d = d x 35 mod 192 = 1 d = (1 + k.φ (n))/e [soit k =0, 1, 2, 3………………] Mettez k = 0 d = (1 + 0 x 192)/35 d = 1/35 Mettez k = 1 d = (1 + 1 x 192)/35 d = 193/35 Mettez k = 2 ré = (1 + 2 x 192)/35 d = 385/35 d = 11 La clé privée est = (11, 221) Par conséquent, clé privée, c'est-à-dire d = 11 Un cryptosystème RSA utilise deux nombres premiers 3 et 13 pour générer la clé publique = 3 et la clé privée = 7. Quelle est la valeur du texte chiffré pour un texte brut ? Explication: Étape 1: Dans la première étape, sélectionnez deux grands nombres premiers, p et q . p = 3 q = 13 Étape 2: Multipliez ces nombres pour trouver n = pxq, où n est appelé module de cryptage et de déchiffrement. Dans un premier temps, nous calculons n = pxq n = 3x13 n = 39 Étape 3: Si n = pxq, alors la clé publique est . Un message en clair m est chiffré à l'aide d'une clé publique. Ainsi la clé publique est = (3, 39). Pour trouver le texte chiffré à partir du texte brut, la formule suivante est utilisée pour obtenir le texte chiffré C. C = mC'estcontre m C = 53vers 39 C = 125 contre 39 C = 8 Par conséquent, le texte chiffré généré à partir du texte brut, C = 8. Un système de chiffrement RSA utilise deux nombres premiers, 3 et 11, pour générer une clé privée = 7. Quelle est la valeur du texte chiffré pour un texte brut 5 utilisant l'algorithme de chiffrement à clé publique RSA ? Explication: Étape 1: dans un premier temps, sélectionnez deux grands nombres premiers, p et q . p = 3 q = 11 Étape 2: Multipliez ces nombres pour trouver n = pxq, où n est appelé module de cryptage et de déchiffrement. Dans un premier temps, nous calculons n = pxq n = 3x11 n = 33 Étape 3: Choisissez un numéro C'est moins ça n , tel que n est premier par rapport à (p - 1) x (q -1). Cela signifie que C'est et (p - 1) x (q - 1) n'ont pas de facteur commun sauf 1. Choisissez 'e' tel que 1 Deuxièmement, nous calculons φ (n) = (p - 1) x (q-1) (n) = (3 - 1) x (11 - 1) (n) = 2 x 10 (n) = 20 Étape 4: Pour déterminer la clé publique, nous utilisons la formule suivante pour calculer le d tel que : Calculer e x d = 1 mod φ (n) e x 7 = 1 contre 20 e x 7 = 1 contre 20 e = (1 + k. φ (n))/ ré [soit k =0, 1, 2, 3………………] Mettez k = 0 e = (1 + 0 x 20) / 7 e = 1/7 Mettez k = 1 e = (1 + 1 x 20) / 7 e = 21/7 e = 3 La clé publique est = (3, 33) Par conséquent, la clé publique, c'est-à-dire e = 3 'l'algorithme de Kruskal'
Exemple 2 :
Exemple 3 :
code de nombre aléatoire c
Exemple 4 :