KRIPTOSISTEM KURVA ELIPS (ELLIPTIC CURVE CRYPTOSYSTEM)
Disarikan oleh: Dinisfu Sya’ban (0403100596)
SEKOLAH TINGGI SANDI NEGARA BOGOR 2007
PENDAHULUAN Pada tahun 1985, Neil Koblitz dan Viktor Miller secara terpisah memproposalkan kriptosistem kurva elips (Elliptic Curves Cryptosystem - ECC) yang menggunakan masalah logaritma diskrit pada titik-titk kurva elips yang disebut dengan ECDLP (Elliptic Curves Discrete Logarithm Problem). Kriptosistem kurva ellips ini dapat digunakan pada beberepa keperluan seperti : •
Skeme enkripsi (ElGamal ECC)
•
Tanda tangan digital (ECDSA – Elliptic Curves Digital Signature)
•
Protokol pertukaran kunci (Diffie Hellman ECC)
Saat ini ada tiga macam sistem kriptografi kunci publik yang aman dan efisien yang dikelompokan berdasarkan permasalahan matematis, yaitu : •
Sistem Pemfaktoran Bilangan Integer (Integer Factorization Systems) Tipe ini menngunakan masalah matematis yang disebut Integer Factorization Problem (IFP).
Jika diberikan bilangan integer n yang
merupakan hasil kali dua buah bilangan prima, maka harus dicari kedua bilangan prima p dan q yang merupakan faktor n, sehingga n = p * q. Cara ini tentunya akan menyebabkan kesulitan menghitung faktor integer yang besar. •
Sistem Logaritma Diskrit (Discrete Logarithm Systems) Tipe ini menggunakan masalah matematis yang disebut Discrete Logarithm Problem (DLP). Taher ElGamal adalah orang pertama mengajukan kriptosistem kunci publik berdasarkan masalah ini. Pada tahun 1991, Clauss Schnorr menemukan variasi ElGamal untuk membuat tanda tangan digital yang menawarkan keamanan tambahan dibandigkan dengan sistem aslinya. Pemerintah Amerika Serikat menggunakan DSA (Digital Signature Algorithm) yang berdasarkan ElGamal ini. DLP nerupakan masalah yang didefinisikan pada aritmetika modular serta penggunaan grup perkalian. Jika dipilih bilangan prima p dan diberikan bilangan integer g antara 0 dan p-1 serta y merupakan pemangkatan dari g sehingga :
y = gx (mod p) (6) untuk beberapa x. Masalah logaritma diskrit pada modulo p adalah untuk mencari x jika diberikan pasangan bilangan g dan y. Cara ini menyebabkan kesulitan menghitung x = (log b) mod p. •
Kriptosistem Kurva Elips (Elliptic Curves Cryptosystem) Pada sistem ini digunakan masalah logaritma diskrit kurva elips dengan menggunakan grup kurva elips. Struktur kurva elips digunakan sebagai grup operasi matematis untuk melangsungkan proses enkripsi dan deskripsi. Cara ini menyebabkan kesulitan menghitung k jika diketahui Q dan P dimana Q = k P.
1.
Kurva Elips Pada bagian ini akan dibahas teknik dasar kurva elips dalam Fp dimana p
adalah bilangan prima yang lebih besar dari 3. Selanjutnya kurva elips secara umum didefinisikan sebagai field berhingga (finite field). Sebuah kurva elips E pada Fp didefinisikan dalam persamaan : y2 = x3 + ax + b, (7) dimana a,b∈ Fp dan 4a3 + 27b2 ≠ 0 (mod p), dan sebuah titik O yang disebut dengan titik infinity. Himpunan E(Fp) adalah semua titik (x,y), untuk x,y ∈ Fp, yang memenuhi persamaan (1) pada titik O. Untuk menjelaskan uraian di atas, berikut ini diberikan contoh pencarian himpunan E(Fp). Diberikan persamaan kurva elips E: y2 = x3 + x + 1 dengan p = 23, yaitu F23 ( pada persamaan (1) a = b = 1 ). Maka untuk nilai 4a3 + 27b2 = 4 + 27 ≠ 0, sehingga E ada dalam kurva elips. Titik-titik dalam E(F23) adalah : (0,1) (0,22) (1,7) (1,16)
(6,4) (6,19) (7,11) (7,12)
(12,19) (13,7) (13,16) (17,3)
(3,10) (3,13) (4,0) (5,4) (5,19)
(9,7) (9,16) (11,3) (11,20) (12,4)
(17,20) (18,3) (18,20) (19,5) (19,18)
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
0
1
2
3
4
5
6
7
8
9
10 11
12 13
14 15
16 17
18 19
Gambar 1. Sebaran titik-titik pada kurva elips E(F23) untuk E: y2 = x3 + x + 1
2.
Aturan Penjumlahan Dua Titik pada Kurva Elips Untuk membentuk elliptic curve cryptoystem (ECC) diperlukan aturan
penjumlahan dua titik pada kurva elips E(Fp) yang menghasilkan titik ke tiga pada kurva elips. Aturan ini dapat dijelaskan secara geometris sebagai berikut : 1. P + O = O + P = P untuk setiap P∈ E(Fp). 2. Jika P = (x,y) ∈ E(Fp) maka (x,y) + (x,-y) = O. (Titik (x,-y) dinyatakan dengan –P, dan disebut negatif P. Tentunya –P merupakan sebuah titik dalam kurva ). 3. Diberikan P = (x1,y1) ∈ E(Fp) dan Q = (x2,y2) ∈ E(Fp), dimana P = -Q. Maka P+Q = (x3,y3) diperoleh dengan mengambil garis L yang melewati
20
titik P dan Q atau garis singgung L untuk P=Q. Misalkan garis L : y = λx + β di mana :
y 2 − y1 x − x untuk P=Q 2 1 λ= 2 3 x1 + a untuk P≠Q 2 y1 maka diperoleh (x3,y3) sebagai berikut : x3 = λ2 − x1 − x 2 y 3 = λ ( x1 + x3 ) − y1
y
Q=(x2,y2) x P=(x1,y1) R=(x3,y3) Gambar 2. Gambaran secara geometri penjumlahan dua titik berbeda
y P=Q=(x1,y1)=(x1,x2)
x
R=(x3,y3)
Gambar 3. Gambaran secara geometri penjumlahan dua titik sama
Untuk mengilustrasikan penjelasan di atas, perhatikan contoh berikut ini. 1. Contoh P≠Q, untuk P=(3,10) dan Q=(9,7), maka P+Q=(x3,y3) diperoleh melalui :
λ=
7 − 10 = 11 ∈ Z 23 9−3
x3 = 112 – 3 – 9 = -6 ≡ 17 (mod 23) dan y3 = 11(3 – (-6)) -10 = 89 ≡ 20 (mod 23) Jadi P+Q = (17,20) Hasil ini diperlihatkan secara geometris dalam gambar di bawah ini. 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
(17,20)
(3,10)
(9,7)
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Gambar 4. Gambaran geometris untuk (3,10) + (9,7) = (17,20)
2. Contoh P=Q, untuk P=(3,10), maka 2P=P+P=(x3,y3) diperoleh melalui :
18
19
20
λ=
3(3 2 ) + 1 = 6 ∈ F23 20
x3 = 62 – 6 = 30 ≡ 7 (mod 23) y3 = 6(3 – 7)-10 = -11 ≡ 12 (mod 23) Jadi 2P = (7,12) Hasil ini diperlihatkan secara geometris dalam gambar 8. 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
(7,12)
(3,10)
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Gambar 5. Gambaran geometris untuk (3,10) + (3,10) = (7,12) 3. Order dari Sebuah Titik Penjumlahan secara berulang dari suatu titik terhadap dirinya sendiri (perkalian dengan sebuah skalar) akan menghasilkan suatu titik baru, Q = k P, yang mana pada suatu saat akan terdapat integer k sedemikian sehingga O = k P. Order dari titik P adalah bilangan positif integer terkecil k sedemikian sehingga O = k P.
Tabel.3. Titik-Titik pada ECC
20
Tabel di atas menunjukkan seluruh titik pada E F (
23
) : y2 = x3 + x +1 beserta
order dari masing-masing titik. Semua titik dengan order 28 merupakan generator dari maksimal subgrup E F (23) : y2=x3+x+1 (mod 23), karena mereka menghasilkan semua titik pada E F (23) : y2=x3+x+1. Sedangkan titik P (7,11) merupakan sebuah generator dari sebuah subgrup yang berbeda yang menghasilkan 14 titik. Sedangkan yang dimaksud dengan order dari kurva adalah order maksimum dari semua titik yang terdapat pada E F (
23
) : y2 = x3 + x +1. Order dari setiap
titik merupakan faktor dari order kurva.
4. Teorema Hasse Teorema ini menyatakan bahwa jumlah seluruh titik pada E(Fp) terletak pada kisaran :
5. Pemilihan Sebuah Kurva Elips dan Titik Generator Berikut ini merupakan salah satu prosedur untuk memilih suatu kurva elips. Langkah-langkahnya antara lain : 1) Pilih sebuah bilangan prima yang besar p untuk digunakan sebagai bilangan pemodulo.
2) Pilih koefisien a dan b secara acak dan definisikan 2
E F (23) :
3
y =x +ax+b. 3) Hitung order dari kurva #E(Fp). 4) Periksa apakah ia memenuhi kondisi MOV atau tidak. 5) Periksa apakah #E(Fp) dapat dibagi oleh bilangan prima n yang cukup besar, n > 2160, agar resisten terhadap serangan Pollard–ρ dan Pollard-λ yang dilakukan secara paralel. 6) Periksa apakah bilangan prima terbesar pembagi #E(Fp) tidak membagi pk-1 untuk k = 1,2,3,…..
. Setelah menentukan kurva elips, kita pilih titik G sebagai generator subgroup. 1. Pilih sebuah titik secara acak pada E(Fp) dan sebuah bilangan prima yang besar n sehingga membagi #E(Fp). 2. Periksa apakah nG = O, jika terpenuhi maka n sebagai order dari titik.
6. Parameter-Parameter pada Domain Kurva Elips pada Fp Domain kurva elips Fp memeliki beberapa parameter, antara lain : •
Sebuah integer p sehingga
jika t ≠ 256 atau sedemikian sehingga
jika t = 256. •
Integer t ∈ (56, 64, 80, 96, 112, 128, 192, 256), merupakan pendekatan mengenai tingkat keamanan kurva elips dalam ukuran bit.
•
Koefisien a dan b yang menentukan kurva elips E(Fp) yang memenuhi persamaan y2 = x3 + ax +b (mod p), keduanya terletak pada interval [0,p-1] dan memenuhi 4a3 + 27b2 ≠ 0 (mod p).
•
Titik basis G = (xG, yG) pada E(Fp), dimana xG dan yG merupakan integer pada selang [0,p-1]. Sebuah bilangan prima n, sehingga n.G = O. Periksa bahwa pB ≠ 1 (mod
•
n) untuk 1≤ B ≤ 20. •
Sebuah integer h yang merupakan kofaktor, h = [ # E (Fp)]/ n, h ≤ 4 dan n.h ≠ p.
7. Parameter-Parameter pada Domain Kurva Elips pada F2m Domain kurva elips F2m memeliki beberapa parameter, antara lain : •
Sebuah integer m yang memenuhi finite field F2m .
•
Sebuah polinomial biner yang irredusibel f(x) dengan derajat m .
•
Elemen a dan b yang menentukan kurva elips E(F2m) yang memenuhi persamaan y2 + xy = x3 + ax + b pada E(F2m). a dan b merupakan polinomial biner dengan derajat < m-1 dan b ≠ 0.
•
Titik basis G = (xG, yG) pada E(F2m).
•
Sebuah bilangan prima n, sehingga n.G = O. Periksa bahwa 2BM ≠ 1 untuk 1≤ B ≤ 20.
•
Sebuah integer h yang merupakan kofaktor, h = [ # E (F2m)], h ≤ 4 dan n.h ≠ p.
Berdasarkan penjelasan di atas, operasi grup untuk kurva elips E(Fp) disebut dengan operasi penjumlahan, dan disebut operasi perkalian pada grup F*p. Untuk lebih jelasnya, tabel 1 memberikan hubungan antara F*p dengan E(Fp)
Tabel 4. Hubungan antara F*p dengan kurva E(Fp) F*p
Label Elemen
Integer {1,2, … , p-1}
Kurva E(Fp) Titik (x,y) pada kurva E +
O Aturan operasi
Perkalian modulo p
Penjumlahan 2 titik
Notasi
Elemen : g,h
Elemen : P,Q
Discrete Logarithm Problem
Perkalian : g • h
Perkalian : P + Q
Invers : g-1
Invers : -P
Pembagian : g / h
Pembagian : P – Q
Pemangkatan : ga
Perkalian : aP
Diberikan g∈F *p dan h = ga mod p, cari a
Diberikan P∈E(Fp) dan Q = aP, cari a
