Eric Rykwalder je softverski inženjer i jedan od lanca. com osnivača. Ovdje daje pregled matematičkih temelja bitcoin protokola.

Jedan od razloga zašto bitcoin može biti zbunjujuće za početnike jest da tehnologija iza nje redefinira koncept vlasništva.

Posjedovati nešto u tradicionalnom smislu, bilo da je riječ o kući ili zbroju novca, znači osobno skrbništvo nad stvarom ili izdavanje skrbništva povjerljivom entitetu, kao što je banka.

S bitcoinom slučaj je drugačiji. Bitcoinovi se ne pohranjuju ni centralno niti lokalno, pa niti jedan entitet nije njihov skrbnik. Oni postoje kao zapisi o distribuiranoj knjizi koja se naziva blok-lanac, čiji kopije dijele dobrovoljna mreža povezanih računala. Da bi "posjedovao" bitcoin jednostavno znači imati sposobnost prebaciti kontrolu nad njom na nekog drugog stvarajući zapis o prijenosu u blok-lancu. Što daje tu sposobnost? Pristup ECDSA osobnom i javnom paru ključa. Što to znači i kako to osigurava bitcoin?

Pogledajmo ispod nape.

ECDSA kratko je za algoritam digitalnog potpisa eliptičkih krivulja. To je proces koji koristi eliptičnu krivulju i konačno polje za "potpisivanje" podataka na takav način da treće strane mogu potvrditi autentičnost potpisa dok potpisnik zadržava ekskluzivnu sposobnost stvaranja potpisa. Uz bitcoin, podaci koji su potpisani su transakcija koja prenosi vlasništvo.

ECDSA ima zasebne postupke za potpisivanje i potvrdu. Svaki postupak je algoritam koji se sastoji od nekoliko aritmetičkih operacija. Algoritam za potpisivanje koristi privatni ključ, a postupak provjere koristi javni ključ. Ovaj ćemo primjer pokazati kasnije.

Ali prvo, tečaj sudara na eliptičnim krivuljama i konačnim poljima.

Eliptičke krivulje

Eliptička krivulja je algebarski prikazana kao jednadžba oblika:

y 2 = x 3 + ax + b

a = 0 i b = 7 (verzija koju koristi bitcoin) izgleda ovako: Elliptske krivulje imaju korisna svojstva. Na primjer, ne-okomita linija koja presijeca dvije ne-tangentne točke na krivulji uvijek presijeca treću točku na krivulji. Dalje je svojstvo da ne-vertikalna linija tangenta krivulje u jednoj točki presijeca točno drugu točku na krivulji.

Pomoću ovih svojstava možemo definirati dvije operacije: dodavanje točke i udvostručavanje točaka.

Dodatak točke

, P + Q = R, definira se kao refleksija kroz x-osi trećeg križanja R ' na liniji koja uključuje P i P . Najlakše je to razumjeti pomoću dijagrama: Slično tome,

točkovi udvostručenja , P + P = R definirani su pronalaženjem linije tangente do točke koja se udvostručuje, P i uzimanje refleksije kroz x-osi križanja R ' na krivulji kako bi dobili R .Evo primjera što bi to izgledalo: Zajedno, ove dvije operacije se koriste za

skalarnu množenje , R = a P, definiran dodavanjem točke P za sebe a puta. Na primjer: R = 7P

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

Postupak skalarne množenja normalno se pojednostavljuje kombinaciju točaka dodavanja i dubliranja točaka. Na primjer:

7P

R = P + 2 (3P)

R = P + 2 (P + 2P)

R = P +

je podijeljen u dva koraka stupnja udvostručenja i dva koraka dodatnih koraka.

Konačna polja Konačno polje, u kontekstu ECDSA, može se smatrati predefiniranim rasponom pozitivnih brojeva unutar kojih svaki proračun mora pasti. Bilo koji broj izvan tog raspona "okreće se" tako da se nalazi unutar raspona. Najjednostavniji način razmišljanja o tome je izračunavanje ostataka, kao što predstavlja operator modula (mod). Primjerice, 9/7 daje 1 s ostatkom od 2:

9 mod 7 = 2

Ovdje je naše konačno polje modulo 7, a sve mod operacije preko ovog polja daju rezultat koji se nalazi u rasponu od 0 do 6.

Stavljanje zajedno

ECDSA koristi eliptične krivulje u kontekstu konačnog polja, što uvelike mijenja njihov izgled, ali ne i njihove temeljne jednadžbe ili posebna svojstva. Ista jednadžba koja je gore opisana, u konačnom polju modulo 67, izgleda ovako:

Sada je skup točaka, u kojima su sve vrijednosti

x

i

y cijeli brojevi između 0 i 66. Imajte na umu da "krivulja" i dalje zadržava vodoravnu simetriju. Dodavanje točke i udvostručenje sada su malo drugačije vizualno. Linije izvučene na ovom grafu će se okrenuti horizontalnim i vertikalnim pravcima, baš kao u igri asteroida, održavajući isti pad. Dakle, dodavanje točaka (2, 22) i (6, 25) izgleda ovako: Treća točka presjeka je (47, 39) i točka refleksije je (47, 28). Povratak na ECDSA i bitcoin

Protokol kao što je bitcoin odabire skup parametara za eliptičku krivulju i njegov konačni prikaz polja koji je fiksan za sve korisnike protokola. Parametri uključuju

jednadžbu

,

premijera modulo polja, i osnovna točka koja pada na krivulju. poredak osnovne točke, koja nije samostalno odabrana, već je funkcija drugih parametara, može se smatrati grafički kao broj puta kada se ta točka može dodati do sebe sve dok njena nagiba ne bude beskonačna, ili okomita crta. Baza je odabrana tako da je red veliki premijer. Bitcoin koristi vrlo velike brojeve za svoju osnovnu točku, glavni modul i red. U stvari, sve praktične primjene ECDSA koriste ogromne vrijednosti. Sigurnost algoritma se oslanja na te vrijednosti koje su velike, i stoga nepraktične za silu ili obrnuti inženjer. U slučaju bitcoina: Jednadžba eliptičkih krivulja: y

2

= x

3 + 7 Prime modulo = 2 256 2

9 - 2 8 - 2 7 - 2 6 - 2 4 - 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F Baza bod = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8 Red = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 Tko je odabrao te brojeve i zašto?Mnogo istraživanja, i fer iznos intriga, okružuje izbor odgovarajućih parametara. Uostalom, veliki, naizgled slučajan broj mogao sakriti backdoor način rekonstrukcije privatnog ključa. Ukratko, ova realizacija prolazi nazivom secp256k1 i dio je obitelji rješenja eliptičnih krivulja nad konačnim poljima predloženim za upotrebu u kriptografiji. Osobni ključevi i javni ključevi Uz ove formalnosti izvan načina, mi smo sada u stanju razumjeti privatne i javne ključeve i kako su oni povezani. Ovdje je ukratko: u ECDSA, privatni ključ je nepredvidljivo odabrani broj između 1 i reda. Javni je ključ izveden iz privatnog ključa skalarnom množenjem osnovne točke nekoliko puta jednakoj vrijednosti privatnog ključa. Izraženo kao jednadžba:

javni ključ = privatni ključ * osnovna točka

Ovo pokazuje da je maksimalni mogući broj privatnih ključeva (i time bitcoin adresa) jednak redoslijedu.

U kontinuiranom polju mogli smo tlocrtati tangentnu liniju i odrediti javni ključ na grafikonu, ali postoje neke jednadžbe koje ostvaruju istu stvar u kontekstu konačnih polja.

p 999> p

p

p

p

x = c 2 - p x

