BAB IV KURVA ELIPTIK DAN ID BASED CRYPTOSYSTEM

BAB IV KURVA ELIPTIK DAN ID BASED CRYPTOSYSTEM 4.1.

Kurva Eliptik Misalkan 𝑝 adalah bilangan prima yang lebih besar dari 3. Sebuah kurva eliptik

atas lapangan hingga dengan ukuran p dinotasikan dengan 𝐺𝐹(𝑝) dan diberikan oleh sebuah persamaan dalam bentuk 𝑦 2 = 𝑥 3 + 𝑎𝑥 + 𝑏, dimana 𝑎, 𝑏 ∈ 𝐺𝐹(𝑝). (Persamaan atas lapangan hingga dengan ukuran 2𝑛 dinotasikan sebagai 𝐺𝐹(2𝑛 ) akan sedikit berbeda, dan akan dibahas nanti.) Himpunan titik-titik pada kurva adalah kumpulan pasangan terurut (𝑥, 𝑦) yang merupakan koordinat pada lapangan sehingga x dan y memenuhi persamaan yang mendefinisikan kurva tersebut, ditambah dengan titik tambahan 𝒪 yang disebut sebagai titik tak hingga. Titik-titik ini membentuk sebuah grup abelian 𝐸 dengan operasi khusus atas 𝐺𝐹(𝑝). 𝐸 = {(𝑥, 𝑦)⋃𝒪 |(𝑥, 𝑦) memenuhi persamaan 𝑦 2 = 𝑥 3 + 𝑎𝑥 + 𝑏, 𝑥, 𝑦 ∈ 𝐺𝐹(𝑝)}.

4.2.1. Operasi Grup Pada Kurva Eliptik Misalkan 𝑃, 𝑄 ∈ 𝐸, ℓ adalah garis yang mengandung P dan 𝑄 (garis singgung jika 𝑃 = 𝑄) dan 𝑅, titik ke tiga perpotongan ℓ dengan 𝐸. Misalkan ℓ′ adalah garis yang menghubungkan 𝑅 dengan 𝒪. Maka 𝑃” + ”𝑄 adalah titik sehingga garis ℓ′ memotong 𝐸 di R, 𝒪, P” + ”Q. Catatan : untuk selanjutnya operasi penjumlahan pada grup ini akan dilambangkan dengan lambang „+‟ Asumsikan bahwa 𝑃 = (𝑥𝑃 , 𝑦𝑃 ) dan 𝑄 = (𝑥𝑄 , 𝑦𝑄 ) berada dalam kurva, 𝜆 adalah gradien garis yang melalui 𝑃 dan 𝑄, maka koordinat dari 𝑃 + 𝑄 = (𝑥𝑃+𝑄 , 𝑦𝑃+𝑄 ) adalah 𝑥𝑃+𝑄 = 𝜆2 − 𝑥𝑃 − 𝑥𝑄 dan 𝑦𝑃+𝑄 = 𝜆 𝑥𝑃 − 𝑥𝑃+𝑄 − 𝑦𝑃 , di mana

𝜆=

𝑦𝑄 − 𝑦𝑃 , 𝑗𝑖𝑘𝑎 𝑃 ≠ 𝑄 𝑥𝑄 − 𝑥𝑃 3𝑥𝑃 2 + 𝑎 , 𝑗𝑖𝑘𝑎 𝑃 = 𝑄 2𝑦𝑃 21

Titik tak hingga memainkan peranan sebagai elemen identitas, yaitu , 𝑃 + 𝒪 = 𝒪 + 𝑃 = 𝑃 untuk sebarang titik 𝑃 ∈ 𝐸. Setiap titik memiliki elemen invers tunggal – 𝑃 sehingga 𝑃 + (−𝑃) = 𝒪. Untuk 𝑃 = (𝑥𝑃 , 𝑦𝑃 ) pada kurva eliptik 𝐸 atas 𝐺𝐹(𝑝), invers penjumlahan tersebut didefinisikan dengan −𝑃 = (𝑥𝑃 , −𝑦𝑃 ). Kategori lain dari kurva eliptik didefinisikan atas lapangan hingga dengan ukuran 2𝑛 dinotasikan dengan 𝐺𝐹(2𝑛 ). Persamaan yang mendefinisikan eliptic curve atas 𝐺𝐹(2𝑛 ) adalah dalam bentuk 𝑦 2 + 𝑥𝑦 = 𝑥 3 + 𝑎𝑥 2 + 𝑏, dimana 𝑎, 𝑏 ∈ 𝐺𝐹(2𝑛 ). Operasi penjumlahan terhadap titik P dan Q adalah sebagai berikut : 𝑥𝑃+𝑄 = 𝜆2 + 𝜆 + 𝑥𝑃 + 𝑥𝑄 + 𝑎 dan 𝑦𝑃+𝑄 = 𝜆 𝑥𝑃 + 𝑥𝑃+𝑄 + 𝑥𝑃+𝑄 + 𝑦𝑃 , di mana 𝑦𝑄 + 𝑦𝑃 𝑗𝑖𝑘𝑎 𝑃 ≠ 𝑄 𝑥𝑄 + 𝑥𝑃 𝜆= 𝑦𝑃 𝑥𝑃 + 𝑗𝑖𝑘𝑎 𝑃 = 𝑄 𝑥𝑃 Invers dari titik 𝑃 = (𝑥𝑃 , 𝑦𝑃 ) ∈ 𝐸 atas lapangan biner 𝐺𝐹(2𝑛 ) didefinisikan oleh – 𝑃 = (𝑥𝑃 , 𝑥𝑃 + 𝑦𝑃 ) . Untuk kurva eliptik, operasi pada grup ditulis sebagai penjumlahan bukan perkalian. Jadi pemangkatan pada grup multiplikatif secara umum dapat disebutkan sebagai perkalian dengan skalar dalam grup kurva eliptik. Yang mana kita nyatakan sebagai 𝑟𝑃 yaitu 𝑃 + 𝑃 + ⋯ + 𝑃 sebanyak 𝑟 kali, untuk sebuah integer 𝑟.

4.2.2. Zero dan Pole Dari Fungsi Rasional Misalkan 𝑓 𝑥, 𝑦 adalah sebuah fungsi rasional pada kurva eliprik 𝐸 𝑥, 𝑦 = 0, dimana 0 ∈ 𝐺𝐹(𝑝), atau secara umum pada lapangan tempat kurva eliptik berada. Untuk titik 𝑃 ∈ 𝑓 ∩ 𝐸, 𝑃 disebut zero jika 𝑓 𝑃 = 0 dan pole jika 𝑓 𝑥, 𝑦 = ∞, kita dapat tuliskan ∞ = 0−1 . Dalam lapangan hingga, sebuah zero 𝑓 𝑃 = 0 dapat difaktorisasi menjadi 𝑓 𝑃 = 0𝑖 ∙ 𝑔(𝑃) sedemikian sehingga 𝑖 adalah sebuah bilangan bulat positif dan 𝑔 adalah fungsi rasional yang memenuhi 𝑔(𝑃) ≠ 0 dan 𝑔(𝑃) ≠ ∞. Jelas, bahwa dalam faktorisasi ini, jika 𝑔 𝑃 = 0 maka kita dapat menaikkan nilai 𝑖 sampai 𝑔(𝑃) ≠ 0; jika

22

𝑔 𝑃 = ∞ maka kita dapat mengurangi 𝑖 sampai 𝑔(𝑃) ≠ ∞. Hal ini memungkinkan karena pada lapangan hingga tidak memiliki pembagi nol. Jika kita menuliskan ∞ sebagai 0−1 , kita dapat memfaktorisasi 𝑓 𝑃 = ∞ menjadi 0−𝑖 ∙ 𝑔(𝑃) untuk sebuah bilangan bulat 𝑖 dan sebuah fungsi rasional 𝑔 yang memenuhi 𝑔 𝑃 ≠ 0 dan 𝑔(𝑃) ≠ ∞. Misalkan 𝑜𝑟𝑑𝑃 menunjukkan bilangan bulat 𝑖 atau – 𝑖, saat 𝑓(𝑃) difaktorisasi dengan metode di atas. Nilai dari 𝑜𝑟𝑑𝑃 menunjukkan seberapa „kuat‟ sebuah zero atau pole tersebut. Kita dapat menyatakan seperti ini : 𝑜𝑟𝑑𝑃 > 0 jika 𝑃 adalah sebuah zero 𝑜𝑟𝑑𝑃 < 0 jika 𝑃 adalah sebuah pole 𝑜𝑟𝑑𝑝 = 0 jika 𝑃 bukan zero atau pole (di mana 𝐸 dan 𝑓 tidak berpotongan).

4.2.3. Orde Zero pada Fungsi Linear Misalkan 𝐿: 𝑦 − 𝑢𝑥 + 𝑣 = 0 adalah sebuah garis (𝑢 ≠ 0). Sebuah zero 𝑃 = (𝑥0 , 𝑦0 ) dari 𝐿 = 0 adalah solusi terbatas yang diselesaikan dari bentuk 𝐿 ∩ 𝐸: (𝑢𝑥 + 𝑣)2 = 𝑦 2 = 𝑥 3 + 𝑎𝑥 + 𝑏 Kita bisa melihat bahwa 𝑥0 adalah akar dari persamaan (𝑢𝑥 + 𝑦)2 − 𝑥 3 + 𝑎𝑥 + 𝑏 = 0. Jelas, bahwa 0 dapat difaktorisasi menjadi

(𝑥 − 𝑥0 )𝑑 ∙ 𝑔 dengan 𝑔(𝑥0 ) ≠ 0 dan 𝑑 =

2 , 1

2 jika 𝑃 titik singgung dan 1 untuk 𝑃 yang lain. Karena itu

𝑜𝑟𝑑𝑃 𝐿 =

1 jika 𝐿 memotong 𝐸 di 𝑃 . 2 jika 𝐿 menyinggung 𝐸 di 𝑃

23

4.2.4. Orde Pole pada Fungsi Linear Sebuah garis 𝐿 = 𝑢𝑥 + 𝑣𝑦 + 𝑤 = 0 memotong 𝐸 tidak hanya di titik ketika 𝐿 pada 𝐸 menghasilkan zero, tetapi juga di titik infinity 𝒪 di mana 𝐿 pada 𝐸 menghasilkan pole. Kita dapat menuliskan E menjadi 1 1 = 3 2 𝑦 𝑥 (1 + 𝑎/𝑥 2 + 𝑏/𝑥 3 ) Karena itu 𝑥 𝑥= 𝑦

Kita tahu bahwa

𝑥 𝑦

2

∙

1 (1 + 𝑎/𝑥 2 + 𝑏/𝑥 3 )

= 0 pada titik 𝒪; dan

1 (1+⋯ )

= 1 pada titik 𝒪; karena itukita

mendapatkan 𝑜𝑟𝑑𝒪 𝑥 = −2. Lebih jauh karena

𝑦=

𝑥 𝑦

−1

∙𝑥 =

𝑥 𝑦

−3

∙

1 (1 + 𝑎/𝑥 2 + 𝑏/𝑥 3 )

Kita mendapatkan 𝑜𝑟𝑑𝒪 𝑦 = −3. Dengan mudah dapat dicek bahwa 𝑜𝑟𝑑𝒪 𝑢𝑥 = −2 dan 𝑜𝑟𝑑𝒪 𝑣𝑦 = −3 dan berlaku untuk sebarang 𝑢 ≠ 0 dan 𝑣 ≠ 0. Selain itu 𝑜𝑟𝑑𝒪 𝑢𝑥 + 𝑣𝑦 + 𝑤 = −3 asalkan 𝑣 ≠ 0. −3 𝑜𝑟𝑑𝒪 𝑢𝑥 + 𝑣𝑦 + 𝑤 = −2 0

𝑗𝑖𝑘𝑎 𝑣 ≠ 𝑜 𝑗𝑖𝑘𝑎 𝑣 = 0, 𝑢 ≠ 0 𝑢𝑛𝑡𝑢𝑘 𝑘𝑒𝑎𝑑𝑎𝑎𝑛 𝑙𝑎𝑖𝑛

24

4.2.4. Divisor Divisor adalah sebuah bentuk formal :

𝐷=

𝑛𝑃 [𝑃] 𝑃∈𝐸

di mana 𝑛𝑃 adalah sebuah bilangan bulat yang merupakan orde dari titik 𝑃 dan [𝑃] adalah simbol formal. Tanda kurung siku pada 𝑃 hanyalah cara agar tidak terjadi kebingungan membedakan [𝑃] dengan titik 𝑃. Sebagai contoh, 𝑖 𝑃 + 𝑗[𝑄] adalah sebuah divisor (bentuk formal) sedangkan 𝑖𝑃 + 𝑗𝑄 adalah sebuah titik di 𝐸. Dengan pertidaksamaan 𝑛𝑃 > 0 menyatakan bahwa titik 𝑃 adalah sebuah zero dan 𝑛𝑃 < 0 menyatakan bahwa titik 𝑃 adalah sebuah pole. Sebagai contoh, untuk 𝑃, 𝑄, 𝑅 ∈ 𝐸, 𝐷1 = 2 𝑃 + 3 𝑄 − 3[𝑅] menyatakan bahwa divisor 𝐷1 memiliki zero di 𝑃 dan 𝑄 dengan orde 2 dan 3, selanjutnya sebuah pole di 𝑅 dengan orde 3. Dan 𝐷2 = 2 𝑃 + −2𝑃 − 3[𝒪] menyatakan bahwa 𝑃 dan −2𝑃 adalah zero dengan orde 2 dan 1, dan 𝒪 adalah pole dengan orde 3 untuk divisor 𝐷2 . Kita dapat melihat bahwa tanda kurung siku berguna untuk memisahkan orde dengan titik yang dimaksud. Grup divisor pada 𝐸, dinyatakan sebagai 𝐷𝑖𝑣(𝐸), membentuk sebuah grup abelian dengan operasi penjumlahan berikut. Untuk 𝐷1 , 𝐷2 ∈ 𝐷𝑖𝑣(𝐸), jika 𝐷1 = 𝑃∈𝐸

𝑛𝑃 [𝑃] , 𝐷2 =

𝑃∈𝐸 (𝑛𝑃

𝑃∈𝐸 𝑚𝑃 [𝑃],

lalu

𝐷1 + 𝐷2 =

+ 𝑚𝑃 )[𝑃]. Untuk sebuah divisor 𝐷 =

𝑃 ∈ 𝐸 𝑛𝑃 ≠ 0

𝑃∈𝐸

𝑃∈𝐸 𝑛𝑃 [𝑃]

+

𝑃∈𝐸 𝑚𝑃 [𝑃]

=

𝑛𝑃 [𝑃] kita definisikan 𝑠𝑢𝑝𝑝 𝐷 =

sebagai pendukung dari divisor 𝐷, dan

deg 𝐷 =

𝑃∈𝐸

𝑛𝑃

menyatakan derajat dari divisor 𝐷. Sebagai contoh, jika 𝐷1 = 2 𝑃 + 3 𝑄 − 3[𝑅], 𝐷2 = 2 𝑃 + −2𝑃 − 3[𝒪], maka 𝑠𝑢𝑝𝑝 𝐷1 = 𝑃, 𝑄, 𝑅 , 𝑠𝑢𝑝𝑝 𝐷1 = 𝑃, −2𝑃, 𝒪 dan deg 𝐷1 = 2 + 3 − 3 = 2, deg 𝐷1 = 2 + 1 − 3 = 0. Mulai sekarang kita membahas hanya himpunan divisor yang berderajat nol, dilambangkan sebagai 𝐷𝑖𝑣 0 (𝐸). Misalkan 𝑓 adalah fungsi rasional dari 𝐾 × 𝐾 ke 𝐾, di 3𝑦−2𝑥−5

mana 𝐾 adalah lapangan hingga. Sebagai contoh, 𝑓 𝑥, 𝑦 = 5𝑦 +3𝑦 −2 . Evaluasi fungsi rasional 𝑓 pada titik 𝑃 = (𝑥𝑃 , 𝑦𝑃 ) di definisikan oleh 𝑓 𝑃 = 𝑓(𝑥𝑃 , 𝑦𝑃 ) dan evaluasi 𝑓

25

pada

sebuah

𝑃∈𝑠𝑢𝑝𝑝 (𝐷) 𝑓(𝑃)

divisor 𝑛𝑃

𝐷=

𝑃∈𝐸 𝑛𝑃 [𝑃]

di

definisikan

sebagai

𝑓 𝐷 =

.

Divisor dari Fungsi Rasional Sebuah divisor menyediakan representasi untuk mengindikasikan apakah sebuah titik adalah zero atau pole beserta ordenya masing-masing terhadap sebuah fungsi rasional atas kurva eliptik. Misalkan 𝑓 adalah sebuah fungsi rasional di 𝐸. Divisor dari 𝑓 adalah 𝑑𝑖𝑣 𝑓 =

𝑃∈𝐸

𝑛𝑃,𝑓 𝑃 ,

dengan 𝑛𝑃,𝑓 adalah orde dari zero atau pole dari titik 𝑃 di 𝑓. Derajat divisor dari sebuah fungsi rasional adalah nol; oleh karena itu 𝑑𝑖𝑣(𝑓) ∈ 𝐷𝑖𝑣 0 (𝐸) untuk sebarang fungsi rasional 𝑓.

Contoh: Misalkan 𝑃 = (𝑥𝑃 , 𝑦𝑃 ) ∈ 𝐸, 𝑓 𝑥, 𝑦 = 𝑥 − 𝑥𝑃 , maka 𝑑𝑖𝑣 𝑓 = 𝑑𝑖𝑣 𝑥 − 𝑥𝑃 = 𝑃 + −𝑃 − 2[𝑂]. 𝑃 dan – 𝑃 adalah zero dari 𝑓 karena hanya 2 titik tersebut yang berada di garis vertikal 𝑥 − 𝑥𝑃 = 0 dan di kurva eliptik 𝐸. Titik tak hingga 𝒪 adalah pole dengan orde 2 karena 𝑑𝑖𝑣(𝑓) ∈ 𝐷𝑖𝑣 0 (𝐸). Untuk 2 fungsi rasional, fungsi 𝑓1 dan 𝑓2 , berlaku sifat : 1. 𝑑𝑖𝑣 𝑓1 + 𝑑𝑖𝑣 𝑓2 = 𝑑𝑖𝑣 𝑓1 𝑓2 dan 2. 𝑑𝑖𝑣 𝑓1 − 𝑑𝑖𝑣 𝑓2 = 𝑑𝑖𝑣(𝑓1 /𝑓2 ). Contoh : Misalkan 𝐸 adalah kurva eliptik dengan persamaan 𝑦 2 = 𝑥 3 + 7𝑥 atas 𝐺𝐹(13). Kita punya 𝑃 = 4,1 , 𝑄 = (5,2) ∈ 𝐸 dan 𝑃 + 𝑄 = (5,11). Ambil 𝑓 𝑥, 𝑦 =

𝑦−𝑥+3 𝑥−5

. Karena

𝑃, 𝑄, − 𝑃 + 𝑄 = 5,2 = 𝑄 terdapat di garis 𝑦 − 𝑥 + 3 = 0, maka 𝑑𝑖𝑣 𝑦 − 𝑥 + 3 = 𝑃 + 𝑄 + − 𝑃+𝑄

− 3 𝒪 = 𝑃 + 2 𝑄 − 3[𝒪]. Dan juga 𝑑𝑖𝑣 𝑥 − 5 = 𝑄 +

−𝑄 + 2 𝒪 = 𝑄 + 𝑃 + 𝑄 − 2[𝒪] karena 𝑄, −𝑄 = 5,11 = 𝑃 + 𝑄 berada di garis

26

𝑥 − 5 = 0. Karena itu, kita mendapatkan 𝑑𝑖𝑣 𝑓 = 𝑑𝑖𝑣 𝑦 − 𝑥 + 3 − 𝑑𝑖𝑣 𝑥 − 5 = 𝑃 + 𝑄 − 𝑃 + 𝑄 − [𝒪]. Sebuah divisor 𝐷 ∈ 𝐷𝑖𝑣 0 𝐸 dikatakan principal jika 𝐷 = 𝑑𝑖𝑣(𝑓) untuk sebuah fungsi rasional 𝑓. Divisor principal 𝐷 =

𝑃∈𝐸

𝑛𝑃 (𝑃) mempunyai ciri-ciri

𝑃∈𝐸 𝑛𝑃 𝑃

=

0.

Contoh : misalkan 𝐷3 = 𝑃 + −𝑃 − 2[𝒪] , maka 𝐷3 memenuhi deg 𝐷3 = 0 dan 𝑃 + −𝑃 − 2𝒪 = 𝑃 − 𝑃 = 𝒪. Oleh karena itu 𝐷3 adalah principal. Faktanya 𝐷3 = 𝑑𝑖𝑣(𝑥 − 𝑥𝑃 ) untuk fungsi 𝑥 − 𝑥𝑃 . Dua buah divisor 𝐷1 , 𝐷2 ∈ 𝐷𝑖𝑣 0 (𝐸) dikatakan ekivalen (dinotasikan 𝐷1 ~𝐷2 ) jika 𝐷1 − 𝐷2 adalah principal. Untuk sebarang divisor 𝐷 = terdapat sebuah titik unik 𝑃 =

𝑅∈𝐸 𝑛𝑅 𝑅

𝑅∈𝐸 𝑛𝑅 (𝑅)

∈ 𝐷𝑖𝑣 0 (𝐸),

∈ 𝐸 sedemikian sehingga 𝐷~ 𝑃 − [𝒪].

Dengan kata lain 𝐷 dapat selalu dituliskan dalam bentuk kanonik 𝐷 = 𝑃 − 𝒪 + 𝑑𝑖𝑣(𝑓), di mana 𝑓 adalah sebuah fungsi rasional. Sekarang kita akan memperkenalkan sebuah rumus untuk menambahkan dua buah divisor dalam bentuk kanonik. Rumus ini menyediakan sebuah metode untuk menemukan fungsi rasional dengan 𝑑𝑖𝑣 𝑓 = 𝐷 untuk sebuah divisor 𝐷, dan sangat berguna untuk menghitung Pasangan Weil. Misalkan 𝐷1 , 𝐷2 ∈ 𝐷𝑖𝑣 0 (𝐸) dengan 𝐷1 = 𝑃1 − 𝒪 + 𝑑𝑖𝑣(𝑓1 ) dan 𝐷2 = 𝑃2 − 𝒪 + 𝑑𝑖𝑣(𝑓2 ). Kita asumsikan bahwa 𝑃1 + 𝑃2 = 𝑃3 . Misalkan 𝑕𝑃1 ,𝑃2 𝑥, 𝑦 = 𝑎𝑦 + 𝑏𝑥 + 𝑐 adalah persamaan garis lurus yang melalui 𝑃1 dan 𝑃2 , dan 𝑕𝑃3 (𝑥, 𝑦) = 𝑥 + 𝑑 sebuah persamaan garis vertikal yang melalui 𝑃3 . (Dengan catatan bahwa jika 𝑃1 = 𝑃2 , 𝑕𝑃1 ,𝑃2 𝑥, 𝑦 adalah garis singgung di 𝑃1 . Dan jika 𝑃3 = 𝒪, maka 𝑕𝑃3 𝑥, 𝑦 = 1.) Lalu kita dapatkan 𝑑𝑖𝑣 𝑕𝑃1 ,𝑃2 = 𝑃1 + 𝑃2 + −𝑃3 − 3[𝒪] di mana 𝑃1 , 𝑃2 , dan −𝑃3 adalah zero karena ketiga titik itu berada pada garis 𝑕𝑃1 ,𝑃2 , dan 𝑑𝑖𝑣(𝑕𝑃3 = 𝑃3 + −𝑃3 − 2[𝒪]) di mana 𝑃3 , −𝑃3 adalah zero karena keduanya berada pada garis 𝑕𝑃3 . Dari persamaan-persamaan di atas, jumlah dari divisor 𝐷1 + 𝐷2 dapat dituliskan :

27

𝐷1 + 𝐷2 = 𝑃1 + 𝑃2 − 2 𝒪 + 𝑑𝑖𝑣 𝑓1 𝑓2 = 𝑃3 − 𝒪 + 𝑑𝑖𝑣 𝑓1 𝑓2 + 𝑑𝑖𝑣 𝑕𝑃1 ,𝑃2 − 𝑑𝑖𝑣(𝑕𝑃3 ) = 𝑃3 − 𝒪 + 𝑑𝑖𝑣(𝑓1 𝑓2 𝑕𝑃1 ,𝑃2 /𝑕𝑃3 ) Persamaan akhir ini akan digunakan untuk menghitung pasangan weil.

4.2.5. Pasangan bilinear Misalkan 𝐺1 adalah sebuah grup siklis yang dibangun oleh 𝑂, dengan orde prima 𝑞, dan 𝐺2 adalah grup multiplikatif siklis dengan orde sama 𝑞. 𝑒: 𝐺1 × 𝐺1 → 𝐺2 adalah pasangan bilinear jika memenuhi sifat-sifat berikut : 1. Bilinear 𝑒 𝑃, 𝑄 + 𝑅 = 𝑒 𝑃, 𝑄 𝑒 𝑃, 𝑅 dan 𝑒 𝑃 + 𝑅, 𝑄 = 𝑒 𝑃, 𝑄 𝑒 𝑅, 𝑄

untuk setiap

𝑃, 𝑄, 𝑅 ∈ 𝐺1 . 2. Computability Terdapat algoritma yang efisien untuk menghitung 𝑒(𝑃, 𝑄) untuk semua 𝑃, 𝑄 ∈ 𝐺1 . 3. Non-degenerate Terdapat 𝑃 ∈ 𝐺1 dan 𝑄 ∈ 𝐺1 sedemikian sehingga 𝑒(𝑃, 𝑄) ≠ 1. 4.3.

Pasangan Weil Diberikan sebuah kurva eliptik 𝐸 atas lapangan hingga 𝐾, misalkan 𝑚 adalah

sebuah bilangan bulat prima adalah 𝑐𝑕𝑎𝑟(𝐾), karakteristik dari 𝐾. Sebagai contoh, 𝑐𝑕𝑎𝑟 𝐺𝐹 𝑝

= 𝑝 dan 𝑐𝑕𝑎𝑟 𝐺𝐹 2𝑚

= 2. Pasangan weil adalah fungsi

𝑒 = 𝐸[𝑚] × 𝐸[𝑚] → 𝑈𝑚 di mana 𝐸 𝑚 = {𝑃|𝑚𝑃 = 𝑂, 𝑃 ∈ 𝐸}, 𝑈𝑚 adalah grup yang anggotanya akar dari 𝑥 𝑚 = 1 di 𝐾. Pasangan weil 𝑒(𝑃, 𝑄) didefinisikan sebagai berikut. Diberikan 𝑃, 𝑄 ∈ 𝐸[𝑚], terdapat divisor 𝐷𝑃 , 𝐷𝑄 ∈ 𝐷𝑖𝑣 0 𝐸 sedemikian sehingga 𝐷𝑃 ~ 𝑃 − [𝒪] dan 𝐷𝑃 ~ 𝑄 − [𝒪]. Kemudian kita memilih titik 𝑇, 𝑈 ∈ 𝐸[𝑚] secara acak dan menetapkan 𝐷𝑃 =

28

𝑃 + 𝑇 − [𝑇] dan 𝐷𝑄 = 𝑄 + 𝑈 − [𝑈]. Dengan mudah kita bisa mengetahui bahwa 𝐷𝑃 ~ 𝑃 − [𝒪] dan 𝐷𝑄 = 𝑄 − [𝑈]. Karena 𝑚𝑃 = 𝑚𝑄 = 𝒪, maka divisor 𝑚𝐷𝑃 dan 𝑚𝐷𝑄 adalah principal dan terdapat fungsi rasional 𝑓𝑃 , 𝑓𝑄 sedemikian sehingga 𝑑𝑖𝑣 𝑓𝑃 = 𝑚𝐷𝑃 dan 𝑑𝑖𝑣 𝑓𝑄 = 𝑚𝐷𝑄 . Misalkan 𝑠𝑢𝑝𝑝 𝐷𝑃 ∩ 𝑠𝑢𝑝𝑝 𝐷𝑄 = ∅, maka pasangan weil dari titik 𝑃 dan 𝑄 didefinisikan : 𝑓 (𝐷 )

𝑒 𝑃, 𝑄 = 𝑓𝑃 (𝐷𝑄 ). 𝑄

𝑃

Pasangan weil memiliki sifat bilinear : untuk 𝑃, 𝑄, 𝑅 ∈ 𝐸[𝑚], berlaku 𝑒 𝑃 + 𝑄, 𝑅 = 𝑒 𝑃, 𝑄 𝑒(𝑄, 𝑅) dan 𝑒 𝑃, 𝑄 + 𝑅 = 𝑒 𝑃, 𝑄 𝑒(𝑃, 𝑅). Algoritma pertama untuk menghitung 𝑒(𝑃, 𝑄) adalah sebagai berikut.

Algoritma Miller

INPUT

: 𝑃, 𝑄 ∈ 𝐸[𝑚]

OUTPUT

: 𝐸(𝑃, 𝑄)

Langkah 1.

Pilih sebarang titik 𝑇, 𝑈 ∈ 𝐸 sedemikian sehingga 𝑃 + 𝑇, 𝑇, 𝑄 + 𝑈, 𝑈 berbeda. Lalu buat 𝐷𝑃 = 𝑃 + 𝑇 − [𝑇] dan 𝐷𝑄 = 𝑄 + 𝑈 − [𝑈].

Langkah 2.

Gunakan

algoritma

untuk

menghitung

𝑓𝑃 𝑄 + 𝑈 , 𝑓𝑃 𝑈 , 𝑓𝑄 𝑃 +

𝑇 , 𝑓𝑄 (𝑇), di mana 𝑓𝑃 dan 𝑓𝑄 memenuhi 𝑑𝑖𝑣 𝑓𝑃 = 𝑚𝐷𝑃 dan 𝑑𝑖𝑣 𝑓𝑄 = 𝑚𝐷𝑄 . Langkah 3.

Hitung 𝑒

𝑃, 𝑄 =

𝑓 𝑃 (𝐷𝑄 ) 𝑓 𝑄 (𝐷𝑃 )

=

𝑓 𝑃 𝑄+𝑈 𝑓 𝑄 (𝑇) 𝑓 𝑄 𝑃+𝑇 𝑓 𝑃 (𝑈)

Bagian yang sangat penting dalam Algoritma Miller adalah algoritma menghitung fungsi evaluasi 𝑓𝑃 dan 𝑓𝑄 di Langkah 2. Algoritma untuk menghitung 𝑓𝑃 (𝑆) menghasilkan 𝑓𝑃 sedemikian sehingga 𝑑𝑖𝑣 𝑓𝑃 = 𝑚𝐷𝑃 , dan menghitung 𝑓𝑃 (𝑥𝑆 , 𝑦𝑆 ) untuk 𝑆 = (𝑥𝑆 , 𝑦𝑆 ). Kita lihat kembali 𝐷𝑃 = 𝑃 + 𝑇 − [𝑇]. Untuk setiap integer 𝑘, terdapat sebuah fungsi rasional 𝑓𝑘 yang memenuhi 𝑑𝑖𝑣 𝑓𝑘 = 𝑘 𝑃 + 𝑇 − 𝑘 𝑇 − 𝑘𝑃 + [𝒪].

29

Jika 𝑘 = 𝑚, maka 𝑑𝑖𝑣 𝑓𝑚 = 𝑚 𝑃 + 𝑇 − 𝑚 𝑇 − 𝑚𝑃 + 𝒪 = 𝑚 𝑃 + 𝑇 − 𝑚[𝑇], dan 𝑓𝑃 = 𝑓𝑚 . Untuk sebarang titik 𝑅, 𝑆, misalkan 𝑕𝑅,𝑆 dan 𝑕𝑅 adalah fungsi linear, di mana 𝑕𝑅,𝑆 𝑥, 𝑦 = 0 adalah garis lurus yang melewati 𝑅, 𝑆, dan 𝑕𝑅 𝑥, 𝑦 = 0 adalah garis vertikal yang melalui 𝑅. Selanjutnya kita memiliki

𝑑𝑖𝑣 𝑓𝑘 1 +𝑘 2 = 𝑘1 + 𝑘2 𝑃 + 𝑇 − 𝑘1 + 𝑘2 𝑇 −

𝑘1 + 𝑘2 𝑃 + 𝒪

= 𝑘1 𝑃 + 𝑇 − 𝑘1 𝑇 − 𝑘1 𝑃 + 𝒪 +𝑘2 𝑃 + 𝑇 − 𝑘2 𝑇 − 𝑘2 𝑃 + 𝒪 + 𝑘1 𝑃 + 𝑘2 𝑃 + − 𝑘1 + 𝑘2 𝑃 − 3[𝒪] −{ (𝑘1 + 𝑘2 𝑃 + − 𝑘1 + 𝑘2 𝑃 − 2[𝒪]} = 𝑑𝑖𝑣 𝑓𝑘 1 + 𝑑𝑖𝑣 𝑓𝑘 2 + 𝑑𝑖𝑣 𝑕𝑘 1 𝑃,𝑘 2 𝑃 − 𝑑𝑖𝑣(𝑕(𝑘 1 +𝑘 2 )𝑃 ) dan karenanya 𝑓𝑘 1 +𝑘 2 =

𝑓𝑘 1 𝑓𝑘 2 𝑕𝑘 1 𝑃𝑘 2 𝑃 . 𝑕(𝑘 1 +𝑘 2 )𝑃

Persamaan di atas adalah persamaan rekursif dengan kondisi awal 𝑓0 = 1 dan 𝑓1 =

𝑕 𝑃 +𝑇 𝑕 𝑃 ,𝑇

karena 𝑑𝑖𝑣 𝑓1 = 𝑃 + 𝑇 − 𝑇 − 𝑃 + [𝒪] = 𝑃+𝑇 + − 𝑃+𝑇

−2 𝒪

−{ 𝑃 + 𝑇 + − 𝑃 + 𝑇

− 3[𝒪]}

= 𝑑𝑖𝑣 𝑕𝑃+𝑇 − 𝑑𝑖𝑣 𝑕𝑃,𝑇 .

Berdasarkan persamaan rekursif di atas, cara konvensional dengan metode double and add adalah metode yang diusulkan untuk mengevaluasi fungsi rasional 𝑓𝑃 pada titik 𝑆 yang diberikan, di mana 𝑓𝑃 memenuhi 𝑑𝑖𝑣 𝑓𝑃 = 𝑚 𝑃 + 𝑇 − 𝑚 𝑇 . Algoritma yang dimaksud dengan algoritma double and add adalah sebagai berikut :

30

Algoritma Double and Add (Langkah 2, Algoritma Miller) INPUT

: titik 𝑃, 𝑇, 𝑆 dan ordenya 𝑚 =

OUTPUT

: 𝑓𝑚 𝑆 = 𝑓𝑃 (𝑆)

𝑓1 ←

𝑛 −1 𝑖 𝑖=0 𝑏𝑖 2

dengan 𝑏𝑖 ∈ 0,1 , 𝑏𝑛 −1 = 1

𝑕𝑃+𝑇 (𝑆) ; 𝑕𝑃,𝑇 (𝑆)

𝑓 ← 𝑓1 ; 𝑍 ← 𝑃; for 𝑗 ← 𝑛 − 2 , 𝑛 − 3 , … ,0 do 𝑓 ← 𝑓2

𝑕𝑍,𝑍 (𝑆) ; 𝑍 ← 2𝑍; 𝑕2𝑍 (𝑆)

if 𝑏𝑖 = 1 then 𝑕

(𝑆)

𝑓 ← 𝑓1 𝑓 𝑕 𝑍,𝑃 (𝑆) ; 𝑍 ← 𝑍 + 𝑃; 𝑍+𝑃

endif endfor return 𝑓

4.4.

ID Based Cryptosystem Skema ID based encryption (IBE) dengan menggunakan pemetaan bilinear yaitu

pasangan weil atas kurva eliptik pertama kali dicetuskan oleh Boneh dan Franklin. Pemetaan bilinear mentransformasi sepasang anggota di grup 𝐺1 dan memetakannya ke sebuah anggota di 𝐺2 dalam sebuah cara yang memenuhi beberapa kriteria. Kriteria yang paling penting adalah kebilinearan itu sendiri, di mana ia haruslah bilinear untuk setiap pasangan anggota dari domain yang dimasukkan. Untuk membuat sebuah ID based cryptosystem diperlukan sebuah Private Key Generator yang berfungsi untuk menentukan s yaitu master key yang dijaga kerahasiaannya, lalu mengumumkan informasi-informasi yang diperlukan termasuk persamaan kurva eliptik yang akan dipakai, titik basis 𝑃, kunci publik 𝑠𝑃, dan beberapa fungsi hash yang dipakai. Setiap pemakai memiliki kunci publik dinotasikan 𝐾𝑈 = 𝑄𝐼𝐷 yaitu sebuah titik pada kurva eliptik yang berkorespondensi dengan 𝐼𝐷 nya dan diketahui oleh semua pengguna. Kunci pribadi dinotasikan 𝐾𝑅 = 𝑠𝑄𝐼𝐷 , dimana 𝑠 diperoleh dari PKG.

31

Misalkan Anita ingin mengirimkan pesan 𝑀 kepada Budi maka enkripsi dan dekripsinya adalah sebagai berikut : Anita ingin mengirim pesan 𝑀. Ia memilih integer 𝑟 random lalu mengirim : (𝑈, 𝑉) = (𝑟𝑃, 𝑀 ⊕ 𝑕(𝑒(𝑄𝐼𝐷 , 𝑠𝑃)𝑟 )) Ketika Budi menerima (𝑈, 𝑉) kemudian dia menghitung : 𝑀 = 𝑉 ⊕ 𝑕(𝑒(𝑠𝑄𝐼𝐷 , 𝑈)). Dengan 𝑕 merupakan fungsi hash yang diumumkan PKG dan 𝑒 adalah pasangan weil. Hal ini dapat terjadi karena sifat kebilinearan dari pasangan weil, yaitu 𝑒 𝑠𝑄𝐼𝐷 , 𝑈 = 𝑒 𝑠𝑄𝐼𝐷 , 𝑟𝑃 = 𝑒(𝑄𝐼𝐷 , 𝑃)𝑠𝑟 = 𝑒(𝑄𝐼𝐷 , 𝑠𝑃)𝑟 .

32