Différences

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

--- nsi:tds:cryptographie:ecc [2023/04/11 14:52] – goupillwiki
+++ nsi:tds:cryptographie:ecc [2023/05/08 16:53] (Version actuelle) – [Nombre plutôt que point] goupillwiki
@@ Ligne 107: / 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 176: / Ligne 176: @@
 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 290: / 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 296: / 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$.
-La clé public était $K_{PU} = (p, d, h)$.
+Bob choisit $p$, $d$ et $s$ avec  $p$ premier, $1 < d < p$ et $s > 1$ puis il calculait $h = d^s \mod p$.
-**Avec les courbes elliptiques :** 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$.
+  * $K_{PU} = (p, d, h)$
+  * $K_{PR} = (p, d, s)$
-La clé public est $K_{PU} = (a, b, p, D, H)$.
+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)$
-==== Chiffrement ====
+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$
-Avec ElGamal, Alice choisissait $z$ entier quelconque et pour transmettre l'entier $m$ elle calculait $r = m\cdot h^z \mod p$ et $t = d^z \mod p$.
+==== Version ECC ====
-Elle envoyait enfin $(r, t)$.
+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$.
-**Avec les courbes elliptiques :** le message d'Alice est le point $M$. Elle choisit $z$ entier quelconque et elle calcule les points $R = M + z\cdot H$ et $T = z\cdot D$.
+  * $K_{PU} = (a, b, p, D, H)$
+  * $K_{PR} = (a, b, p, D, s)$
+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 = z\cdot D$ donc
+$T = z\cdot D$ donc
 $$s\cdot T = s\cdot z \cdot D = z \cdot (s \cdot D) = z \cdot H$$
 $$R - s \cdot T = M + z \cdot H - z \cdot H = M$$
@@ Ligne 332: / 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 338: / 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.