- p x 999> x - r x ) - p y = c (p x

p kako bi pronašli r je sljedeći: c = (3p x 2

+ a) / 2p y r 2 - 2p x r y

= c (p x - r x ) - p

y U praksi, izračunavanje javnog ključa razvrstava se u nekoliko točaka udvostručavanja i dodavanja točaka s početnom točkom. Pokrenimo pozadinu primjera omotnice pomoću malih brojeva kako bismo dobili intuiciju o tome kako se ključevi konstruiraju i koriste za potpisivanje i potvrđivanje. Parametri koje ćemo koristiti su: Jednadžba: y 2

= x 3 +7 (što znači a = 0 i b = 7) Prime Modulo : 67 Baza: (2, 22) Narudžba: 79

Privatni ključ: 2 Prvo pronađimo javni ključ. Budući da smo odabrali najjednostavniji mogući privatni ključ s vrijednošću = 2, od osnovne će točke zahtijevati samo jednu radnju udvostručenja. Izračun izgleda ovako: c = (3 * 2 2 + 0) / (2 * 22) mod 67 c = (3 * 4) / (44) mod 67 c = 12/44 mod 67 Ovdje moramo pauzirati za malo štipanje ruku: kako izvodimo podjelu u kontekstu konačnog polja, gdje rezultat mora uvijek biti cijeli broj? Moramo se umnožiti inverznim, koji prostor ne dopušta da ovdje definiramo (ovdje vas i ovdje zanima). U ovom slučaju, morat ćete nam se pouzdati u trenutku:

44

-1

= 32 Pomicanje desno: c = 12 * 32 mod 67 x

= (49

2

- 2 * 2) mod 67

r

x

c = 384 mod 67 < > 999> x = 52 r

y

= (> Mod 67

r

y = (49 * (-50) - 22) mod 67 r

2450 - 22) mod 67

r

y

= -2472 mod 67

r y = 7 Naš javni ključ odgovara točki (52, 7 ).Sve to radi za privatni ključ od 2! Ova operacija - od privatnog do javnog ključa - računalno je jednostavna u usporedbi s pokušajem rada unazad za zaključak privatnog ključa iz javnog ključa, koji je, premda teoretski moguć, računalno neizvediva zbog velikih parametara koji se koriste u stvarnoj eliptičnoj kriptografiji ,

Dakle, od privatnog ključa do javnog ključa dizajn je jednosmjerno. Kao i kod privatnog ključa, javni ključ obično predstavlja heksadecimalni niz. No, pričekajte, kako ćemo dobiti od točke na avionu, opisano s dva broja, na jedan broj? U nekomprimiranom javnom ključu dva 256-bitna broja koji predstavljaju koordinate x

i y jednostavno su zaglavljeni u jednom dugom nizu. Također možemo iskoristiti simetriju eliptične krivulje kako bi se stvorio komprimirani javni ključ, zadržavajući samo vrijednost

x i napomenuvši koja je polovica krivulje točka. Iz ovih djelomičnih informacija možemo obnoviti obje koordinate. Potpisivanje podataka s privatnim ključem

Sada kada imamo privatni i javni ključ, potpišimo neke podatke! Podaci mogu biti bilo koje duljine. Uobičajeni prvi korak je iskriviti podatke za generiranje broja koji sadrži isti broj bita (256) kao redoslijed krivulje. Ovdje, radi jednostavnosti, preskočit ćemo korak napuštanja i potpisati neobrađene podatke z

. Nazvat ćemo G osnovnu točku,

n narudžbu, a d

privatni ključ. Recept za potpisivanje je sljedeći: Izaberite jedan cijeli broj k između 1 i n - 1. Izračunaj točku (x, y) = k * G pomoću skalarne množenja.

Pronađi r = x mod n. Ako je r = 0, vratite se na korak 1. Pronađi s = (z + r * d) / k mod n. Ako je s = 0, vratite se na 1. korak. Potpis je par (r, s)

Kao podsjetnik, u koraku 4, ako brojevi rezultiraju u djeliću (koji u stvarnom životu gotovo uvijek ), brojnik treba pomnožiti inverznim nazivnikom. U koraku 1 važno je da se

k

ne ponavlja u različitim potpisima i da treća strana ne može nagaći. To jest,

k trebaju biti slučajni ili generirani determinističkim sredstvima koja se čuvaju tajnim od trećih strana. Inače bi bilo moguće izvući privatni ključ iz koraka 4, budući da s , z , r

,

k

i n svi su poznati. Ovdje možete pročitati o prošlom iskorištavanju ove vrste. Odaberite naše podatke kao broj 17 i slijedite recept. Naše varijable: z = 17 (podaci) n = 79 (red) G = (2,22) (osnovna točka) d = 2 (privatni ključ) slučajni broj:

  1. k = rand (1, n - 1)
  2. k = rand (1,79-1)
  3. k = 3 (je li to stvarno slučajno? naš primjer jednostavniji!)
  4. Izračunaj točku. To se vrši na isti način kao i određivanje javnog ključa, no za kratkoću izostavimo aritmetičku vrijednost za dodavanje točke i dvostruko povećanje točke. (X, y) = (2, 22) + (52, 7)
  5. (x, y) = 3G

r : r = x mod n r = 62 mod 79 r (62, 63) x = 62 y = = 62 s : s = (z + r * d) / k mod n s = (17 + 62 * 2) / 3 mod 79 < = (17 + 124) / 3 mod 79 s = 141/3 mod 79 s = 47 mod 79

s = 47

Imajte na umu da smo gore mogli podijeliti za 3 od rezultata bio je cijeli broj.U stvarnim slučajevima koristili smo inverzno od

k

(kao prije, skrivali smo neke krhke detalje računanjem negdje drugdje):

s = (z + r * d) / k mod n

  1. s = 141/3 mod 79

s = 141 * 3

s = (17 + 124) / 3 mod 79

> 999> s = 7473 mod 79

  1. s = 47

Naš je potpis par (

r

,

s

) = (62, 47).

Kao i kod privatnih i javnih ključeva, ovaj potpis obično predstavlja heksadecimalni niz.

  1. Potvrđivanje potpisa s javnim ključem Sada imamo neke podatke i potpis za te podatke. Treća osoba koja ima javni ključ može primiti naše podatke i potpis i potvrditi da smo pošiljatelji. Pogledajmo kako to funkcionira. Budući da je

Q

javni ključ i druge varijable definirane kao prethodno, koraci za potvrdu potpisa su sljedeći:

Potvrdite da su r i s između 1 i n - 1.

  1. Izračunaj u = z * w mod n Izračunaj v = r * w mod n Izračunaj točku (x, y) = Izračunaj w = s

-1

uG + vQ

Potvrdite da r = x mod n. Potpis je nevažeći ako nije.

Zašto ove korake funkcioniraju? Preskačemo dokaz, ali ovdje možete pročitati pojedinosti. Pratimo recept i vidimo kako to funkcionira. Naše varijable, još jednom:

g = 17 (podaci)

(r, s) = (62, 47) (potpis)

n = 79 (red) Provjerite da su r

i

s

između 1 i

n

(osnovna točka) Q = (52, 7) - 1. Provjerite i provjerite. :

w = s

-1

r = 1 <= 62 <79

  1. s: 1 <= 47 < w = 47 -1 mod 79 w = 37

Izračunaj

u

:

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

  1. Izračunaj
  2. v : v = rw mod n
  3. v = 62 * 37 mod 79
  4. v = 999> x
  5. ,
  6. y

):

