ECDH - Multiplier un entier par un point de la courbe elliptique

Application des courbes elliptiques sur l'algorithme de Diffie-Hellman

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

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
#!/usr/bin/python3
# Yarflam - ECDH

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]

# Definition de la courbe elliptique y**2 = x**3 + ax + b mod n
a = 1
b = 1
n = 263 # n doit etre un nombre premier

# Choix d'une base G, un point de la courbe
g = [148, 27]

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 envoit "+str(Sa)+" a Bob.")
print("Bob envoit "+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 envoit 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 envoit "+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()

Édité par Coyote

Tant de choses, tant de vies, tant de possibilités.

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte