Matematyka kryjąca się za Bitcoin

Artykuł opisuje matematyczne podstawy BTC takie jak arytmetyka modularna, obliczenia w ciele, kryptografia krzywych eliptycznych i związane z tym pojęcia klucza prywatnego, klucza publicznego i cyfrowego podpisu. Jako jeden z nieliczych artykułów oddaje to czym tak naprawdę jest bitcoin i jaka matematyka leży u jego fundamentów.

Technologia Bitcoin definiuje nam na nowo pojęcie własności.  Właściciela  BTC charakteryzuje to, że posiada dostęp do transferu określonej liczby BTC, nie posiada ich natomiast fizycznie. Każdy transfer BTC jest zapisywany w tzw. łańcuchu bloków (blockchain). Posiadanie odpowiedniej pary kluczy ECDSA daje możliwość otrzymywania i wysyłania BTC. Na pytanie: co to tak naprawdę znaczy i na ile jest bezpieczne, postaram się odpowiedzieć poniżej.

ECDSA (Elliptic Curve Digital Signature Algorithm) to algorytm cyfrowego podpisu przy pomocy krzywych eliptycznych. Jest to proces, który wykorzystuje krzywe eliptyczne i ciało skończone do „podpisania” danych w taki sposób, że osoba otrzymująca te dane może zweryfikować autentyczność podpisu pod warunkiem że podpisujący się zachowuje wyłączność tworzenia tego podpisu. W technologii BTC danymi, które są w ten sposób podpisywane jest transakcja, która przenosi własność.

ECDSA posiada oddzielne procedury podpisywania i weryfikacji. Każda procedura jest algorytmem składającym się z kilku operacji arytmetycznych. Algorytm podpisu wykorzystuje klucz prywatny, a algorytm weryfikacji wykorzystuje klucz publiczny. Najpierw opisze krzywe eliptyczne i ciało skończone, a następnie przedstawie przykłady.

 Krzywe Eliptyczne

 Krzywe eliptyczne reprezentuje równanie algebraiczne:

y2 = x3 + ax + b

W przypadku technologii BTC a = 0 i b = 7, krzywa wygląda:

elliptic-curves

Krzywe eliptyczne mają użyteczne właściwości.  Prosta która nie jest styczną i przechodzi przez dwa punkty leżące na krzywej eliptycznej, przechodzi również przez trzeci punkt leżący na tej krzywej. Kolejną właściwością jest to, że nie pionowa linia styczna do krzywej eliptycznej w danym punkcie przechodzi także przez dokładnie jeden drugi punkt.

Te własności wykorzystano to zdefinowania dwóch operacji: dodania punktu i podwojenia punktu.

 Dodanie punktu

P + Q = R, jest zdefiniowane jako odbicie przez oś x trzeciego punktu przecinającego R’ na linii, która zawiera P i Q. Łatwiej to zrozumieć patrząc na poniższy rysunek:

point-addition

Podwojenie punktu

P + P = R, jest definiowane przez znalezienie lini stycznej do punktu, który ma być podwojony, P, i wykonanie odbicia przez oś x przecinającego punk R’ na krzywej eliptycznej, aby otrzymać punkt R. Zilustrowano to poniżej:

point-doubling

Razem, te dwie operacje są wykorzystywane w mnożeniu skalarnym, R = aP, definiowanym jako dodanie punktu P do samego siebie a razy. Na przykład:

R = 7P
R = P + (P + (P + (P + (P + (P + P)))))

Proces mnożenia skalarnego jest skrócany przez kombinację operacji dodania punktu i podwojenia punktu. Na przykład:

R = 7P
R = P + 6P
R = P + 2 (3P)
R = P + 2 (P + 2P)

Proces mnożenia skalarnego 7P został skrócony do dwóch operacji dodania punktu i dwóch operacji podwojenia punktu.

Ciało Skończone

Ciało skończone wkontekście ECDSA możemy traktować jako predefiniowany zakres liczb dodatnich w którym wynik każdej kalkulacji musi się zawierać. Każda liczba poza tym zakresem „jest w pętli” tak długo aż wpadnie w ten zakres.

Najprostszą drogą do zrozumienia tego jest wyznaczenie reszty z dzielenia (dzielenie modulo). Dla przykładu reszta z dzielenia 9 przez 7 to 2, co zapisujemy:

