Perkalian titik kurva eliptis

Perkalian skalar kurva eliptik adalah operasi pertambahan berulang sebuah titik di sepanjang kurva eliptik dengan dirinya sendiri. Perhitungan ini dipakai dalam kriptografi kurva eliptik (ECC) sebagai cara untuk membuat fungsi satu arah. Nama yang terkenal luas adalah perkalian titik kurva eliptik. Namun, nama itu bisa memberikan makna yang kurang tepat, yakni perkalian antara dua titik.

Dasar-dasar

Diberikan kurva E yang didefinisikan sebagai $y 2 = x 3 + ax + b$ dalam medan berhingga. Perkalian titik didefinisikan sebagai pertambahan berulang sebuah titik dalam kurva tersebut. Operasi ini ditulis sebagai $nP = P + P + ... + P$ dengan n bilangan bulat dan titik $P = (x, y)$ berada pada kurva E. Kurva jenis ini disebut juga kurva Weierstrass.

Keamanan ECC modern bergantung pada kesulitan untuk mencari n dari $Q = nP$ bila diketahui nilai P dan Q jika n besar. Masalah tersebut dikenal sebagai masalah logaritma diskret kurva eliptik. Masalah ini muncul karena penjumlahan dua titik (atau dengan dirinya sendiri) menghasilkan titik pada kurva yang tidak memiliki hubungan yang jelas dengan letak titik sebelumnya. Hasil nP bisa ada di mana saja.

Masalah tersebut bisa digambarkan seperti menambahkan sekian menit pada jarum jam n kali. Bila n kecil, letak jarum asal bisa dicari. Namun, setelah ribuan kali, bahkan jutaan kali, letak jarum asal bisa di mana saja. Untuk membaliknya, yaitu mencari nilai n, kita hanya bisa mencoba nilai n satu demi satu yang, kalau n sangat besar, akan sulit dilakukan.

Operasi titik

Operasi titik kurva eliptik: pertambahan (kasus I), penggandaan (kasus II dan IV), dan negasi (kasus III)

Ada tiga operasi yang sering dipakai untuk titik pada kurva eliptik, yaitu pertambahan titik, penggandaan titik, dan negasi titik.

Titik di takhingga

Titik di takhingga $({\mathcal {O}})$ adalah elemen identitas dalam aritmetika kurva eliptik. Penambahan titik dengannya menghasilkan titik itu sendiri, termasuk titik di takhingga sendiri.

{\begin{aligned}{\mathcal {O}}+{\mathcal {O}}&={\mathcal {O}}\\{\mathcal {O}}+P&=P\end{aligned}}

Titik di takhingga juga ditulis sebagai 0.

Negasi titik

Negasi sebuah titik adalah titik yang, bila ditambahkan kepada titik tersebut, menghasilkan titik di takhingga $({\mathcal {O}})$ .

P+(-P)={\mathcal {O}}

Untuk kurva eliptik, negasi titiknya adalah titik yang sama, tetapi nilai y-nya diganti jadi lawannya (negatifnya).

{\begin{aligned}(x,y)+(-(x,y))&={\mathcal {O}}\\(x,y)+(x,-y)&={\mathcal {O}}\\(x,-y)&=-(x,y)\end{aligned}}

Pertambahan titik

Pertambahan dua titik yang berbeda, P dan Q, didefinisikan sebagai negasi dari titik hasil perpotongan kurva E dengan garis lurus yang dibentuk oleh P dan Q. Hasilnya disimbolkan dengan R.

{\begin{aligned}P+Q&=R\\(x_{p},y_{p})+(x_{q},y_{q})&=(x_{r},y_{r})\end{aligned}}

Untuk kurva eliptik $y 2 = x 3 + ax + b$ , titik R dapat dihitung sebagai berikut:

{\begin{aligned}\lambda &={\frac {y_{q}-y_{p}}{x_{q}-x_{p}}}\\x_{r}&=\lambda ^{2}-x_{p}-x_{q}\\y_{r}&=\lambda (x_{p}-x_{r})-y_{p}\end{aligned}}

Persamaan di atas berlaku untuk dua titik yang berbeda dan tiada yang berupa titik di takhingga.

Penggandaan titik

Ketika titik P dan Q berhimpit, pertambahannya mirip di atas. Namun, karena tidak jelas gradien garis lurus yang melintasi titik tersebut, dipakailah limitnya, yaitu gradien garis singgung kurva E di P:

\lambda ={\frac {3x_{p}^{2}+a}{2y_{p}}}

dengan a adalah koefisien x seperti persamaan di atas.

Perkalian titik

Lihat pula

Daftar pustaka

Hankerson, Darrel; Vanstone, Scott; Menezes, Alfred (2004). Guide to Elliptic Curve Cryptography. Springer Professional Computing. New York: Springer-Verlag. doi:10.1007/b9764891 (tidak aktif 1 September 2020). ISBN 0-3879-5273-X.
Stinson, Douglas Robert; Paterson, Maura B. (2019). Cryptography: Theory and Practice. Textbooks in mathematics. New York: CRC Press. ISBN 978-1-1381-9701-5.