Algorithme de génération de clés :

 C'est l'algorithme original :

1. Générer deux grands nombres premiers aléatoires, p et q, de taille approximativement égale de telle sorte que leur produit n = p q est de la longueur de bits nécessaires, par exemple 1024 bits.
2. Calculer n = p q et φ = (p-1)(q-1) .
3. Choisissez un entier e, 1 <e< φ, tel que pgcd(e, φ) = 1 .
4. Calculer l’exposant privé d, 1 <d < φ , tel que ed ≡ 1 (mod φ) .
5. La clé publique est (n, e) et la clé privée (d, p, q). Gardez toutes les valeurs d, p, q et φ secrètes. [Nous préférons parfois écrire la clé privée comme (n, d) car vous avez besoin de la valeur de n lors de l'utilisation d.]

• n est connu comme le module.
• e est connue sous le nom exposant public ou de l'exposant de chiffrement ou tout simplement l’exposant.
• d est connu sous le nom exposant privé ou de l'exposant de déchiffrement.

 Chiffrement :

Un expéditeur A effectue les opérations suivantes:

1. Obtient la clé publique du destinataire B : (n, e).
2. Représente le message en clair comme un entier positif m, 1 <m <n .
3. Calcule le cryptogramme c = m ^e mod n .
4. Envoie le texte chiffré C à B.

 Déchiffrement :

Le destinataire B effectue les opérations suivantes: -

1. Utilise sa clé privée (n, d) pour calculer m = c ^d mod n .
2. Extraits le texte clair du message représentant m .

 Résumé du RSA :

• n = p q, où p et q sont des nombres premiers distincts.
• φ = (p-1) (q-1)
• e <n tel que pgcd (e, φ) = 1
• d = e ^-1 mod φ.
• c = m ^e mod n, 1 <m <n.
• m = c ^d mod n.

Un exemple très simple de chiffrement RSA :

Ceci est un exemple extrêmement simple en utilisant des nombres que vous pouvez calculer avec une calculatrice de poche.

1. Sélectionnez deux nombres premiers p = 11, q = 3.
2. n = p*q = 11*3 = 33 
   φ = (p-1) (q-1) = 10*2 = 20
3. Choisissez e = 3 
   Vérifiez que le pgcd (e, p-1) = pgcd (3, 10) = 1 (c'est à dire 3 et 10 n'ont pas de facteurs communs, sauf 1), 
   et vérifier que le pgcd (e, q-1) = pgcd (3, 2) = 1 
   donc pgcd (e, φ) = pgcd (e, (p-1) (q-1)) = pgcd (3, 20) = 1
4. Calculer d tel que ed ≡ 1 (mod φ) 
   ie calculer d = e ^-1 mod φ = 3^-1 mod 20 
   ie trouver une valeur pour d telle que φ divise d (ed-1) 
   ie trouver d tel que 20 divise 3d-1. 
   Test simple : (d = 1, 2, ...) donne d = 7 
   Vérifiez: ed-1 = 3*7 - 1 = 20, qui est divisible par φ.
5. La clé publique = (n, e) = (33, 3) 
   La clé privée = (n, d) = (33, 7).

C'est en fait la plus petite valeur possible pour le module n pour lequel l’algorithme RSA fonctionne.

Maintenant disons que nous voulons chiffrer le message m = 7, 
c = m^e mod n = 7³ mod 33 = 343 mod 33 = 13. 
Ainsi le texte chiffré c = 13.

Pour vérifier le décryptage, nous calculons 
m'= c^d mod n = 13⁷ mod 33 = 7. 
Notez que nous n'avons pas à calculer la valeur totale de 13 à la puissance 7 ici. Nous pouvons faire usage du fait que a = bc mod n = (b mod n). (c mod n) mod n 
Une manière de calculer m' est comme suit:
A noter que tout nombre peut être exprimé comme une somme de puissances de deux. Alors d'abord calculer les valeurs des 13² , 13⁴ , 13⁸ , ... de façon répétée les valeurs au carré successives modulo 33. 
13² = 169 ≡ 4, 13⁴ = 4*4 = 16, 13⁸ = 16*16 = 256 ≡ 25. 
Ensuite, depuis le 7 = 4 + 2 + 1, nous avons m'= 13⁷ = 13^{(4 +2 +1)} = 13⁴ *13² *13¹
≡ 16 x 4 x 13 = 832 ≡ 7 mod 33

Maintenant, si on calcule le cryptogramme C pour toutes les valeurs possibles de m (0 à 32), nous obtenons

m	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
c	0	1	8	27	31	26	18	13	17	3	10	11	12	19	5	9	4

m	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32
c	29	24	28	14	21	22	23	30	16	20	15	7	2	6	25	32

Si nous voulions utiliser ce système pour garder les secrets, nous pourrions laisser:

A = 2, B = 3, ..., Z = 27.

Ainsi, le message en clair "HELLOWORLD" serait représenté par l'ensemble des entiers m₁, m₂, ...

(9,6,13,13,16,24,16,19,13,5)

En utilisant notre tableau ci-dessus, nous obtenons des entiers cryptogramme C₁, C₂ , ...

(3,18,19,19,4,30,4,28,19,26)

 

Rappelez-vous que le calcul de m^e mod n est facile, mais le calcul de l'inverse c^-e mod n est très difficile pour les grands n de toute façon. Cependant, si nous pouvons mettre n en facteurs premiers p et q, la solution devient facile encore une fois, même pour les grands n. Évidemment, si nous pouvons mettre la main sur l’exposant privée d, la solution est facile aussi.