Bonjour à tous,
Je m’intéresse en ce moment au chiffrement sur les courbes elliptiques. La variante de Diffie-Hellman est probablement la plus simple et la plus répandu. Je m’y attèle.
Sauf que je coince au niveau de la multiplication de l’entier K et du point P :
- Définition de la courbe elliptique par A et B pour la fonction $y^2 = x^3 + ax + b$.
- A = 38
- B = 76
- $y^2 = x^3 + 38x + 76$
- Création d’un point P appartenant à la courbe.
- Px = 723
- Py = $\sqrt{723^3 + 38*723 + 76} = 19441.209$
- P(723, 19441.209)
- Alice et Bob choisissent une valeur K
- Ka = 45
- Kb = 61
- Alice et Bob s’échangent le produit de KP
Je n’ai pas trouvé de site traitant de cette curieuse méthode. Vu que P est définit par X et Y, je pensais simplement calculer $S(K.Px, K.Py)$, sauf que non ! Si un homme au milieu de l’échange connaît P, il peut aisément retrouver K. J’avais essayé $S(K.Px, Py')$ pour recalculer l’ordonnée du point, mais sans succès, Alice & Bob se retrouvaient avec deux valeurs différentes.
Comment dois-je m’y prendre ? 
Merci d’avance pour vos réponses.
Edit : Du coup sur Open Classroom j’ai posté un code Python fonctionnel.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | #!/usr/bin/python3 import random import math def addPointCurve (p, q, a, b, n): # Addition if p[0] == 0 and p[1] == 0: return q if q[0] == 0 and q[1] == 0: return p if p[0] == q[0] and (p[1] != q[1] or p[1] == 0): return [0,0] if p[0] == q[0]: l = (3 * p[0] * p[0] + a) * modInv(2 * p[1], n)[0] % n else: l = (q[1] - p[1]) * modInv(q[0] - p[0], n)[0] % n x = (l * l - p[0] - q[0]) % n y = (l * (p[0] - x) - p[1]) % n return [x, y] def multiPointCurve (p, f, a, b, n): # Produit r = [0,0] q = p while f > 0: if (f & 1) == 1: r = addPointCurve(r, q, a, b, n) f, q = f >> 1, addPointCurve(q, q, a, b, n) return r def modInv (a, b): x,y = [0, 1] if (a % b) != 0: x,y = modInv(b, (a % b)) x,y = [y, x-y*int(a/b)] return [x,y] def randomPrim (a,b): l, c = [2], 2 for i in range(1, round(b/2)): x, t = (i*2)+1, 1 for k in range(0, int(len(l)/2)): if not x % l[k]: t = 0 break if t: c = x if a > c else c l.append(x) l = l[l.index(c):] return l[random.randint(0,len(l)-1)] def curve (x, a, b, n): return int(math.sqrt( x ** 3 + a * x + b ) % n) # Definition de la courbe elliptique y**2 = x**3 + ax + b mod n a = random.randint(20,150) b = random.randint(20,150) n = randomPrim(500,1000) # n doit etre un nombre premier # Choix d'une base G, un point de la courbe rnd = random.randint(500,1000) g = [rnd, curve(rnd, a, b, n)] print("EC("+str(a)+","+str(b)+","+str(n)+"); G="+str(g)+";") # Alice et Bob choisissent chacun un nombre Ka = 51 Kb = 212 print("\n\tAlice: K="+str(Ka)) print("\tBob: K="+str(Kb)+"\n") # Echange de sessions (socket) Sa = multiPointCurve(g, Ka, a, b, n) Sb = multiPointCurve(g, Kb, a, b, n) print("Alice envoie "+str(Sa)+" a Bob.") print("Bob envoi "+str(Sb)+" a Alice.") # Calcul de la clef d'echange Ea = multiPointCurve(Sb, Ka, a, b, n) Eb = multiPointCurve(Sa, Kb, a, b, n) print("\n\tAlice: E="+str(Ea)) print("\tBob: E="+str(Eb)+"\n") # Alice envoie le message [20,5] a Bob msg_alice = [20, 5] print("\n\tAlice: MSG="+str(msg_alice)+"\n") encrypt_alice = [((msg_alice[0]*Ea[0]) % n), ((msg_alice[1]*Ea[1]) % n)] print("Alice envoie "+str(encrypt_alice)+" a Bob.") EbInv = [modInv(Eb[0],n)[0], modInv(Eb[1],n)[0]] decrypt_bob = [((encrypt_alice[0]*EbInv[0]) % n), ((encrypt_alice[1]*EbInv[1]) % n)] print("\n\tBob: MSG="+str(decrypt_bob)+"\n") input() |