enkripsi didefinisikan oleh mod dan menghasilkan siferteks c. 3. Algoritme 3 Dekripsi Untuk menemukan kembali m dari c, B harus melakukan hal-hal berikut a. Menggunakan kunci pribadi a untuk mod . Dengan menghitung . catatan b. Menemukan kembali m dengan mod . menghitung Pada proses dekripsi, dengan dan didefinisikan : , sehingga fungsi dekripsi didefinisikan oleh mod . (Menezes et al. 1996) Berikut ini diberikan suatu ilustrasi penyandian yang dihitung dengan menggunakan software Maple 12 dengan PC processor Intel Pentium Dual Core 1,73 GHz, Ram 512 MB. Contoh ElGamal A mengirim pesan kepada B. Pesan tersebut adalah 91819250104. Langkah pertama, B membuat kunci publik dan kunci pribadi. Setelah melalui
Algoritme 1 Pembangkitan Kunci, diperoleh kunci publik , , (9574006709478958 762709029785327385064807, 5, 468663437 0436292147431903521064446370856) dan kunci pribadi (665638090635425982769 337333168305062441). Kemudian, kunci publik tersebut dikirim ke A. Setelah A memperoleh kunci publik , , dari B, kemudian A memilih integer positif acak k dan menghitung mod 52940576363150816401527749mod = 5986545355441362, dan 510960553455680182318130888811111301. A mengirim pesan yang telah disandikan tadi (siferteks) kepada B dengan bentuk , = (529405763631508164015277496545355441362, 598510960553455680182318130888811111301). Setelah B menerima siferteks tadi, maka B mendekripsikan siferteks tadi untuk menemukan kembali pesan m dengan menggunakan kunci pribadi, 91819250104 mod , dimana pesan yang telah didekripsikan tadi sama dengan pesan yang sebelum dienkripsikan.
III PEMBAHASAN Field dengan karakteristik prima 2 merupakan suatu kasus khusus, dimana tidak ada pengurangan pada operasi aljabarnya. Seperti yang telah dipaparkan pada bab 2, di bawah ini akan dibahas struktur grup kurva Supersingular dengan , 0 eliptik dan Non-Supersingular 0 sehingga titik (0,0) berada di luar kurva yang merepresentasikan titik ∞. 3.1 Aritmetika Kurva Eliptik Supersingular. adalah field dengan Misalkan karakteristik prima 2 Supersingular dengan bentuk sederhana dari persamaan kurva eliptiknya adalah : dan ∆ 0 ∆ dengan , , 0. Didefinisikan persamaan kurva eliptik Supersingular | , ∞. 1. Misalkan terdapat titik , sembarang. Karena syarat
0
dan dengan 0, maka titik 0,0 dijamin tidak terletak pada kurva dan dapat digunakan untuk merepresentasikan ∞ 0,0 . Akibatnya, ∞ 0, 0 , 2. Dengan titik 0,0 yang direpresentasikan dengan titik di tak-hingga maka untuk , terdapat setiap , invers dari yang dinotasikan dengan – , berlaku, 0,0 ∞. dimana ∞ ∞. , dimana setiap , , dan , maka titik yang akan dicari adalah , . Terdapat tiga titik pada E, maka berlaku tiga persamaan (1.1) (1.2) (1.3) Jika dilihat dari definisi secara , geometri, maka , dan adalah segaris. Jika gradiennya
3. Untuk
6
dimisalkan dengan persamaan
maka diperoleh
. (1.7) Jika ditarik garis lurus P dan R’ (titik sebelum dicerminkan terhadap sumbu-x), terlihat merupakan sebuah garis singgung. Dimisalkan gradiennya , maka (1.8)
(1.4) Kemudian apabila dari persamaan (1.1) dan (1.3) kita jumlahkan dan dimodulokan dengan dua, akan diperoleh
Kemudian, dengan turunan implisit , , dengan memisalkan dapat kita peroleh nilai yaitu
Apabila pada ruas kiri kita tambahkan nilai 2 , maka persamaan di atas menjadi 2
3 2
,
,
(1.9) Sama halnya dengan penurunan kasus (pada persamaan 1.5), diperoleh persamaan
Kemudian kedua ruas disederhanakan dan diperoleh dibagi dengan
Sehingga . Untuk diperoleh dari persamaan (1.8) yaitu (1.5) Setelah memperoleh persamaan (1.5) dengan dari persamaan (1.4), maka untuk persamaan (1.2), (1.3) akan diperoleh dengan cara yang sama, sehingga didapatkan (1.6) dan , akan Untuk memperoleh dijumlahkan persamaan (1.5), (1.6) sehingga kita peroleh Apabila kita bagi kedua ruas dengan maka didapatkan
dan dari
dengan
Dari uraian di atas, diperoleh aritmetik Supersingular sebagai pada kurva eliptik berikut 1. Titik di luar kurva yang digunakan adalah ∞ 0,0 . 2.
3.
dan – , apabila dijumlahkan menghasilkan titik ∞. ,
,
dan
maka, , dan dengan
dimana
dihasilkan ,
dihasilkan
,
.
dengan ,
4.
dan dengan
,
dimana ,
. Jadi,
.
.
4. Untuk setiap , dan , titik yang ingin ditentukan , . adalah Apabila diperhatikan secara geometri, titik P dan R berada pada kurva E. Oleh sebab itu, terdapat dua persamaan dan
dan ,
berlaku
, dimana
dan dengan
.
Di bawah operasi di atas, maka kurva supersingular merupakan grup eliptik dengan unsur identitas ∞ 0,0 dan invers dari adalah – , .
7
3.2 Algoritme Aritmetik Kurva Eliptik Supersingular. 3.2.1 Pembangkitan Kurva Eliptik K(a,b,c) INPUT : Memasukkan nilai m OUTPUT : nilai kurva , , Mulai . 1. Pilih acak , , 2. Lakukan sampai i proses jika ∞ dengan cara a. Mengacak b. Selesai 3. Kemudian lakukan juga sampai i proses jika diperoleh ∞ dengan cara a. Mengacak b. Selesai 4. Tampilkan , , 3.2.2 Menentukan Titik P(x,y) INPUT : Nilai kurva , , OUTPUT : Titik , Mulai 1. Hitung 2. Lakukan sampai i proses jika diperoleh ∞ dengan cara a. Menentukan kembali b. Selesai. 3. Tampilkan nilai memenuhi dengan
, ∞.
, , 3.2.3 Adisi Titik ,Q , INPUT : P , dengan , , , OUTPUT : Titik Mulai 1. Jika ∞ atau ∞, maka a. b. dan , maka 2. Jika 0 a. 0 b. 3. Jika . Maka a. b. c. 4. Jika tidak
, maka :
a. b. c. 5. Tampilkan
,
yang
3.2.4 Menentukan Invers (Negatif) Titik INPUT : Titik P , dengan kurva eliptik , , c OUPUT : P , Mulai c 1. Dengan , . 2. Tampilakan 3.2.5 Menentukan (Kelipatan sebanyak ) dan INPUT : Titik P , merupakan integer positif acak dengan , , OUPUT : Mulai 1. Pilih suatu integer acak dan diubah menjadi basis 2 2. Misalkan 3. Jika hanya terdapat satu titik P, maka a. Nilai yaitu nilai P b. Selesai 4. Untuk langkah kedua, lakukan sampai i kali apabila terdapat beberapa titik yang sama dengan cara a. Nilai yaitu nilai . Jadi apabila terdapat dua titik yang sama dan masing-masing bisa dipasangkan, titik tersebut digandakan sampai i sehingga ditemukan satu titik. b. Jika operasi ke i kali yang nilai biner 1 (terdapat satu titik yang tidak ada pasangan untuk digandakan), maka lakukan 1. Titik yang digandakan sebelumnya dijumlahkan dengan satu titik yang tidak mempunyai pasangan sehingga proses a 2. Selesai c. Selesai 5. Tampilkan titik Non3.3 Aritmetika Kurva Eliptik Supersingular. adalah field dengan Misalkan karakteristik prima 2 Non-Supersingular dengan bentuk sederhana dari persamaan kurva eliptiknya adalah : dan ∆ 0. dengan , Didefinisikan persamaan kurva eliptik Non-Supersingular | , ∞.
8
1. Misalkan terdapat titik , sembarang. Karena syarat 0, maka titik 0,0 dijamin tidak terletak pada kurva dan dapat digunakan untuk 0,0 . Akibatnya, merepresentasikan ∞ ∞ 0, 0 , . 2. Dengan titik 0,0 yang direpresentasikan dengan titik di tak-hingga maka untuk , terdapat setiap , invers dari yang dinotasikan dengan – , berlaku, 0,0 ∞. dimana ∞ ∞. dimana setiap , , , , dan maka titik yang akan dicari adalah , . Apabila ditelaah pada tiga titik pada E, maka berlaku tiga persamaan (2.1) (2.2) (2.3) Jika dilihat dari definisi secara , geometri, maka P, Q dan adalah segaris. Jika gradiennya dimisalkan dengan λ maka diperoleh persamaan
3. Untuk
(2.4) Kemudian dari penjumlahan persamaan (2.1) dan (2.3) yang kemudian dimodulokan dengan dua diperoleh
(2.6) Dengan nilai gradien seperti pada (2.4), sehingga penjumlahan dari (2.5) dan (2.6) menghasilkan
dan dari persamaan (2.4) diperoleh
Dengan demikian, , dimana dan
diperoleh dengan
. 4. Untuk setiap , dan , titik yang ingin ditentukan , . adalah Dilihat secara geometri, titik dan , segaris. Titik dan , merupakan garis singgung kurva pada titik . Maka berlaku persamaan (2.7) (2.8) Dimisalkan gradiennya dengan (2.9) Kemudian, dengan turunan implisit , , dengan memisalkan dapat kita peroleh nilai yaitu
2 2
2
3
2
3
2
2
3 2
2
(3.0) karena dalam biner, maka (2.8) menjadi
/ ⁄
(2.5) Dengan cara yang sama dari persamaan (2.2), (2.3), dan (2.4) diperoleh
,
1, 1
(3.1) Seperti pada penurunan persamaan (2.5), dari persamaan (2.7), (2.8), dan (2.9) diperoleh
9
dengan menerapkan maka diperoleh
persamaan
(3.1)
3.4 Algoritme Aritmetika Kurva Eliptik Non-Supersingular
Selanjutnya, dengan membagi kedua dan diterapkan ruas dengan juga persamaan (2.9) diperoleh
Untuk digunakan diperoleh
mendapatkan nilai persamaan (2.9), maka
dengan persamaan (3.1) persamaan di atas menjadi 1 Akhirnya diperoleh , dimana 1 dengan
dan .
Dari uraian di atas, diperoleh aritmetik Non-Supersingular pada kurva eliptik sebagai berikut a. Titik di luar kurva yang digunakan adalah ∞ 0,0 . b.
c.
dan – , apabila dijumlahkan menghasilkan titik ∞. ,
,
,
,
sembarang. Misalkan , dan
maka, , dimana
dan dan
dengan d. Untuk setiap , berlaku dimana dengan
Di bawah operasi di atas, maka kurva Non-Supersingular merupakan eliptik grup dengan unsur identitas ∞ 0,0 dan invers dari adalah – , .
adalah . ,
dan , dan .
3.4.1 Pembangkitan Kurva K(a,b) INPUT : Memasukkan nilai m , OUTPUT : Nilai kurva Mulai . 1. Pilih acak , 2. Lakukan sampai i proses dengan syarat ∞ dengan cara a. Mengacak b. Selesai 3. Tampilkan , 3.4.2 Menentukan Titik P(x,y) INPUT : Nilai kurva , OUTPUT : Titik , Mulai 1. Hitung ∞
2. Lakukan sampai i proses apabila dengan cara a. Hitung b. Selesai. 3. Tampilkan dan
,
dengan
∞.
, , 3.4.3 Adisi Titik , Q , INPUT : P , dengan , , OUTPUT : Titik Mulai 1. Jika ∞ atau ∞, maka a. b. dan , maka 2. Jika 0 a. 0 b. 3. Jika . Maka a. b. c. 4. Jika tidak a. b. c. 5. Tampilkan
, maka :
,
1
10
3.4.4 Menentukan Invers (Negatif) Titik dengan INPUT : Titik P , , OUPUT : P , Mulai 1. Hitung , 2. Tampilkan 3.4.5 Menentukan (kelipatan sebanyak k kali) dan INPUT : Titik P , merupakan integer positif acak dengan , , OUPUT : Mulai 1. Pilih suatu integer acak dan diubah menjadi basis 2 2. Misalkan 3. Jika hanya terdapat satu titik P, maka a. Nilai yaitu nilai P b. Selesai 4. Untuk langkah kedua, lakukan sampai i kali apabila terdapat beberapa titik yang sama dengan cara a. Nilai yaitu nilai . Jadi apabila terdapat dua titik yang sama dan masing-masing bisa dipasangkan, titik tersebut digandakan sampai i sehingga ditemukan satu titik. b. Jika operasi ke i kali yang nilai biner 1 (terdapat satu titik yang tidak ada pasangan untuk digandakan), maka lakukan 1. Titik yang digandakan sebelumnya dijumlahkan dengan satu titik yang tidak mempunyai pasangan sehingga proses a 2. Selesai c. Selesai 5. Tampilkan titik 3.5 ElGamal Kurva Eliptik atas Untuk penerapan kurva eliptik dalam algoritme ElGamal, maka terdapat beberapa perubahan yang terjadi dalam algoritme tersebut. Perubahannya dari grup yang digeneralisasi menjadi multiplikatif aritmetik kurva eliptik . Berikut langkah-langkah penyandian digeneralisasi. dengan grup multiplikatif Diilustrasikan A mengirim pesan kepada B. 1. Algoritme 1 Pembangkitan Kunci B membuat sebuah kunci publik dan kunci pribadi. Hal yang dilakukan adalah
a. Memilih suatu grup siklik dengan generator . b. Memilih suatu integer acak 1 1. . c. Menghitung d. Kunci publik B adalah kunci pribadi B adalah a. e. Kemudian kunci publik dikirimkan ke A.
berorder a dalam ,
dan tersebut
2. Algoritme 2 Enkripsi A menyandikan atau me-enkripsi sebuah pesan m ke B. Langkah-langkah yang harus dilakukan oleh A adalah a. Memperoleh kunci publik , . b. Merepresentasikan pesan tersebut sebagai suatu integer c. Memilih integer acak k, dimana positif. dan . d. Menghitung e. Mengirim siferteks , ke B. 3. Algoritme 3 Dekripsi Untuk menemukan kembali m dari c, B harus melakukan hal-hal berikut a. Menggunakan kunci pribadi a untuk . Dengan catatan menghitung . b. Menemukan kembali m dengan , sehingga diperoleh menghitung . (Menezes et al. 1996) Sedangkan untuk aritmetika kurva eliptik digunakan aturan definisi grup kurva eliptik dengan menggunakan proses adisi. Perubahan yang terjadi adalah menjadi a. Sebanyak
kali
b. menjadi . Oleh karena itu, algoritme ElGamal dalam diatas diganti menjadi grup multiplikatif aritmetika kurva eliptik (diilustrasikan A mengirim pesan ke B). 1. Algoritme 1 Pembangkitan Kunci B membuat sebuah kunci publik dan kunci pribadi. Hal yang dilakukan adalah a. Memilih suatu generator , yang merupakan titik pada kurva . eliptik. b. Memilih suatu integer acak a dalam 1 1. c. Menghitung . d. Kunci publik B adalah , dan kunci pribadi B adalah a. e. Mengirim kunci publik ke A.
11
2. Algoritme 2 Enkripsi A menyandikan atau me-enkripsi sebuah pesan m ke B. Langkah-langkah yang harus dilakukan oleh A adalah a. Memperoleh kunci publik , . b. Merepresentasikan pesan tersebut . sebagai suatu titik 1 c. Memilih integer acak k, 1 d. Menghitung dan . e. Mengirim siferteks , ke B. 3. Algoritme 3 Dekripsi Untuk menemukan kembali m dari c, B harus melakukan hal-hal berikut a. Menggunakan kunci pribadi a untuk menghitung . b. Menemukan kembali pesan m dengan menghitung , sehingga diperoleh . Contoh ElGamal Kurva Eliptik (Lihat Lampiran 4) : Diilustrasikan Andi mengirim pesan kepada Beni. Hal pertama yang dilakukan Beni adalah membuat kunci pribadi dan kunci publik. Dimisalkan menggunakan Nonaritmetik kurva eliptik Supersingular. Hal ini dikarenakan langkahlangkah yang dilakukan sama. 1. Algoritme 1 Pembangkitan Kunci. a. Beni memilih generator yang merupakan suatu titik pada kurva eliptik. , 2,5,7,9 , 0,1,3, 4,5,7,8 . b. Beni memilih integer acak yang nantinya merupakan kunci pribadi 93. c. Kemudian menghitung 2,7,8 , 0,1,6,8,9 . d. Kunci Publik adalah , dengan nilai 2,5,7,9 , 0,1,3,4,5,7,8 , 2,7,8 , 0,1,6,8,9 . 2. Algoritme 2 Enkripsi Setelah menerima kunci publik dari Beni, Andi menyandi pesan tersebut dengan
menggunakan kunci tersebut. Kemudian yang dilakukan Andi adalah a. Membangkitkan pesan. Di sini dimisalkan pesan yang dibangkitkan Andi adalah suatu titik 1,2,3,4,5,8 , 3,5,8,9 . b. Kemudian Andi memilih sembarang integer 53. c. Setelah itu Andi mencari nilai 0,1,2,3,6,7,9 , 2,5,6,9 . Kemudian, mencari nilai 3,4,5,8,9 , 0,2,3,7,9 . d. Nilai yang diperoleh tersebut dikirim kepada Beni dalam bentuk siferteks , 0,1,2,3,6,7,9 , 2,5,6,9 , 3,4,5,8,9 , 0,2,3,7,9 . 3. Algoritme 3 Dekripsi Setelah Beni menerima siferteks, barulah dia menemukan kembali pesan yang telah disandikan tersebut dengan menggunakan kunci pribadi yang hanya dia sendiri yang mengetahuinya dengan cara a. Mencari – dimana a merupakan kunci pribadi, sehingga diperoleh – 0,1,3,4,5,7,9 , 1,3,5,6 . b. Menemukan kembali m dengan menghitung sehingga diperoleh pesan yang sama seperti pesan yang belum disandikan 1,2,3,4,5,8 , 3,5,8,9 . Terlihat dengan jelas bahwa dalam melakukan penyandian tersebut, digunakan empat prinsip hukum grup dari kurva eliptik . Titik yang diperoleh di atas merupakan suatu himpunan. Himpunan-himpunan tersebut merupakan pangkat dari definisi . Misalkan contoh pesan yang digunakan pada contoh di atas. Pasangan titik 1,2,3,4,5,8 , 3,5,8,9 sama dengan 1. 1. pasangan polinomial 1. 1. 1. , 1. 1. 1. 1. . Sedangkan untuk nilai 1 merupakan 1. nilai untuk a. Ini dikarenakan berapapun nilai a dan dimodulokan dengan dua, hasilnya hanya mempunyai nilai 0 atau 1.
