Dodatek do krzywych eliptycznych

_{Zastrzeżenie: To nie oddaje sprawiedliwości w bogatym temacie krzywych eliptycznych. Jest bardzo uproszczone. Ponieważ krzywe eliptyczne zyskały ostatnio dużą uwagę mediów w kontekście szyfrowania, chciałem dać trochę wglądu, jak faktycznie działa „obliczanie” krzywej eliptycznej.}

Wprowadzenie

Krzywe eliptyczne to zbiory punktów (x,y)w płaszczyźnie formy y^2 = x^3+Ax+B. (Dodatkowo, 4A^3+27B^2 ≠ 0aby uniknąć nieprzyjemnych osobliwości.) Możesz rozważyć te krzywe w dowolnym polu. Jeśli użyjesz pola liczb rzeczywistych, krzywe mogą być wizualizowane i wyglądają tak:

_Źródło

Cechą szczególną tych krzywych jest to, że mają one wbudowaną operację arytmetyczną, która jest analogiem dodawania. Możesz dodawać i odejmować punkty, a ta operacja jest zarówno asocjacyjna, jak i przemienna (grupa abelowa).

Jak działa dodawanie?

Uwaga: dodawanie punktów na krzywych eliptycznych nie jest intuicyjne. Ten rodzaj dodatku jest zdefiniowany tak, jak jest, ponieważ ma pewne miłe właściwości. To dziwne, ale działa.

Ponieważ krzywe eliptyczne tworzą grupę, istnieje addytywna tożsamość, która jest równoważna 0. Oznacza to, że dodanie 0do dowolnego punktu nie zmieni wyniku. Ta addytywna tożsamość jest „punktem” w nieskończoności. Wszystkie linie na płaszczyźnie zawierają ten punkt w nieskończoności, więc dodanie go nie ma znaczenia.

Powiedzmy, że każda linia przecina krzywą w trzech punktach, które mogą być 0, i że suma tych trzech punktów wynosi 0. Mając to na uwadze, spójrz na ten obraz.

_Źródło

