Elliptic Curve Cryptography

A. Definisi Elliptic curve Dan Algoritma Elliptic curve Digital Signature
1. Non-supersingular elliptic curve pada finite field GF (2n)
Elliptic curve adalah bidang kurva yang didefinisikan oleh persamaan berderajat 3, yaitu:
y2 + axy + by = x3 + cx2 + dx + e
dimana a,b,c,d,e Є Fp, normalnya F adalah bilangan prima, dibatasi dengan Fp dan E(Fp) untuk kurva elips. Kita gunakan Ep(a,b) yang menunjukkan grup kurva elips modulo p dan elemen tersebut adalah pasangan integer non negatif (x,y) dimana kurang dari p dan memenuhi kurva perkalian diatas dan eleman lainnya adalah infinity point O.
Persamaan dari kurva elips non-supersingular pada finite field GF (2n) adalah:
y2 + xy = x3 + ax + b
dimana a,b Є GF (2n), b≠o dan E(GF (2n)) adalah himpunan yang disusun dari infinity point O dan titik (x,y) Є GF (2n) x GF (2n) dimana terkandung persamaan diatas.
2. Algoritma Elliptic curve Digital Signature
Kita pilih rational point P pada E(GF(2n)) yang dinamakan sebagai base point, kemudian kita cari n dimana n adalah bilangan prima yang memenuhi rumus nP=0. menurut SHA-1, kita pilih one-way secure hash function h(x). untuk setiap user dari sistem, dia memiliki sebuah kunci privat a, menghitung kunci public Pa = aP. Anggap bahwa user A ingin menandatangani informasi m, skema algoritma elliptic curve digital signature dapat didekripsikan sebagai berikut :
a. User A memilih sebuah integer k secara random, dimana 1 < k < n, hitung kP = (x,y), r = x mod n, if r = 0, return to (1);
b. Hitung e = h(m); s = (ke+ra)P;
c. Ambil (r,s) sebagai digital signature dari informasi m yang ditandatangani oleh A.
Verifikasi dari digital signature tersebut yaitu sebagai berikut:
a. Hitung e = h(m);
b. Hitung x = e-1 (s-rPa) = (x1,y1);
c. If x = 0, periksa menolak tandatangan tersebut; else dia menghitung r1 = x1 mod n, if r1 = r, then periksa terima tandatangan tersebut.

B. Blind Digital Signature Berdasarkan Pada Elliptic curve
Asumsikan bahwa user A meminta pada user B untuk menandatangani informasi m, pertama, user A memilih sebuah rational point P pada elliptic curve sebagai basic point, hitung n, n adalah pangkat dari P, sebuah bilangan prima memenuhi nP = O. Kedua, kita pilih suatu one way secure hash function h(m,c) menurut SHA-1. Anggap bahwa kunci privat si B adalah x, kemudian kunci publik B adalah y = xP, skema blind signature dideskripsikan sebagai berikut:
1. Proses Signing
a. User B secara random memilih sebuah integer k, 1b. User A secara random memilih a,b dimana 1c. User B menghitung S=xQ’-R , mengirimkan S kepada user A kemudian (Q,S) merupakan blind signature untuk informasi m dari user B.
2. Proses verifikasi
a. User A menghitung S’ = bS-aP;
b. User A menghitung F=h(m,Qy-S’) ; if F=Q, A menyetujui tandatangan, else A menolaknya.
3. Pembuktian validitas dari skema
Qy - S’ = Qy - (bS-aP) = Qy +aP-b( xQ’-R )
= Qy + aP-b( xQb-1P ) + bR
= Qy + aP - Qy + bR
= aP + bR = R’
kemudian F = h(m,Qy-S’) = h(m,R’) = Q. maka kita dapat menyakinkan validitas atau keaslian dari skema tersebut.

C. Broadcast Multi Blind Digital Signature Berdasarkan Pada Elliptic curve
Asumsikan bahwa user A meminta sebanyak d user dalam sistem seperti u1,u2,u3,...,ud untuk menandatangani informasi m yang sama, dengan skema blind signature pada saat yang sama, pertama, masing-masing user ui (i=1,2,...,d) memilih xi sebagai kunci private milik masing-masing, hitung yi = xiP = (wi,vi) sebagai kunci publiknya, user A menghitung y = ∑ yi, multi blind signature dideskripsikan sebagai berikut:
1. Proses Signing
a. User ui (i=1,2,3,..,n) secara random memilih sebuah integer ki, 1b. User A menghitung R = ∑ Ri ;
c. User A secara random memilih dua buah integer a,b dimana 1< a,bd. User ui menghitung Si = xiQ’-Ri dan mengirimkan Si kepada user A, (Q, Si, Ti) merupakan blind signature information m dari user ui, dimana Ti adalah waktu dari user A menerima tanda tangan.
2. Proses Verifikasi
a. Untuk setiap tanda tangan dari user ui, pemeriksa dari tanda tangan A menghitung Ti=Ti-T, jika Ti melewati dari waktu yang ditetapkan (stated time) maka A menolak tanda tangan tersebut.
b. Else, user A menghitung S=∑ Si ; Si = bS-aP ;
c. User A menghitung F=h(m,Qy-S’,T), if F = Q, maka ia menerima tanda tangan, else ia menolaknya.
3. Pembuktian Validitas Dari Skema
Qy-S’ = Qy – (bS-aP) = Qy + aP - b∑Si
= Qy + aP – b (∑ xiQ’-∑Ri)
= Qy +aP – b ( ∑ xiQb-1P)+bR
= Qy +aP – Q ∑yi+bR = aP+bR=R’
kemudian F = h(m, Qy-S’, T) = h(m, R’, T)= Q meyakinkan validitas dari skema.