9 mod 7 = 2

Ciałem skończonym jest tutaj modulo 7 i wszystkie wyniki obliczeń nad tym ciałem zawierają się  ostatecznie w zbiorze liczb całkowitych z zakresu od 0 do 6 („wpadają do tego zbioru”).

Połączmy wszystko razem

Użycie krzywych eliptycznych w kontekście pola skończonego,  zmienia ich wygląd ale nie zmienia ich równania i specjalnych właściwości wymienionych w powyższej części tekstu. Równanie krzywych eliptycznych dla ciała skończonego modulo 67 na wykresie wygląda następująco:

MB

Każdy punkt otrzymano przez dzielenie modulo 67 wyniku równania krzywej eliptycznej. Jest to teraz zbiór punktów, gdzie zmienne x i y przyjmują wartość z zakresu od 0 do 66. Zauważ, że „krzywa” wciąż zachowuje swoją poziomą symetrię.

Dodanie punktu i jego podwojenie wygląda teraz nieco inaczej wizualnie. Dodanie punktu (2,22) i (6,25) wygląda tak:

putting-together-2

Trzecim interesującym punktem jest (47,39) i jego odbicie na (47,28).

Powróćmy do ECDSA i Bitcoina.

Protokół BTC wybiera parametry krzywej eliptycznej i jej skończonej reprezentacji pola. Te wartości są ustalane dla wszystkich użytkowników protokołu. W parametrach zawarte jest równanie krzywej, zakres ciała skończonego(prime modulo) i punkt bazowy, który mieści się na krzywej. Argument punktu bazowego nie jest wybierany przypadkowo, a zależy od innych parametrów. Jest on dużą liczbą pierwszą.

Protokół BTC używa bardzo dużych liczb jako punktu bazowego i bardzo dużych liczb pierwszych jako podstawy dzielenia modulo. Wszystkie praktyczne zastosowania ECDSA opierają się na bardzo dużych liczbach.

W przypadku BTC równanie krzywej eliptycznej wygląda następująco:

y2 = x3 + 7

Przykładowe wartości:

Prime modulo = 2256 – 232 – 29 – 28 – 27 – 26 – 24 – 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

Punkt bazowy = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Argument punku bazowego = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Klucze prywatne i publiczne

W skrócie: kluczem prywatnym jest losowo wybrana liczba z zakresu od 1 do wartości argumentu punktu bazowego.  Kluczem publicznym jest iloczyn klucza prywatnego i punktu bazowego:

klucz publiczny = (klucz prywarny)x(punkt bazowy)

Ukazuje to, że maksymalna liczba kluczy prywatnych jest równa argumentowi punktu bazowego.

W ciele skończonym można narysować linię styczną i wskazać w ten sposób klucz publiczny na wykresie. Są też pewne wzory dla ciała skończonego, dzięki którym można obliczyć klucz publiczny. Wzór na dodanie punktów p i q, żeby wyznaczyć r wygląda następująco:

c = (qy – py) / (qx – px)
rx = c2 – px – qx
ry = c (px – rx) – py

Wzór na podwojenie punktu p, żeby znaleźć punkt r:

c = (3px2 + a) / 2py
rx = c2 – 2px
ry = c (px – rx) – py

Zobaczmy jak to wszystko działa na przykładzie małych liczb:

  • Równanie:  y2 = x3 + 7
  • prime modulo: 67
  • Punkt bazowy (2,22)
  • argument punktu bazowego: 79
  • klucz prywatny 2

Najpierw poszukajmy klucza publicznego. Ponieważ wybraliśmy bardzo mały klucz prywatny, to będzie wymagało tylko jednej operacji podwojenia punktu bazowego. Obliczenia wyglądają tak:

c = (3 * 22 + 0) / (2 * 22) mod 67
c = (3 * 4) / (44) mod 67
c = 12 / 44 mod 67

Teraz żeby zrozumieć dalszą część warto zapoznać się z podstawowymi działaniami na ciele skończonym. Odwrotność 44 to 32:

44-1 = 32

c = 12 * 32 mod 67
c = 384 mod 67
c = 49

rx = (492 – 2 * 2) mod 67
rx = (2401 – 4) mod 67
rx = 2397 mod 67
rx = 52