Naturalne pytanie brzmi: co to jest P+Q? Cóż, jeśli P+Q+R = 0, to P+Q = -R(alternatywnie napisane jako R'). Gdzie jest -R? Jest gdzie R + (-R) = 0, co jest po drugiej stronie od osi x Rtak, że linia przez nich jest pionowa, przecinających się tylko R, -Ri 0. Możesz to zobaczyć w pierwszej części tego obrazu:

_Źródło

Inną rzeczą, którą można zobaczyć na tych obrazach, jest to, że suma samego punktu oznacza, że ​​linia jest styczna do krzywej.

Jak znaleźć przecięcia linii i krzywych eliptycznych

W przypadku dwóch różnych punktów

Zasadniczo istnieje dokładnie jedna linia przechodząca przez dwa punkty P=(x0,y0), Q=(x1,y1). Zakładając, że nie jest on pionowy, a dwa punkty są różne, możemy to zapisać jako y = m*x+q. Kiedy chcemy znaleźć punkty przecięcia z krzywą eliptyczną, możemy po prostu napisać

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

który jest wielomianem trzeciego stopnia. Zasadniczo nie są one tak łatwe do rozwiązania, ale znamy już dwa zera tego wielomianu: Dwie xwspółrzędne x0, x1dwóch punktów, które chcemy dodać!

W ten sposób możemy się czynnikiem czynników liniowych (x-x0)i (x-x1)i pozostają z trzecim współczynnikiem liniowym, którego korzeniem jest x-coordinate punktu R. ( -Rrównież z powodu symetrii. Zauważ, że jeśli R = (x2,y2)tak -R = (x2,-y2). Pochodzi -z grupy; nie jest to minus wektorowy).

W przypadku dodania jednego punktu Pdo siebie

W tym przypadku musimy obliczyć styczną krzywej na P=(x0,y0). Możemy pisać bezpośrednio mi qpod względem A,B,x0,y0:

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

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

Otrzymujemy równanie y = m*x+qi możemy postępować tak samo, jak w powyższym akapicie.

Kompletne drzewo spraw

Oto pełna lista sposobów obsługi wszystkich tych przypadków:

Niech P,Qbędą punkty na krzywej eliptycznej (w tym punkt „nieskończoności” 0)

• Jeśli P = 0lub Q = 0, to P+Q = Qlub P+Q = P, odpowiednio
• Inny P ≠ 0i Q ≠ 0tak niech P = (x0,y0)i Q = (x1,y1):
  • Jeśli P = -Q(to znaczy x0 = x1i y0 = -y1) toP+Q = 0
  • Jeszcze P ≠ -Q
    • Jeśli x0 = x1tak, mamy P=Qi obliczamy styczną (patrz sekcja powyżej), aby uzyskać R. NastępnieP+Q = P+P = 2P = -R
    • W przeciwnym razie możemy skonstruować linię formularza y = m*x+yprzez te dwa punkty (patrz sekcja powyżej) w celu obliczenia R. NastępnieP+Q=-R

Pola skończone

W przypadku tego wyzwania weźmiemy pod uwagę tylko te pola wielkości, w pktórych pjest liczba pierwsza (i ze względu na pewne szczegóły p ≠ 2, p ≠ 3). Ma to tę zaletę, że można po prostu obliczyć mod p. Arytmetyka w innych dziedzinach jest znacznie bardziej skomplikowana.

To w tym przykładzie ustaliliśmy p = 5i wszystkie równości tutaj są przystające 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

Wyzwanie

Biorąc pod uwagę parametry A,Bkrzywej eliptycznej, charakterystykę pola głównego pi dwa punkty P,Qna krzywej eliptycznej, zwracają swoją sumę.

• Możesz założyć, że parametry A,Bfaktycznie opisują krzywą eliptyczną, co oznacza, że 4A^3+27B^2 ≠ 0.
• Możesz założyć, że w P,Qrzeczywistości są to punkty na krzywej eliptycznej lub 0punkt - point.
• Możesz założyć, że p ≠ 2,3jest to liczba pierwsza.

Przypadki testowe

Zrobiłem (niezbyt elegancką) implementację w MATLAB / Octave, którą możesz wykorzystać do własnych przypadków testowych: ideone.com Mam nadzieję, że jest poprawna. Przynajmniej odtworzyło kilka obliczeń, które wykonałem ręcznie.

Zwróć uwagę na trywialne przypadki testowe, które działają dla wszystkich krzywych, które rozważamy tutaj:

Dodawanie zera: P+0 = P Dodawanie odwrotności:(x,y) + (x,-y) = 0

Dla p = 7, A = 0, B = 5dwóch punktów P = (3,2)i Q = (6,2)są na krzywej eliptycznej. Następnie następujące blokady:

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

Wszystkie punkty na krzywej eliptycznej są (3,2),(5,2),(6,2),(3,5),(5,5),(6,5),0

Bo p = 13, A = 3, B = 8dostaniemy

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

Za p = 17, A = 2, B = 2i P=(5,1) dostajemy

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)

Jeśli jesteś naprawdę ambitny, weź

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

i spróbuj znaleźć liczbę naturalną ntaką, że n*(x0,y0) = (x1,y1). Więcej informacji tutaj.

dodatek

Przede wszystkim wielkie DZIĘKUJEMY @ @ El'endiaStarman za przejrzenie i edycję mojego szkicu!

Dlaczego krzywe eliptyczne?

