ELLIPTIC CURVE CRYPTOGRAPHY
Disarikan oleh: Dinisfu Sya’ban (0403100596)
SEKOLAH TINGGI SANDI NEGARA BOGOR 2007
A. Fungsi Elliptic Curves 1. Definisi Elliptic Curves Definisi 1. : Misalkan k merupakan field dengan karakteristik ≠ 2, 3, dengan k dapat merupakan field bilangan real R, field bilangan rational Q, field bilangan complex C atau finite field Fq dengan q = pr elemen. Misalkan x3 + ax + b (dimana a, b ∈ k), dimana 4a3 + 27b2 ≠ 0, dengan DE (discriminant E) = -16 (4a3 + 27b2) dan invariant kurva didefinisikan sebagai j(E)= 2833a3/(4a3 + 27b2) merupakan polynomial pangkat tiga tanpa mempunyai akar perkalian. Elliptic curves dalam k merupakan himpunan titik-titik (x, y) dengan x, y ∈ k memenuhi persamaan y2 = x3 + ax + b
(1)
dengan sebuah elemen tunggal yang dinotasikan dengan OE yang disebut “point at infinity”. a) Jika k merupakan field dengan karakteristik 2 , maka elliptic curves dalam k adalah himpunan titik-titik yang memenuhi persamaan sebagai berikut : y2 + cy = x3 + ax + b
(2a)
y2 + xy = x3 + ax2 + b
(2b)
atau memenuhi
dengan sebuah “point at infinity” OE (tidak perduli persamaan kubik di kanan mempunyai akar perkalian atau tidak).
b) Jika k merupakan field dengan karakteristik 3, maka elliptic curves dalam k
adalah himpunan titik-titik yang memenuhi persamaan
sebagai berikut : y2 = x3 + ax2 + bx + c
(3)
dengan sebuah “point at infinity” OE (dimana persamaan kubik di kanan tidak mempunyai akar perkalian). Selain persamaan di atas, terdapat persamaan umum yang dapat digunakan pada sebarang field yaitu : y2 + a1xy + a3y = x3 + a2x2 + a4x + a6 . Persamaan di atas dapat ditranformasikan dalam bentuk y2 = x3 + ax2 + bx + c jika karakteristik k ≠ 2 dan menjadi y2 = x3 + bx + c untuk karakteristik k > 3. Jika dimisalkan F(x, y) = 0, maka suatu titik pada elliptic curves dikatakan non singular jika setidaknya turunan partial dari ∂F/∂x, ∂F/∂y bernilai tidak sama dengan nol pada titik tersebut. Atau dengan perkataan lain syarat persamaan kubik pada bagian kanan persamaan (1) dan (3) tidak mempunyai akar perkalian akan sama dengan semua titik yang terdapat pada kurva merupakan titik non singular. 2. Persamaan Elliptic curves yang Terdefinisi dalam Bilangan Real Misalkan E merupakan elliptic curves yang terdefinisi dalam bilangan real dan misalkan P dan Q titik-titik pada elliptic curves. Aturan-aturan dalam elliptic curves dapat dijelaskan sebagai berikut : 1) Jika P merupakan “point at infinity” OE , maka dapat didefinisikan
–P = OE dan P + Q = OE; OE berperan sebagai identitas penjumlahan (“elemen nol”) dari group yang dibentuk titik-titik pada elliptic curves. Selanjutnya dimisalkan P dan Q ≠ OE. 2) Negatif P merupakan titik yang mempunyai koordinat x yang sama dengan P tetapi koordinat y pada titik tersebut negatif, dapat dinotasikan sebagai P = (x, y), –P = –(x,y) = (x,–y). Dari persamaan (1) jelas terlihat (x,–y) terdapat pada kurva jika (x,y) juga terdapat pada kurva. 3) Jika P dan Q mempunyai koordinat x yang berbeda, maka sebuah garis l = PQ yang melalui P dan Q memotong kurva tepat hanya satu titik yaitu pada titik R. Begitu pula jika garis tersebut merupakan garis tangent pada kurva di titik P, untuk kasus R = P, atau di Q, jika R = Q. Maka dapat didefinisikan P + Q adalah –R yaitu merupakan pencerminan terhadap koordinat x dari titik potong garis l pada kurva. 4) Jika Q = –P, dengan pengertian Q seperti 2), maka didefinisikan P + Q = OE . 5) Kemungkinan terakhir yang didapat jika P = Q. Misalkan l merupakan garis tangent terhadap kurva di P, misalkan R merupakan satu-satunya titik potong l terhadap kurva, maka dapat didefinisikan P + Q = –R. Sebagai ilustrasi untuk memperjelas definisi di atas maka diberikan contoh sebagai berikut :
Misalkan elliptic curves dengan persamaan y2 = x3 – x pada koordinat xy. Untuk mencari nilai P + Q, gambar garis melalui P dan Q, nilai P + Q merupakan titik yang simetris (terhadap koordinat x) terhadap titik ketiga di mana garis yang melalui P dan Q memotong kurva tersebut. Jika P dan Q sama dan dicari nilai 2P, maka gambar garis tangent di P terhadap kurva,
nilai 2P
merupakan titik yang simetris terhadap titik ketiga di mana garis tangent memotong kurva.
Operasi Penjumlahan dan Perkalian pada Elliptic curves Operasi penjumlahan pada elliptic curves disebut tangent and chord method. Operasi tersebut dapat dijabarkan sebagai berikut misalkan (x1, y1), (x2, y2), dan (x3, y3) melambangkan koordinat P, Q dan P + Q. (x3, y3) akan dinotasikan dalam x1, y1, x2, y2. Pada kasus 3) definisi P + Q, misalkan y = ∝x + β merupakan persamaan garis yang melalui P dan Q dan bukan merupakan garis vertikal pada kasus 3. maka didapatkan ∝ = (y2 – y1)/( x2 – x1), dan β = y1 – ∝x1. Suatu titik pada l , yaitu (x, ∝x + β), terletak pada kurva jika dan hanya jika (∝x + β)2 = x3 + ax + b. Maka hanya akan terdapat satu titik potong untuk setiap akar persamaan kubik x3 + (∝x + β)2 + ax + b. Telah diketahui terdapat dua akar yaitu x1 dan x2, karena (x1, ∝x1 + β) dan (x2, ∝x2 + β) merupakan titik P dan Q pada kurva seperti yang telah dimisalkan di awal. Karena jumlah dari akar polynomial monik sama dengan negatif koefisien dari pangkat kedua tertinggi, maka dapat disimpulkan x3 = ∝2 – x1 – x2. Sehingga didapat persamaan untuk P + Q = (x3, – (∝x3 + β)), yang jika dinotasikan dalam x1, y1, x2, y2 sebagai berikut :
2
y − y1 – x1 – x2; x3 = 2 x 2 − x1 y − y1 y3 = – y1 + 2 x 2 − x1
2
(4)
(x1 − x3 )
Pada kasus 5) di mana P = Q, persamaan yang didapatkan hampir mirip hanya saja ∝ diganti dengan turunan
dy di P. Turunan dari persamaan (1) y2 = x3 dx
3x 2 + a . Perhitungannya adalah sebagai + ax + b didapatkan formula α = 1 2 y1 berikut : y2 = x3 + ax + b 2y
dy dy dy = 3x2 +a + 0; dx dx dx
Dari perhitungan di atas didapatkan nilai α sehingga formula untuk mencari nilai 2P adalah sebagai berikut : 2
3x 2 + a – x1 – x2; x3 = 2y 3x 2 + a y3 = – y1 + 2y
2
(5)
(x1 − x3 )
Contoh perhitungan untuk memperjelas ilustrasi di atas adalah sebagai berikut : Misalkan pada persamaan elliptic curves y2 = x3 – 36x, P = (–3, 9) dan Q = (–2, 8) merupakan titik-titik yang terdapat dalam persamaan tersebut. Akan dicari P + Q dan 2P, proses yang dilakukan :
a)
P+Q
Substitusikan x1 = –3, y1 = 9, x2 = –2, y2 = 8 pada persamaan (4) menghasilkan x3 = 6. Sedangkan persamaan kedua didapat y3 = 0. 2
8−9 – ( –3) – (–2); x3 = − 2 − (−3) x3 = 6; 2
8−9 (– 3 – 6) y3 = – 9 + − 2 − (−3)
y3 = 0. Jadi nilai P + Q = (6, 0). b)
2P Substitusikan x1 = –3, y1 = 9, a = –36 pada persamaan (5) yang
menghasilkan x3 =
25 − 35 dan y3 = . 4 8 2
3(−3) 2 + (−36) – 2 ( –3); x3 = 2(9)
x3 =
25 ; 4 2
3(−3) 2 + (−36) 25 (– 3 – ) y3 = – 9 + 2(9) 4 y3 =
− 35 8
Jadi didapatkan nilai 2P = (
25 − 35 , ). 4 8
Perkalian dalam elliptic curves dinotasikan sebagai nP , yang didefinisikan sama seperti group abelian lain, yaitu menambahkan P sebanyak n kali pada titik itu sendiri jika n positif atau menambahkan –P pada dirinya sendiri sebanyak n kali jika n negatif. Point at Infinity (Titik di Tak Terhingga) Point at infinity, seperti yang telah dijelaskan pada definisi 1) merupakan elemen identitas untuk operasi penjumlahan dalam group yang dibentuk oleh titiktitik yang terletak pada kurva. Titik ini dilambangkan dengan OE. Titik ini merupakan titik perpotongan sebarang garis vertikal dengan kurva, yaitu garis vertikal yang melalui (x1, y1) dan (x1, – y1).
Gambar 4 Elliptic curves dan operasi penjumlahan P1 + P2 (P1 ≠ P2)5 5
Http://www.rsasecurity.com/rsalabs/faq/2-3-10.html/eca.gif
3. Persamaan Elliptic curves yang Terdefinisi dalam Finite Field Misalkan k merupakan finite field Fq dengan q = pr anggota atau q merupakan bilangan prima, E merupakan persamaan elliptic curves yang terdefinisi dalam Fq, P dan Q titik-titik pada elliptic curves. Persamaan elliptic curves yang terdefinisi dalam finite field juga memenuhi persyaratan 4a3 + 27b2 (mod q) ≠ 0. Titik-titik pada elliptic curves ini membentuk group modulus q, dengan q merupakan pangkat bilangan prima atau bilangan prima. Jumlah titik yang terdapat pada persamaan elliptic curves yang terdefinisi dalam finite field harus memenuhi Teorema Hasse.
Teorema 2. (Hasse 6) : Misalkan N merupakan jumlah titik pada elliptic curves yang terdefinisi dalam Fq, maka :
N − (q + 1) ≤ 2 q atau dapat ditulis dalam bentuk lain sebagai berikut:
q +1− 2 q ≤ N ≤ q +1+ 2 q {Pembuktian dari teorema di atas dapat dilihat di lampiran.} Menghitung Jumlah Titik pada Elliptic curves Perhitungan titik pada elliptic curves dengan persamaaan y2 = x3 + ax + b secara sederhana dapat dijelaskan sebagai berikut : a. Untuk setiap x di mana 0 ≤ x < N , hitung nilai x3 + ax + b (mod N).
6
N. Koblitz, A Course in Number Theory and Cryptography, Second Edition, Springer Verlag, New York, 1994, hal 174.
b. Setiap hasil yang didapat dari langkah selanjutnya, periksa apakah hasil tersebut mempunyai akar kuadrat modulo N. Jika tidak terdapat hasil tersebut maka tidak ada titik dengan nilai x pada EN . Sebaliknya jika ada, maka akan ada dua nilai y yang memenuhi persamaan tersebut (kecuali nilai y yang tunggal yaitu 0). Titik (x, y) tersebut merupakan titik pada persamaan elliptic curves.
ELLIPTIC CURVE EL GAMAL CRYPTOSYSTEM (ECELG) Algoritma Pembangkit Kunci Untuk ECELG : 1. Generate bilangan prima besar p dan α dari grup perkalian Zp dari bilangan integer modulo p. 2. Pilih sebuah bilangan acak integer a dimana 1 ≤ a ≤ p-2 dan hitung β = aα mod p 3. Kunci publik (p, α, aα). Kunci privat : a.
Algoritma Penyandian : 1. Diketahui public key (p, α, aα). 2. Ubah pesan m ke dalam titik-titik dalam elliptic curve dengan range {0, 1, ..., p-1}. 3. Pilih bilangan integer secara acak k, dimana 1 ≤ k ≤ p-2. 4. Operasi Enkripsi : eK(m,k) = (γ, δ) = (kα, m+kβ), dimana : γ = kα mod p
δ = (m+kβ) mod p
Algoritma Pembukaan : 1. Diketahui public key (p, α, aα). 2. Operasi Dekripsi : dK(γ, δ) = (δ - aγ) mod p.
MENEZES-VANSTONE ELLIPTIC CURVE CRYPTOSYSTEM E : elliptic curve yang didefinisikan pada Zp (p>3, prima) ∋ E berisi sebuah cyclic subgrup H dimana masalah discrete logaritmanya sulit dipecahkan.
℘ = Z *p x Z *p
C = E x Z *p x Z *p K = {(E, α, a, β) : β = aα}, dimana α∈E. Kunci publik : α, β. Kunci privat : a. K = (E, α, a, β), pilih bilangan random secret k∈ZH, dan untuk m = (m1, m2)∈ Z *p x Z *p , dimana m bukan titik di E, definisikan : eK(m,k) = (y0, y1, y2), dimana : y0 = kα (c1, c2) = kβ y1 = c1x1 mod p y2 = c2x2 mod p
Dekripsi :
y = (y0, y1, y2), definisikan : dK(y) = (y1c1-1 mod p, y2c2-1 mod p), dimana ay0 = (c1, c2).