(x, y) = uG + vQ

Izračunaj točku razvrstavaju udvostručavanje točaka i dodavanje zasebno u

uG

i

vQ

  1. . uG = 2 (G + 18G)) uG = 2 (38G) uG = 2 (2 (19G) (G + 2 (G + 2 (GG2)) uG = 2 (G + 2 (G + 8G))) uG = 999> UG = 2 (2 (G))))) Sjednite na trenutak da biste shvatili da pomoću trikova grupiranja smanjujemo 75 uzastopnih dodatnih operacija na samo šest operacija udvostručavanje točke i dvije operacije dodavanja točke. Te će trikove biti korisne kada brojevi doista dođu do velikih.

Radimo svoj put iznutra izvana:

uG = 2 (2 (G + 2 (G + 2 (2 (2, 22))))))

  1. uG = 2 (G + 2 (25, 17)))) uG = 2 (G + 2 (G + 2 (52, 7) (2, (2, 22) + (21,42)))) uG = 2 (G + 2 (13,44) 999> uG = 2 (27, 40)

uG = (62, 4) UG = 2 (38, 26) za vQ

vQ = Q + 2Q vQ = Q + 2 (52, 7) vQ = (52, 7) + (25, (X, y) = (62, 4) + (11, 20)

vQ = )

  1. (x, y) = (62, 63) Jasno je da je korak 5 najveći dio posla.Za konačni korak, Potvrdite da je naš potpis važeći! R = x mod n

r = x mod n

62 = 62 mod 79

62 = 62

  1. Zaključak Za one od vas koji su vidjeli sve jednadžbe i preskočili na dno, što smo upravo naučili? Razvili smo neku intuiciju o dubokom matematičkom odnosu koji postoji između javnih i privatnih ključeva. Vidjeli smo kako čak iu najjednostavnijim primjerima matematika iza potpisa i verifikacije brzo postaje komplicirana, a mi možemo uvažiti ogromnu složenost koja mora biti uključena kada su uključeni parametri 256-bitni brojevi. Vidjeli smo kako pametna primjena najjednostavnijih matematičkih postupaka može stvoriti jednosmjerne "zamke" funkcije potrebne za očuvanje asimetrije informacija koja definira vlasništvo nad bitcoinom. I imamo novostvoreno povjerenje u robusnost sustava, pod uvjetom da pažljivo čuvamo znanje o našim privatnim ključevima.

Drugim riječima, to je razlog zašto se obično kaže da je bitcoin "potpomognut matematikom".

Ako ste se objesili kroz složene bitove, nadamo se da vam je to povjerenje da poduzmete sljedeći korak i isprobate matematiku sami (modularni aritmetički kalkulator čini konačnu matematiku puno lakši). Otkrili smo da prolazimo kroz korake potpisivanja i provjere podataka ručno pružamo dublje razumijevanje kriptografije koja omogućuje bitcoinov jedinstveni oblik vlasništva.

Ovaj je članak ponovo objavljen ovdje uz dopuštenje autora. Izvorno objavljen na Lancu. com. Autor daje posebnu zahvalnost Stevenu Phelpsu za pomoć u ovom članku.

Slika preko Shutterstock