Matematika už bitino | LT.democraziakmzero.org

Matematika už bitino

Matematika už bitino

Ericas Rykwalder yra programinės įrangos inžinierius ir vienas iš Chain.com įkūrėjų. Čia jis suteikia matematinių pamatų Bitcoin protokolo apžvalga.

Viena iš priežasčių Bitcoin gali būti painu pradedantiesiems yra tai, kad už jį technologija iš naujo nuosavybės sampratą.

Turėti kažką tradicine prasme, ar tai būtų namų arba pinigų suma, reiškia, kad arba turintys asmeninę globą dalykas ar suteikti globą į patikimo asmens, kaip antai banko.

Su Bitcoin bylą yra skirtingos. Bitcoins patys nėra saugomi centralizuotai ar lokaliai, todėl niekas subjektas yra jų saugotojas. Jie egzistuoja kaip įrašai apie paskirstytos knygoje vadinamas blokas grandinę, kopijos, kurios dalijasi savanorių tinklą sujungtų kompiuterių. Į "savo" Bitcoin tiesiog reiškia turėti galimybę perduoti valdymą jį kam nors kitam, sukuriant iš bloko grandinės perdavimo rekordą. Kas suteikia šį gebėjimą? Prieiga prie ECDSAprivate ir viešojo rakto pora. Ką tai reiškia ir kaip daro, kad saugi Bitcoin?

Leiskite turėti išvaizdą pagal gaubtu.

ECDSAis trumpas elipsinės kreivės DSA. Tai procesas, kuris naudoja elipsinės curveand baigtinio lauko į "Prisijungti" duomenų tokiu būdu, kad tretieji asmenys gali patikrinti parašo autentiškumą, o signataras išlaiko išimtinę galimybę sukurti parašą. Su Bitcoin, duomenų, kad yra pasirašyta yra sandoris, perleidžia nuosavybės.

ECDSA turi atskiras procedūras pasirašymo ir tikrinimo. Kiekvienos procedūros yra algoritmas susideda iš kelių aritmetinių operacijų. Pasirašymo algoritmas pasinaudoja privataus rakto ir patvirtinimo procesas pasinaudoja viešuoju raktu. Mes jums parodysime Tokio pavyzdį vėliau.

Bet pirma, avarijos metu nuo elipsės kreivių ir baigtinių laukų.

Elipsinės kreivės

Elipsės formos kreivė yra atstovaujama algebrinį kaip formos lygtį:

Y2 = x3 + ax + b

A = 0and b = 7 (versija naudojamas Bitcoin), jis atrodo taip:

Elipsinės kreivės turi naudingų savybių. Pavyzdžiui, ne vertikali linija kerta dvi ne liestinė taškų kreivė visada susikerta trečią tašką kreivės. Dar nuosavybė yra tai, kad ne vertikali linija liestinė kreivės vienu metu bus susikerta tiksliai viena kitą tašką kreivės.

Mes galime naudoti šias savybes apibrėžti dvi operacijas: taškas to, ir taškas dvigubinti.

Punktas Be to, P + Q = R, yra apibrėžiamas kaip atspindys per x-ašies trečiojo kerta punkte R'on linija, kuri apima pand Q. Lengviausia suprasti, kad taip naudojant diagramą:

Be to, dvigubai taškas P + P = Ris apibrėžta rasti linijos liestine taške turi būti dvigubai, P, ir atsižvelgiant atspindys per x-ašies susikertančių taško R'on kreivės gauti R. Štai pavyzdys ką tai turėtų atrodyti:

Kartu, šie du operacijos yra naudojamas Skaliarinė dauginimo, R = P ', apibrėžtą pridedant tašką pati Pto atimes. Pavyzdžiui:

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

Skaliarinė dauginimo procesas yra paprastai supaprastinti naudojant to tašką ir "dvigubai operacijų derinys. Pavyzdžiui:

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

Čia 7Phas buvo suskirstyti į du taškiniai dvigubai žingsnių ir dviejų prijungimo taškas žingsnius.

Baigtinių laukų

Baigtinio lauko, į ECDSA kontekste, gali būti suvokiami kaip anksto asortimentą teigiamų skaičių, per kurį kiekvienas skaičiavimas turi nukristi. Bet koks skaičius už šio intervalo ribų "kimba" taip, kad patenka į diapazoną.

Paprasčiausias būdas galvoti apie tai apskaičiuojant likučius, nes atstovauja modulio (mod) operatorius. Pavyzdžiui, 9/7 suteikia 1 su 2 likusiam:

9 mod 7 = 2

Čia mūsų ribotas laukas yra modulį 7, ir visi mod operacijos per šioje srityje duoda rezultatą, patenkančia į intervalą nuo 0 iki 6.

Išleidimą kartu

ECDSA naudoja elipsės kreives į skaičiavimą baigtinio lauko, o tai labai keičia jų išvaizdą, bet ne jų pagrindines lygtis ar specialių savybių kontekste. Tas pats lygtis aukščiau nubrėžtos iš baigtinio lauko, Modulo 67, atrodo taip:

Tai dabar kiekis, kurioje visos panaudotos xand yvalues ​​yra sveikieji skaičiai nuo 0 iki 66. Atkreipkite dėmesį, kad "kreivė" vis dar išlaiko savo horizontalią simetrijos rinkinys.

Punkto papildymas ir padvigubinti dabar yra šiek tiek skiriasi vizualiai. Tempti šioje diagramoje eilutės bus vyniojami aplink horizontalia ir vertikalia kryptimis, kaip į asteroidų žaidimas, išlaikant tą patį nuolydį. Taigi pridedant taškų (2, 22) ir (6, 25) atrodo taip:

Trečiasis susikertančios taškas yra (47, 39) ir jos atspindys taškas yra (47, 28).

Atgal į ECDSA ir Bitcoin

Protokolas, pavyzdžiui, Bitcoin atrenka parametrų elipsinės kreivės ir jos baigtinio lauko atstovavimo, kad yra nustatytos visų protokolo rinkinį naudotojų. Parametrai apima equationused, pagrindinis moduloof srityje, ir bazę pointthat patenka ant kreivės. Orderof į atraminio taško atžvilgiu, kuris yra ne nepriklausomai, yra parinkti bet yra naudojamas kaip kitų parametrų funkcija, gali būti manoma, grafiniu, kiek kartų taškas gali būti dedama į savaime tol, kol jo nuolydis yra begalinė, arba vertikali linija numeriu. Bazinė taškas pasirenkamas toks, kad užsakymas yra didelis pirminis skaičius.

Bitcoin naudoja labai daug dėl jo atraminio taško atžvilgiu, premjero modulo ir tvarką. Tiesą sakant, visi praktiniai taikymai ECDSA naudoti milžiniškus vertybes. Algoritmo saugumas remiasi šios vertybės yra didelis, todėl nepraktiška brutalia jėga ar perdaryti.

Jei Bitcoin atveju:

Elipsinės kreivės lygtis: Y2 = x3 + 7

Pirmininkas modulį = 2256- 232- 29- 28- 27- 26- 24- 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

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

Užsakyti = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Kas pasirinko šiuos numerius, ir kodėl? Daug mokslinių tyrimų ir nemažai intrigos, supa atitinkamų parametrų pasirinkimą. Galų gale, didelis, iš pažiūros atsitiktinių skaičių gali paslėpti backdoor metodą rekonstruojant privatų raktą. Trumpai tariant, tai ypač realizavimas eina į secp256k1 vardu ir yra dalis iš elipsinės kreivės sprendimų nei siūlomų naudoti kriptografijos baigtinių laukų šeima.

Privačios raktai ir viešieji raktai

Su šių formalumų iš kelio, dabar mes esame tokioje padėtyje, kad suprasti privačius ir viešuosius raktus ir kaip jie yra susiję. Čia jis yra trumpai: Be ECDSA, privatus raktas yra nenuspėjamai pasirinktas skaičius tarp 1 ir tvarka. Viešasis raktas yra kilęs iš privataus rakto iki skaliarinės daugybos pagrindo nurodo keletą kartų, kiek yra privataus rakto numerį. Išreikšta lygtimi:

Viešojo rakto = privatus raktas * bazė taškas

Tai rodo, kad didžiausias galimas skaičius privačių raktų (ir tokiu būdu Bitcoin adresai) yra lygus tvarka.

Nepertraukiamu srityje galėtume sklypas liestinė linijos ir tiksliai viešąjį raktą dėl diagramoje, tačiau yra keletas equationsthat atlikti tą patį į baigtinių laukų kontekste. Punkto papildymas p + qto rasti RIS apibrėžta komponentas-protingas taip:

C = (QY - py) / (qx - px)
Ry = C (px - RX) įrangos ir - py

Ir taškas dvigubinimas PTO surasto R yra taip:

C = (3px2 + per) / 2py
Ry = C (px - RX) - py

Praktiškai skaičiavimo viešojo rakto yra suskirstytas į keletą taškas dvigubi ir pridėjus kablelio operacijų skaičių, pradedant nuo atraminio taško atžvilgiu.

Leiskite paleisti voko Pavyzdžiui atgal naudojant nedidelį skaičių, gauti intuicija apie tai, kaip raktai sukonstruoti ir naudojami pasirašymo ir tikrinimas. Parametrai mes naudojame, yra:

Lygtis: Y2 = x3 + 7 (kuris yra pasakyti, a = 0 ir b = 7)
Asmeninis klavišas: 2

Pirma, galime rasti viešojo rakto. Kadangi mes pasirinkote paprasčiausią galimą privataus rakto su value = 2, tai reikės tik vieną tašką padvigubinti operaciją iš atraminio taško atžvilgiu. Skaičiavimas atrodo taip:

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

Čia mes turime sustoti ir apgaulės-of-vertus tiek: kaip mes atliekame padalinį į skaičiavimą baigtinio lauko, kur rezultatas visada turi būti sveikasis skaičius kontekste? Mes turime padauginti iš atvirkštinių, kuris erdvė neleidžia mums apibrėžti čia (mes vadiname jums hereand hereif domina). Nagrinėjamu atveju, jūs turite pasitikėti mumis to momento, kai:

44-1 = 32

Perkraustymo teisę kartu:

C = 12 * 32 mod 67
c = 49

RX = (492- 2 * 2) mod 67
RX = 52

Ry = (49 * (2-52) - 22) mod 67
Ry = 7

Taigi mūsų viešas raktas atitinka tašką (52, 7). Visa tai darbas privataus rakto 2!

Ši operacija - vyksta nuo asmeninio prie visuomeninio raktu - tai skaičiavimais lengva palyginti bando dirbti atgal išvesti privatų raktą iš viešojo rakto, kuris nors teoriškai įmanoma, yra skaičiavimais neįvykdomi dėl didelių parametrų, naudojamų faktinio elipsinės kriptografija.

Todėl vyksta iš privataus rakto į viešojo rakto yra dizainas vieną pusę kelionė.

Kaip su privačiu raktu, viešasis raktas paprastai atstovauja šešioliktainiu eilutę. Bet palaukit, kaip mes gauti iš taško į plokštumą, aprašyto dviejų skaičių, į vieną numerį? Nesuspaustu viešojo rakto dvi 256 bitų numeriai atstovaujančios xand y koordinatės yra tik sulipę į vieną ilgą eilutę. Mes taip pat gali pasinaudoti iš elipsinės kreivės simetrijos gaminti suspaustas viešąjį raktą, išlaikant tik X reikšmė ir paminėti, kuris pusę kreivės taškas yra. Iš šio dalinio informacijos galime susigrąžinti abi koordinates.

Pasirašymo duomenis su privačiu raktu

Dabar, mes turime privatų ir viešojo rakto pora, tegul pasirašo tam tikrus duomenis!

Duomenys gali būti bet kokio ilgio. Įprasta Pirmasis žingsnis yra maišos duomenis generuoti numerį, kuriame tą patį skaičių bitai (256) Kadangi kreivės tvarka. Čia, paprastumo dėlei, mes praleisti maišos žingsnį ir tik pasirašyti pirminius duomenis z. Mes vadiname Gthe atraminio taško atžvilgiu, nEsamos užsakymą ir dthe privatų raktą. Už pasirašymo receptas yra toks:

  1. Pasirinkti keletą sveikasis skaičius tarp 1 ir k n - 1.
  2. Apskaičiuoti tašką (x, y) = k * G, naudojant skaliarinį dauginimąsi.
  3. Rasti r = x mod n. Jei r = 0, grįžti į 1 žingsnį.
  4. Rasti s = (Z + R * r) / k mod n. Jei s = 0, grįžti į 1 žingsnį.
  5. Parašas yra pora (R, S)

Primename, 4 žingsnyje, jei numeriai sukelti trupmena (kuri realiame gyvenime jie beveik visada bus), skaitiklis turi būti padauginta iš vardiklio atvirkštinė. 1 žingsnyje, svarbu, kad mazgas kartoti įvairiuose parašų ir kad ji nebus atspėjami trečiosios šalies. Tai yra, kshould būti arba atsitiktinis, arba generuoja deterministiniais priemonėmis, kurios yra laikoma paslaptyje iš trečiųjų šalių. Priešingu atveju tai būtų įmanoma išgauti raktą nuo 4 žingsnyje, nes S, Z, R, kand nAr visi žinomi. Galite paskaityti apie praeities išnaudoti šio tipo čia.

Leiskite pasiimti savo duomenis, kad būtų numeris 17, ir sekti receptą. Mūsų kintamieji:

Z = 17 (duomenų)
d = 2 (privatusis raktas)

  1. Pasirinkite atsitiktinių skaičių:

K = rand (1, n - 1)
k = 3 (?! tai tikrai atsitiktinai Gerai jums mus gavo, bet tai leis mūsų pavyzdys paprastesnis)

  1. Apskaičiuokite taško. Tai daroma taip pat, kaip nustatyti viešąjį raktą, bet glaustumo tegul praleisti už to taško ir taško dvigubai aritmetiką.

(x, y) = 3G
Y = 63

  1. Ieškoti R:

R = x mod n
R = 62

  1. Ieškoti S:

S = (Z + R * d) / K mod n
s = 47

Dėmesį, kad aukščiau mes galėjo padalinti 3 nes rezultatas buvo sveikas skaičius. Be realaus gyvenimo atvejais mes naudoti K atvirkštinis (kaip ir anksčiau, mes paslėpti kai Kalnai detales skaičiavimo kitur):

S = (Z + R * d) / K mod n
s = 47

  1. Mūsų parašas yra pora (R, S) = (62, 47).

Kaip ir su privačių ir viešųjų raktų, šis parašas yra paprastai atstovauja šešioliktainiu eilutę.

Tikrinant parašą su viešuoju raktu

Mes dabar turime tam tikrus duomenis ir dėl to duomenų parašą. Trečioji šalis, kuri turi savo viešąjį raktą galite gauti mūsų duomenis ir parašo, ir įsitikinti, kad mes esame siuntėjai. Pažiūrėkime, kaip tai veikia.

Su Qbeing viešąjį raktą ir kitus apibrėžtus kaip anksčiau kintamuosius, kaip patikrinti parašą žingsniai yra tokie:

  1. Patikrinti, ar r ir s yra tarp 1 ir n - 1.
  2. Apskaičiuoti W = S-1 mod n
  3. Apskaičiuoti u = Z * W mod n
  4. Apskaičiuoti v = R * W mod n
  5. Apskaičiuoti tašką (x, y) = ug + VQ
  6. Patikrinti, ar r = x mod n. Parašas yra negaliojantis, jei tai ne.

Kodėl šie veiksmai veikia? Mes praleidžiant įrodymus, tačiau jūs galite perskaityti informaciją čia. Leiskite sekti receptą ir pamatyti, kaip ji veikia. Mūsų kintamieji dar kartą:

Z = 17 (duomenų)
Q = (52, 7) (viešasis raktas)

  1. Patikrinkite, ar randas Sare tarp 1 ir n-1. Patikrinkite ir čekiu.

R: 1 <= 62 <79
S: 1 <= 47 <79

  1. Apskaičiuoti w:

W = S-1 mod n
w = 37

  1. Apskaičiuokite u:

U = ZW mod n
u = 76

  1. Apskaičiuokite V:

V = RW mod n
v = 3

  1. Apskaičiuoti tašką (x, y):

(X, y) = ug + VQ

Leiskite sugriauti taškų dvigubai ir įtraukimui uGand vQseparately.

Ug = 76G
ug = 2 (2 (g + 2 (g + 2 (2 (2G)))))

Sėdėti akimirkai suprasti, kad naudojant grupavimo triuką mes sumažinti 75 eilės pridėjimo operacijos į vos šešių operacijas dvigubai taškas ir dvi operacijas to taško. Šios gudrybės bus praversti kai skaičiai gauti tikrai didelis.

Darbas iš vidaus į išorę savo kelią:

Ug = 2 (2 (g + 2 (g + 2 (2 (2 (2, 22))))))
ug = (62, 4)

O dabar VQ:

VQ = 3Q
VQ = (11, 20)

Išleisti jas kartu:

(x, y) = ug + VQ
(x, y) = (62, 63)

Aiškiai 5 žingsnis yra didžioji darbo dalis. Dėl galutinio žingsnio,

  1. Patikrinti, ar r = x mod n

R = x mod n
62 = 62

Mūsų parašas galioja!

Išvada

Tiems iš jūsų, kurie matė visa lygtis ir praleista į dugną, kas yra mes tiesiog išmoko?

Mes sukūrėme tikrą intuiciją apie giliai matematinės santykius tarp viešojo ir privataus raktų. Mes matėme, kaip net paprasčiausių pavyzdžių Už parašų ir patikrinimo matematikos greitai bus sudėtinga, ir mes galime vertiname didžiulį sudėtingumą, kuris turi būti įtrauktas, kai parametrai susiję yra 256-bitų skaičiai. Mes matėme, kaip protingas taikymas paprasčiausių matematinių procedūrų gali sukurti vieno kelio "Trap Door" funkcijas, būtinas siekiant išsaugoti informacijos asimetriją, kuri apibrėžia nuosavybę Bitcoin. Ir mes turime naujai atrastą pasitikėjimą sistemos, su sąlyga, kad mes atidžiai apsaugoti mūsų privačių raktų žinių tvirtumo.

Kitaip tariant, tai yra, kodėl ji yra dažniausiai sakė, kad Bitcoin yra "paremta matematikos".

Jei pakabintas per sudėtingų bitai, mes tikimės, kad jis davė jums pasitikėjimo žengti kitą žingsnį ir išbandyti matematikos nuo jūsų pačių (modulinė aritmetinis skaičiuotuvas daro baigtinio lauko matematikos daug lengviau). Mes nustatėme, kad išgyvena pasirašymo veiksmus ir patikrinti duomenis vertus, suteikia gilesnį supratimą apie kriptografija, kuri leidžia Bitcoin unikalią formą nuosavybės.

Šis straipsnis buvo publikuojamas čia su leidimo iš autoriaus. Iš pradžių paskelbtas Chain.com. Autorė suteikia ypatingą padėką Steven Phelps pagalbos su šiame straipsnyje.

Bitcoin ProtocolCryptography

Susiję straipsniai


Post Bitcoin

Kovojant su bitkuinu karas, vienu metu sukčiaujama

Post Bitcoin

Bitcoin Core Roadmap pristatė parašo optimizavimo planą

Post Bitcoin

Federalinės agentūros atsakymai atskleidžia JAV vyriausybės požiūrį į Bitcoin

Post Bitcoin

Australijos senato komitetas siekia panaikinti Bitcoin mokesčių įstatymą

Post Bitcoin

Darni plėtra per bitukines

Post Bitcoin

Kaip Bitcoinas pakeičia viską

Post Bitcoin

Izraelio Bitukino konferencija atidėta dėl Gazos krizės

Post Bitcoin

$ 10K ekspozicija? Bitcoin Bulls nepavyko ginti kainos aukštį

Post Bitcoin

Bitcoin mazgo numeriai kris po šlamšto sandorio atakos

Post Bitcoin

Atsargiai buldogas? 6000 USD Play kaip Bitcoin Price Stages Sharp Recovery

Post Bitcoin

Palauk ir pažiūrėk Bitcoin kainos kyla netoli Make or Break lygio

Post Bitcoin

Gavinas Andresenas: Vyriausybėms bus sunku kontroliuoti Bitcoin