Ajout sur les courbes elliptiques

_{Avertissement: cela ne rend pas justice au sujet riche des courbes elliptiques. C'est beaucoup simplifié. Comme les courbes elliptiques ont récemment attiré beaucoup d'attention des médias dans le contexte du chiffrement, je voulais donner un petit aperçu du fonctionnement réel du "calcul" sur une courbe elliptique.}

introduction

Les courbes elliptiques sont des ensembles de points (x,y)dans le plan de la forme y^2 = x^3+Ax+B. (De plus, 4A^3+27B^2 ≠ 0pour éviter les singularités désagréables.) Vous pouvez considérer ces courbes dans n'importe quel domaine. Si vous utilisez le champ des nombres réels, les courbes peuvent être visualisées et elles ressemblent à ceci:

_{La source}

La particularité de ces courbes est qu'elles ont une opération arithmétique intégrée qui est l'analogue de l'addition. Vous pouvez ajouter et soustraire des points, et cette opération est à la fois associative et commutative (un groupe abélien).

Comment fonctionne l'addition?

Remarque: l'ajout de points sur les courbes elliptiques n'est pas intuitif. Ce type d'ajout est défini tel qu'il est car il possède certaines propriétés intéressantes. C'est bizarre, mais ça marche.

Comme les courbes elliptiques forment un groupe, il existe une identité additive équivalente à 0. Autrement dit, l'ajout 0à n'importe quel point ne changera pas le résultat. Cette identité additive est le «point» à l'infini. Toutes les lignes de l'avion incluent ce point à l'infini, donc l'ajouter ne fait aucune différence.

Disons que toute ligne donnée coupe la courbe en trois points, ce qui peut être le cas 0, et que la somme de ces trois points est 0. Gardant cela à l'esprit, regardez cette image.

_{La source}

