Bitcoin's Curve (secp256k1)

Public key generation, signature generation dan signature verification pada Bitcoin. 

Skenarionya adalah sebagai berikut: 

• Alice ingin menandatangani pesan dengan kunci pribadinya (privKey), dan Bob ingin memvalidasi tanda tangan menggunakan kunci publik Alice (publicKeyy). Alice harus bisa menghasilkan tanda tangan digital yang sah. Dan setiap orang termasuk Bob harus bisa memeriksa keabsahan tanda tangan yang dibuat Alice.

• Alice dan Bob menggunakan parameter domain yang sama. Algoritma yang digunakan adalah ECDSA (Elliptic Curve Digital Signature Algorithm) yang merupakan varian dari Digital Signature Algorithm yang diterapkan pada Elliptic Curve.

ECDSA bekerja pada hash pesan, bukan pada pesan itu sendiri. Pilihan fungsi hash terserah kita, tapi harus jelas bahwa fungsi hash kriptografi yang dipilih harus aman. Hash dari pesan harus dipotong sehingga panjang bit dari hash sama dengan panjang bit n (n adalah urutan subgroup dari order fungsi Elliptic Curve yang digunakan). Hash terpotong adalah bilangan bulat dan akan dinotasikan sebagai z.

Adapun algoritma yang dilakukan oleh Alice untuk menandatangani pesan adalah sebagai berikut:

• Public key dan signature generation:

1. Pilih sebuah bilangan integer random k (1,...,n-1)
2. Hitung titik P dimana P = k*G (G adalah titik Generator yang dipilih)
3. Hitung r = xP mod n  (xP adalah koordinat x dari titik P)
4. Jika r = 0 maka pilih k yang lain dan ulangi kembali
5. Hitung \(s =k^{-1}\left(z+ r*privKey\right)\bmod n\) dimana privKey  adalah Private Key Alice, \(k^{-1}\) adalah invers perkalian dari k mod n
6. Jika s = 0 maka pilih nilai k yang lain dan ulangi kembali.

Pasangan (r,s) adalah Signature-nya.

• Signature verification. Untuk memverifikasi tanda tangan digital Alice, kita memerlukan kunci publik Alice , hash dan tanda tangan digitalnya (signature) yaitu (r, s)

1. Hitung nilai \(u_{1}=s^{-1}z \bmod n\)
2. Hitung nilai \(u_{2}=s^{-1}r \bmod n\)
3. Hitung nilai titik P dengan cara  \(P = u_{1}G+u_{2}publicKey\)
4. Signature valid jika r = xP mod n

Pembuktian kebenaran algoritma tersebut sebagai berikut :

\(P = u_{1}G+u_{2}publicKey\) dan,

publicKey = privKey*G

sehingga:

\(P = u_{1}G+u_{2}publicKey\)

\(P = u_{1}G+u_{2}*privKey*G\)

\(P = (u_{1}+u_{2}*privKey)G\)

Dengan nilai \(u_{1}=s^{-1}z \bmod n\) dan \(u_{2}=s^{-1}r \bmod n\), kita dapatkan:

\(P = (u_{1}+u_{2}*privKey)G\)

\(P = (s^{-1}z+s^{-1}*r*privKey)G\)

\(P = s^{-1}(z+r*privKey)G\)

Dari nilai  \(s =k^{-1}\left(z+ r*privKey\right)\bmod n\) di atas, kalikan persamaan tersebut dengan k dan bagi dengan s sehingga didapat:
 \(k =s^{-1}\left(z+ r*privKey\right)\bmod n\) lalu substitusikan persamaan ini dengan persamaan P di atas sehingga didapatkan:
\(p = s^{-1}(z+r*privKey)G\)
\(P=kG\)

Berikut contoh programnya: 

Referensi :

1. ECDSA
2. What is Blockchain
3. How Bitcoin works in 5 minutes
4. Wiki Bitcoin Secp256k1
5. ECDSA Bitcoin