Cóż, może się to wydawać jakimś arbitralnym równaniem, ale tak nie jest, jest dość ogólne: Ogólnie rzecz biorąc, rozważamy te geometryczne „kształty” w płaszczyźnie rzutowej (stąd pochodzi „nieskończoność”. Tam uważamy wszystkie za jednorodne wielomiany trzeciego stopnia (te o niższym lub wyższym stopniu byłyby zbyt trudne lub po prostu trywialne do zbadania). Po zastosowaniu pewnych ograniczeń w celu uzyskania pożądanych dobrych właściwości i po dehomogenizacji tych wielomianów (rzutowanie na jedną z trzech płaszczyzn afinicznych ) otrzymujemy równania takie jaky^2+a*x*y+b*y = x^3+c*x^2+d*x+eJest to krzywa eliptyczna w długiej formie Weierstrass. Są to zasadniczo te same krzywe, które rozważaliśmy, ale tylko nieco wypaczone. Za pomocą liniowej transformacji współrzędnych można łatwo wykonać z tego krótkie równanie Weierstrasa. przykład , który wciąż posiada wszystkie interesujące właściwości.

Dlaczego wykluczyliśmy p=2,3?

Ma to związek z faktem, że w przypadku krótkiej formy Weierstrass potrzebujemy ograniczenia 4A^3+27B^2 ≠ 0, aby uniknąć osobliwości (więcej na ten temat poniżej). Na polu charakterystycznym 2 mamy, 4 = 0a na polu charakterystycznym 3 mamy 27 = 0, co uniemożliwia uzyskanie krzywych w postaci krótkiej Weierstrass dla tego rodzaju pól.

Jakie są osobliwości?

Jeśli równanie się 4A^3+27B^2=0zachowuje, mamy osobliwości, takie jak: Jak widać w tych punktach, nie można znaleźć pochodnej, a zatem nie ma stycznej, która „zabija” operację. Możesz spojrzeć na równania y^2 = x^3luby^2 = x^3-3*x+2

Dlaczego w ogóle nazywane są krzywymi eliptycznymi ?

Powodem jest to, że równania tego kształtu wyskakują w całkach eliptycznych, np. Które otrzymujesz, gdy chcesz obliczyć np. Długość łuku elipsy. Krótki pokaz slajdów na temat pochodzenia nazwy.

Co mają wspólnego z kryptografią?

Istnieją sposoby na nP = P+P+...+Pbardzo wydajne obliczenia . Można to wykorzystać na przykład przy wymianie kluczy Diffie Hellman . Modułową arytmetykę można zastąpić dodatkiem do podgrup skrętnych, są to tylko punkty na krzywej, które mają skończony porządek. (Oznacza to, że mP = 0dla niektórych mjest to po prostu obliczenie mod m).

Pyth, 105 100 bajtów

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

Dane wejściowe są oczekiwane jako (p, A, P, Q), gdzie Pi Qsą dwa punkty formularza (x, y)lub, jeśli są one 0punktem specjalnym , tak jak 0. Możesz to wypróbować online tutaj . Dwa ostatnie przykłady pokazują, jak 0działa ten specjalny .

Aby zaoszczędzić kilka bajtów, używam tylko mod postatecznej odpowiedzi. Oznacza to, że robi x0^pto kilka razy bez modularnego potęgowania, więc może być bardzo powolny.

Działa według mniej więcej tej samej logiki, co funkcja 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)

Jest to w dużej mierze zależne od faktu, że modularna odwrotność multiplikatywna xjest równa x^(p-2) mod pif pjest liczbą pierwszą. W ten sposób jesteśmy w stanie obliczyć mnachylenie linii, znajdując modułową multiplikatywną odwrotność mianownika i mnożąc ją przez licznik. Bardzo przydatny. Funkcja Python powinna nieco bardziej efektywnie obliczać większe problemy ze względu na użycie pow.

Użyłem również skrótów pokazanych na stronie Wikipedii na ten temat . To dość interesujące, że używam go tylko Araz i Bwcale.

Również dla zabawy:

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)

multi_nPDziałanie oblicza n*Pdla danej liczby całkowitej ni punkt P. Wykorzystuje strategię rekurencyjną, dzieląc nna dwie części p2fi remaindertakie tamto p2f + remainder = ni tamto p2f = 2^k. Następnie ponownie wywołujemy funkcję na tych częściach, dodając wynik za pomocą add_ellip. Zastosowałem również podstawowe podejście do programowania dynamicznego, zapisując już obliczone wartości w dykcie d.

Następna funkcja teoretycznie rozwiązałaby pytanie premiowe przy użyciu tej samej strategii:

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

Niestety nie działa wystarczająco szybko, aby go obliczyć. Sądzę, że mogą istnieć o wiele bardziej wydajne sposoby, aby to zrobić, zwłaszcza jeśli nie musimy powtarzać każdej możliwej wartości n.

Python 3, 193 191 bajtów

Rozwiązanie oparte na odpowiedzi Pyth firmy Rhyzomatic i ich logice w języku Python. W szczególności. Podobało mi się jak znaleźli trzeci korzeń Monic sześcienny wielomianu x^3 + bx^2 + cx + dgdy masz dwa korzenie x_1i x_2zauważając, że b == x_1 + x_2 + x_3i odpowiednio odjęcie. Planuję dodać wyjaśnienie, pograć w golfa i być może przełożyć je na Ruby, jeśli Ruby okaże się krótsza.

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)