Exercices td cryptographie rsa avec p 7 et q 11 cryptographi
Télécharger PDFExercice 5 : Cryptographie RSA
1. Calcul des clés publiques et privées
On utilise les nombres premiers p = 7 et q = 11.
Calcul de n : n = p × q = 7 × 11 = 77.
Calcul de φ(n) : φ(n) = (p - 1) × (q - 1) = 6 × 10 = 60.
Choix d'un exposant e tel que pgcd(e, 60) = 1. Les nombres premiers inférieurs à 60 sont : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59. On préfère choisir le plus petit possible pour simplifier les calculs. Par exemple, e = 7.
Vérification : pgcd(7, 60) = 1.
Calcul de l'inverse de e modulo φ(n) avec l'algorithme d'Euclide étendu pour trouver d tel que d × e ≡ 1 mod φ(n).
On cherche d tel que d × 7 ≡ 1 mod 60.
Algorithme d'Euclide étendu :
1 = 4 - 1 × 3
1 = 4 - 1 × (7 - 1 × 4) = 4 - 1 × 7 + 1 × 4 = 2 × 4 - 1 × 7
1 = 2 × (60 - 8 × 7) - 1 × 7 = 2 × 60 - 16 × 7 - 1 × 7 = 2 × 60 - 17 × 7
Donc, d ≡ -17 mod 60.
Pour obtenir un nombre positif, on calcule : d = -17 + 60 = 43.
Table des clés :
| Privé | Public |
|---|---|
| d = 43 | e = 7 |
| n = 77 | n = 77 |
2. Chiffrement du message
Le message à chiffrer est : TOUTEFOIS LES CARACTÈRES DES DIFFÉRENTES VERSIONS SONT LES MÊMES.
Conversion des lettres en valeurs numériques (A=0, B=1, ..., Z=25) :
| Lettre | Valeur numérique |
|---|---|
| T | 19 |
| O | 14 |
| U | 20 |
| T | 19 |
| E | 4 |
| F | 5 |
| O | 14 |
| I | 8 |
| S | 18 |
Chiffrement avec l'équation : xe ≡ me mod n.
Exemple pour T (19) : 197 mod 77 = 68.
Le cryptogramme RSA correspondant est : 68, 42, 48, 68, 60, 47, 42, 57, 39.
3. Déchiffrement du cryptogramme
Déchiffrement avec l'équation : m ≡ xd mod n.
Exemple pour 68 : 6843 mod 77 = 19.
Le message déchiffré est : TOUTEFOIS LES CARACTÈRES DES DIFFÉRENTES VERSIONS SONT LES MÊMES.
FAQ
Qu'est-ce que l'algorithme d'Euclide étendu ?
L'algorithme d'Euclide étendu est une méthode pour trouver les coefficients de Bézout, c'est-à-dire les entiers x et y tels que a × x + b × y = pgcd(a, b). Il permet de calculer l'inverse modulo d'un nombre.
Comment convertir une lettre en valeur numérique pour RSA ?
Pour RSA, on utilise généralement la conversion A=0, B=1, ..., Z=25. Les lettres accentuées ou autres caractères peuvent être traitées différemment selon le contexte.
Pourquoi choisir un petit exposant e pour le chiffrement ?
Choisir un petit exposant e simplifie les calculs de chiffrement et de déchiffrement sans affecter la sécurité du système RSA, tant que pgcd(e, φ(n)) = 1.