ry = (49 * (2 – 52) – 22) mod 67
ry = (49 * (-50) – 22) mod 67
ry = (-2450 – 22) mod 67
ry = -2472 mod 67
ry = 7

Klucz publiczny odpowiada zatem punktowi (52,7). Tyle obliczeń dla klucza prywatnego 2, a co dopiero przy większych wartościach!

Operacja obliczenia klucza publicznego z prywatnego jest stosunkowo łatwa w porównaniu z obliczeniem klucza prywatnego z klucza publicznego. Z teoretycznego punkt widzenia jest to możliwe jednak w praktyce przy dużych wartościach niewykonalne. W związku z tym obliczenie klucza publicznego z prywatnego jest podróżą w jedną stronę.

Tak jak klucz prywatny, klucz publiczny jest reprezentowany przez szesnastkowy ciąg znaków. Więc pojawia się pytanie w jaki sposób dostać się do punktu na płaszczyźnie (opisany przez współrzędne x,y) jeśli jest on opisany jedną liczbą. W nieskompresowanym kluczu publicznym obie wartości 256 bitowe x i y są po prostu sklejone w jeden ciąg. Można również skorzystać z symetrii krzywej eliptycznej to obliczenia skompresowanego klucza publicznego otrzymując tylko wartość x. Mając tą informację można obliczyć y.

Podpisywanie danych kluczem prywatnym

Teraz gdy mamy parę kluczy prywatnych i publicznych możemy podpisywać dane. Zestaw danych może być dowolnej długości. Przeważnie pierwszym etapem jest haszowanie  danych żeby wygenerować 256 bitowy numer. W opracowaniu dla uproszczenia pomijamy krok haszowania danych i po prostu będziemy je podpisywać „na surowo”. Nazwijmy sobie G punktem bazowym, n argumentem punktu bazowego i d kluczem prywatnym. Przepis na podpisanie wygląda następująco:

  1. Wybierz liczbę całkowitą k z przedału od 1 do n-1.
  2. Oblicz punt (x,y) = k*G używając mnożenia skalarnego.
  3. Znajdź r = x mod n . Jeśli r = 0 to wróć do kroku pierwszego.
  4. Znajdź s = (z + r * d) / k mod n. Jeśli s = 0 to wróć do kroku pierwszego.
  5. Podpisem jest para (r,s)

W kroku pierwszym bardzo ważne jest, żeby k nie powtarzało się w podpisach i nie może być do odgadnięcia przez osoby trzecie. K powinno być generowane losowo lub przy pomocy algorytmów deterministycznych, które są trzymane w tajemnicy. W przeciwnym wypadku możliwe byłoby obliczenia klucza prywatnego z etapu czwartego, ponieważ s, Z, R, K i n znane. O hakowaniu z wykorzystaniem słabego k możesz przeczytać tutaj.

Niech nasze dane będą oznaczone liczbą 17. Nasze zmienne:

z = 17 (dane)
n = 79 (argument punktu bazowego)
G = (2, 22) (punkt bazowy)
d = 2 (klucz prywatny)

  1. Wybieramy losowe k:

k = rand(1, n – 1)
k = rand(1, 79 – 1)
k = 3  (Czy naprawdę jest wybrane losowo?  Masz nas, dla prostszego zilustrowania wybraliśmy 3.)

  1. Obliczamy punkt. Odbywa się to w taki sposób jak ustalenie klucza publicznego, ale dla uroszczenia pomijamy arytmetykę dodania punktu i podwojenia punktu.

(x, y) = 3G
(x, y) = G + 2G
(x, y) = (2, 22) + (52, 7)
(x, y) = (62, 63)
x = 62
y = 63

  1. Szukamy r:

r = x mod n
r = 62 mod 79
r = 62

  1. Szukamy s:

s = (z + r * d) / k mod n
s = (17 + 62 * 2) / 3 mod 79
s = (17 + 124) / 3 mod 79
s = 141 / 3 mod 79
s = 47 mod 79
s = 47

Zauważ że w powyższym przykładzie dzieliliśmy przez 3. Jednak w wielu praktycznych zastosowaniach zamiast dzielić przez jakąś liczbę, to mnożymy przez jej odwrotność.