Maintenant, la question naturelle est, qu'est-ce que c'est P+Q? Eh bien, si P+Q+R = 0, alors P+Q = -R(également écrit comme R'). O is est -R? Il est là R + (-R) = 0, ce qui est de l'autre côté de l'axe x de Rsorte que la ligne à travers eux est vertical, coupant uniquement R, -Ret 0. Vous pouvez le voir dans la première partie de cette image:

_{La source}

Une autre chose que vous pouvez voir dans ces images est que la somme d'un point avec lui-même signifie que la ligne est tangente à la courbe.

Comment trouver des intersections de lignes et de courbes elliptiques

Dans le cas de deux points distincts

Généralement, il y a exactement une ligne passant par deux points P=(x0,y0), Q=(x1,y1). En supposant qu'il n'est pas vertical et que les deux points sont distincts, nous pouvons l'écrire comme y = m*x+q. Lorsque nous voulons trouver les points d'intersection avec la courbe elliptique, nous pouvons simplement écrire

0 = x^3+Ax+B-y^2 = x^3+Ax+B-(m*x+q)^2

qui est un polynôme du troisième degré. Ceux-ci ne sont généralement pas faciles à résoudre, mais nous connaissons déjà deux zéros de ce polynôme: les deux xcoordonnées x0, x1des deux points que nous voulons ajouter!

De cette façon, nous factorisons les facteurs linéaires (x-x0)et nous nous retrouvons (x-x1)avec un troisième facteur linéaire dont la racine est la xcoordonnée du point R. ( -Raussi à cause de la symétrie. Notez que si R = (x2,y2)alors -R = (x2,-y2). Le -est du groupe; ce n'est pas un moins vectoriel.)

Dans le cas de l'ajout d'un point Pà lui-même

Dans ce cas, nous devons calculer la tangente de la courbe à P=(x0,y0). Nous pouvons écrire directement met qen termes de A,B,x0,y0:

     3*x0^2 + A
m = ------------
        2*y0

     -x0^3 + A*x0 + 2*B
q = --------------------
          2*y0

Nous obtenons l'équation y = m*x+qet pouvons procéder de la même manière que dans le paragraphe ci-dessus.

Un arbre de cas complet

Voici une liste complète de la façon de gérer tous ces cas:

Soit des P,Qpoints sur la courbe elliptique (y compris le point "infini" 0)

• Si P = 0ou Q = 0, alors P+Q = Qou P+Q = P, respectivement
• Sinon P ≠ 0et Q ≠ 0, alors laissez P = (x0,y0)et Q = (x1,y1):
  • Si P = -Q(cela signifie x0 = x1et y0 = -y1) alorsP+Q = 0
  • Autre P ≠ -Q
    • Si x0 = x1alors nous avons P=Qet nous calculons la tangente (voir section ci-dessus) pour obtenir R. ensuiteP+Q = P+P = 2P = -R
    • Sinon: Nous pouvons construire une ligne du formulaire à y = m*x+ytravers ces deux points (voir la section ci-dessus) afin de calculer R. ensuiteP+Q=-R

Champs finis

Pour ce défi, nous ne considérerons que les champs de taille poù pest premier (et à cause de certains détails p ≠ 2, p ≠ 3). Cela a l'avantage que vous pouvez simplement calculer mod p. L'arithmétique dans d'autres domaines est beaucoup plus compliquée.

Dans cet exemple, nous définissons p = 5et toutes les égalités ici sont des congruences mod 5.

2+4 ≡ 6 ≡ 1
2-4 ≡ -2 ≡ 3
2*4 ≡ 8 ≡ 3
2/4 ≡ 2*4 ≡ 3 because 4*4 ≡ 16 ≡ 1, therefore 1/4 ≡ 4

Défi

Étant donné les paramètres A,Bd'une courbe elliptique, une caractéristique de champ premier pet deux points P,Qsur la courbe elliptique, renvoient leur somme.

• Vous pouvez supposer que les paramètres A,Bdécrivent réellement une courbe elliptique, cela signifie que 4A^3+27B^2 ≠ 0.
• Vous pouvez supposer qu'il P,Qs'agit en fait de points sur la courbe elliptique ou le 0point.
• Vous pouvez supposer que p ≠ 2,3c'est primordial.

Cas de test

J'ai fait une implémentation (pas très élégante) dans MATLAB / Octave, que vous pouvez utiliser pour vos propres cas de test: ideone.com J'espère que c'est correct. Il reproduit au moins quelques calculs que j'ai faits à la main.

Notez les cas de test triviaux qui fonctionnent pour toutes les courbes que nous considérons ici:

Ajout de zéro: P+0 = P Ajout de l'inverse:(x,y) + (x,-y) = 0

Pour p = 7, A = 0, B = 5les deux points P = (3,2)et Q = (6,2)sont sur la courbe elliptique. Ensuite, les prises suivantes:

2*Q = Q+Q = P
2*P = P+P = (5,2)
3*P = P+P+P = (5,2)+P = (6,5)
4*P = P+P+P+P = (5,2)+(5,2) = (6,5)+(5,2) = Q

Tous les poins de la courbe elliptique sont (3,2),(5,2),(6,2),(3,5),(5,5),(6,5),0

Car p = 13, A = 3, B = 8nous obtenons

(1,8)+(9,7) = (2,10)
(2,3)+(12,11) = (9,7)
2*(9,6) = (9,7)
3*(9,6) = 0

Pour p = 17, A = 2, B = 2et P=(5,1) nous obtenons

2*P = (6,3)
3*P = (10,6)
4*P = (3,1)
5*P = (9,16)
6*P = (16,13)
7*P = (0,6)
8*P = (13,7)
9*P = (7,6)
10*P = (7,11)

Si vous êtes vraiment ambitieux, prenez

p = 1550031797834347859248576414813139942411
A = 1009296542191532464076260367525816293976
x0 = 1317953763239595888465524145589872695690
y0 = 434829348619031278460656303481105428081
x1 = 1247392211317907151303247721489640699240
y1 = 207534858442090452193999571026315995117

et essayez de trouver un nombre naturel ntel que n*(x0,y0) = (x1,y1). Plus d'informations ici.

appendice

Tout d'abord un grand MERCI à @ El'endiaStarman pour avoir révisé et édité mon brouillon!

Pourquoi des courbes elliptiques?

Eh bien, cela peut apparaître comme une sorte d'équation arbitraire, mais ce n'est pas le cas, c'est assez général: en général, nous considérons ces «formes» géométriques dans le plan projectif (c'est de là que vient «l'infini». Là, nous considérons toutes homogènes polynômes de troisième degré (ceux de degré inférieur ou supérieur seraient trop difficiles ou simplement triviaux à examiner). ) on se retrouve avec des équations commey^2+a*x*y+b*y = x^3+c*x^2+d*x+eIl s'agit d'une courbe elliptique sous la forme longue de Weierstrass. Ce sont essentiellement les mêmes courbes que nous avons considérées, mais juste un peu asymétriques. Avec une transformation de coordonnées linéaire, vous pouvez facilement en faire une courte équation de Weierstras. exemple , qui détiennent toujours toutes les propriétés intéressantes.

Pourquoi avons-nous exclu p=2,3?

Cela a à voir avec le fait que pour la forme courte de Weierstrass, nous avons besoin de la restriction 4A^3+27B^2 ≠ 0afin d'éviter les singularités (plus de détails ci-dessous). Dans un champ de la caractéristique 2 que nous avons 4 = 0et dans un champ de la caractéristique 3 que nous avons 27 = 0, cela rend impossible d'avoir des courbes sous forme de weierstrass courtes pour ces types de champs.

Quelles sont les singularités?

Si l'équation 4A^3+27B^2=0est vraie, nous avons des singularités comme celles-ci: Comme vous le voyez à ces points, vous ne pouvez pas trouver de dérivée et donc pas de tangente, ce qui "tue" l'opération. Vous pourriez regarder les équations y^2 = x^3ouy^2 = x^3-3*x+2

Pourquoi sont-ils appelés des courbes elliptiques de toute façon?

La raison en est que les équations de cette forme apparaissent dans les intégrales elliptiques, par exemple, ce que vous obtenez lorsque vous voulez calculer par exemple la longueur d'arc d'une ellipse. Un petit diaporama sur l'origine du nom.

Qu'est-ce qu'ils ont à voir avec la cryptographie?

Il existe des moyens de calculer nP = P+P+...+Ptrès efficacement. Cela peut être utilisé par exemple dans l' échange de clés Diffie Hellman . L'arithmétique modulaire peut être remplacée par l'addition sur les sous-groupes de torsion, ce ne sont que les points de la courbe qui ont un ordre fini. (Cela signifie que mP = 0pour certains m, ce qui est essentiellement juste du calcul mod m).

Pyth, 105 100 octets

A,@Q3eQ?qGZH?qHZG?&=YqhHhGqeG%_eHhQZ_m%dhQ,-*J?Y*+*3^hG2@Q1^*2eG-hQ2*-eGeH^-hGhH-hQ2-hGK--^J2hGhHeGK

L'entrée est attendue comme (p, A, P, Q), où Pet Qsont les deux points du formulaire (x, y)ou, s'ils sont le 0point spécial , tout comme 0. Vous pouvez l'essayer en ligne ici . Les deux derniers exemples montrent comment fonctionne le spécial 0.

Afin d'économiser quelques octets, je n'utilise que mod psur la réponse finale. Cela signifie qu'il fait des choses comme x0^pplusieurs fois sans faire d'exponentiation modulaire, donc cela peut être très lent.

Il fonctionne en suivant à peu près la même logique que cette fonction Python:

def add_ellip(p, A, P, Q): # points are in format (x, y)
    z = 0 # representing special 0 point

    if (P == z):
        return Q
    if (Q == z):
        return P

    if P[0] == Q[0]:
        if (P == (Q[0], -Q[1] % p)):
            return z
        else:
            m = ((3*pow(P[0], 2, p) + A)*pow(2*P[1], p-2, p)) % p
    else:
        m = (P[1] - Q[1])*pow(P[0] - Q[0], p-2, p) % p

    x = (pow(m, 2, p) - P[0] - Q[0]) % p
    y = (m*(P[0] - x) - P[1]) % p
    return (x, y)

Cela dépend fortement du fait que l'inverse multiplicatif modulaire de xest égal à x^(p-2) mod pif pest premier. Ainsi, nous sommes capables de calculer mla pente de la droite, en trouvant l'inverse multiplicatif modulaire du dénominateur et en le multipliant par le numérateur. Assez pratique. La fonction Python devrait calculer les problèmes plus importants un peu plus efficacement en raison de l'utilisation de pow.

J'ai également utilisé les raccourcis affichés sur la page Wikipédia à ce sujet . C'est assez intéressant, je ne l'utilise Aqu'une seule fois, et Bpas du tout.

Aussi juste pour le plaisir:

def pow2floor(x):
    p = 1
    x >>= 1
    while (x > 0):
        x >>= 1
        p <<= 1
    return p

def multi_nP(p, A, n, P):
    d = {}

    def rec_helper(n, P):
        if (n == 0):
            return (0, 0)
        elif (n == 1):
            return P
        elif (n in d):
            return d[n]
        else:
            p2f = pow2floor(n)
            remainder = n - p2f

            lower_half = rec_helper(p2f//2, P)
            d[p2f//2] = lower_half
            nP = add_ellip(p, A, lower_half, lower_half)

            if (remainder):
                nP = add_ellip(p, A, nP, rec_helper(remainder, P))

            d[n] = nP
            return nP

    return rec_helper(n, P)

La multi_nPfonction calcule n*Ppour un entier net un point donnés P. Il utilise une stratégie récursive en se divisant nen deux parties p2fet de remaindertelle sorte que p2f + remainder = net que p2f = 2^k. Ensuite, nous appelons à nouveau la fonction sur ces parties, en ajoutant le résultat avec add_ellip. J'ai également utilisé une approche de programmation dynamique de base en enregistrant des valeurs déjà calculées dans le dict d.

La fonction suivante résoudrait théoriquement la question bonus en utilisant la même stratégie:

def find_nPQ(p, A, P, Q): # P is input point, Q is what we're looking for
    d = {}
    found_Q = False

    def rec_helper(n, P):
        if (n == 0):
            return (0, 0)
        elif (n == 1):
            return P
        elif (n in d):
            return d[n]
        else:
            p2f = pow2floor(n)
            remainder = n - p2f

            lower_half = rec_helper(p2f//2, P)
            d[p2f//2] = lower_half

            nP = add_ellip(p, A, lower_half, lower_half)

            if (remainder):
                nP = add_ellip(p, A, nP, rec_helper(remainder, P))

            d[n] = nP
            return nP


    for x in range(p):
        xP = rec_helper(x, P)
        if (xP == Q):
            return x

Malheureusement, il ne fonctionne nulle part assez rapidement pour le calculer. Je suppose qu'il pourrait y avoir des moyens beaucoup plus efficaces de le faire, surtout si nous n'avons pas à parcourir toutes les valeurs possibles pour n.

Python 3, 193 191 octets

Une solution basée sur la réponse Python de Rhyzomatic et leur logique Python. En particulier. J'ai aimé comment ils ont trouvé la troisième racine d'un polynôme cubique monique x^3 + bx^2 + cx + dlorsque vous avez deux racines x_1et x_2en notant cela b == x_1 + x_2 + x_3et en soustrayant en conséquence. Je prévois d'ajouter une explication, de jouer au golf, et peut-être de la transpiler en Ruby, si Ruby s'avère plus court.

def e(p,A,B,P,Q):
 if P==0:return Q
 if Q==0:return P
 f,g=P;j,k=Q
 if f==j:
  if g==-k%p:return 0
  m=(3*f*f+A)*pow(2*j,p-2)
 else:m=(g-k)*pow(f-j,p-2)
 x=m*m-f-j;y=m*(f-x)-g;return(x%p,y%p)

Ungolfing:

def elliptic_curve_addition(p, A, B, P, Q):
    if P == 0:
        return Q
    if Q == 0:
        return P
    f,q = P
    j,k = Q
    if f==j:
        if g == (-k) % p:
            return 0
        m = (3 * f**2 + A) * pow(2*j, p-2)
    else:
        m = (g-k) * pow(f-j, p-2)
    x = m**2 - f - j
    y = m * (f-x) - g
    return (x%p, y%p)