Différences

Ci-dessous, les différences entre deux révisions de la page.

--- nsi:tds:cryptographie:ecc [2023/03/13 22:14] – [Fichier de base] goupillwiki
+++ nsi:tds:cryptographie:ecc [2023/05/08 16:53] (Version actuelle) – [Nombre plutôt que point] goupillwiki
@@ Ligne 14: / Ligne 14: @@
 $$(E): y^2 = x^3 + a\cdot x + b$$
+<WRAP tip>
 Une **ellipse** a une équation plutôt de la forme $\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1$.
 Les courbes elliptiques tiennent leur nom du fait qu'elles sont apparues au XIXe siècle dans des travaux de Weierstrass sur la circonférence des ellipses. Depuis elles se sont avérées très fécondes : elles permettent de décrire le mouvement d'une toupie, elles ont été utilisées dans la démonstration du théorème de Fermat et, ce qui nous intéresse maintenant, elles sont utilisées en cryptographie.
+</WRAP>
 ==== Une courbe particulière ====
@@ Ligne 48: / Ligne 50: @@
 {{ ecc-3.png?nolink&400 |}}
-La droite $(PQ)$ est verticale et n'a pas d'autre intersection avec la courbe. On définit alors un point $P_0$ qui est en quelque sorte à l'infini. On dit que dans ce cas là, $(PQ)$ coupe la courbe en l'infini, donc en $P_0$ et alors $P + Q = P_0$.
+La droite $(PQ)$ est verticale et n'a pas d'autre intersection avec la courbe. On définit alors un point $P_0$ qui est en quelque sorte à l'infini. On dit que dans ce cas là, $(PQ)$ coupe la courbe en l'infini, donc en $P_0$ et alors $P + Q = P_0$ -- //on appelle cela de la géométrie projective.//
-On définit aussi que $P_0$ est l'**élément neutre** de notre addition, c'est à dire le $0$. Autrement dit, on a toujours $P + P_0 = P$ -- de même que l'on dirait $x + 0 = x$.
+On définit aussi que $P_0$ est l'**élément neutre** de notre addition, c'est à dire le $0$. Autrement dit, on a toujours $P + P_0 = P$ tout comme on dirait $x + 0 = x$.
 Ainsi notre addition a deux nouvelles propriétés essentielles :
@@ Ligne 62: / Ligne 64: @@
 {{ ecc-4.png?nolink&400 |}}
-Ainsi, nous pouvons obtenir $P + P = 2P$ et son opposé $-2p$. Partant de là on pourra calculer $P + 2P = 3P$ et déduire $-3P$. Etc.
+Ainsi, nous pouvons obtenir $P + P = 2P$ et son opposé $-2P$. Partant de là on pourra calculer $P + 2P = 3P$ et déduire $-3P$. Etc.
 Ainsi, on a donné un sens à $n\cdot P, n\in\mathbb{Z}$.
@@ Ligne 68: / Ligne 70: @@
 ==== Une arithmétique de points ====
-Notre addition a toutes les propriétés nécessaires et tous les calculs que l'on a envie de faire sont valables : Par exemple $2\cdot(3P + Q) = 6P + 2Q$.
+Prenons deux calculs :
-  - Concrètement pour le premier calcul, $3P$ s'obtient en calculant $P+P = 2P$ puis $P + 2P = 3P$. Ensuite On cherche un point $Z = 3P + Q$. Enfin on cherche $Z + Z = 2Z$. Nous avons défini chacun de ces calculs élémentaires.
+  - D'abord $2\cdot(3P + Q)$\\ cela veut dire que l'on calcule $2P = P + P$ puis $3P = 2P + P$, puis $Z = 3P + Q$ et enfin le résultat $2Z = Z + Z$.
-  - Pour le second calcul, on calculerait $2P = P+P$, puis $4P = 2P + 2P$, puis $6P = 4P + 2P$, puis $2Q = Q + Q$ et enfin $4P + 2Q$.
+  - Ensuite $6P + 2Q$\\ on calcule $2P = P + P$, $4P = 2P + 2P$, $6P = 4P + 2P$, $2Q = Q + Q$ et enfin le résultat $6P + 2Q$
-Ce qui est remarquable, c'est que ces deux constructions graphiques produiront le même résultat. C'est pour cette raison que l'on peut parler d'addition : l'addition ainsi définie a les bonnes propriétés.
+Les deux constructions / calculs produisent le même résultat. C'est pour cette raison que l'on peut écrire $2(3P + Q) = 6P + 2Q$. Nos constructions respectent les règles de calculs habituelles comme le fait de développer une multiplication sur une addition.
+L'addition définie par la courbe elliptique a toute les propriétés d'une bonne addition.
 ==== Les formules ====
@@ Ligne 103: / Ligne 107: @@
 Comme avec les nombres entiers, il est plus intéressant de travailler avec modulo :
   * Les calculs seront exclusivement sur des nombres entiers ce qui facilitera les choses,
-  * comme avec les nombres entiers, les modulos "//embrouillent//" un peu les calculs ce qui est idéal pour la cryptographie.
+  * comme avec les nombres entiers, les modulos « //embrouillent// » un peu les calculs ce qui est idéal pour la cryptographie.
 On modifie un peut la définition :
-  * On choisit un premier $p$, en situation réelle on le prend assez grand.
+  * On choisit un premier $p$, en situation réelle on le prend assez grand.\\ on note $a \overset{p}{\equiv} b$ pour $a = b \mod p$.
   * Les points considérés ont des coordonnées $(x ; y)$ entières.
-  * On considère que deux points $P_1(x_1;y_1)$ et $P_2(x_2;y_2)$ sont identiques si $x_1 \equiv x_2 [p]$ et $y_1 \equiv y_2 [p]$
+  * On considère que deux points $P_1(x_1;y_1)$ et $P_2(x_2;y_2)$ sont identiques si $x_1 \overset{p}{\equiv} x_2$ et $y_1 \overset{p}{\equiv} y_2$
-  * L'équation de la courbe est maintenant $(E): y^2 \equiv x^3 + a\cdot x + b [p]$
+  * L'équation de la courbe est maintenant $(E): y^2 \overset{p}{\equiv} x^3 + a\cdot x + b$
-  * La contrainte devient $4\cdot a^3 + 27 \cdot b^2 \not\equiv 0 [p]$
+  * La contrainte devient $4\cdot a^3 + 27 \cdot b^2 \overset{p}{\not\equiv}  0$
 Dans le cadre de ce TD, on prendra $p = 13$ et toujours $a=-1$ et $b=1$.
@@ Ligne 120: / Ligne 124: @@
 Les formules présentées plus haut sont toujours valides à ceci près que toutes les quantités sont calculées modulo $p$. De plus, vous pouvez voir des divisions. On n'utilisera pas l'opérateur de division, mais on utilisera l'[[nsi:tds:cryptographie:inverse_modulaire|inverse modulaire]].
+<WRAP important>
+Puisque nous sommes dans le cas modulaire, les calculs sont un peu changés. Par exemple pour le cas 1 ci-dessus, il faudra lire $x_p \neq x_Q \mod p$, et par exemple pour le calcul de $m$ :
+$$m = (y_P - y_Q)\times \text{inverse modulaire}(x_P - x_Q)$$
+</WRAP>
 ===== Implémentation =====
@@ Ligne 161: / Ligne 170: @@
     RENVOYER Q
 </code>
+==== Point de base ====
+Il n'est pas forcément évident de trouver au moins un point sur la courbe. Une possibilité est de tirer au hasard des paires $(x;y)$ telles que $0 \leq x < p$ et $0 \leq y < p$ jusqu'à trouver une paire sur la courbe.
+J'ai fait le test avec $a=-1$, $b = 1$ et $p = 502181$. J'obtiens rapidement des points. Par exemple $(224426 ; 32906)$.
+<WRAP tip> Dans le module suivant {{ :nsi:tds:cryptographie:sqrtmod.py |}}, j'ai implémenté les fonctions ''is_quadratic'' et ''sqrt'' qui permettent de travailler sur les équations $a \overset{p}{\equiv} x^2$. La première fonction indique si une telle solution existe et la deuxième fonction permet d'extraire une des deux solutions -- il y a 0 ou deux solutions, s'il y en a deux leur somme est le premier ''p''.
+Avec ces fonctions, pour un $x$ donné, on peut calculer $y^2 = x^3 - a\cdot x + b \mod p$ puis extraire la racine pour obtenir $y$, si toutefois elle existe. Il est alors aisé de trouver les points de la courbe.
+Par exemple, pour $a=-1$, $b = 1$ et $p = 502181$, on trouve que si $x = 97$, $y^2 = 410\,396$ dont une racine modulaire est $285\,923$. Le point $(97\,;\,285\,923)$ est donc sur la courbe. Il y a beaucoup de points. On peut choisir $x$ au hasard, calculer $y^2$, vérifier si $y^2$ est un résidu quadratique (càd si on peut calculer $y$), si oui calculer $y$ sinon essayer un autre $x$.
+</WRAP>
 ==== Fichier de base ====
