KONSTRUKSI HUKUM GRUP KURVA ELIPTIK ATAS
IBRAHIM AMIN G54104053
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2010
ABSTRACT IBRAHIM AMIN. Construction of Group Laws on Elliptic Curves Upon SUGI GURITMAN dan NUR ALIATININGTYAS. Elliptic curves upon
. Supervised by
can be divided in two cases, i.e. supersingular and non-
supersingular case. Based on group laws on elliptic curves, a new arithmetic upon
can be
formulated as an addition process of two random points on the curve. This addition process can then be applied to the ElGamal algorithm. Key words : Elliptic curves, algorithm.
, supersingular, non-supersingular, group laws, ElGamal
ABSTRAK IBRAHIM AMIN. Konstruksi Hukum Grup Kurva Eliptik Atas GURITMAN dan NUR ALIATININGTYAS. Kurva eliptik atas
. Dibimbing oleh SUGI
dibagi menjadi dua kasus yaitu supersingular dan non-
supersingular. Berdasarkan hukum grup kurva eliptik didapatkan aritmatik baru dari kurva eliptik atas
berupa proses adisi pada dua titik acak pada kurva baik pada untuk titik yang sama
maupun berbeda. Kemudian dari proses adisi tersebut diaplikasikan pada algoritme ElGamal. Kata Kunci : Kurva eliptik, ElGamal.
, supersingular, non-supersingular, hukum grup, algoritme
KONSTRUKSI HUKUM GRUP KURVA ELIPTIK ATAS
Skripsi Sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Oleh : IBRAHIM AMIN G54104053
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2010
Judul
: Konstruksi Hukum Grup Atas
Nama
: Ibrahim Amin
NRP
: G54104053
Menyetujui, Pembimbing I
Pembimbing II
Dr. Drs. Sugi Guritman, MS NIP. 19620927 199203 1 004
Dra. Nur Aliatiningtyas, MS NIP. 19610104 198803 2 002
Mengetahui, Ketua Departemen Matematika Institut Pertanian Bogor
Dr. Berlian Setyawati, MS NIP. 131 835 248
Tanggal Lulus :
RIWAYAT HIDUP Penulis dilahirkan di Tenggarong, Kutai Kartanegara, Kalimantan Timur pada tanggal 17 april 1986 dari pasangan Hadi Haryanto dan Ema Sahani. Penulis merupakan putra pertama dari lima bersaudara. Penulis menyelesaikan masa studinya di SD Muhammadiyah Kota Tenggarong Kabupaten Kutai Kartanegara, kemudian melanjutkan ke Madrasah Tsanawiyah PPKP(Pondok Pesantren Karya Pembangunan) Ribathul Khail Kota Tenggarong Kabupaten Kutai Kartanegara selama tiga tahun, kemudian melanjutkan kembali ke Madrasah Aliyah PPKP(Pondok Pesantren Karya Pembangunan) Ribathul Khail Kota Tenggarong Kabupaten Kutai Kartanegara selama tiga tahun. Penulis lulus dari Madrasah Aliyah PPKP(Pondok Pesantren Karya Pembangunan) Ribathul Khail pada tahun 2004 dan pada tahun yang sama penulis melanjutkan pendidikan sarjana strata satu di Departemen Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA) Institut Pertanian Bogor (IPB) melalui jalur Beasiswa Utusan Daerah (BUD). Selama masa perkuliahan berjalan, penulis pernah mengikuti berbagai pelatihan diantaranya pembelajaran Corel Draw untuk mahasiswa Tingkat Persiapan Bersama (TPB) IPB. Penulis juga aktif dalam organisasi kemahasiswaan sebagai anggota departemen Keilmuan Gugusan Mahasiswa Matematika (GUMATIKA) IPB tahun 2005/2006,sekretaris umum Dewan Perwakilan Mahasiswa(DPM) 2006/2007, anggota divisi keilmuan SERUM-G IPB tahun 2007/2008. Penulis juga tergabung dalam organisasi mahasiswa daerah (OMDA) yaitu Forum Mahasiswa Beasiswa Utusan Daerah Kutai Kartanegara (FMBUD KUKAR) IPB dan diantaranya menjadi anggota divisi PSDM pada tahun 2005-2008. Selain itu penulis pernah mengikuti berbagai kegiatan dan seminarseminar di dalam kampus baik yang berupa ilmu pengetahuan umum maupun religi, diantaranya penulis berlaku sebagai panitia dalam pesta Sains di IPB pada tahun 2007.
KATA PENGANTAR Syukur Alhamdulillah penulis ucapkan kepada Allah SWT yang ilmunya maha luas dan nikmatnya yang tak terbalas yang dengan izinnya pula lah penulis mampu menyelesaikan skripsi yang merupakan salah satu syarat kelulusan penulis agar penulis dapat lulus dari Departemen Matematika IPB. Dalam penyelesaian skripsi ini, penulis banyak dibantu oleh berbagai pihak. Terima kasih penulis sampaikan kepada kedua orangtua beserta saudara-saudara penulis yang telah memberikan bantuan berupa do’a, moril dan materil. Tak lupa ucapan terima kasih penulis sampaikan kepada bapak Sugi Guritman dan ibu Nur Aliatiningtyas sebagai pembimbing tugas akhir yang sangat semangat dalam membimbing penulis. Terima kasih juga penulis ucapkan kepada seluruh staf Departemen Matematika IPB yang juga berperan dalam penyelesaian tugas akhir ini. Rekan-rekan seperjuangan di Forum Mahasiswa Beasiswa Utusan Daerah Kutai Kartanegara (FMBUD KUKAR) IPB. Sahabat-sahabat BBB(Slamet Riyadi, Ecka S, Syahrul Anwar, Nur Azizah, Desi Dwi, Rizki S N) dan DOTA(Deny Irawan, Hery Mulyono, M Izzudin, Tb Gamma, Adung Surya P, Haryanto, dll) yang selalu mendukung dan menyemangati penulis. Teman-teman di Matematika 41 terutama Rangga Nakasumi, Mahar M, Ika dan yang lainnya yang insya Allah setia selalu menemani dan menghibur penulis sehingga penulis menjadi semangat luar biasa. Irsyad Ramli rekan sepenelitian yang selalu membantu dalam pembuatan program. Dan juga teman-teman penulis yang lain yang tidak dapat dituliskan satu per satu karena sangat banyak. Demikian skripsi ini penulis buat, semoga dapat bermanfaat untuk kita semua terutama untuk perkembangan teknologi di Indonesia. Kritik dan saran yang membangun sangat penulis harapkan untuk kemajuan teknologi mengenai aplikasi agar dapat lebih berkembang lagi. Semoga Allah SWT senantiasa melimpahkan rahmat dan karunianya untuk kita semua. Amiin. Bogor, September 2010
Ibrahim Amin
DAFTAR ISI Halaman DAFTAR ISI............................................................................................................................ vii DAFTAR GAMBAR ............................................................................................................... viii DAFTAR LAMPIRAN ............................................................................................................ viii PENDAHULUAN.................................................................................................................... 1 Latar Belakang .................................................................................................................... 1 Tujuan ........................................................................................................................... 1 LANDASAN TEORI ............................................................................................................... Grup .................................................................................................................................... Grup Siklik.......................................................................................................................... Ring..................................................................................................................................... Lapangan ............................................................................................................................. Pengenalan Kurva Eliptik.................................................................................................... Penyederhanaan Persamaan Weierstrass............................................................................. Hukum Grup Kurva Eliptik................................................................................................. Algoritme ElGamal .............................................................................................................
1 1 1 2 2 2 3 3 4
PEMBAHASAN ...................................................................................................................... Aritmatik Kurva Eliptik ...................................................................................................... Penyandian Kunci Publik ElGamal Digeneralisasi ............................................................. Konversi Algoritme ElGamal Modulo p Kedalam Kurva Eliptik ElGamal ............................................................................................... 7 Algoritme Enkripsi dan Deskripsi Kurva Eliptik ElGamal ................................................. Program Enkripsi dan Dekripsi Kurva Eliptik ElGamal .....................................................
5 5 7 8 8
KESIMPULAN DAN SARAN ................................................................................................ 9 Kesimpulan .............................................................................................................................. 9 Saran ........................................................................................................................................ 9 DAFTAR PUSTAKA .............................................................................................................. 10 LAMPIRAN............................................................................................................................. 11
vii
DAFTAR GAMBAR 1 2 3 4
Adisi + = ………… ...................................................................................................... 3 Adisi + = ...................................................................................................................... 4 Sifat asosiatif: (P + Q) + R...................................................................................................... 4 Sifat asosiatif: P + (Q + R)...................................................................................................... 4
DAFTAR LAMPIRAN
1 Program Aritmatik
............................................................................................................ 12
2 Program Aritmatik Kurva Eliptik Atas
............................................................................. 17
3 Program Kurva Eliptik ElGamal Atas
.............................................................................. 19
viii
I PENDAHULUAN 1.1 Latar Belakang Keamanan informasi (information security) merupakan bagian yang sangat penting dari sebuah sistem dalam sebuah jaringan komputer terutama yang terhubung dengan internet. Suatu sistem yang mempermudah dan memanjakan pengguna tidak akan berguna tanpa didukung dengan sistem keamanan yang tinggi. Oleh karena itu, informasi atau data rahasia yang akan dikirim harus disandikan agar tidak dapat dibaca oleh orang lain yang tidak berkepentingan. Untuk mengamankan informasi rahasia tersebut diperlukan suatu teknik pengamanan yakni teknik kriptografi. Kriptografi adalah studi teknik matematika yang berhubungan dengan aspek keamanan informasi seperti kerahasiaan, integritas data, otentikasi entitas, dan otentikasi data asli (Menezes,
1997). Algoritme kriptografi adalah suatu fungsi matematika yang digunakan untuk enkripsi (menyandi) dan dekripsi (membuka sandi) (Schneier, 1996). Salah satu teknik dalam mengamankan suatu informasi atau data rahasia adalah dengan menggunakan algoritme ElGamal. Algoritme ini sebenarnya bekerja dalam grup ℤ , tetapi algoritme ElGamal bisa dikonversi kedalam himpunan yang mempunyai grup siklik. Salah satu himpunan tersebut adalah grup siklik dari kurva eliptik. 1.2 Tujuan Tujuan dari penulisan ini adalah untuk menemukan aritmatik baru dalam dan kurva eliptik atas mensimulasikannya dalam algoritme ElGamal kurva eliptik.
II LANDASAN TEORI 2.1 Grup Definisi 2.1.1 Diberikan sebarang himpunan tak kosong G dan operasi biner ∗ pada G. Himpunan G disebut grup terhadap operasi ∗ jika memenuhi : a. Operasi biner pada G bersifat asosiatif. ∗ ( ∗ ) = ( ∗ ) ∗ , ∀ , G, ∈ b. Terdapat elemen identitas ∈G untuk ∗ pada G sehingga berlaku : ∗ = ∗ = , ∀G ∈ c. Untuk setiap ∈G terdapat elemen invers, yaitu ∈ G sehingga berlaku ∗ = ∗ = .
(Fraleigh 1994) 2.2 Grup Siklik Definisi 2.2.1 Misalkan G grup dan ∈G dan n bilangan bulat positif, maka : = …, (sebanyak n kali) a. b. = … , (sebanyak n kali). = . c. (Aliatiningtyas 2002) Teorema 2.2.1 Jika G suatu grup dan a ∈ G, maka untuk setiap bilangan bulat m dan n berlaku hukum eksponen : a. = b. ( ) c. =( ) =( ) (Guritman 2004)
Definisi 2.2.2 Misalkan G grup dan a ∈ G. Order dari a (dinotasikan o(a)) didefinisikan sebagai bilangan bulat = , jika positif terkecil m sehingga bilangan tersebut ada. Jika tidak terdapat bilangan m yang demikian, maka order dari a adalah tak hingga atau nol. (Aliatiningtyas 2002) Definisi 2.2.3 Misalkan G grup. Jika ada ∈G ( disebut generator) elemen sehingga G=< >= { | ∈ ℤ} maka G disebut grup siklik (cyclic group). Jika G berhingga dan berorder m, maka dapat ditunjukkan =<
>= { =
=<
>= {
,
, ,…
}.
m,
∈ ℤ}
dapat
Jika G adalah grup aditif, maka dapat dituliskan
dan jika berorder ditunjukkan =<
>= {
=
|
,
maka
, ( , …−, ) }
(Guritman 2004)
2
2.3 Ring Definisi 2.3.1 Himpunan R dengan operasi penjumlahan + dan operasi perkalian ∙ disebut ring jika memenuhi aksioma-aksioma berikut. a.
grup komutatif. b. Operasi perkalian bersifat asosiatif. c. Hukum distributif kiri berlaku ∀ , , ∈ (, + ) = + d. Hukum distributif kanan berlaku ∀ , , ∈( ,+ ) = + Elemen identitas terhadap + dinotasikan dengan 0 dan disebut elemen nol. Selanjutnya, a. Jika operasi perkalian bersifat komutatif, ∀ , ∈ , = maka R disebut ring komutatif. b. Jika ada elemen identitas di bawah operasi perkalian (elemen ini disebut unsur kesatuan, dinotasikan dengan 1 dan disingkat dengan unkes), ∀ ∈ , ∃1 ∈ , ∙ 1 = 1 ∙ = maka R disebut ring dengan unkes. (Aliatiningtyas 2002) 2.4 Lapangan (Field) Definisi 2.3.1 Suatu ring yang komutatif, ada unkes dan setiap elemen tak nolnya mempunyai invers (perkalian) disebut lapangan (field). (Aliatiningtyas 2002) Berdasarkan definisi diatas dapat ditunjukkan sebagai berikut. tak Suatu lapangan adalah himpunan kosong yang dilengkapi dengan dua operasi biner yaitu operasi penjumlahan + dan operasi multiplikasi ∙ yang memenuhi a. < , +>merupakan grup abelian dengan elemen identitas (penjumlahan) 0. b. < ∗ ,∙> dimana ∗ = − {0}merupakan grup abelian dengan elemen identitas (multiplikasi) 1. c. Untuk setiap a,b,c ∈ berlaku sifat distributif, yaitu ( + ) ∙ = ∙ + ∙ ∙( + ) = ∙ + ∙
Salah satu contoh field adalah . adalah himpunan Dalam teori matematis semua polinomial-polinomial berderajat − 1yang dinyatakan secara paling banyak = { 0 + 1 +⋯+ unik sebagai −1 | ∈ ℤ }. Operasi dalam meliputi −1 3 operasi penjumlahan dan perkalian. Operasi penjumlahan didefinisikan sebagai
penjumlahan antar pasangan elemen dan dimodulokan dengan 3. Untuk operasi perkalian didefinisikan sebagai perkalian polinomial modulo ( ,) yaitu mengambil ( )dan ( )setelah sisa dari perkalian dengan dibagi dengan ( .)Himpunan definisi operasi diatas merupakan field. Representasi lain adalah field yang elemen-elemennya merupakan vektor dari ℤ yang dapat dinyatakan sebagai = ]| ∈ ℤ }, yang akan {[ , , , … digunakan untuk konstruksi program kurva eliptik. Contoh operasi penjumlahan dan adalah berikut. perkalian dalam 1.
Operasi Penjumlahan
2.
122 1+2 102⊕ ⟺ 1+ 221 2+2 Operasi Perkalian
+2 2 ⨁ +
1 2 2 ⟺ (1 + 2 + 2 )(1 + 2 ) 102⊗ =2 + + + 211 000 1+2 +2 122 ⊕ = 1+2 + + + 1 2 1 1 1 ≅ (2 + 2 )( + 2 + 1)
(Ilham 2009) Operasi penjumlahan dan perkalian akan digunakan dalam program kurva eliptik atas . 2.5 Pengenalan Kurva Eliptik Definisi 2.4.1 Suatu kurva eliptik atas field didefinisikan sebagai kurva dengan persamaan ≔
+
+ + ….(1)
=
+
+
, , , , ∈ dan Δ ≠ 0 dimana merupakan diskriminan dari yang di definisikan sebagai berikut: Δ=− − 8 − 27 + 9 = +4 =2 + = +4 = +4 − + − Persamaan (1) disebut dengan persamaan Weierstrass dan kurva eliptik dinotasikan ( ).
3
( ) ={( , ) ∈
+ −
× |
− −
(Hankerson et al 76, 2004) 2.6 Penyederhanaan Persamaan Weierstrass
Definisi 2.5.1 Dua kurva eliptik dan atas field ∶ + + = + + + ∶ + + = + + + dikatakan isomorfik atas jika ada u, r, s,t ∈ , u ≠ 0 sehingga pengubahan variabel ( , )→( + , + + ) mentransformasikan dan . Transformasi yang demikian disebut pengubahan variabel sah. Terkait dengan kriptografi, kurva eliptik ∶ + + = + + + dikenakan atas field berhingga dimana p prima. Berdasarkan Definisi 2.5.1, berikut ini diberikan 3 kelompok besar kurva eliptik yang dibedakan atas field dasar . 1. Jika ≠ 2dan ≠ 3, maka pengubahan variabel sah dinyatakan ( , )→(
,
−
) Mentransformasikan menjadi = + + dimana , ∈ dan diskriminan kurva Δ = −16(4 + 27 ).
2. Jika = 2, maka diperhatikan 2 kasus: Jika ≠ 0, maka pengubahan variable sah dinyatakan ( , )→(
+ ,
+
dimana , , ∈ dan diskriminan kurva Δ = . Kurva dalam kelompok ini disebut supersingular kasus biner.
+ − = 0}⋃{∞}
)
Mentransformasikan menjadi + = + + dimana , ∈ dan diskriminan Δ= . Kurva dalam kurva nonkelompok ini disebut supersingular kasus biner. Jika = 0, maka pengubahan variable sah dinyatakan ( , )→( + , ) Mentransformasikan menjadi + = + +
3. Jika = 3, maka diperhatikan 2 kasus: Jika ≠ − , maka pengubahan variable sah dinyatakan ( , )→( + , + + +
) dimana = + dan = − mentransformasikan menjadi = + + dimana , ∈ dan diskriminan . Kurva dalam kurva Δ = − nonkelompok ini disebut supersingular kasus terner. Jika = − , maka pengubahan variable sah dinyatakan ( , )→( , + + ) mentransformasikan menjadi = + + dimana , , ∈ dan diskriminan kurva Δ = − . Kurva dalam kelompok ini disebut supersingular kasus terner. (Hankerson et al 78, 2004)
2.7 Hukum Grup Kurva Eliptik Misalkan E adalah kurva eliptik yang didefinisikan atas . Dengan mengambil = ℝ, misal E diambil dua titik yang berbeda = ( , ), = ( , ). Maka garis ⃖ ⃗ memotong kurva dititik ketiga ′ = ( , ′) kemudian diperoleh titik = ( , ). Titik ini merupakan hasil dari pencerminan titik R’ terhadap sumbu x. Proses ini disebut dengan proses adisi titik. Adisi titik dari P dan Q dinotasikan ( , ) + = =
Gambar 1. Adisi
+
=
Jika ⃖ ⃗ sejajar dengan sumbu-y, maka titik yang ketiga didefinisikan sebagai titik di tak-hingga, notasi ∞, sehingga
4
Jika , maka kondisi ini disebut Adisi Titik yang sama dan disebut pendobelan (doubling). ). Dinotasikan
Gambar 2. Doubling Jika diambil titik dan
, akan dibuktikan memenuhi sifat asosiatif. Dalam hal ini akan dilakukan sebanyak dua tahap. Tahap pertama menyelesaikan operasi sisi sebelah kiri yaitu kerjakan . Seperti terlihat pada gambar 3, .
Demikian pula dengan tahap kedua yaitu menyelesaikan ikan operasi sisi sebelah kanan yang ang sama seperti pada tahap pertama, bedanya yang dilakukan pertama kali adalah . Hasil tahapan ini dapat dilihat pada gambar 4. Dari uraian diatas, operasi perasi adi adisi titik pada himpunan semua titik pada kurva dan titik di tak-hingga dibawah operasi penjumlahan merupakan struktur grup yang disebut juga dengan grup kurva eliptik. Dalam hal ini, adalah elemen identitas. Untuk setiap R pada E, negatif dari R yang dinotasikan dengan merupakan titik pada E yang merupakan hasil pencerminan dari R terhadap sumbu sumbux. Operasi grup kurva eliptik cukup mudah diilustrasikan secara geometri ketika E didefinisikan atas bilangan real seperti gambar di atas. Akan tetapi, jika E didefinisikan terhadap field berhingga dimana p adalah karakterist karakteristik prima, maka secara geometri akan tersamarkan dan sulit dibayangkan. Oleh sebab itu, yang hanya bisa dilakukan adalah dengan pendekatan aksiomatik ksiomatik (aljabar). Sedangkan metodenya disebut dengan aritmetik kurva eliptik. (Hankerson et al 79, 2004) 2.8 Algoritme ElGamal
Gambar 3. Sifat asosiatif: Kemudian tambahkan titik R yang diperoleh dengan titik T dengan menghubungkan kedua titik tersebut akan diperoleh perpotongan dengan kurva eliptik tepat disatu titik, sebut –S. Titik –S direfleksikan dengan sumbu x diperoleh titik S yang merupakan hasil terakhir dari penjumlahan.
Gambar 4. Sifat asosiatif:
Algoritme penyandian ElGamal El merupakan salah satu jenis kriptografi kunci publik. Algoritme ini aritmatiknya berbasis intejer grup siklik pada grup multiplikatif . Ada tiga algoritma untuk ntuk penyandian kunci Publik ElGamal. amal. Algoritma 1 untuk pembangkitan kitan kunci, Algoritma 2 untuk enkripsi kunci publik, ublik, dan Algoritma 3 untuk dekripsi. Misalkan A mengirimkan pesan kepada B. Pesan tersebut ingin disandikan. Maka yang akan dilakukan adalah 1. Pembangkitan Kunci B membuat sebuah kunci publik dan kunci pribadi. Hal yang dilakukan adalah a. Dengan prima acak yang besar, kemudian dilakukan pembangkitan generator dari grup dengan intejer intejerintejer modulo p. b. Memilih suatu intejer acak a, dengan c. Menghitung
5
d. Kunci publik B adalah ( , , ) dan kunci pribadi B adalah a. Dalam algoritme pembangkitan kunci pada penyandian kunci public ElGamal, dijelaskan membangkitkan suatu bilangan prima p yang besar dan generator dari grup . 2. Enkripsi A menyandikan atau me-enkripsi sebuah pesan t ke B. Langkah-langkah yang harus dilakukan oleh A adalah a. Memperoleh kunci publik otentik ( , ,. ) b. Merepresentasikan pesan tersebut sebagai suatu intejer t pada interval [0, ].
c. Memilih intejer acak k, dimana ∈ . d. Menghitung = mod dan mod . e. Mengirim siferteks = ( , ke ) B.
=
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 t dengan menghitung mod . (Menezes et al 295, 1996)
III PEMBAHASAN
3.1 Aritmatik Kurva Eliptik Dalam skripsi ini akan ditunjukkan dari aritmatik kurva eliptik dalam hukum grup yang diberikan pada subbab 2.7. Hukum grup kurva non-supersingular
eliptik
Persamaan kurva eliptik atas supersingular ∶ = + dengan a,b ∈
+ …(2) dan ∆= −
Dimisalkan himpunan ( ) = {( , ) ∈ | × = + + } ∪ {∞}
atas
= + + …(3) = + + …(4) = + + …(5) Di lain pihak, berdasarkan definisi adisi , , titik secara geometri, maka ( , − ) adalah segaris. Jika gradiennya dimisalkan dengan , maka diperoleh persamaan
non-
≠ 0.
) Penjelasan hukum grup pada ( non-supersingular. 1. Dalam persamaan (2) dilakukan penyederhanaan dengan mengambil ≠ 0,maka (0,0) dijamin tidak terletak pada kurva sehingga bisa digunakan untuk merepresentasikan titik di takhingga ∞ = (0,0). Akibatnya, ∀ = ) dan ∀ , ∈ ( , )∈( berlaku + ∞ = ( + 0, + )0 =( , )= 2. Terkait dengan representasi ∞ = (0,0), ) dan − = ( , − ) , ∀ ∈ ( ∀ , ∈ berlaku + (− ) = (0,0) = ∞ 3. Pembuktian + =( , ) untuk ≠ .Perhatikan bahwa , ,( , ) adalah tiga titik pada , maka berlaku tiga persamaan
=
=
−
=(
=
…(6)
kemudian dari persamaan (3), (5) dan (6) diperoleh − ⇔ − ⇔( −
−
=(
−
) + (
)
+
)
− ) + ( + )…(7) dan dari analogi persamaan (7) juga didapat (
) =(
−
)+ (
−
)
=(
(
− ) + + )…(8)
dari persamaan (7) dan (8) didapat (
−
)
= ( − + (
)+ − − )…(9)
dari persamaan (6) dan (9) didapat = + + dan didapat = + − − =( − ) −
+
6
4. Pembuktian + =( , ), dan ( , ) terletak pada E, maka = + + …(10) = + + …(11) dan Di lain pihak, berdasarkan definisi adisi titik secara geometri, maka garis dari P ke titik ( , − ) merupakan garis singgung kurva di titik P. jika gradiennya dimisalkan dengan , maka
dan 3 = ⟺
= |( , ) +2 |( 2 = |( , )
,
,) ( ( ,
)
)
,
)
=
…(12)
dari persamaaan (10), (11) dan (12) diperoleh − = ( − )+ ( − )⇔ − =( − ) + ( + ) − − =( − ) + + ⇔ − =( − ) ⟺ + + ⟺ (− − ) =( − ) + ( − ) ⟺ = − + = + − ⟺ =( − ) −
Dari uraian diatas diperoleh aritmatik sebagai berikut. 1. Titik di tak hingga yang diambil ∞ = (0,0). ), = ( , dan ) 2. ∀ ∈ ( − = ( , − , )∀ , ∈ 3. + =( , ) dengan ≠± = − − − dan ⇔ =( − ) − dimana = dan , ∈ i=1,2,3. 4. 2 =( , ) ⇔ = + − dan =( − ) − dimana = dan , ∈ i=1,2,3.
Berdasarkan aritmatik diatas ( ) merupakan grup dengan elemen identitas ∞ = (0,0) dan elemen invers − = ( , − .)
∶
=
+
+ ...(13)
dan ∆= − dengan a, b ∈ dimisalkan himpunan ) = {( , ) ∈ = +
(
= (
Hukum grup kurva eliptik supersingular Persamaan kurva eliptik atas supersingular
× +
atas
≠ 0,
| } ∪ {∞}
) Penjelasan hukum grup pada ( supersingular. 1. Dalam persamaan (13) dilakukan penyederhanaan dengan mengambil ≠ 0, maka (0,0) dijamin tidak terletak pada kurva sehingga bisa digunakan untuk merepresentasikan titik di takhingga ∞ = (0,0).Akibatnya, ∀ = ) ( , )∈( dan ∀ , ∈ , berlaku + ∞ = ( + 0, + )0 =( , )= 2. Terkait dengan representasi ∞ = (0,0), ) dan − = ∈ ( untuk setiap berlaku ( , − ,) ∀ , ∈ + (− ) = (0,0) = ∞ 3. Pembuktiaan + =( , ) untuk ≠ .Perhatikan bahwa , ,( , ) adalah tiga titik pada , maka berlaku tiga persamaan = + + …(14) = + + …(15) = + + …(16) di lain pihak, berdasarkan definisi adisi , , titik secara geometri, maka ( , − ) adalah segaris.Jika gradiennya dimisalkan dengan , maka diperoleh persamaan =
=
=
…(17)
kemudian dari persamaan (14), (16) dan (17) diperoleh = ( − )+ ( − ) − ⇔ =( − ) + − ⇔ ( − ) =( − ) + …(18) −
dan dari analogi persamaan (18) didapat (
−
)
=(
−
) + …(19)
7
dari persamaan (18) dan (19) didapat (
−
= (
)
)+
−
−
…(20)
dari persamaan (17) dan (20) didapat = + + dan didapat = − − =( − ) −
4. Pembuktian + =( , ), dan ( , ) terletak pada E, maka = + + …(21) = + + …(22) dan di lain pihak, berdasarkan definisi adisi titik secara geometri, maka garis dari P ke titik ( , − ) merupakan garis singgung kurva di titik P. jika gradiennya dimisalkan dengan , maka
dan = |(
|(
|(
− = ,) (
,) (
,) (
,
)
,
,
)
=
)
=
⟺
− − =
= − …(23)
dari persamaaan (21), (22) dan (23) diperoleh − = ( − )+ ( − ) − =( − ) + ⇔ − ⇔ ( − ) =( − ) − ⟺ ( − + )=( − ) ⟺ (− − ) = ( − ) ⟺ = − ⟺ = + dan =( − ) − Dari uraian di atas diperoleh aritmatik sebagai berikut. ) ∞ ∈ ( 1. Titik di tak-hingga merupakan unsur identitas dan =( , ) merupakan titik acak pada kurva. + ∞ = ( + 0, + )0 ) dan =( , )= ,∀ ∈ ( , ∈ 3 2. Dengan representasi ∞ = (0,0) dan − = ( ,− . ) + (− ) = (0,0) = ∞, ∀ , ∈ 3. Untuk setiap =( , ), =( , ) ∈ ) dengan ( ≠ ± maka + =( , ) ⇔ = − − dan = ( − ) −
dimana i=1,2,3.
=
. dan
,
∈
4. Untuk setiap =( , ) ∈ ( ≠ − , berlaku + =( , ) = + dan ⇔ =( − ) − dimana = − dan , ∈
) dan
i=1,2,3.
3.2 Penyandian Kunci Publik ElGamal Digeneralisasi Setelah kita menemukan aritmatik baru, saatnya mensimulasikan aritmatik tersebut kedalam algoritme ElGamal kurva eliptik. Algoritme tersebut dijelaskan bekerja dalam grup multiplikatif dan dapat digeneralisasi dengan mudah untuk bekerja dalam grup siklik berhingga G. Seperti halnya dengan penyandian ElGamal, keamanan dari algoritme penyandian ElGamal digeneralisasi didasarkan pada kekuatan MLD(Masalah Logaritma Diskret) di grup G. Grup G harus dipilih secara cermat untuk memenuhi dua kondisi berkut ini: 1. Untuk efisiensi, operasi grup pada G harus relative mudah diaplikasikan. 2. Untuk keamanan, MLD pada G harus menjadi tidak layak/mungkin secara komputasional. Salah satu grup yang memenuhi dua kondisi di atas adalah grup dari titik kurva eliptik atas lapangan berhingga. 3.3 Konversi Algoritme ElGamal Modulo p Kedalam Kurva Eliptik ElGamal Dalam bagian ini hanya di ambil dua proses dalam ElGamal modulo P yaitu pembangkitan kunci dan enkripsi sedangkan untuk proses dekripsi akan sama penjelasannya. Pembangkitan kunci dalam ElGamal modulo p dimulai dengan pengambilan integer positif acak a dan yang merupakan generator dari ℤ kemudian didapat kunci publik ( , ). Sedangkan kurva eliptik merupakan grup yang terdefinisi dalam operasi penjumlahan sehingga dalam definisi 2.2.1 kita bisa tulis = + + + (sebanyak a kali) jadi untuk kurva eliptik dalam pembangkitan )untuk kunci kita dapatkan ( ,
8
Algoritma Dekripsi Kurva ElGamal Input : Parameter domain (3 , kunci pribadi , siferteks ( , ). Output : pesan .
merupakan integer positif acak dan merupakan titik acak pada kurva eliptik. Selanjutnya untuk proses enkripsi dalam modulo p kita membuat pesan chipherteks [ , ( ) ], t merupakan pesan yang akan dikirimkan dan representasi dari integer modulo p. Jika proses perkalian pesan t dengan ( ) dalam notasi penjumlahan maka bisa ditulis + ( ) sehingga kita dapatkan chiperteks untuk , +( )]. Untuk t kurva eliptik yaitu [ merupakan pesan yang direprsentasikan sebagai titik pada kurva eliptik. Berikut adalah algoritme enkripsi dan deskripsi kurva eliptik ElGamal.
= 1. Hitung dari . 2. Hasil ( ).
3.4 Algoritme Enkripsi dan Deskripsi Kurva Eliptik ElGamal Grup kurva eliptik melibatkan operasi penjumlahan pada semua titik kurva tersebut termasuk sebuah titik tertentu ∞(titik infinity). Algoritma Pembangkitan Kunci Enkripsi Kurva Eliptik ElGamal Input : Parameter domain (3 , , , ), Output : Kunci Publik dan kunci pribadi . 1. Pilih ∈ [1, − 1] . = . 2. Hitung 3. Hasil ( , .) Parameter-parameter domain umum kurva eliptik (3 , , , )menjelaskan bahwa adalah suatu kurva eliptik yang misalkan didefinisikan atas lapangan berhingga dan adalah sebuah titik pada ( ). Algoritma Enkripsi Kurva ElGamal Input : Parameter domain (3 , kunci public , pesan . Output : Siferteks ( , ).
1. Representasikan pesan titik pada ( ). . 2. Pilih ∈ [1, − 1] = . 3. Hitung = + . 4. Hitung 5. Hasil ( , ).
,
sebagai sebuah
, dan
,
,
diperoleh
3.5 Program Enkripsi dan Dekripsi Kurva Eliptik ElGamal Sebelum kita memasuki proses enkripsi kita terlebih dahulu membuat kunci publik dengan mengambil titik secara acak pada ( ) yaitu [1, 0, 1, 0, 2, 1, 1, 0, 1, 2], [2, 2, 2, 2, 2, 0, 0, 2, 0, 2] dan suatu positif integer acak yang bernilai 93. Nilai didapat dari mengalikan 93 dengan titik kemudian didapat [2, 2, 1, 0, 2, 0, 2], [0, 0, 0, 2, 2, 0, 2, 2, 0, 2], sehingga kita dapatkan kunci publik ( , .)
Proses Enkripsi. Dalam proses enkripsi kita mula-mula merepresentasikan pesan ( pada bagian ini saya mengambil titik acak pada kurva sebagai pesan t ) yaitu [1, 2, 2, 2, 1, 0, 0, 1], [1, 2, 2, 0, 1, 0, 0, 2, 1, 2] dan mengambil yang bernilai 38. positif integer acak kemudian hitung = = [1, 0, 0, 0, 0, 0, 0, 2, 0, 2], [0, 1, 0, 2, 0, 1, 1, 2, 1]dan = + = [2, 0, 2, 1, 2, 0, 0, 0, 0, 2], [2, 2, 1, 0, 1, 2, 0, 2, 2], sehingga kita dapatkan siferteks ( , ).
Proses Dekripsi. Dalam proses ini kita hanya mengembalikan pesan yang telah dikirimkan melalui siferteks dengan cara hitung = − dan akhirnya kita dapatkan kembali pesan dari hasil perhitungan tersebut.
Eliptik ,
−
Eliptik
),
Operasi aritmatik perhitungan ElGamal di atas menggunakan aritmatik kurva eliptik (lihat lampiran).
),
IV Kesimpulan Dan Saran Kesimpulan 1. Aritmatik baru dalam kurva eliptik merupakan proses adisi yang didapat dari . persamaan kurva eliptik atas Terdapat dua kasus untuk kurva eliptik dalam field terner yaitu supersingular dan non-supersingular. 2. Dalam kasus supersingular kita dapatkan untuk + = ( , ), dengan = − − dan =( − ) − dimana = . Selanjutnya untuk 2 = + dan =( − ) dimana = − .
=( , −
), dengan
3. Dalam kasus non-supersingular kita = ( , ), dengan dapatkan untuk + = − − − dan =( − ) − dimana = . Selanjutnya untuk 2 = ( , = + − dan =( − ) − dimana =
), dengan
Saran 1. Dalam skripsi ini untuk program kurva , penulis hanya eliptik atas mengambil aritmatik dari kasus supersingular, jika ada yang mau meneruskan mungkin bisa dicoba untuk kasus non-supersingular, kemudian bandingkan antara 2 kasus tersebut dalam algoritme ElGamal yang memenuhi kriteria keamanan. 2. Sebenarnya kurva eliptik tidak hanya bisa di aplikasikan dalam ElGamal saja tapi bisa dalam system keamanan lain yang berdasarkan pada grup siklik seperti ECDSA, ECESA, DSA, dll.Mungkin bisa dicoba salah satunya.
V Daftar Pustaka Hankerson, Menezes, Vanstone. 2004. Guide to Elliptic Curve Crypthography. Springer-Verlag. New York, Inc. Ilham. 2009. Konstruksi Algoritma (3) Dengan Operasi Aritmatik Dibangkitkan Dari Sifat Grup Siklik .IPB, Bogor. Is Esti Firmanesa. 2009. Konstruksi Algoritme Penandaan Dijitel ElGamal Berbasis Grup Kurva Eliptik. IPB, Bogor. Menezes,van Oorschot , Vanstone.1996. Handbook of Applied Cyrptography. Massachusetts Institute of Technology.
Klima, Sigmon, Stitzinger. 1999. Applications of Abstract Algebra with MAPLE. CRC Press LLC. New York, Washington, D.C. Blake, Seroussi, Smart. 2005. Advances in Elliptic Curve Cryptography. Cambridge University Press. New York, US.
LAMPIRAN
LAMPIRAN I Program Aritmatik UbahBinKeDes adalah Prosedur yang mengubah Vektor Biner ke Desimal dari Order Rendah ke Order Tinggi.
> UbahTerKeDes := proc( N::list ) local D1, D2 :: list, Des::integer; D1:=map(x -> 3^x,[seq(i,i=0..(nops(N)-1))]): D2:=[seq(N[j]*D1[j],j=1..nops(N))]: Des:=add( i, i=D2 ); end proc: UbahDesKeTer adalah Prosedur yang mengubah Interjer Desimal ke Vektor Terner.
UbahDesKeTer := proc(B::integer) local Kv::list: Kv:=convert(B,base,3): end proc: Acak Ter adalah membangkitkan vektor terner dimensi m tit secara acak.
AcakTer:=proc(m::posint) local AcIn::procedure, p::integer: AcIn := rand(3^m): p:=AcIn(): UbahDesKeTer(p); end proc: AcakTerX adalah membangkitkan vektor terner dimensi m bit dengan bit pertama tak nol secara acak.
AcakTerX:=proc(m::posint) local AcIn::procedure, p,q,i::integer: AcIn := rand(3^m): p:=AcIn(): q:=p mod 3: for i while q=0 do p:=AcIn(): q:=p mod 3: end do: UbahDesKeTer(p); end proc: ReduNol:=proc(R::list) local T::list, j,t::integer: T:=R: t:=nops(T): for j while T[t]=0 and t>1 do T:=subsop(t=NULL,T): t:=t-1: end do:
13
return(T); end proc: AdisiT adalah penjumlahan vector.
AdisiT:=proc(S::list,T::list) local R::list, s,j,t::integer: s:=nops(S): t:=s: if S=[0] then return(T); elif T=[0] then return(S); elif s=nops(T) then R:=[seq((op(i,S)+op(i,T)) mod 3,i=1..s)]; R:=ReduNol(R); elif nops(S)<nops(T) then subsop(seq(i=(op(i,S)+op(i,T) mod 3),i=1..nops(S)),T); else subsop(seq(i=(op(i,T)+op(i,S)mod 3),i=1..nops(T)),S); end if: end proc: Negasi Vektor
NegT:=proc(L::list) map(x->(-x mod 3),L); end proc: Kelipatan Vektor
KVekT:=proc(L::list,n::integer) if n=0 then return([0]); elif n=1 then return(L); else return(NegT(L)) end if; end proc: GSatuT:=proc(T::list,m::posint) local R,H,L::list, t::integer: L:=DatT[m]: t:=nops(T): if t<m then R:=[0,op(T)]; else R:=[0,op(subsop(m=NULL,T))]: R:=ReduNol(R); H:=KVekT(L,op(t,T)): AdisiT(R,H); end if: end proc:
14
MultiT adalah kali A dan B mod 3^m-3.
MultiT:=proc(A::list,B::list,m::posint) local R,U,V,S,T::list, s,j,t,a::integer: if A=[0] or B=[0] then return([0]) end if; s:=nops(A): t:=nops(B): S:=A: T:=B: if t<s then S:=B: T:=A: a:=s: s:=t: t:=a: end if: R:=KVekT(T,op(1,S)); for j from 1 to (s-1) do T:=GSatuT(T,m): V:=KVekT(T,op(j+1,S)): R:=AdisiT(R,V): end do: return(R); end proc:
KaliT adl kali A dan B tanpa mod
KaliT:=proc(A::list,B::list) local R,U,V,S,T::list, s,j,t,a::integer: if A=[0] or B=[0] then return([0]) end if; s:=nops(A): t:=nops(B): S:=A: T:=B: if t<s then S:=B: T:=A: a:=s: s:=t: t:=a: end if: R:=KVekT(T,op(1,S)); for j from 1 to (s-1) do T:=[0,op(T)]; V:=KVekT(T,op(j+1,S)): R:=AdisiT(R,V): end do: return(R); end proc: BagiT:=proc(T::list,S::list) local K,Q,R,H::list, i,g,r,s,k,h,t::integer: if S=[0] then return(false) end if: R:=T: r:=nops(R): s:=nops(S): k:=r-s: Q:=[seq(0,j=1..k+1)]: g:=op(s,S): if s=1 then Q:=KVekT(R,op(S)):
15
R:=[0]: return([Q,R]); end if: for i while r>=s do k:=r-s: t:=op(r,R): h:=(t/g) mod 3: if k=0 then K:=KVekT(S,h): Q:=subsop(k+1=h,Q): else H:=KVekT(S,h): K:=[seq(0,j=1..k),op(H)]: Q:=subsop(k+1=h,Q): end if: K:=NegT(K): R:=AdisiT(K,R): r:=nops(R): end do: return([Q,R]); end proc: InvT:=proc(T::list,m::integer) local QA,QB,RA,RB,R,S,L,Tmp,H::list, i::integer: S:=NegT(DatT[m]): if T=[0] then return(false) end if: if nops(T)=1 then return(T) end if: RA:=[op(S),seq(0,j=1..(m-nops(S))),1]: RB:=T: QA:=[0]: QB:=[1]: L:=BagiT(RA,RB): RA:=RB: RB:=op(2,L): for i while RB<>[0] do Tmp:=QA: QA:=QB: H:=KaliT(QB,op(1,L)): R:=NegT(H): QB:=AdisiT(Tmp,R): L:=BagiT(RA,RB): RA:=RB: RB:=op(2,L): end do: H:=KVekT(QB,op(RA)): return(H); end proc:
16
Divisi adl bagi A oleh B mod m.
DivT:=proc(A::list,B::list,m::integer) local iB::list: iB:=InvT(B,m); MultiT(A,iB,m); end proc: ModI adalah Prosedur yang menghitung a mod n dalam rentang negatif.
ModN:= proc(a::integer, n::posint) local b, c::integer: b := a mod n: c := floor(n/2): if b > c then b := -(n-b) end if: return(b): end proc: Exp adl A pangkat ke x mod m.
ExpT:=proc(A::list,x::integer,m::integer) local H,G,X::list, i,p,k,n::integer: p:=3^m-1: k:=ModN(x,p): if k>=0 then X:=convert(k,base,2); G:=A: H:=[1]: if op(1,X)=1 then H:=G: end if: for i from 2 to nops(X) do G:=MultiT(G,G,m): if op(i,X)=1 then H:=MultiT(H,G,m): end if: end do: else n:=-k: X:=convert(n,base,2); G:=InvT(A,m): H:=[1]: if op(1,X)=1 then H:=G: end if: for i from 2 to nops(X) do G:=MultiT(G,G,m): if op(i,X)=1 then H:=MultiT(H,G,m): end if: end do: end if: return(H); end proc:
17
AkarT menghitng akar kuadrat dalam GF(3^m).
AkarT:=proc(A::list,m::posint) local R,H,G,S,T::list, d,q,n,i,s,u,k::integer: q:=3^m-1: d:=q/2: n:=1: for i while d mod 2 = 0 do d:=d/2: n:=n+1: end do: R:=ExpT(A,d,m): k:=0: for i while R<>[1] do R:=ExpT(R,2,m): k:=k+1: end do: if k=n then return(false): elif k=0 then s:=(d+1)/2: H:=ExpT(A,s,m): return(H): else u:=2^(n-k): H:=ExpT([0,1],u/2,m): G:=ExpT(H,2,m): T:=G: S:=ExpT(T,2,m): for i from 1 while G<>A do H:=MultiT(H,T,m); G:=MultiT(G,S,m); end do: return(H); end if: end proc: (Ilham,2009)
LAMPIRAN II Program Aritmatik Kurva Eliptik Atas ECAcakTs adalah Prosedur untuk membangkitkan parameter A dan B (persamaan kurva) dengan A tidak nol .
> ECAcakTs:=proc(m::posint) local A,B::list, i::integer: A:=AcakTerX(m): B:=AcakTerX(m): for i while B={} do B:=AcakTerX(m): end do: return([A,B]):
18
end proc:
AcakPtTn adalah Prosedur untuk memilih serta satu titik P = (X,Y) pada kurva, secara acak pada kurva K=[A,B].
AcakPtTn:=proc(K::list,m::posint) local X,Y,H,G,T,M,V,C,D::list, i::integer: X:=AcakTerX(m): D:=MultiT(X,X,m): H:=MultiT(X,D,m): T:=MultiT(X,K[1],m): T:=AdisiT(H,T): C:=AdisiT(T,K[2]): V:=AkarT(C,m): for i while V='false' do X:=AcakTerX(m): D:=MultiT(X,X,m): H:=MultiT(X,D,m): T:=MultiT(X,K[1],m): T:=AdisiT(H,T): C:=AdisiT(T,K[2]): V:=AkarT(C,m): end do: V:=AkarT(C,m): M:=NegT(V,m): return([X,V],[X,M]); end proc: AddPtTerSs adalah prosedur menjumlahkan dua titik X dan Y pada kurva eliptik A, dengan unsur identitas [0,0] (titik di tak hingga).
AddPtTerSs:=proc(X::list,Y::list,K::list,m::posint) local A,B,E,M,R,N,H,T,S,L,Q,V::list: if X=[[0],[0]] or Y=[[0],[0]] then A:=AdisiT(X[1],Y[1]); B:=AdisiT(X[2],Y[2]); return([A,B]); end if: T:=AdisiT(X[2],Y[2]); if X[1]=Y[1] and T=[0] then A:=[0]: B:=[0]: return([A,B]); elif X=Y then S:=NegT(K[1]): E:=NegT(X[2]): V:=DivT(S,X[2],m): H:=MultiT(V,V,m): H:=AdisiT(H,X[1]): L:=NegT(H): R:=AdisiT(X[1],L): R:=MultiT(R,V,m): R:=AdisiT(R,E):
19
return([H,R]); else M:=NegT(X[1]): E:=NegT(X[2]): N:=NegT(Y[1]): Q:=AdisiT(Y[1],M): S:=AdisiT(Y[2],E): V:=DivT(S,Q,m): H:=MultiT(V,V,m): H:=AdisiT(H,N): H:=AdisiT(H,M): L:=NegT(H): R:=AdisiT(X[1],L): R:=MultiT(R,V,m): R:=AdisiT(R,E): return([H,R]); end if: end proc: MulPtTerSs adalah Prosedur untuk menghitung kelipatan titik sebanyak k kali.
MulPtTerSs:=proc(P::list,k::integer,K::list,m::posint) local H,G,X::list, i::integer: X:=convert(k,base,2); G:=P: H:=[[0],[0]]: if op(1,X)=1 then H:=G: end if: for i from 2 to nops(X) do G:=AddPtTerSs(G,G,K,m); if op(i,X)=1 then H:=AddPtTerSs(H,G,K,m): end if: end do: return(H); end proc: LAMPIRAN III Program Kurva Eliptik ElGamal Atas Pembangkitan Kunci Enkripsi Kurva Eliptik ElGamal
> d:=Generate(integer(range=1..99));
> m:=10: > K:=ECAcakTs(m);
20
> P:=AcakPtTn(K,m);
> P1:=P[1]: > Q:=MulPtTerSs(P1,d,K,m);
> A:=([Q,d]);
Proses Enkripsi Kurva Eliptik ElGamal
> t:=AcakPtTn(K,m);
> k:=Generate(integer(range=1..99));
> P1:=P[1]: > C1:=MulPtTerSs(P1,k,K,m);
> t1:=t[1]: N:=MulPtTerSs(Q,k,K,m): C2:=AddPtTerSs(t1,N,K,m);
Proses Dekripsi Kurva Eliptik ElGamal
> B:=MulPtTerSs(C1,d,K,m): Y:=NegT(B[2]): L:=[B[1],Y]:
21
X:=AddPtTerSs(N,L,K,m): M:=AddPtTerSs(t1,X,K,m);