D. Sequence Multi Blind Digital Signature Scheme Berdasarkan Pada Elliptic curve
Asumsikan bahwa A meminta sebanyak d users dalam sistem, u1,u2,u3,...,ud untuk menandatangani informasi m dengan skema blind signature dalam rangkaian u1,u2,u3,...,ud. Pertama, masing-masing user di ui (i=1,2,3,...,d) memilih xi sebagai kunci private masing-masing, hitung yi-xiP = (wi,vi) sebagai kunci publik masing-masing. User A menghitung y = ∑ yi, mengirimkan batas waktu tanda tangan T kepada semua user dalam sistem. Dengan tujuan untuk mencegah tanda tangan dari rebroadcast, ia meminta setiap user menandatangani informasi pada waktu yang dijadwalkan Ti, multi blind digital signature scheme dideskripsikan sebagai berikut :

1. Proses Signing Dan Verifikasi
a. User ui(i=1,2,3,..,n) memilih sebuah integer ki secara random, dimana 1b. User A menghitung R = Ri ;
c. User A memilih dua buah integer a,b dimana 1d. Setelah user ui menerima informasi Q’, pertama di memvalidasinya, proses validasinya sebagai berikut:
1). Hitung Ti = Ti+T , if informasi Q’ tidak datang sebelum waktu T, ia mengirimkan pesan over time kepada user A, dimana berarti bahwa tanda tangan tersebut gagal, else ia menerima informasi ini.
2). User ui akan menandatangani informasi, dengan proses signing yaitu hitung Si = (x, Q’-ki)P, mengirimkan Si kepada user u2, (Q,S) merupakan blind signature dari user Ui.
e. Ketika user ui ( i=1,2,3,…,d ) menerima informasi Si-1. Pertama ia akan memvalidasi, proses validasinya yaitu hitung Ti = ∆Ti + T, jika informasi Si-1 telah datang sebelum waktu Ti , ia akan menghitung rumus sebagai berikut :
i-1 i=1
Q’ ∑yj – Si-1 = ∑Rj .
j=1 j=1
Jika dapat dipertahankan, ia akan menandatangani informasi, jika tidak maka meminta user ui-1 mengirimkan informasi tanda tangannya lagi. Jika informasi Si-1 tidak datang sebelum waktu Ti, user ui akan mengirimkan pesan overtime kepada ui-1 menunjukkan kegagalan dari tanda tangan. Proses tanda tangan dari user ui adalah menghitung Si = Si-1 + ( xiQ’-ki ) P dan mengirimkan Si kepada user ui+1 , ( Q, Si ) merupakan blind signature dari user ui .

f. Ketika user A telah menerima informasi Sd dari user Ud , ia harus memvalidasi tanda tangan tersebut sebelum ia menyetujuinya. Proses validasinya yaitu hitung Td = ∆Td+T kemudian ia akan menentukan jika informasi Sd tiba sebelum waktu Td , jika hal itu terjadi, maka termasuk dalam situasi yang pertama, lalu ia akan mengikuti langkah sebagai berikut :
Pertama ia menghitung rumus
d d
Q’ ∑yj – Sd = ∑Rj .
j=1 j=1
Jika dapat dipertahankan, ia meminta Ud mengirimkan informasi tanda tangan lagi, jika tidak ia akan memvalidasi seluruh tanda tangan dari semua penanda tangan, prosesnya :
1) hitung S’ = bSd – aP
2) hitung F = h (m, Qy – S’ , T )
3) jika F = Q dapat dipertahankan, user A akan menerima atau menyetujui tanda tangan , jika tidak maka menolaknya.
Dalam situasi yang lain, informasi Sd tidak datang sebelum waktu Td , kemudian user A akan mempertimbangkan blind signature dari m menjadi tidak berhasil.

2. Pembuktian validasi dari skema
Bukti untuk tanda tangan user ui+1 :
Si = Si-1 + ( xiQ’ki )P
i i
= ( ∑xj Q’ – ∑kj )
j=1 j=1
i i
= Q’ ∑yj – ∑Rj
j=1 j=1
Kemudian rumus :
i i
Q’ ∑yj – Si = ∑Rj dapat dipertahankan
j=1 j=1



Untuk user A
d d
Sd = Q’ ∑yj – ∑Rj
j=1 j=1
d d
S’ = bSd – aP = b ( Q’ ∑yj – ∑Rj ) - aP
j=1 j=1
Kemudian
Qy – S’ = Qy - b ( Q’y - R ) + aP
= Qy – b ( Qb-1y ) + bR +aP
= Qy – Qy + bR +aP
= bR +aP
= R’

E. Analisis Keamanan Dan Kompleksitas Perhitungan Dari Skema
Skema tersebut merupakan pengembangan digital signature dengan non-supersingular elliptic curve pada finite field GF (2n). Keamanannya terletak pada keamanan dari non-supersingular elliptic curce cryptosystem, maka dapat dipercaya. Ketika attacker mencoba mendapatkan xi dari yi ( dimana yi adalah kunci publik ), mereka harus memecahkan persoalan logaritma diskrit kurva elips yang sulit. Kesulitan lainnya adalah attacker harus mengedepankan persoalan logaritma diskrit kurva elips yang sulit jika mereka menginginkan untuk memperoleh k dari informasi tanda tangannya.

PUSTAKA
www.wikipedia.com
Menezes, Alfred J, Dkk, Handbook of Applied Cryptography, 1996