s = (z + r * d) / k mod n
s = (17 + 62 * 2) / 3 mod 79
s = (17 + 124) / 3 mod 79
s = 141 / 3 mod 79
s = 141 * 3-1 mod 79
s = 141 * 53 mod 79
s = 7473 mod 79
s = 47

  1. Nasz podpis jest parą (r, s) = (62, 47).

Podobnie tak jak klucz prywatny i publiczny podpis ten jest zwykle reprezentowany przez ciąg szesnastkowy.

Weryfikacja podpisu kluczem publicznym

Mamy już podpisane dane. Osoba trzecia, która ma nasz klucz publiczny może nim sprawdzić podpisane dane, czy faktycznie to myśmy się pod nimi podpisali. Zobaczmy jak to działa. Q to jest nasz klucz publiczny, pozostałe wartości oznaczamy tak jak w powyższym przykładzie.

  1. Upewnij się, że r i s są w przedziale od 1 do n – 1.
  2. Oblicz w = s-1 mod n
  3. Oblicz u = z * w mod n
  4. Oblicz v = r * w mod n
  5. Oblicz punkt (x, y) = uG + vQ
  6. Sprawdź czy r = x mod n. Podpis jest nieprawidłowy jeśli nie są równe.

Dokładny dowód można znaleźć tutaj. Zobaczmy teraz jak to działa w praktyce na naszych zmiennych:

z = 17 (dane)
(r, s) = (62, 47) (podpis)
n = 79 (argument punktu bazowego)
G = (2, 22) (punkt bazowy)
Q = (52, 7) (klucz publiczny)

  1. Upewnij się, że r i s są w przedziale od 1 do n – 1.

r: 1 <= 62 < 79
s: 1 <= 47 < 79

  1. Oblicz w:

w = s-1 mod n
w = 47-1 mod 79
w = 37

  1. Oblicz u:

u = zw mod n
u = 17 * 37 mod 79
u = 629 mod 79
u = 76

  1. Oblicz v:

v = rw mod n
v = 62 * 37 mod 79
v = 2294 mod 79
v = 3

  1. Oblicz punkt (x, y) = uG + vQ

Zrobimy dodawanie punktu i podwojenie w uG i vQ oddzielnie

uG = 76G
uG = 2(38G)
uG = 2( 2(19G) )
uG = 2( 2(G + 18G) )
uG = 2( 2(G + 2(9G) ) )
uG = 2( 2(G + 2(G + 8G) ) )
uG = 2( 2(G + 2(G + 2(4G) ) ) )
uG = 2( 2(G + 2(G + 2( 2(2G) ) ) ) )

 Zauważ, że stosując sztuczkę grupowanie opisaną na początku artykułu redukujemy liczbę możliwych operacji dodawania z 75 na zaledwie 6 operacji podwojenia punktów i dwie operacje dodawania punktów. Sztuczki te bardzo się przydają gdy mamy do czynienia z naprawdę dużymi liczbami.

Po podstawieniu punktu:

uG = 2( 2(G + 2(G + 2( 2( 2(2, 22) ) ) ) ) )
uG = 2( 2(G + 2(G + 2( 2(52, 7) ) ) ) )
uG = 2( 2(G + 2(G + 2(25, 17)  ) ) )
uG = 2( 2(G + 2( (2, 22) + (21, 42) ) ) )
uG = 2( 2(G + 2(13, 44) ) )
uG = 2( 2( (2, 22) + (66, 26) ) )
uG = 2( 2(38, 26) )
uG = 2(27, 40)
uG = (62, 4)

A teraz obliczenia dla vQ:

vQ = 3Q
vQ = Q + 2Q
vQ = Q + 2(52, 7)
vQ = (52, 7) + (25, 17)
vQ = (11, 20)

Poskładajmy to razem:

(x, y) = uG + vQ
(x, y) = (62, 4) + (11, 20)
(x, y) = (62, 63)

Wyraźnie widać, że najwięcej pracy trzeba poświęcić na

  1. Sprawdzamy czy r = x mod n

r = x mod n
62 = 62 mod 79
62 = 62

Nasz podpis jest poprawny!