@@ Ligne 257: / Ligne 279: @@
     # petit test
     # définition de points se trouvant sur la courbe (avec modulo)
-    P = Point(1,1)
+    P = Point(3,8)
-    Q = Point(3,5)
+    Q = Point(5,2)
-    R = Point(4,3)
+    R = Point(6,4)
     # exemple de calculs :
     Z = P + Q
+    assert Z == Point(1, 12)
     print("P + Q -> {}".format(Z))
     W = R*2
+    assert W == Point(5,11)
     print("2R -> {}".format(W))
     # remarque : pour l'utilisation de __mul__, il faut écrire R*2 et pas 2*R
@@ Ligne 273: / Ligne 297: @@
     assert P + Q == Q + P
+</code>
+Si vous voulez tenter le point aléatoire, en utilisant {{ :nsi:tds:cryptographie:sqrtmod.py |}}, on peut ajouter une méthode :
+<code python>
+# module ecc.py
+import sqrtmod
+from random import randrange
+class Point:
+    ...
+    @absrtactmethod
+    def alea_point():
+        """
+        renvoie un point aléatoire sur la courbe
+        """
+        x = randrange(Point.P) # il faut P impair
+        y2 = x**3 + Point.A * x + Point.B
+        while not sqrtmod.is_quadratic(y2, self.P):
+            x = randrange(Point.P)
+            y2 = x**3 + self.A * x + self.B
+        y = sqrtmod.sqrt(y2, Point.P)
+        return Point(x, y)
 </code>
@@ Ligne 279: / Ligne 327: @@
 Reprenons le [[nsi:tds:cryptographie:elgamal|chiffrement de ElGamal]] -- on pourrait faire autrement, nos points ont les mêmes capacités que les entiers.
-==== Calcul des clés ====
+==== Rappel ElGamal ====
-Dans le chiffre de ElGamal, Bob choisissait $p$, $d$ et $s$ avec  $p$ premier, $1 < d < p$ et $s > 1$ puis il calculait $h = d^s \mod p$.
+Bob choisit $p$, $d$ et $s$ avec  $p$ premier, $1 < d < p$ et $s > 1$ puis il calculait $h = d^s \mod p$.
-La clé public était $K_{PU} = (p, d, h)$.
+  * $K_{PU} = (p, d, h)$
+  * $K_{PR} = (p, d, s)$
-**Avec les courbes elliptiques :** Bob choisit sa courbe, le nombre premier $p$, un point $D$ de la courbe et un entier $s > 1$. Il calcule $H = s\cdot D$.
+Alice chiffre un message $m$ (un entier).
+  * Elle choisit un $z > 1$ aléatoire, et calcule
+  * $r = m\cdot h^z \mod p$
+  * $t = d^z \mod p$.
+et elle envoie $(r, t)$
-La clé public est $K_{PU} = (\text{la courbe}, p, D, H)$.
+Pour déchiffrer, Bob dispose de sa clé $(p, d, s)$ et du message $(r, t)$. Il calcule
+  * $t^s$,
+  * il cherche $u$ l'inverse de $t^s$
+  * $m = r\cdot u$
+Il a retrouvé $m$
-==== Chiffrement ====
+==== Version ECC ====
-Avec ElGamal, Alice choisissait $a$ entier quelconque et pour transmettre l'entier $m$ elle calculait $r = m\cdot h^a \mod p$ et $t = d^a \mod p$.
+Bob choisit sa courbe (c'est à dire $a$ et $b$), le nombre premier $p$, un point $D$ de la courbe et un entier $s > 1$. Il calcule $H = s\cdot D$.
-Elle envoyait enfin $(r, t)$.
+  * $K_{PU} = (a, b, p, D, H)$
+  * $K_{PR} = (a, b, p, D, s)$
-**Avec les courbes elliptiques :** le message d'Alice est le point $M$. Elle choisit $a$ entier quelconque et elle calcule les points $R = M + a\cdot H$ et $T = a\cdot D$.
+Alice chiffre un message $M$ (un point de la courbe)
+  * Elle choisit $z > 1$ au hasard et calcule
+  * $R = M + z\cdot H$,
+  * $T = z\cdot D$.
 Elle envoie $(R, T)$
-==== Déchiffrement ====
+Pour déchiffrer, Bob connaît $s$. Il calcule
+  * $M = R - s\cdot T$
+c'est fini, Bob a $M$.
-Avec ElGamal, Bob calculait $t^s$, il cherchait $u$ l'inverse de $t^s$ puis il calculait $r\cdot u$ ce qui lui donnait $m$.
+<WRAP tip>
+Le point $D$ est le point de base. Quand les cryptographes choisissent une courbe elliptique, ils choisissent ce $D$ avec soin. En effet, quand on calcule $n\times D$, on génère des points différents mais on finit par trouver un certain $n$ tel que $n\times D = P_0$ de sorte qu'après cela, on reboucle sur les mêmes points. Si on veut que le chiffrement soit fort, il faut que ce bouclage arrive pour $n$ très grand.
+</WRAP>
-**Avec les courbes elliptiques :** Bob calcule le point $s\cdot T$, il cherche son opposé $-s\cdot T$ -- //ce qui est très rapide// -- puis il calcule $R - s\cdot T$ ce qui lui donne $M$.
+==== Pourquoi ça marche ? ====
-**Comprendre pourquoi ça marche :** $T = a\cdot D$ donc
+$T = z\cdot D$ donc
-$$s\cdot T = s\cdot a \cdot D = a \cdot (s \cdot D) = a \cdot H$$
+$$s\cdot T = s\cdot z \cdot D = z \cdot (s \cdot D) = z \cdot H$$
-$$R - s \cdot T = M + a \cdot H - a \cdot H = M$$
+$$R - s \cdot T = M + z \cdot H - z \cdot H = M$$
 Le calcul est même plus simple qu'avec ElGamal, dès lors que l'on ne pense pas trop au fait que l'on calcule avec des points !
@@ Ligne 315: / Ligne 379: @@
 Écrire de plus les fonctions suivantes :
-  * ''%%calculer_cle_prive(D, s)%%'' qui renvoie ''%%(D, H)%%''
+  * ''%%calculer_cle_publique(D, s)%%'' qui renvoie ''%%(D, H)%%''
   * ''%%chiffrer(M, D, H)%%'' qui renvoie la paire ''%%(R, T)%%'' du message chiffré
   * ''%%dechiffrer(R, T, D, s)%%'' qui renvoie ''%%M%%''.
@@ Ligne 321: / Ligne 385: @@
 La connaissance du nombre premier $p$ et de la courbe choisie sont important mais ces éléments sont déjà contenus dans notre classe ''%%Point%%''. On pourra donc supposer que Alice et Bob ont déjà ces informations en main.
-Faire le test en choisissant ''%%p = 17%%'', ''%%d = 5%%'', ''%%s = 12%%'' et ''%%M = Point(5,11)%%''.
+Faire le test en choisissant ''%%p = 17%%'', ''%%D = Point(3,8)%%'', ''%%s = 12%%'' et ''%%M = Point(5,11)%%''.
+==== Nombre plutôt que point ====
+Quand on écrit la clé ou le message dans un fichier comme un certificat, on peut trouver gênant d'avoir à l'écrire sous forme d'une paire $(x;y)$.
+Il existe une astuce : comme on l'a expliqué, connaissant $x$, on peut calculer $y^2$ et en déduire $y$. Pour une valeur de $x$ donné, avec $p$ impair, il y a toujours deux $y$ possibles : $y_1$ et $y_2$ et on a toujours $y_1 + y_2 = p$ de sorte que $y_1$ et $y_2$ n'ont pas la même parité (l'un est pair et l'autre impair).
+Ainsi si on donne la valeur de $x$ et que l'on précise pair ou impair, on peut déduire de façon unique la valeur de $y$ correspondante.
+Ainsi, on peut résumer la paire $(x;y)$ en un seul nombre :
+  * $k = 2\cdot x$ pour le cas $x$ avec le $y$ pair,
+  * $k = 2\cdot x + 1$ pour le cas $x$ avec le $y$ impair
+Dans l'autre sens, on fait :
+  * $x = k \div 2$
+  * on cherche les solutions $y$ telles que $y^2 = x^3 + a\cdot x + b$
+  * si $k$ pair on retient le $y$ pair, si $k$ impair, on retient le $y$ impair.