Exercices td cryptographie elliptique sur z11 cryptographie
Télécharger PDFExercice sur les courbes elliptiques
Rappel : Une courbe elliptique est une équation de la forme y² = x³ + ax + b, définie sur ℤ/pℤ. Ici, p est un nombre premier supérieur ou égal à 5, et a, b sont choisis tels que 4a³ + 27b² ≠ 0 (discriminant non nul).
Règles de l'addition
Soit la courbe elliptique cryptographique y² ≡ (x³ + ax + b) mod p. Le nombre p doit être un nombre premier. Lors des calculs, une division par 0 peut survenir, auquel cas le point résultat est appelé « infini ». Voici les règles :
1. infini + infini = infini
2. (x₁, y₁) + infini = (x₁, y₁)
3. (x₁, y₁) + (x₁, -y₁) = infini
4. Si x₁ ≠ x₂, alors (x₁, y₁) + (x₂, y₂) = (x₃, y₃), avec :
x₃ = (k² - x₁ - x₂) mod py₃ = (k(x₁ - x₃) - y₁) mod pk = (y₂ - y₁) · (x₂ - x₁)⁻¹ mod p
y₁ ≠ 0, alors (x₁, y₁) + (x₁, y₁) = 2(x₁, y₁) = (x₃, y₃), avec :
x₃ = (k² - 2x₁) mod py₃ = (k(x₁ - x₃) - y₁) mod pk = (3x₁² + a) · (2y₁)⁻¹ mod p
Multiplication d'un point par un nombre entier
La multiplication d'un point par un nombre entier se fait par une série d'additions. Par exemple, pour la courbe y² ≡ (x³ + x + 2) mod 11, calculons d·P avec d = 3 et P = (4, 2). On vérifie d'abord que P appartient bien à la courbe elliptique.
Calculons P + P (c'est-à-dire 2P) selon la règle 5 :
k = (3·4² + 1) · (2·2)⁻¹ mod 11 = (3·16 + 1) · 4⁻¹ mod 11 = 49 · 3⁻¹ mod 11 = 5 · 4 mod 11 = 20 mod 11 = 9
x₃ = (9² - 2·4) mod 11 = (81 - 8) mod 11 = 73 mod 11 = 7
y₃ = (9(4 - 7) - 2) mod 11 = (9(-3) - 2) mod 11 = (-27 - 2) mod 11 = -29 mod 11 = 3
Donc 2P = (7, 3).
Ensuite, calculons 2P + P selon la règle 4 :
k = (3 - 2) · (7 - 4)⁻¹ mod 11 = 1 · 3⁻¹ mod 11 = 1 · 4 mod 11 = 4
x₃ = (4² - 7 - 4) mod 11 = (16 - 11) mod 11 = 5 mod 11 = 5
y₃ = (4(7 - 5) - 3) mod 11 = (4·2 - 3) mod 11 = (8 - 3) mod 11 = 5 mod 11 = 5
Donc 3P = (5, 5).
Exercice cryptographie elliptique
Soit E la courbe définie sur ℤ/11ℤ d'équation y² ≡ x³ + x + 6 mod 11.
- Montrer que
Eest une courbe elliptique surℤ/11ℤ. - Montrer que le point
P = (2, 7)appartient àE(ℤ/11ℤ).
Solution exercice 1 : Vérification du discriminant
Le discriminant est donné par 4a³ + 27b² mod p. Pour E, on a a = 1 et b = 6.
4a³ + 27b² mod 11 = 4·1³ + 27·6² mod 11 = 4 + 27·36 mod 11.
Calculons 36 mod 11 = 3, donc 27·36 mod 11 = 27·3 mod 11 = 81 mod 11 = 4.
Le discriminant est donc 4 + 4 = 8 mod 11 ≠ 0, ce qui prouve que E est une courbe elliptique définie sur ℤ/11ℤ.
Solution exercice 2 : Vérification du point P = (2, 7)
Pour montrer que P appartient à E, on vérifie si y² ≡ x³ + x + 6 mod 11.
y² = 7² mod 11 = 49 mod 11 = 5.
x³ + x + 6 = 2³ + 2 + 6 mod 11 = 8 + 2 + 6 mod 11 = 16 mod 11 = 5.
Puisque y² ≡ x³ + x + 6 mod 11, le point P = (2, 7) appartient bien à E(ℤ/11ℤ).
Solution exercice 3 : Calcul de la clé publique d'Alice
Alice utilise la clé secrète s = 7 pour calculer sa clé publique Kpub = s·P = 7P.
On calcule d'abord 2P avec P = (2, 7) selon la règle 5 :
k = (3·2² + 1) · (2·7)⁻¹ mod 11 = (12 + 1) · 14⁻¹ mod 11 = 13 · 3⁻¹ mod 11 = 2 · 4 mod 11 = 8.
x₃ = (8² - 2·2) mod 11 = (64 - 4) mod 11 = 60 mod 11 = 5.
y₃ = (8(2 - 5) - 7) mod 11 = (-24 - 7) mod 11 = -31 mod 11 = 2.
Donc 2P = (5, 2).
On calcule ensuite 4P = 2·(2P) = 2P + 2P :
k = (3·5² + 1) · (2·2)⁻¹ mod 11 = (75 + 1) · 4⁻¹ mod 11 = 76 · 3 mod 11 = 10 · 3 mod 11 = 30 mod 11 = 8.
x₃ = (8² - 2·5) mod 11 = (64 - 10) mod 11 = 54 mod 11 = 10.
y₃ = (8(5 - 10) - 2) mod 11 = (-40 - 2) mod 11 = -42 mod 11 = 2.
Donc 4P = (10, 2).
Enfin, on calcule 6P = 2P + 4P = (5, 2) + (10, 2) selon la règle 4 :
k = (2 - 2) · (10 - 5)⁻¹ mod 11 = 0 · 5⁻¹ mod 11 = 0.
x₃ = (0² - 5 - 10) mod 11 = -15 mod 11 = 7.
y₃ = (0(5 - 7) - 2) mod 11 = -2 mod 11 = 9.
Donc 6P = (7, 9).
Pour calculer 7P = P + 6P = (2, 7) + (7, 9) :
k = (9 - 7) · (7 - 2)⁻¹ mod 11 = 2 · 5⁻¹ mod 11 = 2 · 9 mod 11 = 18 mod 11 = 7.
x₃ = (7² - 2 - 7) mod 11 = (49 - 9) mod 11 = 40 mod 11 = 7.
y₃ = (7(2 - 7) - 7) mod 11 = (-42 - 7) mod 11 = -49 mod 11 = 2.
Donc Kpub = 7P = (7, 2).
On vérifie que Kpub appartient à E :
x³ + x + 6 = 7³ + 7 + 6 mod 11 = 343 + 7 + 6 mod 11 = 356 mod 11 = 4.
y² = 2² mod 11 = 4 mod 11.
Puisque y² ≡ x³ + x + 6 mod 11, le point Kpub = (7, 2) appartient bien à E.
Solution exercice 4 : Chiffrement et déchiffrement avec ElGamal
Bob souhaite envoyer le message M = (3, 6) à Alice en utilisant le cryptosystème ElGamal associé au couple public (E, P).
Bob choisit aléatoirement l'entier k = 6.
- Calculer
C₁ = k·P = 6P. - Calculer
C₂ = M + k·Kpub = (3, 6) + 6·(7, 2). - Envoyer le message chiffré
(C₁, C₂). - Expliquer comment Alice retrouve le message
M.
D'après la question 3, on a 6P = (7, 9), donc C₁ = (7, 9).
Calculons 6·Kpub = 6·(7, 2) :
D'abord, 2·Kpub = (7, 2) + (7, 2) = (2, 7) selon la règle 5.
Ensuite, 4·Kpub = 2·(2·Kpub) = (2, 7) + (2, 7) = (5, 2).
Enfin, 6·Kpub = 4·Kpub + 2·Kpub = (5, 2) + (2, 7) = (8, 3).
Donc C₂ = M + k·Kpub = (3, 6) + (8, 3) = (3, 5).
Le message chiffré envoyé par Bob à Alice est donc (C₁, C₂) = ((7, 9), (3, 5)).
Alice retrouve le message M en calculant M = C₂ − s·C₁ avec sa clé secrète s = 7.
D'abord, elle calcule 7·C₁ = 7·(7, 9) = 7·6P = 42P.
On sait que 6P = (7, 9), donc 42P = 6P (car 42 mod 11 = 9, et 9P = 6P + 3P).
En simplifiant, 7·C₁ = 7·6P = 42P = 6P (car 42 mod 11 = 9, et 9P = 6P + 3P).
Donc 7·C₁ = (7, 9) + 3·(7, 9).
On calcule 3·(7, 9) :
2·(7, 9) = (7, 9) + (7, 9) = (2, 7) selon la règle 5.
3·(7, 9) = (2, 7) + (7, 9) = (8, 3).
Donc 7·C₁ = (7, 9) + (8, 3) = (8, 3).