Ang elliptic curve digital signature algorithm (ECDSA) ay hango sa elliptic curve cryptography, na syempre galing sa elliptic curve mathematics. Subalit wala ito halos kinalaman sa ellipse. Ha? Maglatag muna tayo uli ng mga konsepto ng matematika.
Discrete Logarithm Problem
Nabanggit sa umpisa ng usapan sa public-key cryptography na base sa integer factorization problem ang mga gamit na iskema. May isa pang problema na pwedeng gawan ng mahirap na halimbawa, na syang sinasamantala sa kriptograpiya: Discrete logarithm problem (DLP).
Sa logarithm na ipinapakitang ganito: logPQ = k (logarithm of Q to the base P is equal to k), ang Q ay ang numero na resulta kapag ang P ay ini-multiply sa sarili nya ng k na beses. Q = PxPxP…xP (k na beses). Kaya ang logarithm ay kabaliktaran ng exponential equation: Pk = Q (P to the power of k is equal to Q). Naaalala mo pa ba ito?
Ang DLP ay ang paghahanap ng k, kapag ang alam na impormasyon ay ang Q at P. Mahirap itong gawin sa malalaking numero dahil trial-and-error ang paraan.
Ngayon, sa discrete logarithm, ang multiplication ay maaring ibang operasyon, gaya ng addition ng integers sa isang cyclic group. Kaya ang k, sa halip na exponent o power, ay magiging numero na kung ilang beses ginawa ang addition ng P sa sarili nito.
Q = P+P+P+…+P (k na beses)
Q = [k]P
Teka, mas madali ang addition sa multiplication, hindi ba? Sa nakagawiang arithmetic, tama ka dyan. Pero ang konsepto ay makahanap ng operasyon na mahirap gawin. Sa grupong pinili sa elliptic curve cryptography, ang tinatawag na ‘addition’ ay komplikado ang pamamaraan.
Cyclic Group
Ano nga ba ang cyclic group? Mainam na intindihin natin ang mga konsepto patungo rito.
Kapag sinabing group (G, *), tumutukoy ito sa isang set G na may operasyong * na sumusunod sa mga axioms na ito:
- Ang operasyon ng group ay associative: a * (b * c) = (a * b) * c sa lahat ng a,b,c ∈ G.
- May isang identity element, 1 ∈ G, kung saan a * 1 = 1 * a = a sa lahat ng a ∈ G.
- Sa bawat a ∈ G, mayroong a-1 ∈ G, tinatawag na inverse of a, kung saan a * a-1 = a-1 * a = 1.
At karagdagang katangian: ang G ay abelian o commutative, kapag:
- a * b = b * a sa lahat ng a, b ∈ G.
Ang inilarawang group ay multiplicative ang ginamit na operasayon. Maaring addition ang operasyon nito, (G, +), bale additive group. Sa lagay na yun, ang identity element ay 0, at ang inverse ng a ay -a.
Ang group ay finite kapag ang bilang ng elements sa G ay may hangganan. Ang bilang ng elements sa isang group, |G| ay tinatawag na order nito.
Naaalala mo ang integers modulo n ℤn na pinag-usapan sa bandang umpisa ng asymmetric cryptography? Ang operasyon nito na addition modulo n ay nakakabuo ng group. Ang identity element ay ang 0, at ang inverse ng a ay kung anong x na kapag dinagdag sa a ay magiging congruent sa 0 (modulo n): a + x ≡ 0 (mod n). Pero ang multiplication modulo n naman nito ay hindi group. Dahil hindi lahat ng element ay may multiplicative inverse (paalala: ax ≡ 1 (mod n)).
Pero, pero, ang multiplicative group na may notasyong ito: ℤ*n (na matatandaan eh, naglalaman ng mga elements na relatively prime/coprime sa n), ay group, dahil lahat ng elements nito ay may multiplicative inverse at naglalaman ng identity element na 1 (mod n). At gaya ng nabanggit na sa usapang Number Theory, ang ℤ*n ay may order na |ℤ*n| = ɸ(n) (Euler phi function).
Ngayon, ano na ang cyclic group? Ito ay kapag ang G ay may element ⍺ ∈ G, kung saan bawat b ∈ G may katumbas na integer i na magpapatotoo sa: b = ⍺i. Ang ⍺ ay tinatawag na generator ng G.
Gamitin uli nating halimbawa ang multiplicative group na ℤ*n. Ang ℤ*13 ay may order na 12. Isa sa mga generators nito ay ⍺ = 2. Nakuha ito dahil sa multiplicative group, malalamang may generator ito kapag may element syang ⍺ɸ(n) ≡ 1 (mod n). Sa halimbawa, 212 ≡ 1 (mod 13). At tunay ngang cyclic ang group na ℤ*13 dahil ang operasyong 2i mod 13 ay magreresulta sa b na napapaloob din sa group. Ito ang talaan:
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 2i mod 13 | 2 | 4 | 8 | 3 | 6 | 12 | 11 | 9 | 5 | 10 | 7 | 1 |
Mula 1-12 na i, nagkaroon ng unique na b, na isa sa mga elements ng ℤ*13. Para mas maimahe mo ang cyclic, ituring na kapag lumagpas ka na sa i = 12, mula 13-24, ang halaga ng 2i mod 13 ay uulit base sa pagkakasunud-sunod ng nasa talaan.
Ihalintulad natin ang operasyon sa Q = [k]P. Nabanggit sa taas na ang ℤn (walang asterisk) sa operasyong addition ay group, at sa +⍺ ay mapapakita mo na cyclic nga ang ℤn. Ang operasyon ay: b = [i]⍺ mod n. Na sa ℤ13 ay b = [i]2 mod 13. Ang [i] ay kung Ilang beses nag +2. (Maliban sa 0, lahat ng element sa ℤ13 ay generator, kaya pwede mo subukan sa iba.)
| [i] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| [i]2 mod 13 | 0 | 2 | 4 | 6 | 8 | 10 | 12 | 1 | 3 | 5 | 7 | 9 | 11 |
Kaya sa Q = [k]P? Ang P ay ang generator ng cyclic group kung saan pinagmulan ang ibang elemento. Ilang beses, yun ang susi. Mapa multiplication o addition, basta ang pagdetermina ng ilang beses ito ginawa ang importante. At gusto nating makahanap ng mga cyclic group na mahirap atakihin ng kalaban, dahil nga komplikado ang operasyon, lalo na kung pabaliktad. Napakadali ng halimbawang pinakita. Paano tayo makakagawa ng ‘addition’ na mahirap?
Pag-usapan natin sa susunod. Subalit mababasa mo na ito sa Kabanata 3.
Kitakits sa ika-10.
Salamat sa mga imaheng ito na pinagsama sa taas:
- Photo by Mikael Blomkvist from Pexels: https://www.pexels.com/photo/simple-workspace-at-home-6476588/
- https://www.slideshare.net/AnjaliPatel131/discrete-logarithm-problem