Podsumowanie

 Po przeczytaniu tego artykułu powinniśmy być zaznajomieni ze związkiem matematycznym jaki istnieje pomiędzy kluczem prywatnym a publicznym. Na prostych przykładach poznaliśmy jak się je wykorzystuje w technologii podpisu cyfrowego. Wszystko to poznaliśmy na prostych przykładach i wyrobiliśmy sobie intuicję jak to może działać przy „dużych” 256 bitowych liczbach. Dowiedzieliśmy się jak kryptografia klucza prywatnego na nowo pozwala nam definiować pojęcie własności. W dalszej nauce pomoże Tobie kalkulator do arytmetyki modularnej.


Krypto Polak

Może Ci się również spodoba

17 komentarzy

  1. kryptopolonia napisał(a):

    Jest to artykuł, który powstał na podstawie tego: http://www.coindesk.com/math-behind-bitcoin/ .
    Autor tłumaczył z angielskiego na język matematyki, a z języka matematyki na język polski. Zagadnienia w nim poruszane nie są łatwe i bardzo proszę o dodatkowe pytania a także uwagi tak abym mógł modyfikować dalej artykuł, żeby był jak najbardziej zrozumiały i przystępny.

    • MusX napisał(a):

      wrzucic kod artykulu na githuba tak aby kazdy z czasem mogl go ulepszac / aktualizowac ;)

    • MichalMat napisał(a):

      Dlaczego w przykładzie jest najpierw modulo 67, a później modulo 79?

      • kryptopolonia napisał(a):

        Tam gdzie jest mod 67 mamy do czynienia z generacją pary kluczy prywatnego i publicznego w oparciu o punkt bazowy, gdzie argumentem jest 79.
        Tam gdzie jest mod 79 mamy do czynienia z cyfrowym podpisem, gdzie punkt bazowy ma argument 79.

  2. kamil napisał(a):

    fajnie jakby był artykuł dalej, jak działają przelewy i potwierdzenia i kopanie btc itd

    • kryptopolonia napisał(a):

      Tak, wiem. Za kilka miesięcy pojawi się dalszy ciąg opisujący dalsze zagadnienia. Strasznie dużo czasu zajmuje napisanie takiego artykułu. Trzeba dokładnie wszystko sprawdzać w książkach z algebry, matematyki, kryptografii, robić samemu próbne obliczenia żeby sprawdzić poprawność wywodu itd.

      • Humbrol napisał(a):

        A na koniec i tak po przeczytaniu nikt nawet commenta nie pusci…
        Just kidding. Dobra robota ! Ja nie zawsze komentuje ale codziennie czytam i polecam znajomym.

  3. kaq napisał(a):

    Genialne i wytłumaczone w bardzo przystępny sposób!

  4. ssd napisał(a):

    Kompletnie nic z tego nie zrozumiałem :)

  5. okamisan napisał(a):

    pięknie i klarownie
    Dziękuje

  6. york23 napisał(a):

    coś tam zrozumiałem na początku a dalej to mur niezrozumienia ALE wielki szacun dla autora że przetłumaczył z angielskiego na „nasze” i starał się klarownie przekazać to zagadnienie. Teraz muszę znaleźć więcej czasu na powolną analizę artykułu . BRAVO tak trzymać

  7. kryptopolonia napisał(a):

    w = 47^-1 mod 79 można zapisać inaczej: (1/47) mod 79 = 37
    Zapraszam też do skorzystania z WolframAlpha: http://www.wolframalpha.com/widgets/view.jsp?id=570e7445d8bdb334c7128de82b81fc13

  8. mikki napisał(a):

    Eh, a dla mnie to i tak dalej czarna magia. Pozazdrościć tym, którzy to rozumieją.

  1. 29 września 2015

    […] Źródło: Matematyka kryjąca się za Bitcoin | Kryptopolonia […]

  2. 12 października 2015

    […] key pair – technologia BTC oparta jest na kryptografii klucza prywatnego i publicznego. Klucz prywatny daje nam prawo własności do określonej liczby BTC, klucz publiczny pozwala nam otrzymywać BTC. Wyjaśnienia w matematycznych podstawach BTC […]

  3. 31 października 2015

    […] artykule dotyczącym matematycznych podstawach bitcoin przybliżyliśmy na czym polega kryptografia krzywych eliptycznych na których oparty jest BTC. W […]

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *