Sa discrete logarithm problem na nirerepresenta ng: Q = [k]P, ano ba ang itsura ng P kapag gumamit tayo ng elliptic curve? Ito ay hindi lang numero, kundi point sa elliptic curve. Ang operasyon para makuha ang susunod na point ay hindi lang basta-bastang addition ng numero. Kailangan, matunton pa ang posisyon ng susunod na point sa curve. Sa kontexto ng Elliptic Curves, and multiplication ay addition, ang squaring ay doubling, at ang division ay subtraction.
Weierstrass Curve
Ang napiling elliptic curve sa paggawa ng pares ng private at public key sa mga wallet ng bitcoin ay isang Weierstrass (mula sa apelyido ng mathematician na si Karl Weierstraß). Upang maging tiyak, isang Short Weierstrass curve ang gamit.
Ang general form ng Weierstrass Curve ay:
E: y2 + a1xy + a3y = x3 + a2x2 + a4x + a6
Sa mga tamang kondisyon, ito ay magagawang Short Weierstrass form sa anyong:
E: y2 = x3 + c4x + c6
Hindi na natin idedetalye kung paano ito nagawa. Basta sa matematika, may konsepto ng isomorphism. Kung saan, may pagmamapa mula sa isang function, object, set, atbp. papunta sa isa pa. At isomorphic sila kapag napapanatili ang istraktura, o ang relasyon ng mga elements. Mula Weierstrass papuntang Short Weierstrass, ang hugis ng curve ay nananatili.
Gamitin natin sa halip ang a at b bilang notasyon ng coefficients:
E: y2 = x3 + ax + b
Ang ilustrasyong susunod ay isang halimbawa ng itsura ng elliptic curve na naka Short Weierstrass form.

Operasyon sa Elliptic Curve
Sa elliptic curve, E, may relasyon ang mga points kung saan: Kapag ang P, Q, R ay nasa linya, ang P + Q + R = ∞
Ang ∞ ay ang point at infinity, na syang identity o neutral element ng group. Isipin mo itong point na syang matutunton sa dulung-dulo pataas o pababa kapag dumeretso ka sa isang linyang x = c (anumang constant), parallel sa y-axis.
Tumatayo rin syang 0 sa operasyon ng addition kaya sya ang neutral/identity element. Espesyal na kaso ito na ginawa para sa Weierstrass curve.
Halimbawa, ang kabaliktaran ng P ay -P, kung saan ang negative ng point na (x,y), ay -(x,y) = (x,-y). Bale kabaliktaran sa kabila ng x-axis.

Kaya kapag kinonekta ang P sa -P, ang linya ay parallel sa y-axis at tumuturo sa kataas-taasan at kailalim-ilaliman. Ito ay addition na ang sum ay equal sa neutral element.
P + -P = ∞
Ang inversion ng point na may coordinates (x,y) ay kung saan -(x,y) = (x,-y)
Punta naman tayo sa addition ng 2 points kung saan P ≠ Q. Para makuha ang ikatlong point na R, ikonekta ang P at Q, at ang susunod na point na tatamaan sa curve ang R. Kunin ang kabaliktaran nito sa kabila ng x-axis para matunton ang -R. Kaya,
P + Q + R = -R + R = (P + Q) + -(P + Q) = ∞ ; na inilalarawan sa susunod na graph:

Kaya ang R ay -(P + Q) o ang kabalitaran ng sum ng 2 points. Kaya kailangan kunin ang -R na syang sagot sa operasyon.
Para makuha ito gamit ang komputasyon, babalikan natin ang kaalaman sa algebra. Ang slope ng linya ay may formula na:
ƛ = (yP – yQ)/(xP – xQ)
Makukuha natin ang susunod na coordinates kasi kapag hinabaan lang ang linya, ang slope ƛ gamit ang coordinates ng R ay dapat parehas lang. Ang xR ay:
xR = ƛ2 – xP – xQ
At sa halip na yR ang kunin natin, baliktarin na agad ang sign para –yR na ang halaga:
–yR = ƛ(xP – xR) – xP
Paano naman ang doubling o ang pag-add ng P sa sarili nito?

Ang P ay ituturing na tangent ng linyang iguguhit, at ang susunod na point na tatamaan sa E ay ang R. Kaya 2P + R = -R + R = 2P + -2P = ∞
Sa formulas, gagamitin natin ang slope ƛ ng isang tangent line. At ang pagpapanatili ng slope kapag hinabaan ang linya hanggang R.
ƛ = (3xP2 + a)/(2yP)
xR = (ƛ2 – 2xP)
–yR = ƛ(xP – xR) – xP
Naimahe mo na, na hindi basta-basta ang operasyon sa elliptic curve? Kaya kapag malaki na ang mga numerong pinag-uusapan, magastos ang komputasyon lalo na sa pagbabaliktad ng operasyon. Iyan naman ang kailangan para sa cyptography.
Balikan natin ito:
Q = [k]P
Nalalaman ang P na syang generator, alam din kung ano ang iskemang gamit, halimbawa nga ang ECDSA. Ang Q ang tumatayong public key, at ang [k] ang sikreto – private key. Dahil iyan ang mahirap kalkulahin pabalik.
Maging mas tiyak pa tayo sa kondisyon.
Fields at Finite Fields
Mabilisang depinisyon lang. Ang Field ay isang set F na may 2 operasyon, addition at multiplication: (F, +, *). May mga axiom kaparehas ng nabanggit sa Group ito: Associativity, Commutativity, Additive at Mutliplicative na Identity elements at Inverses. At karagdagang Distributivity ng multiplication sa addition: a * (b + c) = (a * b) + (a * c)
Ang Finite Field F ay isang field na may hangganan ang bilang ng elements. At gaya sa group, order ang tawag sa bilang ng elements ng finite field. Isa sa mahalagang katangian ng finite field, ay meron itong pm elements. Ang p ay isang prime at ang m ≥ 1.
Nakita natin makailang beses na ang espesyal na papel ng prime numbers sa cryptography.
Sa epektibong gamit ng elliptic curve cryptography, pipili lang tayo ng subset ng curve na limitado ng finite field. Ang group G na pipiliin ay subset ng elliptic curve E na nasa finite field F, na may prime order p (Fp). At ang operasyon ay addition (+).
G ⊂ E(Fp, +)
At magagawa natin ang limitasyon sa finite field kapag ang elliptic curve equation ay nakapares sa modulo arithmetic ng isang prime number.
E: y2 ≡ x3 + ax + b (mod p)
Ngayon, tandaan na sa elliptic curve, gumagamit tayo ng point bilang generator. Kaya ang order (dami ng points) na matutunton ng generator ay hindi nangangahulugang parehas ng prime order ng finite field.
|E(Fp)| ≠ p
(May mga anomalous curves na pwede magparehas ito, pero iniiwasan ang mga ganun.)
Punta na tayo sa gamit sa Bitcoin.
secp256k1
Mula sa NIST, may mga nirekomendang elliptic curves na pwedeng gamitin sa ECDSA. Lahat sila ay naka Short Weierstrass form. Isa sa mga yun ay ang gamit sa bitcoin: secp256k1. Ang palayaw na ito ay hango sa:
Standards for Efficient Cryptography – sec
Parameters over Fp – p
256 bits na haba ng p – 256
Koblitz curve – k
Sequence number – 1
Pasensya na pero gagamit tayo ng notasyon mula sa NIST, na baka ikalito mo dahil iba ang representasyon sa mga naunang diskusyon.
May 6 na parameters na konsiderasyon sa secp256k1.
T = (p, a, b, G, n, h)
p = prime number na bilang ng elements sa Fp
a, b = coefficients ng short Weierstrass curve, kung saan a, b ∈ Fp
G = base point (xG, yG) sa elliptic curve E(Fp) – na syang generator ng subgroup
n = order ng G, o dami ng elements sa subgroup na generated by G (dami ng points sa curve na generated ng G)
h = cofactor kung saan h = #E(Fp)/n
Tala: (#E(Fp) ay parehas sa |E(Fp)|)
Ilagay din natin ang mga napiling halaga ng mga parameters para maimahe mo na mahirap itong maimahe dahil sa laki! Ang mga numero ay naka hexadecimal.
p | FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F = 2256 – 232 – 29 – 28 – 27 – 26 – 24 – 1 |
a | 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 |
b | 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000007 |
G | Compressed (x-coordinate lang ang nakalagay) 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 Uncompressed 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8 |
n | FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 |
h | 01 |
Ganito ang elliptic curve equation:
E: y2 ≡ x3 + 7 (mod (2256 – 232 – 29 – 28 – 27 – 26 – 24 – 1))
Sa haba ng dinaanan natin, ang konsepto ay babalik rin lang sa:
Q = [k]P
Ang [k] ang sikreto o private key, na syang katumbas ng dami ng point additions ng P. Ang P ay alam ng lahat (ito ang G sa kalalatag lang na deskripsyon ng secp256k1). At ang Q ang public key. Ganun lang din, pero malakihang halaga ang usapan.
Ayan susunod na ang Elliptic Curve Digital Signature Algorithm na gamit sa Bitcoin transactions. Pero maaari mo nang tapusin ang paksa sa Kabanata 3! Kung hindi naman, kitakits sa ika-21.