Елиптична крива

Елиптичната крива е множество от точки, които удовлетворяват уравнение от вида y² = x³ + ax + b. Биткойн (bitcoin) използва една определена крива, secp256k1, при която a = 0 и b = 7, така че всяка нейна точка удовлетворява y² = x³ + 7. Можете да съберете две точки, което се нарича събиране, и да умножите точка по цяло число. Умножението е лесно да се изпълни и много трудно да се обърне. Именно това еднопосочно свойство прави подписите ECDSA и Schnorr възможни.

За да използвате биткойн, не ви е нужна тази математика. Програмна библиотека се грижи за нея вместо вас. Прочетете тази страница, ако искате да знаете какво правят библиотеките.

Как изглежда кривата?

Над реалните числа кривата е гладка линия. Има връх отляво, там където x³ + 7 е нула, и два клона, които са огледални спрямо оста x. За всяко x, при което x³ + 7 е положително, има две точки: една над оста и една под нея. Кривата е симетрична, така че точка и нейното огледално отражение имат еднаква координата x.

Биткойн не използва реални числа. Той използва цели числа по модул голямо просто число, както е обяснено по-долу, затова точките изглеждат като разпръснати точки, а не като линия.

Какви са параметрите на secp256k1?

Кривата на биткойн е определена от няколко числа, зададени в SEC 2 от Standards for Efficient Cryptography Group. Всеки нод и всеки портфейл използва едни и същи стойности.

a  = 0
b  = 7
p  = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
n  = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

• p е простото число, което определя размера на полето от числа. То е 2²⁵⁶ − 2³² − 977.
• n е редът на кривата: броят точки, до които се стига, ако събирате генераторната точка сама със себе си. Частните ключове са числа от 1 до n − 1.
• G е генераторната точка. Всеки публичен ключ е кратно на G. SEC 2 фиксира стойността ѝ, която има голямо просто число за ред и няма известна слабост.

Името е код. Той сочи стандартите SEC, просто поле с 256 бита, крива от типа на Коблиц и първата крива от този вид.

Защо кривата изглежда като диаграма с разпръснати точки?

Биткойн смята с цели числа по модул p. Числото се свежда до остатъка след деление на p. Така всяка стойност остава точна, което е важно в компютрите, където десетичните дроби губят точност.

Разгледайте малкото поле по модул 47. Ето точката (17, 19). Проверете: 19² = 361, а 361 mod 47 е 32. Също така 17³ + 7 = 4,920, а 4,920 mod 47 е също 32. Значи точката лежи на кривата. Полето има 47 точки с координати и още една, точката в безкрайността, общо 48. Точката в безкрайността е резултатът, когато съберете точка със собственото ѝ огледално отражение. Secp256k1 има далеч по-голямо поле. Редът ѝ n е около 1.16 × 10⁷⁷, което е от същия порядък като броя атоми във видимата Вселена (около 10⁸⁰).

Какво е модулна обратна стойност?

По модул просто число няма обикновено деление, затова формулите умножават по обратна стойност. Обратната стойност на числото a по модул m е числото b, при което a × b дава остатък 1 при деление на m.

Например 13 × 29 = 377, а 377 = 8 × 47 + 1. Значи 29 е обратната стойност на 13 по модул 47. Python я изчислява директно:

print(pow(13, -1, 47))  # 29

Тъй като p е просто число, всяко ненулево число има обратна стойност. Затова формулите по-долу винаги работят.

Как се събират две точки?

Събирането на две точки не е обикновено събиране. Това е геометрично правило. Прекарайте права през двете точки. Правата пресича кривата в трета точка. Отразете тази трета точка спрямо оста x и резултатът е сборът. Формулите за точките P = (x1, y1) и Q = (x2, y2) са:

s  = (y2 − y1) / (x2 − x1)    mod p
x3 = s² − x1 − x2             mod p
y3 = s·(x1 − x3) − y1         mod p
P + Q = (x3, y3)

Всяко деление използва модулната обратна стойност от предишния раздел. Анимацията по-долу показва стъпките с реални числа, които правят геометрията лесна за проследяване. Точките са P = (1, √8) и Q = (2, √15). Правата има наклон s ≈ 1.045. Тя пресича кривата в (−1.909, −0.210), а отразяването дава P + Q ≈ (−1.909, 0.210).

Как се удвоява точка?

Събирането на точка със себе си се нарича удвояване. Тогава правата става допирателна към кривата в тази точка. Допирателната пресича кривата още веднъж. Отразете третата точка и резултатът е 2P:

s  = (3·x1² + a) / (2·y1)     mod p
x3 = s² − 2·x1                mod p
y3 = s·(x1 − x3) − y1         mod p

Същият пример, P = (1, √8), дава наклон 3 / (2√8) ≈ 0.530. Резултатът 2P ≈ (−1.719, −1.387).

Удвояването е единственият случай, в който формулата за събиране не работи, защото двете точки съвпадат и правата не е определена. Сметнете го с допирателната.

Как се умножава точка по число?

Умножението е многократно събиране, но събирането на точка един милион пъти би било твърде бавно. Методът „удвой и прибави“ изисква по едно удвояване за всеки бит и по едно събиране за всеки бит 1. Запишете числото в двоичен вид и прочетете битовете след водещата единица, отляво надясно. За всеки бит удвоете. Ако битът е 1, прибавете и P.

Ето 21 × P. Числото 21 е 10101 в двоичен вид.

Бит	Стъпка	Кратно на P
Начало	P	1
0	удвояване	2
1	удвояване, после прибавяне на P	5
0	удвояване	10
1	удвояване, после прибавяне на P	21

Същият метод в код чете битовете отляво надясно, както таблицата. None означава точката в безкрайността, неутралният елемент при събиране.

def multiply(k, P):
    R = None                      # None е точката в безкрайността
    for bit in bin(k)[2:]:       # от водещата 1 до последния бит
        R = add(R, R)            # всеки бит: удвояване
        if bit == "1":
            R = add(R, P)        # бит 1: прибавяне на P
    return R

За 256-битово число това отнема около 256 удвоявания и около 128 събирания, тъй като около половината битове са 1. Търсенето с груба сила би отнело далеч повече време.

Защо умножението е трудно за обръщане?

При дадени P и произведението k·P намирането на k се нарича задача за дискретния логаритъм върху елиптична крива. За нея не е известен кратък път. Най-добрите общи атаки изискват около √n операции в групата, което за secp256k1 е около 2¹²⁸ стъпки. Затова публичният ключ може безопасно да се споделя, а частният ключ остава скрит, дори когато публичният ключ е известен.

Къде се появява кривата в биткойн?

Вашият частен ключ е числото d. Вашият публичен ключ е точката d·G. Схемите за подписи използват умножение и събиране върху същата крива. ECDSA подписва със случайна точка, а подписите Schnorr използват точка от същия вид, за да докажат, че притежателят на ключа е подписал съобщението.

Следващата страница, ECDSA, използва умножение на точка, за да създава и проверява подписи. За по-пълно въведение в кривата вижте ръководството на Andrea Corbellini (на английски).