sistem kriptografi kurva eliptik atas zp_puguh w p_063051410.doc

Upload: sandy-bella-marquarius

Post on 02-Jun-2018

224 views

Category:

Documents


0 download

TRANSCRIPT

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    1/133

    SKRIPSI

    SISTEM KRIPTOGRAFI KURVA ELIPTIK ATASZp

    Diajukan Kepada Fakultas Matematika dan Ilmu Pengetahuan Alam

    Universitas Negeri Yogyakarta

    Untuk Memenuhi Seagian Persyaratan !una Memperoleh !elar

    Sarjana Sains

    Disusun Oleh :

    PUGUH WAHYU PRASETYO

    0630!"!0!!

    PROGRAM STUDI MATEMATIKA

    #URUSA$ PE$DIDIKA$ MATEMATIKA

    FAKULTAS MATEMATIKA DA$ ILMU PE$GETAHUA$ ALAM

    U$IVERSITAS $EGERI YOGYAKARTA

    %0!0

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    2/133

    PERSETU#UA$

    S&'i(si

    Sis)e* K'i()+,'-.i Ku'/- Eli()i& -)-sZp

    "elah Disetujui dan Disyahkan pada "anggal # April $%&%

    Untuk Dipertahankan Didepan Panitia Penguji Skripsi

    Program Studi Matematika'urusan Pendidikan Matematika

    Fakultas Matematika dan Ilmu Pengetahuan Alam

    Universitas Negeri Yogyakarta

    Menyetujui

    Pemiming I Pemiming II

    Sukirman( M)Pd *aturiyati( M)Si

    NIP) &+,# %#&-&+.+ %&&%%& NIP)&+-/&$$%%%%/$%%&

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    3/133

    PER$YATAA$

    Yang ertanda tangan di a0ah ini 1

    Nama Mahasis0a 1 Puguh 2ahyu Prasetyo

    NIM 1 %./%3&,&%&&

    'urusan4 Prodi 1 Pendidikan Matematika4 Matematika

    Fakultas 1 MIPA

    'udul "AS 1 Sistem Kriptogra5i Kurva 6liptik atasZp

    Menyatakan ah0a skripsi ini adalah hasil pekerjaan saya sendiri dan sepanjang

    pengetahuan saya( tidak erisi materi yang dipulikasikan atau ditulis oleh orang lain

    atau telah digunakan seagai persyaratan penyelesaian studi di Perguruan "inggi lain

    ke7uali pada agian8agian tertentu yang saya amil seagai a7uan)

    Apaila ternyata terukti pernyataan ini tidak enar( sepenuhnya menjadi

    tanggungja0a saya)

    Yogyakarta( & April $%&%

    Yang Menyatakan

    Puguh 2ahyu Prasetyo

    NIM) %./%3&,&%&&

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    4/133

    PE$GESAHA$

    S&'i(si

    Sis)e* K'i()+,'-.i Ku'/- Eli()i& -)-sZp

    Disusun 9leh 1

    Puguh 2ahyu Prasetyo

    %./%3&,&%&&

    "elah Dipertahankan Di Depan Panitia Penguji Skripsi Program Studi

    Matematika( Fakultas Matematika dan Ilmu Pengetahuan Alam( Universitas NegeriYogyakarta pada tanggal $% April $%&% dan dinyatakan telah memenuhi syarat guna

    memperoleh gelar sarjana sains)

    Susunan Panitia Penguji Skripsi

    Nama 'aatan "anda "angan "anggal

    Sukirman( M)Pd Ketua Penguji

    *aturiyati( M)Si Sekretasis Penguji

    Dr) :artono Penguji Utama

    6mut( M)Si Anggota Penguji

    Yogyakarta( April $%&%

    Fakultas Matematika dan Ilmu Pengetahuan Alam

    Universitas Negeri Yogyakarta

    Dekan

    Dr) Aris0an

    NIP) &/&-+&/.-

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    5/133

    MOTO

    Hai jama'ah jin dan manusia, jika kamu sanggup menembus(melintasi) penjuru langit dan bumi, maka lintasilah, kamu tidakdapat menembusnya kecuali dengan kekuatan (ilmu).

    -QS. Ar Rahmaan !!

    Hai "rang-"rang beriman, apabila kamu mengadakan pembicaraanrahasia, janganlah kamu membicarakan tentang d"sa, permusuhandan berbuat durhaka kepada Rasul. #an bicarakanlah tentangmembuat kebajikan dan tak$a. #an bertak$alah kepada Allah yang

    kepada-%ya kamu akan dikembalikan.-QS. Al &ujaadilah

    Sesungguhnya sesudah kesulitan itu ada kemudahan. &aka apabilakamu telah selesai (dari sesuatu urusan), kerjakanlah dengansungguh-sungguh (urusan) yang lain. #an hanya kepadauhanmulah hendaknya kamu berharap.

    -QS. Alam %asyrah - *

    Allah menghendaki kemudahan padamu semua dan tidak

    menghendaki kesukaran untukmu semua.+

    -QS. Al aarah */

    Allah &aha lembut terhadap hamba-hamba-%ya0 #ia memberi re1ki

    kepada yang di kehendaki-%ya dan #ialah 2ang &aha 3uat lagi

    &aha 4erkasa.

    QS. Asy Syuura

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    6/133

    PERSEMAHA$

    3arya kecil ini penulis persembahkan untuk

    Ayahanda dan 5bunda ercinta, serta Adik

    ersayang.

    6uru-guruku.Sahabat-sahabatku dalam menuntut

    ilmu, terutama teman-temanku

    mahasis$a &atematika Subsidi 7

    S$adana 899.

    4enulis mengucapkan terimakasih kepada

    .5bu 3aryati.8.&as &uhammad :aki Riyant".!.eman-teman &atematika Subsidi 7

    S$adana 899 (Husein, 6igin, ;ucie,

    au

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    7/133

    KATA PE$GA$TAR

    Alhamdulillah( puji syukur penulispanjatkan ke hadirat Allah S2" atas

    segala limpahan rahmat dan karunia8Nya( sehingga penulis dapat menyelesaikan

    penulisan skripsi yang erjudul ;Sistem Kriptografi Kurva Eliptik atas Zp ini)

    Penulis menyadari sepenuhnya ah0a dalam penulisan skripsi ini tidak

    terlepas dari dukungan( motivasi( kerjasama maupun imingan dari eragai pihak)

    9leh karena itu( penulis mengu7apkan terimakasih yang seesar8esarnya kepada 1

    &)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    8/133

    ,)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    9/133

    DAFTAR ISI

    :alaman 'udul =======================)) i

    :alaman Persetujuan ===================== ii

    :alaman Pernyataan ===================== iii

    :alaman Pengesahan ===================== iv

    :alaman Moto =======================) v

    :alaman Persemahan ====================)) viKata Pengantar =======================) vii

    Da5tar Isi =========================)) i>

    Da5tar !amar =======================)) >ii

    Da5tar "ael ========================)) >iii

    Da5tar ?ampiran ======================= >iv

    Da5tar Simol ========================) >v

    Da5tar Algoritma ======================)) >vi

    Astrak ==========================)) >vii

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    10/133

    ,) Fungsi Invers ==================== #

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    11/133

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    12/133

    DAFTAR GAMAR

    !amar $)&) Skema Sistem Kriptogra5i Modern ============ 3.

    !amar /)& Sistem Kriptogra5i Kurva 6liptik atasZp=========) -&

    !amar /)$1Pengiriman Pesan oleh

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    13/133

    DAFTAR TAEL

    "ael $)&) Perhitungan g7dC+%($3 dengan menggunakan

    Algoritma 6u7lid ============)))===)

    "ael /)&) "itik B titik pada kurvay$Ex/x / atasZ11 ====) .+

    "ael /)$) Sugrup Siklik dalamy$Ex/x / mod && dengan

    generator E C3(& =============== -%

    "ael /)/) Konversi Pesan ;mat%.G =============) #&

    "ael /),) Proses 6nkripsi ================= #$

    "ael /)3) Proses Dekripsi ================= #,

    "ael /).) Proses 6nkripsi Pesan Untuk !inanjar ========) ##

    "ael /)-) Proses 6nkripsi Pesan Untuk Kholis ========)) ##

    "ael /)#) Proses Dekripsi Pesan 9leh !inanjar =====)===) #+

    "ael /)+) Proses Dekripsi Pesan 9leh Kholis )========)) +%

    "ael /)&%) Konversi Karakter *ontoh /), ====))====== +3

    "ael /)&&) Proses 6nkripsi oleh King I ===))=======))) +-

    "ael /)&$) Proses Dekripsi Pesan oleh King II ========)) +#

    "ael /)&/) Konversi Karakter Pesan ;Seratus 'utaanG ==))=== &%%

    "ael /)&,) Proses 6nkripsi Pesan oleh King II ========) &%%

    "ael /)&3) Proses Dekripsi Pesan 9leh King II ======== &%&

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    14/133

    DAFTAR LAMPIRA$

    ?ampiran &) Program Maple untuk

    ECH/,-1y2= x3+ x + 3 mod/,-=======) &&&

    ?ampiran $) Prosedur epoints adde! dan elgamal======) &&$

    ?ampiran /) "itik8titik pada Kurva

    ECH/,-1y2

    = x3

    + x + 3 mod /,-=======)) &&,

    ?ampiran ,) Sugrup Siklik dalamECH/,-1y2= x3+ x + 3mod /,-

    dengan generator E C%(+3 ========) &&.

    ?ampiran 3) Konversi Karakter Pesan =========== &

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    15/133

    DAFTAR SIMOL

    x " 1xanggota"

    a # $ 1 amemagi

    g7dCa( 1 Faktor Persekutuan "eresar dari adan $

    a 1 ilangan ulat teresar yang leih ke7il atau sama dengan a

    DCm 1 anyaknya elemen dari himpunan residu sederhana modulo m

    =

    n

    i

    ia&

    1 penjumlahan naaa +++ ))))$&

    n

    i

    ia&=

    1 perkalian naaa ))))) $&

    Hp 1 himpunan semua ilangan ulat modulo p

    Hp 1 himpunan kelas ilangan ulat modulo p yang saling prima dengan p

    6CHp 1 Kurva eliptik atas Hp

    1 titik in5inity)1 akhir suatu ukti)

    M 1 himpunan semua plainte>t)

    * 1 himpunan semua 7hiperte>t)

    el 1 5ungsi enkripsi)

    dl 1 5ungsi dekripsi)

    :@" 1 :impunan @esidu "erke7il)

    S@? 1 Sistem @esidu ?engkap)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    16/133

    DAFTAR ALGORITMA

    Algoritma $)&) Algoritma 6u7lide ===============

    Algoritma $)$) Algoritma 6u7lide yang Diperluas ========)) $&

    Algoritma $)/) Algoritma "est Miller =============)) /$

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    17/133

    Sis)e* K'i()+,'-.i Ku'/- Eli()i& -)-sZp

    Oleh :Pu,uh W-h2u P'-se)2+

    0630!"!0!!

    ASTRAK

    Sistem kriptogra5i kurva eliptik atas Zp( merupakan sistem kriptogra5iasimetri( yang merupakan salah satu solusi dari permasalahan keamaan distriusikun7i pada sistem kriptogra5i simetri) "ingkat keamanan sistem kriptogra5i kurva

    eliptik didasarkan atas Ellipti! %urve &is!rete 'ogaritm (ro$lem C6*D?P padakurva eliptik modulo prima) Semakin esar ilangan prima dan Ellipti! %urve&is!rete 'ogaritmyang digunakan( maka tingkat keamanan pengiriman pesan denganmenggunakan Sistem kriptogra5i kurva eliptik atasZp semakin tinggi)

    Sistem kriptogra5i kurva eliptik atasZp mempunyai kun7i pulik erupa duapasang titik pada kurva eliptik atas Zp dan kun7i rahasia erupa satu ilangan ulat)Sistem kriptogra5i ini melakukan proses enkripsi dan dekripsi pada plaintext dandihasilkan !)ipertext yang masing8masing terdiri dari dua pasang titik pada kurvaeliptik atasZp)

    Pada skripsi ini diahas algoritma kriptogra5i kurva eliptik atas Zp yang

    digunakan dalam proses pementukan kun7i( proses enkripsi dan proses dekripsi)Proses pementukan kun7i yang terdiri dari proses pementukan kun7i pulik dankun7i rahasia) Pada proses pementukan kun7i dipilih CxyE*ZpCkurva eliptikatas Zp( dengan xy Zp dan dipilih ilangan rahasia kZp,- Kemudian di7ari E*Zp dengan menghitung E k) Kun7i pulik adalah pasangan C( dan kun7i rahasianya adalah ilangan k) Kemudian kun7i pulik dikirim kepadapengirim pesan( agar pengirim pesan dapat melakukan proses enkripsi( yangmenghasikan !)ipertext J!&( !$ dengan !& Esdan !$E s untuk setiap. Cplaintext dan searang ilangan ulat a7ak sZp,- Setelah diperoleh!)ipertext( maka pengirim pesan mengirim pesan terseut kepada penerima pesan(kemudian penerima pesan dapat melakukan proses dekripsi( dengan menggunakan

    kun7i rahasia k) Proses dekripsi ini akan menghasilkan Cplaintext denganmenghitung E !$B k,!&( untuk setiap J!&( !$ % C!)ipertext)

    K-)- Kuni : kriptogra5i( sistem kriptogra5i( kurva eliptik( plaintext( !)ipertext(kun7i pulik(Ellipti! %urve &is!rete 'ogaritm (ro$lem-

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    18/133

    A I

    PE$DAHULUA$

    A1 L-)-' el-&-n,

    Perkemangan ilmu pengetahuan yang sangat pesat menuntut eragai pihak

    untuk melakukan penelitian terhadap eragai aspek kehidupan untuk menghasilkan

    sesuatu yang aru) Di antaranya adalah perkemangan matematika( terutama

    perkemangan aplikasinya dalam teknologi in5ormasi yang sangat erman5aat agi

    kehidupan manusia) Salah satu penggunaan teknologi in5ormasi adalah pada

    pengiriman pesan) Akan tetapi seiring dengan erkemangannya ilmu pengetahuan

    dan teknologi( pengiriman pesan terseut juga mengalami anyak kendala( di

    antaranya tentang kerahasiaan suatu pesan( sehingga memutuhkan suatu ilmu untuk

    menjaga keamanan dan kerahasiaan pesan terseut) Dengan hal ini erkemanglah

    kriptogra5i) Sedangkan de5inisi kriptogra5i adalah ilmu pengetahuan yang

    mempelajari suatu sistem matematis untuk menyelesaikan masalah kerahasiaan dan

    keaslian CYan( $%%+ 1 $#-) Selain itu juga terdapat de5inisi yang menyatakan ah0a

    kriptogra5imerupakan ilmu yang mempelajari enkripsi dan dekripsi suatu in5ormasi

    atau pesan CYan( $%%+ 1 $#-) Pesan yang dapat dia7a diseut dengan plaintext-

    Proses untuk merahasiakan suatu plaintext diseut dengan enkripsi( dan hasil dari

    enkripsi plaintextmerupakan pesan yang tidak dapat dia7a dengan jelas diseut

    dengan !)ipertext) 6nkripsi ini digunakan untuk menegaskan ah0a pesan dapat

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    19/133

    dijaga kerahasiaannya dan keasliannya) Sedangkan proses kealikan dari enkripsi ini

    yaitu menguah !)ipertextmenjadi entukplaintextaslinya diseut dengan dekripsi)

    Proses enkripsi dan dekripsi terjadi dalam kerangka suatu sistem kriptogra5i

    CSalomaa( &++. 1 /)S=R

    A>S=R

    =nkripsidengan

    #ekripsi

    dengan

    menggunakan

    kunci rahasiaPlainte

    xt

    Plaintext

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    20/133

    Kun7i Pulik

    %)ipertext

    !amar &)&) Diagram Sistem Kriptogra5i AsimetriKeterangan 1

    1- "erdapatplaintextdari userA)2- Kemudianplaintextterseut dienkripsikan dengan kun7i pulik yang terdapat

    pada user< menjadi !)ipertext-3- Setelah !)ipertext diperoleh user

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    21/133

    atas Hp) DenganZpadalah himpunan ilangan ulat modulopdan padalah ilangan

    prima dan Zp merupakan suatu lapangan hingga) Sedangkan himpunan

    Hp E &( $( /( ,( )))( p8& adalah himpunan ilangan ulat modulo pyang saling

    prima denganp)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    22/133

    dan men7ari generator sugrup siklik dalam kurva eliptik) Pada skripsi ini tidak

    memahas mengenai pengemangan sistem kriptogra5i yang lain) Selain itu juga

    tidak dijelaskan mengenai program dari sistem kriptogra5inya( simulasi sistem

    kriptogra5i kurva eliptik atas Hpdengan ahasa pemrograman maupun aplikasinya

    dalam keamanan email( keamanan 0e( kartu pintar( atau aplikasinya pada idang

    yang lain dan skripsi ini tidak memahas mengenai kesulitan dan 7ara87ara untuk

    meme7ahkan mekanisme penyandian)

    D1 Tuu-n Peneli)i-n

    "ujuan dilaksanakan penelitian ini adalah menjelaskan konsep B konsep

    matematis yang melandasi sistem kriptogra5i kurva eliptik atas Hpdan menerapkan

    sistem kriptogra5i kurva eliptik atas Hpdalam seuah algoritma pementukan kun7i(

    algoritma enkripsi dan dekripsi)

    E1 M-n.--) Penulis-n

    Dari hasil penelitian ini diharapkan dapat memeri in5ormasi tentang kurva

    eliptik atas Hpdan pengemangannya pada sistem kriptogra5i yang erlandaskan teori

    ilangan( logaritma diskrit( dan struktur aljaar) Selanjutnya diharapkan dapat

    memerikan pemahaman agi pema7a dan pihak B pihak yang erke7impung dalam

    kriptogra5i)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    23/133

    A II

    DASAR TEORI

    Pada a ini diahas konsep dasar yang erhuungan dengan 5ungsi( ilangan

    ulat seperti keteragian( 5aktor persekutuan teresar( algoritma pemagian pada

    ilangan ulat( algoritma 6u7lid( Algoritma 6u7lid yang diperluas( kekongruenan(

    perkongruenan linier( eerapa kekongruenan khusus( sisa kuadratik( simol 'a7oi)

    Sedangkan pada struktur aljaar diahas mengenai partisi dan ekuivalensi( grup( grup

    siklik( gelanggang( dan lapangan serta memahas kriptogra5i seperti de5inisi

    kriptogra5i( sejarah kriptogra5i( algoritma kriptogra5i dan sistem kriptogra5i serta

    persamaan 2eierstrass)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    24/133

    A1 Fun,si

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    25/133

    Pemetaan ini surjekti5 sea jika e( maka terdapat ! dengan !

    E$

    #esedemikian hinggafC! EfC

    $

    #e E $C

    $

    #e # E e)

    Karena pemetaan ini injekti5 dan surjekti5 maka dapat disimpulkan ah0a pemetaan

    ini adalah pemetaan ijekti5)"1 Fun,si In/e's

    De.inisi %1"1 7Menees e)1 Al8 !;;< :

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    26/133

    melakukan prosesnya) Pada himpunan ini erlaku si5at assosiati5( komutati5 dan

    distriuti5 perkalian terhadap operasi penjumlahan)

    !1 Ke)e'5-,i-n

    De.inisi %11 7Su&i'*-n8 %006 : 339

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    27/133

    u&)i :

    a#$maka terdapat ilangan ulat msedemikian hingga $ = ma

    $#!maka terdapat ilangan ulat nsedemikian hingga ! = n$E n *ma( sehingga ! =

    mnadengan mnanggota ilangan ulat( akiatnya a#!)

    Te+'e*- %1%) 7Su&i'*-n8 %006 : 3"9

    'ika a#$maka a#m$( untuk setiap milangan ulat)

    u&)i:

    'ika aQ maka terdapat ilangan ulat ksedemikian hingga $ = ka( apaila kedua ruas

    dikalikan dengan ilangan ulat mmaka diperoleh m$ = mka) Misalkan ilangan

    ulat ndengan n = mk( maka m$ = na( sehingga a#m$)

    Apaila a#$ dan a#!( menurut de5inisi $)3( maka diperoleh $ = kadan ! = mauntuk

    ilangan B ilangan ulat kdan m)

    Dari dua kesamaan ini dapat diperoleh ah0a 1

    *i $ + ! = *k+maerartia # *$+!

    *ii $ 5 ! = *k 5maerartia # *$!

    *iii $-! = *kmaaerartia # $!

    Te+'e*- %131 7Su&i'*-n8 %006 : 39

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    28/133

    Apaila a#$dan a#!( maka a# *$+!dan a# $!

    u&)i :

    'ika a#$maka terdapat ilangan ulat msedemikian hingga $ = ma)

    'ika a#!maka terdapat ilangan ulat n sedemikian hingga ! = na)

    Sehingga $ + ! = ma + na

    $ + ! = *m+na

    'adi dapat disimpulkan ah0a a#$+!

    'ika a#$maka terdapat ilangan ulat m sedemikian hingga $ = ma)

    'ika a#!maka terdapat ilangan ulat nsedemikian hingga ! = na)

    Sehingga $! = *ma*na

    $! = *mnaa

    'adi dapat disimpulkan ah0a a#$!

    Te+'e*- %1"17Su&i'*-n8 %006 : 39

    Apaila a#$dan a#!maka a # *m$ + n!untuk setiap ilangan ulat mdan n)

    u&)i :

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    29/133

    Menurut "eorema $)$ jika a#$ maka a#m$untuk setiap ilangan ulat m( demikian

    juga jika a#!maka a#n! untuk setiap ilangan ulat k) Karena a#m$maka m$ = ka

    dengan ilangan ulat k( dan a#n!maka terdapat ilangan ulat l sedemikian sehingga

    n! = la) Sehingga diperoleh m$ + n! = ka + la = *k+la( akiatnya a#*m$ + n!)

    Te+'e*- %117Su&i'*-n8 %006 : 39

    Ci a#auntuk setiap ilangan ulat aCsi5at re5lekti5)

    Cii 'ika a#$maka ma#m$untuk setiap ilangan ulat m)

    Ciii 'ika ma#m$dengan mR %( maka a#$)

    Civ &Qadan aQ%

    Cv 'ika %Qamaka aE %

    Cvi 'ika a#$dengan $R %( maka #a# 6 #$#

    Cvii 'ika a#$dengan $#a( maka Qa# = #$Q)

    u&)i :

    *i a#a( jelas) Karena a = a

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    30/133

    *ii 'ika a#$maka terdapat ilangan ulat n( sedemikian sehingga $ = na) Apaila

    kedua ruas dikali dengan manggota ilangan ulat maka diperoleh m$ = mna

    atau m$ = n*maakiatnya ma#m$

    *iii 'ika ma#m$ dengan m R % maka terdapat ilangan ulat k( sedemikian

    sehingga m$ = kma atau m$ = mka) Apaila kedua ruas diagi dengan m

    diperoleh $ = ka( akiatnya a#$-

    *iv &Qa( jelas) Karena & memagi semua anggota ilangan ulat)

    Karena terdapat ilangan ulat k( dengan kE %( sehingga akE %( akiatnya aQ

    %)

    *v 'ika %Qamaka terdapat ilangan ulat k( dengan nR %( sedemikian sehingga a

    = n)%( karena n R % maka kedua ruas dapat diagi dengan n( sehingga

    diperolehn

    aE %( akiatnya aE %)

    *vi 'ika aQdan % ( maka terdapat ilangan ulat p( denganp % sedemikian

    sehingga $ = a-p) Akiatnya Q$Q = |a-p# |aQ)

    *vii 'ika a#$ dengan $#a) Untuk a#$) Dari pemuktian Cvi diperoleh Qa# 6 #$Q)

    Untuk $#a( maka terdapat ilangan ulat 7( dengan 7 0, sedemikian sehingga

    a = $-7) akiatnya Qa# = #$7# |$|. Sehingga dapat disimpulkan ah0a Qa# = #

    $Q)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    31/133

    %1 F-&)+' Pe'se&u)u-n Te'5es-'

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    32/133

    Te+'e*- %16 7Su&i'*-n %006 : "09

    'ikag!dCa$= d( makag!dCa / d $ / d E &

    u&)i :

    'ika g!dCa$ E d maka dapat disimpulkan ah0a d adalah ilangan ulat positi5

    teresar sedemikian hingga d#adan d#$) Karena d#amaka terdapat ilangan ulat m

    sedemikian hingga a = md akiatnya a/d = m) Demikian juga untuk d#$ maka

    terdapat n anggota ilangan ulat sedemikian hingga $ = nd akiatnya $/d = n)

    Karena dmerupakan 5aktor persekutuan teresar dari adan $( maka ilangan ulat m

    dan nsaling prima sehingga g!dCmn E &) 'adi dapat disimpulkan ah0ag!dCa/d

    $/d Eg!dCmn E &)

    Apaila a dan $ dua ilangan ulat positi5 dengan g!dCa$ E &( maka dikatakan

    ah0a adan $saling prima atau aprima relali5 terhadap $)

    Misalkan a dan dua ilangan ulat dengan a %( maka diagi oleh a akan

    memerikan hasilagi dan sisa pemagian) :al ini dinyatakan seagai teorema

    erikut ini dan terkenal dengan nama8lgoritma (em$agian.

    31 Al,+'i)*- Pe*5-,i-n (->- il-n,-n ul-)

    De.inisi %1=1 7uh*-nn8 %000 : %9

    Untuk setiap ilangan real V R dide5inisikan E ma> L 1 L W V)

    Dengan demikian( merupakan ilangan ulat teresar yang leih ke7il atau sama

    dengan V)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    33/133

    4+n)+h %11

    &) .-(&& E &&

    $) /$(+ E 8&%

    Te+'e*- %1

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    34/133

    kontradiksi dengan yang diketahui yaitu 7E

    $

    a) Selanjutnya( dari hasil terakhir dan

    karena $ %) Maka % W r 9 $) Untuk ukti ketunggalannya( misalkan terdapat

    7172r1r2H sedemikian hingga a = 71$ + r1dan a = 72$ + r2) Akiatnya diperoleh

    C71$ + r1 B C72$ + r2 E % atau $C7172 Cr1r2 E %) Karena 71E

    $

    adan 72E

    $

    a(

    maka 71 = 72( sehingga 71 72E %) Akiatnya r1r2E % atau r1= r2)

    4. Al,+'i)*- Euli>

    Untuk menghitung nilai 5aktor persekutuan teresar dari dua ilangan ulat

    akan sangat e5isien dengan menggunakan seuah algoritma) Dan algoritna ini diseut

    dengan algoritma 6u7lid)

    Te+'e*- %1=) 7uh*-nn8 %000 : !%9

    Dierikan a $H)

    &) 'ika $E %( makag!dCa$ E QaQ)

    $) 'ika $R %( makag!dCa$ Eg!dC$ r( dengan rE a B $k untuk suatu ilangan

    ulat k)

    u&)i:

    &) 'elas ah0ag!dCa$ Eg!dCa(% EQaQ

    $) Misalkan d E g!dCa$ dan r = a mod $) Menurut "eorema $)-( terdapat 7H

    dengan aE 7$ r) Karena rE aB $7maka d#r) Akan ditunjukkan ah0a dE

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    35/133

    g!dC$r) Diamil searang ilangan ulat t sedemikian hingga t#$ dan t#r yaitu

    terdapatn mH sedemikian hingga $ = ntdan r = mt) Sehingga diperoleh aEnt7 mtE tCn7 m atau tQa) Diketahui dEg!dCa$( karena t#adan t#$maka t 6 d

    dan t#d) "erukti ah0a dEg!dCa$ Eg!dC$ r)

    Misalkan di7ari 5aktor persekutuan teresar dari a dan $ atau g!dCa$ dengan

    algoritma 6u7lid dengan langkah B langkah seagai erikut)

    $ = ro = 71-a + r2 ; 9 r29 $

    a = r1 = 72-r2+ r3 ; 9 r39 r2

    r2 = 73-r3+ r ; 9 r9 r3

    r3 = 7-r+ r> ; 9 r>9 r

    r = 7>-r>+ r? ; 9 r>9 r

    ----

    rk2 = 7k1-rk1+ rk ; 9 rk9 rk1

    rk1 = 7k-rk+ ;/

    Dengan menggunakan "eorema $)#) dapat ditunjukan ah0a

    g!dCa$ Eg!dCar2 Eg!dCr2r3 E ))))Eg!dCrk2rk1 Eg!dCrk1rk Eg!dCrk(% E rk)

    Al,+'i)*- %1!1 Al,+'i)*- Euli>e CMeneLes et al( &++. 1 ..

    @nput 1

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    36/133

    &)& Set r

    $

    a a$ $r-

    $) Autput Ca)

    4+n)+h %16

    Akan dihitungg!dC+%($3) Dengan menggunakan algoritma 6u7lide diperoleh 1

    ?angkah & 1g!dC+%($3 Eg!dC$3(&3( karena +% E /)$3 &3)

    ?angkah $ 1g!dC$3(&3 Eg!dC&3(&%( karena $3 E &)&% &3)

    ?angkah / 1g!dC&3(&% Eg!dC&%(3( karena &3 E &)3 &%

    ?angkah , 1g!dC&%(3 E 3( karena &% E $)3 %)

    'adig!dC+%($3 Eg!dC&%(3 E 3

    T-5el %1!1 Pe'hi)un,-ngcd7;08%9 >en,-n *en,,un-&-n Al,+'i)*- Euli>

    k % & $ / , 3

    ak +% $3 &3 &% 3 %7k / & & $

    5. Al,+'i)*- Euli> Y-n, Di(e'lu-s

    Te+'e*- %1;17Su&i'*-n8 %006 : "39

    Apaila adan $ilangan B ilangan ulat tidak nol( maka ada ilangan B ilangan

    ulatxdanysedemikian hingga a-x + $-yEg!dCa $)

    u&)i :

    Dientuk himpunan S( yaitu himpunan semua kominasi linier dari a dan $

    yang ernilai positi5)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    37/133

    SE au + $v # au + $v % dan u vilangan ulat

    Sukan himpunan kosong( karena jika a% dan uE &dengan vE % maka aS danjikaaT %( dengan uE 8& dan vE %( maka QaQ S)

    Karena Smemuat ilangan B ilangan ulat positi5( maka Smemuat anggota

    yang terke7il( misalnya d) Karena d S( maka ada ilangan B ilangan ulatxdany

    sehingga ax + $y = d) Selanjutnya( akan ditunjukan ah0a g!dCa$ E d)

    Menurut algoritma 6u7lid maka untuk adan $terdapat ilangan B ilangan

    ulat 7dan rsedemikian hingga

    a = 7d + rdengan % Wr 9 d)

    r = a 5 7d = a 5 7Cax + $y

    r = aC1 5 7x+ $C7y

    Karena r % dan rmerupakan kominasi linier dari a dan $( maka r S) :al ini

    kontradiksi)

    'adi rE %( sehingga a = 7datau d#a)

    Dengan 7ara yang sama maka diperoleh d#$) Sehingga dapat disimpulkan ah0a d

    merupakan 5aktor persekutuan teresar dari a dan $) Kemudian( jika ! adalah

    searang 5aktor persekutuan dari adan $( yaitu !#adan !#$( maka !#ax + $yatau !#d(

    sehingga ! 6 d):al ini mengakiatkan ax + $y = d Eg!dCa$)

    Sedangkan untuk men7ari nilai x dan y dapat di7ari dengan menggunakan

    algoritma 6u7lide) Dengan algoritma 6u7lide dapat dihitung nilai 5aktor persekutuan

    teresar dari ilangan ulat adan$) Menurut "eorema $)+( terdapat ilangan ulatx

    dan y dengan g!dCa$ E ax + $y) Selanjutnya( algoritma 6u7lid dapat diperluas

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    38/133

    sedemikian hingga dapat digunakan untuk menghitung nilai x danyterseut) Pada

    pemahasan tentang algoritma 6u7lid diketahui ah0a diperoleh arisan sisa yaitu ro

    r1 r2 ---rkdan arisan hasil agi 71 72 73--- 7k)

    Kemudian( dientuk dua arisan Cxn dan Cyn yang diperoleh dari arisan sisa

    dan hasil agi sedemikian hingga pada iterasi terakhir diperoleh xE C8&kxkdan y E C8

    &kyk)

    Ditentukan nilai a0al yaitu xo E &( x&E %( yo E % dany&E &) Selanjutnya(

    dierikan persamaanxn&E 7nxnxn8&danyn&E 7nynyn8&( % W nW k)

    Te+'e*- %1!017uh*-nn8 %000 : !69

    'ikaxoE &(x&E %(yoE %(y&E & denganxn&E 7nxnxn8&danyn&E 7nynyn8&maka rn

    E C8&nxna C8&k+1yk$untuk % W nW k +1)

    u&)i:

    Akan diuktikan dengan menggunakan induksi matematika)

    Untuk kE % diperoleh roE $E C&$BC%aExoa8yo$( selanjutnya

    r&E aE 8C%a C& $E 8x&ay&$

    Misalkan pernyataan enar untuk nW k( maka pernyataan enar untuk n = kyaitu

    rkE C8&nxna C8&

    n+1yn$)

    Akan diuktikan ah0a pernyataan enar untuk kE n &( yaitu

    rk&E C8&n+1xn+1a C8&n+2yn+1$

    Dari pemahasan tentang algoritma 6u7lide( diketahui ah0a rk+1 = rk17krk) 9leh

    karena itu

    rk+1= rk15 7krk

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    39/133

    E JC8&k1xk1a + C8&kyk1$ 7kJC8&kxka + C8&k+1yk$

    E JC8&k1

    xk1 7kC8&k

    xka + JC8&k

    yk1 7kC8&k+1

    yk$

    E JC8&k1xk1 XkC8&k+1xka JC8&k+2yk18 7kC8&

    k+2yk$

    E C8&n+1Jxn1 7kxka C8&n+2Jyk1 7kxk$

    E C8&n+1xn+1a C8&n+2-yn+1$

    Dengan demikian "eorema $)&%) terukti)

    Al,+'i)*- %1%1 Al,+'i)*- Euli>e CMeneLes et al( &++. 1 .-

    @nput 1 a( $H( a $-

    Autput1 dEg!d Ca($ danxyH yang memenuhi a-x + $-y = d-

    ?angkah 1

    &) 'ika $E %( makaset da x&(y%( outputCd(x(y)

    $) Set x$&(x&%(y$%(y&&)

    /) B)ile $ : % 1

    /)& 7

    $

    a( r a 7$(x x$ 8 7x&(y y$ 8 7y&

    /)$ a$ $ r(x$x&(x&x(y$y&(y&y)

    ,) Set da xx$ yy$ output Cd x y-

    4+n)+h %1e Fast Exponentiation

    Misalkan gadalah suatu ilangan ulat dan Dadalah ilangan ulat positi5)

    Maka untuk menghitung gD dapat dilakukan dengan langkah B langkah seagai

    erikut 1

    Dientuk ekspansi iner dari ilangan ulat positi5D( yaituDE =

    k

    i

    i

    ia

    %

    $

    KarenaDditulis dengan ekspansi iner( maka ai%(&) Sehingga

    gD=g=

    k

    i

    iia

    %

    $ ==

    k

    i

    aii

    g%

    $DC E

    = &(&

    $

    aki

    i

    g

    Sehingga diperoleh gD dengan 7ara 7epat yang diseut dengan metode ast

    Exponentiation-

    4+n)+h %1!;1

    Akan dihitung nilai dari 3$+# mod &$/,) Ditentukan ekspansi iner dari $+#( yaitu 1

    $+# E &)$# &)$3 &)$/ &)$&

    Kemudian dihitung 1

    3 %$ E 3

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    50/133

    3 &$ E $3

    3 $

    $ E .$3

    3 /$ .$3$ .#& Cmod &$/,

    3 ,$ .#&$ &%&& Cmod &$/,

    3 3$ &%&&$ /.+ Cmod &$/,

    3 .$ /.+$ ,$& Cmod &$/,

    3 -$ ,$&$ --+ Cmod &$/,

    3 #$ --+$ +,- Cmod &$/,

    Sehingga diperoleh 1

    3$+# 3 #$ )3

    3$ )3 /$ )3

    &$ Cmod &$/,

    +,-) /.+).#&)$3Cmod &$/,

    $$&)+#/ Cmod &$/,

    3$+# 3+ Cmod &$/,

    'adi( 3$+#mod &$/, adalah 3+

    Setelah dijelaskan de5inisi "est Miller( yaitu pada De5inisi $)&3 akan dierikan

    algoritma "est Miller seagai erikut)

    Al,+'i)*- %131 Al,+'i)*- Tes) Mille'1

    @nput 1 Seuah ilangan ulat positi5 ganjilp /)

    9utput 1

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    51/133

    &) "ulispB & E $s)t( dengan t ilangan ulat positi5 ganjil)

    $) Amil searang ilangan ulat positi5 a( $ a p 5 &)/) :itungy atC modp menggunakan metodefast exponentiation)

    ,) 'ikay &C modp atauy C$ 8&C modp dengan $ C s 5 & makap

    suatu ilangan ;kompositG)

    3) 'ika 'ika y &C modp atauy C$ 8&C modp dengan $ C s 5 &

    makap suatu ilangan ;primaG)

    4+n)+h %1%01

    Dierikan ilangan ulat positi5 ganjilp E /,-) Akan ditunjukkan ah0a merupakan

    ilangan prima) Diamil aE $(sE $( dan t E &-/( sehingga diperoleh $&-/ &C mod

    /,- ) 'adi terukti ah0a /,- merupakan ilangan prima)

    10. Sis- Ku->'-)i&

    De.inisi %1!=1 7R+sen8 !;;3 : 33!9

    'ika m adalah ilangan ulat positi5( ilangan ulat a sisa kuadratik dari m( jika

    g!dCam E & dan perkongruenan x$ a Cmod m mempunyai seuah solusi) 'ika

    perkongruenan x$ a Cmod m tidak mempunyai solusi( maka ilangan ulat a

    ukan sisa kuadratik dari m)

    4+n)+h %1%!1

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    52/133

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    53/133

    Dierikanpseuah ilangan prima ganjil dan aseuah ilangan ulat positi5 yang

    tidak teragi olehp1 Maka

    pa E aCp8&4$ Cmodp

    u&)i :

    Pertama( diasumsikan ah0a

    p

    aE &) Maka perkongruenan x$a Cmod p

    mempunyai seuah solusixE xo) Dengan antuan teorema 5ermat maka diperoleh 1

    aCp8&E Cxo$Cp8&4$Exo

    p8&E & Cmodp

    9leh sea itu( jika

    p

    aE &( maka dapat dikatakan

    p

    aE aCp8&4$Cmodp

    Kedua( diasumsikan ah0a

    p

    aE 8&) Maka perkongruenan x$ a Cmod p tidak

    mempunyai solusi) Dengan teorema $) untuk setiap ilangan ulat i sedemikian

    hingga & W iWpB &( terdapat dengan tunggal seuah ilangan ulat Cdengan & W

    iWpB &( sedemikian hingga iC aCmodp) Selanjutnya( karena perkongruenanx$

    aCmodp tidak mempunyai solusi( dapat dikatakan ah0a iRC) 9leh sea itu

    ilangan B ilangan ulat &( $( /( )))( p8& dapat dipasangkan menjadi$

    &ppasang

    dengan perkalian dari a) Dengan mengalikan pasangan8pasangan ini diperoleh Cp8&

    aCp8&4$Cmodp

    Dengan antuan "eorema 2ilson diperoleh 8& aCp8&4$Cmodp)

    Akiatnya

    p

    a aCp8&4$Cmodp)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    54/133

    Te+'e*- %1%=17 R+sen8 !;;3 : 33"9

    Misalkanpadalah ilangan prima ganjil( a dan $adalah ilangan B ilangan ulat

    yang tidak teragi olehp) Maka

    Ci 'ika a $Cmodp( maka

    p

    aE

    p

    $

    Cii

    p

    a)

    p

    $E

    p

    a$

    Ciii

    p

    a $

    E &

    u&)i :

    Ci 'ika a $ Cmodp( maka perkongruenanx$ a Cmodp mempunyai seuah

    solusi jika dan hanya jikax$ $Cmodp mempunyai seuah solusi) 9leh sea

    itu

    p

    aE

    p

    $)

    Cii Dengan antuanEulerFs %riteriondiperoleh 1

    p

    a aCp8&4$Cmodp(

    p

    $ $Cp8&4$Cmodp(

    p

    a$ Ca$Cp8&4$Cmodp)

    p

    a

    p

    $ aCp8&4$) $Cp8&4$Cmodp

    p

    a

    p

    $

    Ca$Cp8&4$Cmodp

    Sehingga dapat disimpulkan ah0a 1

    p

    a

    p

    $E

    p

    a$

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    55/133

    Ciii Karena

    p

    aE &( sehingga dari Cii diperoleh 1

    p

    a$

    E

    p

    a

    p

    aE &

    Te+'e*- %1%;1 7R+sen8 !;;3 : 339'ikapadalah seuah ilangan prima ganjil( maka

    p

    &E

    D,Cmod&jika&

    D,Cmod&jika&

    p

    p

    u&)i :

    Dengan 6ulerZs *riterion diperoleh 1

    p

    & C8&Cp8&4$Cmodp

    'ikap & Cmod ,( makapE ,k & untuk ilangan ulat k) sehingga diperoleh 1

    C8&Cp8&4$E C8&$kE &( akiatnya

    p

    &E&)

    'ikap / Cmod ,( makapE ,k / untuk ilangan ulatp)

    sehingga diperoleh 1

    C8&Cp8&4$

    E C8&$k&

    E 8&( akiatnya

    p

    &

    E 8&)

    !!1 Si*5+l #-+5i

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    56/133

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    57/133

    Civ

    n

    $E C8&Cn

    $ 8&4#)

    u&)i :

    Dengan 5aktorisasi prima nEp&t&p$

    t$ )))pmtm )

    Ci Dari 5aktorisasi prima terseut diketahui ah0a p adalah 5aktor atau pemagi

    prima dari n( maka a $ Cmod n) 9leh sea itu dengan "eorema $)$# Ci

    diperoleh

    p

    a

    E

    p

    $

    ) :al ini juga erlaku untuk na

    dan n$

    ( yaitu 1

    n

    aE

    &

    &

    t

    p

    a

    $

    $

    t

    p

    a

    ))))

    mt

    mp

    a

    E

    &

    &

    t

    p

    $

    $

    $

    t

    p

    $

    ))))

    mt

    mp

    $

    E

    n

    $

    Cii "eorema $)$# Cii menyatakan ah0a

    ip

    a$E

    ip

    a

    ip

    $( sehingga 1

    n

    a$E

    &

    &

    t

    p

    a$

    $

    $

    t

    p

    a$

    ))))

    mt

    mp

    a$

    E&

    &

    t

    p

    a

    $

    $

    t

    p

    a

    ))))

    mt

    mp

    a

    &

    &

    t

    p

    $

    $

    $

    t

    p

    $

    ))))

    mt

    mp

    $

    n

    a$E

    n

    a

    n

    $

    Ciii "eorema $)$- menyatakan ah0a

    p

    & C8&Cp8&4$( denganp adalah ilangan

    prima) Sehingga 1

    n

    &E

    &

    &

    &t

    p

    $

    $

    &t

    p

    ))))

    mt

    mp

    &

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    58/133

    n

    &E C8&

    + $4D&&

    C& pt

    + $4D&

    $C

    $ pt $4D&C)))) +

    mp

    mt

    Dengan 5aktorisasi prima dari n( diperoleh 1

    nE C&Cp&8& &t C&Cp$8& $t )))) C&Cpm8& mt

    Karena CpiB & suatu ilangan genap( maka

    C&Cpi8& &t &tiCpi8& Cmod ,

    Dan

    C&tiCpi8& C&tjCpj8& &tiCpi8& &tjCpj8& Cmod ,

    9leh sea itu(

    n &t&Cp&8& t&Cp$8& ))) tmCpm8& Cmod ,

    akiatnya(

    $

    D&C nE t&Cp&8&4$ t&Cp$8&4$ ))) tmCpm8&4$ Cmod $

    Sehingga diperoleh

    n

    &E C8&

    $

    D&C n

    Civ 'ikapadalah ilangan prima( maka

    p

    $E C8&

    #4D&C $ p) 9leh sea itu

    n

    $E

    &

    &

    $t

    p

    $

    $

    $t

    p

    ))))

    mt

    mp

    $

    n

    $E C8&

    + #4D&C $

    && pt ++ ))))#4D&C $

    $$ pt + #4D&C $

    && pt #4D&C $

    mm pt

    Dari pemuktian teorema $)/% Ciii diperoleh 1

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    59/133

    n$E C&Cp&$8& &t C&Cp$$8& $t ))) C&Cpm$8& mt )

    Karenapj$

    B & % Cmod #( sehingga diperoleh 1

    C&Cpi$8& it & tiCpi$B & Cmod .,

    dan

    C& tiCpi$B & C& tjCpj$B & & tiCpi$B & tjCpj$B & Cmod .,

    9leh sea itu

    n &t&Cp&$8& t&Cp$$8& ))) tmCpm$8& Cmod .,

    sehingga

    #

    D&C $ n

    t&Cp&$8&4# t&Cp$$8&4# ))) tmCpm$8&4# Cmod #

    Atau

    n

    $

    E C8& #

    D&C $ n

    41 S)'u&)u' Al-5-'

    Pada sua ini dijelaskan eerapa konsep dasar struktur aljaar seperti

    Partisi dan relasi ekuivalensi( grup( grup siklik( grup 5aktor( homomor5isma(

    gelanggang dan lapangan) Konsep ini penting( karena pada pemahasan selanjutnya

    mengenai sistem kriptogra5i kurva eliptik( perhitungan8perhitungannya dilakukan di

    dalam suatu struktur aljaar)

    1. P-')isi >-n Rel-si E&ui/-lensi

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    60/133

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    61/133

    De.inisi1 %1%31 7Su&i'*-n8 %003 : "!9

    Misalkan H adalah himpunan yang tidak kosong dan operasi pada Hadalah suatu

    operasi iner) :impunan Hersama B sama dengan operasi iner ditulis CH(

    adalah suatu grup( ila memenuhi aksioma B aksioma erikut( yaitu 1

    Ci

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    62/133

    De.inisi %1%"17Su&i'*-n8 %003 : 39

    Misalkan Hsuatu grup( apailaI HdanI ,makaIdiseut kompleks dari H)

    Apaila(CH adalah himpunan kuasa dari H( yaitu himpunan dari semua himpunan

    agian dari H( maka dapat dide5inisikan operasi B operasi iner pada (CH( misalnya

    irisan C ( gaungan C ( selisih C8)

    De.inisi %1%1 7Su&i'*-n8 %003 : 39

    MisalkanIdanKadalah kompleks B kompleks dari grup H( maka

    Ci IKE a$Q aIdan $K

    Cii I8& E a8&Q aI

    Te+'e*- %13!1 7Su&i'*-n8 %003 : 69

    'ikaIsuatu kompleks dari !rup H( makaI merupakan sugrup H jika dan hanya

    jika a$I( a$8&

    I)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    63/133

    MisalkanJsugrup dari grup H( makaJdiseut sugrup normal dari HditulisJ

    Hjika dan hanya jika gH gJ = Jg dengan gN E gnQ nJ dan JgEngQ nJ)

    De.inisi %1%

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    64/133

    !rup terhadap perkalian dariZnadalahZn E a ZnQg!dCan E &) 'ikapilangan

    primaZp E aZp Qg!dCap E & E aQ & a p 8&)

    De.inisi %13!1 7Menees e)1 -l8 !;;< : 6;9

    9rder dariZn dide5inisikan seagai anyaknya elemenZn yang dinotasikan dengan Q

    ZnQ)

    Dari de5inisi $)$+ dan $)/% dapat disimpulkan ah0a order dariZp adalahp8&)

    Menurut de5inisi $)$+( Zp denganpilangan prima adalah himpunan kelas

    ilangan ulat modulop yang saling prima denganp) :impunanZp terhadap operasi

    perkalian modulopmementuk struktur grup siklik)

    Misalkanp merupakan ilangan prima( maka himpunanZp E &( $( /( )))( p 8& darip

    8& ilangan ulat positi5 pertama adalah grup aelian erhingga dengan order p 8&(

    dengan perkalian modulo pseagai komposisinya)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    65/133

    $) Akan diuktikan Hp ersi5at asosiati5 terhadap operasi perkalian modulop)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    66/133

    Amil searang a$ Zp) Misalkan r a-$ Cmod p dengan r adalah residu

    terke7il tak negati5 modulop( sedemikian hingga kp + r = a$( untuk k anggota

    ilangan ulat) Karena a $merupakan anggota ilangan ulat maka erlaku si5at

    komutasti5( sehingga kp + r = $a r $-a Cmodp) 'adi terukti ah0aZp

    ersi5at komutati5 terhadap operasi perkalian modulop)

    Dari pemuktian diatas dapat disimpulkan ah0a Zp adalah grup aelian dengan

    orderp8&)

    4. H+*+*+'.is*- G'u(

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    67/133

    HZ) :omomorpisme dari suatu grup ke grup itu sendiri diseut endomorpisme)

    6ndomorpisme yang ijekti5 diseut dengan automorpisme)

    De.inisi %13317Su&i'*-n8 %003 : !0!9

    'ikafsuatu homomorpisme dari !rup Hke grup H ( maka kernel Cinti darifCdieri

    simol@ dide5inisikan oleh@E xHQfCx E e )

    Te+'e*- %13317Su&i'*-n8 %003 : !069

    Apailafsuatu homomorpisme dari grup Honto grup HZ dengan kernel@( maka @H

    6?

    Te+'e*- %13"17Su&i'*-n8 %003 : !0=9

    Misalkan f suatu homomorpisme dari grup H onto HZ dengan kernel @ ) IZ suatu

    sugrup dari HZ dan I E aHQfCaIZ yaitu himpunan semua prapeta dari

    elemen B elemenIF( makaIsugrup dari H I @( dan@

    I :Z)

    Te+'e*- %1317Su&i'*-n8 %003 : !0=9

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    68/133

    Misalkan suatu homomorpisme dari grup Honto grup HZ dengan kernel@) JZ

    HZ danJE a HQ Ca JZ( yaitu himpunan semua prapeta dari elemen B

    elemenJZ) MakaJ

    H dan )

    @J

    @H

    5. Gel-n,,-n,

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    69/133

    C( 1 suatu semigrup( yaitu 1*i Si5at tertutup terhadap perkalian)

    a$ *a.$ )*ii Si5at asosiati5) a$! *a.$.! = a.*$.!

    Si5at distriuti5 kiri dan kanan perkalian terhadap penjumlahan( yaitu 1

    a$!erlaku 1*i Distriuti5 kiri)

    *a + $.! = a.! + $.!*ii Distriuti5 kanan)

    a.*$ + ! = a.$ + a.!De.inisi %1317Su&i'*-n8 %006 : 39

    Misalkan C( ( 1 suatu gelanggang) Apaila S S dan CS( ( 1 adalah suatu

    gelanggang( maka dikatakan ah0a S adalah suring Canak gelanggang dari

    dengan operasi B operasi padadan Sharus sama)Te+'e*- %13617Su&i'*-n8 %006 : 369

    Misalkansuatu gelanggang dan S S - Sadalah anak gelanggang darijika

    dan hanya jika a$Serlaku*i a 5 $ S*ii a.$S

    De.inisi %13617Su&i'*-n8 %006 : 09Misalkansuatu gelanggang dan Sanak gelanggang darimaka 1

    *i S diseut ideal kanan dari( jika aS rerlaku a.rS-*ii S diseut ideal kiri dari( jika aS rerlaku r.aS-*iii S diseut ideal dua sisi Cideal dari jika aS( rerlaku

    a.rSdan r.aS-

    !elanggang komutati5 dengan elemen kesatuan dan tanpa elemen pemagi nol

    diseut >-e'-h in)e,'-l) !elanggang komutati5 dengan elemen kesatuan dan setiap

    elemen yang ukan nol mempunyai invers terhadap perkalian diseut *e>-n atau

    l-(-n,-nCfield) !elanggang dengan elemen kesatuan dan setiap elemen yang ukan

    elemen nol memiliki invers terhadap perkalian diseut ,el-n,,-n, (e*5-,i-n

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    70/133

    Cdivision ringL skeM field atau *e>-n *i'in, atau l-(-n,-n *i'in,) 'adi

    gelanggang pemagian komutati5 adalah suatu medan CSukirman( $%%. 1 &.)

    Te+'e*- %13

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    71/133

    is+*+'(is*e dari ke Z) Apaila ada suatu is+*+'(is*e dari gelanggang ke

    gelanggangZ dan ditulis F) H+*+*+'(is*edari suatu gelanggang kedirinya

    sendiri diseut en>+*+'(is*e) En>+*+'(is*e yang ijekti5 diseut

    -u)+*+'(is*e)

    D1 K'i()+,'-.i

    Kriptografi C!ryptograp)y erasal dari ahasa Yunani( terdiri dari dua suku

    kata yaitu kriptos dan grap)ein) Kriptos artinya menyemunyikan( sedangkan

    grap)einartinya menulis) Kriptogra5i adalah ilmu yang mempelajari prinsip B prinsip

    dan teknik B teknik sedemikian hingga dapat menyemunyikan suatu in5ormasi atau

    pesan Cpesan asli plaintext menjadi seuah teks tersemunyi atau !)ipertexts dan

    kemudian 7hiperte>t terseut diuah menjadi pesan asli atauplaintext oleh pengguna

    resmi dengan menggunakan kun7i rahasia atause!ret key CYan( $%%$ 1 //$) Sehingga

    dapat disimpulkan ah0a kriptogra5i erperan penting dalam pengirimanan in5ormasi

    atau pesan terutama pada masalah keamanan) Akan tetapi tidak semua aspek

    keamanan in5ormasi dapat diselesaikan dengan kriptogra5i) Ketika suatu pesan

    dikirim dari suatu tempat ke tempat lain( isi pesan terseut mungkin dapat disadap

    oleh pihak yang tidak resmi yang tidak erhak untuk mengetahui isi pesan terseut)

    Untuk menjaga pesan( maka pesan terseut dapat diuah menjadi suatu teks atau

    seuah kode yang sukar dimengerti C!)ipertext) Enkripsi adalah seuah proses

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    72/133

    pengkodean yang melakukan peruahan seuah kode atau pesan asli dari yang mudah

    dimengerti Cplainteks menjadi seuah teks atau kode yang sukar dimengerti

    C!ip)erteks) Sedangkan proses untuk menguah !ip)ertextmenjadiplaintextdiseut

    dekripsi) Proses enkripsi dan dekripsi memerlukan suatu mekanisme dan kun7i

    tertentu) (laintext iasa disimolkan seagai . C.essage) Sedangkan !)ipertext

    iasanya disimolkan seagai %C%)ipertext)

    Kriptoanalisis C!ryptanalysis erasal dari ahasa Yunani yang terdiri dari dua

    suku kata yaitu kriptos yang artinya menyemunyikan dan analyein yang artinya

    meme7ahkan( sehingga kriptoanalisis adalah kealikan dari kriptogra5i( yaitu suatu

    ilmu untuk meme7ahkan mekanisme kriptogra5i dengan 7ara mendapatkan kun7i dari

    !ip)ertextyang digunakan untuk mendapatkan plainteks) Akan tetapi kritogra5i dan

    kritoanalisis ter7akup dalam suatu ilmu yang diseut dengan Kriptologi C!ryptology

    CYan( $%%$ 1 //$) Yaitu(

    Kriptologidef

    = Kriptogra5i Kriptoanalisis( dan

    Kriptogra5i 6nkripsi Dekripsi)

    Pada kriptogra5i modern( kriptogra5i dapat diartikan seagai ilmu yang

    mempelajari sistem B sistem yang ersi5at matematis untuk meme7ahkan dua masalah

    keamaan( yaitu 1

    Ci Kerahasiaan ataupriva!y)

    Cii Autentikasi atau aut)enti!ation)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    73/133

    Kerahasiaan adalah aspek yang erhuungan dengan penjagaan isi in5ormasi dari

    siapapun ke7uali yang memiliki otoritas atau kun7i rahasia untuk memuka in5ormasi

    yang telah dienkripsi) Sedangkan Autentikasi adalah aspek yang erhuungan dengan

    identi5ikasi atau pengenalan( aik se7ara kesatuan sistem maupun in5ormasi itu

    sendiri) Dua pihak yang saling erkomunikasi harus saling memperkenalkan diri)

    In5ormasi yang dikirimkan harus diautentikasi keaslian( isi datanya( 0aktu

    pengiriman( dan lain8lain)

    !1 Se-'-h K'i()+,'-.i

    Kriptogra5i sudah digunakan sekitar ,% aad yang lalu oleh orang8orang Mesir

    untuk mengirim pesan ke pasukan yang erada di medan perang dan agar pesan

    terseut tidak tera7a oleh pihak musuh 0alaupun pema0a pesan terseut

    tertangkap oleh musuh) Sekitar ,%% SM( kriptogra5i digunakan oleh angsa Spartan

    dalam entuk sepotong papirus atau perkamen yang diungkus dengan atang kayu)

    Pada Laman @oma0i kuno( ketika 'ulius *aesar ingin mengirimkan pesan rahasia

    pada seorang 'endral di medan perang) Pesan terseut harus dikirimkan melalui

    seorang prajurit( tetapi karena pesan terseut mengandung rahasia( 'ulius *aesar tidak

    ingin pesan terseut teruka di tengah jalan) Di sini 'ulius *aesar memikirkan

    agaimana mengatasinya yaitu dengan menga7ak isi pesan terseut menjadi suatu

    pesan yang tidak dapat dipahami oleh siapapun ke7uali hanya dapat dipahami oleh

    'endralnya saja) "entu sang 'endral telah dieri tahu seelumnya agaimana 7ara

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    74/133

    mema7a pesan yang tera7ak terseut( karena telah mengetahui kun7inya) Konversi

    karakter ajad padaNulius %aesarFs %)iperadalah seperti erikut)

    A < * D ===== 2 ] Y H

    D 6 F ! =====) H A < *

    Pada perang dunia kedua( 'erman menggunakan mesin enigma yang

    digunakan :itler untuk mengirim pesan kepada tentaranya di medan perang) 'erman

    sangat per7aya ah0a pesan yang dienkripsi menggunakan enigma tidak dapat

    dipe7ahkan) "api anggapan itu keliru( setelah ertahun8tahun sekutu mempelajarinya

    dan erhasil meme7ahkan kode8kode terseut) Kun7i yang digunakan untuk

    meme7ahkan kode B kode enigmaadalah.ilton Keynes) Setelah 'erman mengetahui

    ah0a enigmadapat dipe7ahkan( maka enigmamengalami eerapa kali peruahan)

    Pengemangan paling mengejutkan dalam sejarah kriptogra5i terjadi pada

    &+-. saat Di55ie dan :ellman mempulikasikan JeM &ire!tions in %ryptograp)y)

    "ulisan ini memperkenalkan konsep revolusioner kriptogra5i kun7i pulik dan juga

    memerikan metode aru untuk pertukaran kun7i( keamanan yang erdasarkan

    masalah logaritma diskret) Meskipun Di55ie dan :ellman tidak memiliki realisasi

    praktis pada ide enkripsi kun7i pulik saat itu( idenya sangat jelas dan menumuhkan

    ketertarikan yang luas pada komunitas kriptogra5i) Pada &+-# @ivest( Shamir dan

    Adleman menemukan ran7angan enkripsi kun7i pulik yang sekarang diseut @SA)

    "ahun #%8an terjadi peningkatan luas di area ini( sistem @SA masih aman) Sedangkan

    pada tahun &+#3( i7tor Miller dan Neil KolitL mengusulkan Ellipti! %urve (u$li!

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    75/133

    Key %ryptosystems C6*PK* yang selanjutnya diseut dengan Ellipti! %urve

    %ryptosystemsC6**)

    %1 Al,+'i)*- >-n Kuni

    Suatu 5ungsi matematis yang digunakan untuk melakukan proses enkripsi dan

    proses dekripsi diseut dengan algoritma kriptogra5i atau !)iper dengan

    menggunakan kun7i Ckey yang disimolkan seagai K)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    76/133

    kun7i aik kun7i enkripsi maupun kun7i dekripsi( dan algoritma kriptogra5i termuat

    dalam suatu sistem yang diseut dengan sistem kriptogra5i)

    31 Sis)e* K'i()+,'-.i

    De.inisi %13;1 7Y-n8 %00; : %==9

    Sistem kriptogra5iC!ryptosystem adalah suatu sistem matematis .8 tuple

    OE C( %( ( ( e d 1

    &).adalah himpunan plainteks(

    $) %adalah himpunan 7ipherteks(

    /) eadalah himpunan dari kun7i B kun7i enkripsi(

    ,) dadalah himpunan dari kun7i B kun7i dekripsi(

    3) adalah proses enkripsi dengan menggunakan e

    el1M %

    ?- adalah proses dekripsi dengan menggunakan d

    dl1 %\ & )

    dan adalah sepasang 5ungsi yang inverti$le dan harus memenuhi diC eiC

    E ( M ( eie did- 'ika e = d( maka " adalah seuah sistem kriptogra5i

    simetri( sealiknya jika e d( maka " diseut dengan seuah sistem kriptogra5i

    asimetri atau dapat dikatakan apaila dalam suatu sistem kriptogra5i digunakan

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    77/133

    algoritma simetri maka sistem kriptogra5i terseut adalah sistem kriptogra5i simetri(

    sedangkan apaila menggunakan algoritma asimetri( maka sistem kriptogra5i terseut

    adalah sistem kriptogra5i asimetri)

    Khalayak umum dan Kriptanalis

    Saluran aman .Z

    (u$li! Key (rivate Key

    G-*5-' %131Skema sistem kriptogra5i modern CYan( $%%+ 1 $+&

    Suatu sistem kriptogra5i terdiri dari seuah algoritma( seluruh kemungkinan

    plainteks( 7ipherteks dan kun7i8kun7inya) Sistem kriptogra5i merupakan suatu

    5asilitas untuk mengkonversikan plainteks menjadi 7ipherteks( dan sealiknya)

    Pada seuah sistem kriptogra5i asimetri( kun7i enkripsi ekereda dengan

    kun7i dekripsi dk)Sistem kriptogra5i asimetri mempunyai eerapa keleihan apaila

    diandingkan dengan sistem kriptogra5i simetri( salah satunya adalah keuntungan

    pada pendistriusian kun7i B kun7i)

    "1 Pe's-*--n Weie's)'-ss

    Pada pemahasan skripsi ini yang dimaksud dengan kurva eliptik E adalah

    seuah gra5ik dari seuah persamaan 1

    4esan=nkripsi

    C =

    Eel(M)

    #ekripsi

    M =

    Ddl(C)

    4esan

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    78/133

    y$Ex/ax + $ C$)&

    dengan suatu konstanta adan $) Persamaan C$)& merupakan persamaan 2eierstrass

    untuk seuah kurva eliptik yang dide5inisikan atas lapangan( misalnya kurva eliptik

    atas ilangan real( kurva eliptik atas ilangan kompleks( kurva eliptik atas lapangan

    hingga)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    79/133

    depressed !u$i! e7uation) Solusi persamaan terseut telah ditemukan oleh !irolamo

    *ardano)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    80/133

    A III

    PEMAHASA$

    Suatu sistem kriptogra5i terdiri dari algoritma kriptogra5i( seluruh

    kemungkinan plainteks( 7ipherteks dan kun7i8kun7inya) Sistem kriptogra5i kurva

    eliptik merupakan sistem kriptogra5i asimetri atau sistem kriptogra5i kun7i pulik)

    Sistem kriptogra5i kurva eliptik( yaitu suatu sistem kriptogra5i yang menggunakan

    algoritma kriptogra5i kurva eliptik( de5inisi himpunanBhimpunanplaintext !)ipertext(

    dan kun7i( sertaproses pementukan kun7i( proses enkripsi dan dekripsi)Untuk saat ini terdapat tiga permasalahan matematika yang menjadi dasar

    sistem kriptogra5i asimetri yang dianggap aman dan e5isien) Sistem8sistem kriptogra5i

    terseut apaila diklasi5ikasikan menurut permasalahan matematikanya adalah 1&) @nteger a!toriDation (ro$lemCIFP( 7ontoh 1 sistem kriptogra5i @SA C@ivest B

    Shamir8Adleman) Dalam sistem kriptogra5i @SA( kun7i pulik merupakan

    pasangan ilangan ulat Cn e( sedangkan kun7i rahasianya adalah pasangan

    ilangan ulat Cn d)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    81/133

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    82/133

    algoritma kriptogra5i kurva eliptik atasZp( akan diahas mengenai kurva eliptik atas

    Zperikut ini)

    1. Ku'/- Eli()i& -)-sZpKurva 6liptik yang dide5inisikan atasZpmerupakan materi terpenting dalam

    sistem kriptogra5i kurva eliptik atas Zp( karena proses pementukan kun7i( proses

    enkripsi( dan dekripsi menggunakan titik8titik pada kurva eliptik atas Zp eserta

    dengan operasi8operasi yang perlaku pada kurva eliptik atasZp)De.inisi 31!1 7S)ins+n8 %006 : %=9

    Misalkan padalah seuah ilangan prima yang leih esar dari /) Kurva eliptik

    atas Hp dide5inisikan oleh 1E CZp E CxyZp>ZpQy$ x/ ax $Cmodp

    dengan a($Zp sedemikian hingga ,a/ $-$$ % Cmod p) "itik diseut dengan

    titik infinity atau titikin5initas)

    1.1 O(e'-si @ O(e'-si (->- Ku'/- Eli()i& -)-s pDierikan suatu kurva eliptik atas Hp( yaitu E*Zp 1 y

    2= x3 + ax + $modp

    dengan titik infinity seagai elemen identitas terhadap operasi penjumlahan)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    83/133

    E&$

    &$

    xx

    yy

    C/)$

    danv = $$&& xyxy = )

    Untuk mendapatkan titik8titik pada ECZp yang dilalui garis '( sustitusi

    persamaan /)& kedalam persamaan kurva eliptik y2= x3 + ax + $( sehingga

    diperoleh 1Cx v$ = x3 + ax + $

    %D$C $$$/ =++ v$xvaxx C/)/

    'ika x&( x$( x/ merupakan solusi dari persamaan y2 = x3 + ax + $ maka

    erlaku 1

    %DCDCDC /$&/$/&$&$

    /$

    /& =+++++ xxxxxxxxxxxxxxx C/),

    Dari persamaan /)/ dan /), diperoleh

    $&

    $

    / xxx = C/)3Untuk men7ari nilai y/( harus dihitung kemiringan dari suatu garis yang

    melalui titik Cx&(y& dan C /x ( /y ( yaitu 1

    &/

    &/

    xx

    yy

    = C/).

    Dari persamaan /). diperoleh&/&/ DC yxxy = C/)-

    Dari penjaaran diatas dapat disimpulkan ah0a pada kasus I( untuk

    penjumlahan dua titik( P ECZp dengan( = Cx&(y& dan P = Cx$(y$) 'ikax&

    x$makaCx&(y& Cx$(y$ E Cx/(y/ C/)#

    dengan

    $&

    $

    / xxx = C/)+

    &/&/ DC yxxy = C/)&%dan

    E&$

    &$

    xx

    yy

    C/)&&

    51 K-sus II

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    84/133

    Apailax& Ex$ dany&E $y atau dengan kata lain( untuk penjumlahan dua

    titik( P ECZp dengan( = Cx&(y& dan P = C && ( yx makaC && (yx C && ( yx E C D( // yx

    Untuk men7ari x/ dany/( maka harus di7ari kemiringan garis '( yaitu suatu

    garis yang memotong kurva eliptik ECZp( dan melalui titik( = Cx&(y& dan

    P = C && ( yx yaitu 1

    &$

    &$

    xx

    yy

    = E =+

    =$$

    $$

    xx

    yy

    Kemudian sustitusi = ke persamaan /)+ dan /)&%( sehingga diperoleh 1

    x/ Ey/ Eatau

    Cx/(y/ E

    Dari penjaaran diatas dapat disimpulkan ah0a Cxy C D( yx E (

    DCD(C pZEyx )

    1 K-sus III

    Apailax&E x$dany&E y$atau dengan kata lain( apaila dierikan suatu titik

    ( = Cx&(y& ECZp( maka penggandaan atas titik(( yaitu(( adalah 1Cx&(y& Cx&(y& E Cx/(y/

    Untuk men7ari x/ dany/( maka harus di7ari kemiringan garis '( yaitu suatu

    garis yang memotong kurva eliptikECZp dan melalui titik( = Cx&(y&( dengan

    men7ari turunan pertama dari persamaan kurva eliptik 1 y2 = x3 + ax + $

    terhadapx) "urunan pertama dari persamaan kurva eliptik terseut adalah 1

    axdx

    dyy += $/$ C/)&$

    Atau

    y

    ax

    dx

    dy

    $

    / $ +

    = C/)&/

    Karenadx

    dy= ( maka dari persamaan /)&/ diperoleh

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    85/133

    y

    ax

    $

    / $ +=

    SustitusixEx&danyEy&( sehingga diperoleh 1

    &

    $

    &

    $

    /

    y

    ax += C/)&,

    Untuk mendapatkan titik8titik pada ECZp yang dilalui garis '( sustitusi

    persamaan /)& kedalam persamaan kurva eliptik y2= x3 + ax + $( sehingga

    diperoleh 1

    %D$C $$$/ =++ v$xvaxx C/)&3

    'ikax&(x$(x/ merupakan solusi dari persamaan C/)&3 maka erlaku 1

    %DCDCDC /$&/$/&$&$

    /$

    /&

    =+++++ xxxxxxxxxxxxxxx C/)&.Dari persamaan /)&3 dan /)&. diperoleh

    $&

    $

    / xxx = C/)&-Untuk men7ari nilai y/( harus dihitung kemiringan dari suatu garis yang

    melalui titik Cx&(y& dan Cx/(8y/( yaitu 1

    &/

    &/

    xx

    yy

    = C/)

    Dari persamaan /) diperoleh

    &/&/ DC yxxy = C/)&+

    Dari penjaaran diatas dapat disimpulkan ah0a pada kasus III( untuk

    penggandaan atas titik(ECZp dengan( = Cx&(y&( makaCx&(y& Cx&(y& E Cx/(y/ C/)$%

    dengan

    $&

    $

    / xxx = C/)$&

    &/&/ DC yxxy = C/)$$dan

    &

    $

    &

    $

    /

    y

    ax += C/)$/

    Dari penjaaran diatas( maka dapat disimpulkan ah0a operasi8operasi yang erlaku

    pada kurva 6liptikECZp 1y2= x3 + ax + $atas Hp antara lain 1

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    86/133

    &) Kurva 6liptik ECZp mempunyai elemen identitas terhadap operasi

    penjumlahan( yaitu titik ( sehingga ( +=+ ( = ( untuk semua

    (ECZp)$) Untuk setiap titik pada kurva 6liptik ECZp mempunyai invers

    terhadap operasi penjumlahan atau se7ara matematis

    =+== DCD(CD(CD(CD(C ((ZEyx(ZEyx( pp )/) Penjumlahan titik)

    Misalkan D(CD(CdD(CD(C $$&& pp ZEyxPanZEyx( == dengan ( P(

    maka D(C // yxP( =+ ( dengan

    $&

    $

    &$

    &$

    / xxxx

    yyx

    = dan )DC &/&&$

    &$

    / yxxxx

    yyy

    =

    ,) Penggandaan titik)

    Misalkan DCD(C && pZEyx( = ( dengan (( ) Maka $( = (+( =Cx/(y/(

    dengan

    &

    $

    &

    $

    &/ $

    $

    /x

    y

    axx

    += dan )DC

    $

    // &/&

    &

    $

    & yxxy

    axy

    +=

    Untuk leih jelasnya( erikut dierikan seuah 7ontoh men7ari titik B titik pada

    kurva eliptik dan salah satu titik pada kurva eliptik terseut ditentukan seagai

    generator suatu sugrup siklik dalam kurva eliptik)

    4+n)+h 31!

    MisalkanECZ11 adalah seuah kurva 6liptiky$Ex/x / atasZ11) Akan di7ari titik8

    titik padaECZ11)

    T-5el 31!1 Ti)i& @ )i)i& (->- &u'/-"%Bx3CxC 3 -)-sZ11

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    87/133

    x x/x / mod &&Sisa

    Kuadratik y *x y

    % / Ada 3 dan . C%(3 dan C%(.& 3 Ada , dan - C&(, dan C&(-

    $ $ "idak Ada 8 8

    / % Ada % C/(%

    , 3 Ada , dan - C,(, dan C,(-

    3 & Ada & dan &% C3(& dan C3(&%

    . 3 Ada , dan - C.(, dan C.(-

    - & Ada & dan &% C-(& dan C-(&%

    # . "idak Ada 8 -

    + , Ada $ dan + C+($ dan C+(+

    &% & Ada & dan &% C&%(& dan C&%(&%

    'adi titik8titiknya adalah 1 (&C%(3_($C%(._(/C&(,_(,C&(-_(3C/(%_(.C,(,_(-C,(-_

    (#C3(&_(+C3(&%_(&%C.(,_(&&C.(-_(&$C-(&_(&/C-(&%_(&,C+($_(&3C+(+_ (&.

    C&%(&_(&-C&%(&%)

    Kurva 6liptikECZ111y

    $

    Ex

    /

    x / atasZ11mempunyai titik)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    88/133

    x/ By&( dengan E 3( x1E 3(y1E &(x2E 3 (y2E &( maka diperolehx/E ,( dany/E

    ,)

    Sehingga( + PE E C3(& C3(& E C,(, E $ ) Se7ara analog diperoleh 1

    T-5el 31%1 Su5,'u( Si&li& >-l-*"%Bx3CxC 3 *+> !! >en,-n ,ene'-)+'

    B 78!9.

    & E C3(& - E C+($ &/ E C&%(&

    $ E C,(, # E C.(- &, E C-(&%

    / E C%(. + E C/(% &3 E C%(3, E C-(& &% E C.(, &. E C,(-

    3 E C&%(&% && E C+(+ &- E C3(&%

    . E C&(, &$ E C&(- E

    Setelah dijelaskan tentang kurva eliptik atas Zp erikut akan dijelaskan

    algoritma kurva eliptik atas Zp( yaitu suatu algoritma yang digunakan dalam sistem

    kriptogra5i kurva eliptik atasZp)

    2. Al,+'i)*- Ku'/- Eli()i& A)-sZp

    Dalam algoritma kriptogra5i terdapat tiga proses yaitu proses pementukan

    kun7i( proses enkripsi( dan proses dekripsi) Untuk leih jelasnya mengenai algoritma

    kurva eliptik AtasZperikut ini dierikan suatu gamaran singkat proses pengiriman

    pesan dengan menggunakan sistem kriptogra5i kurva eliptik atasZp)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    89/133

    Penerima

    Pesan

    Pengirim

    Pesan

    "idak

    Ya

    Penerima "idak

    Pesan

    Ya

    G-*5-' 31!Sistem Kriptogra5i Kurva 6liptik atasZp-

    MU?AI

    Proses 6nkripsi 1

    el*s=*s , + s, = *!

    1!

    2

    Proses Dekripsi 1

    dlC!

    1!

    2E !

    2 k , !

    1

    S6?6SAI

    Proses Pementukan Kun7i

    Penerima Pesan Mengirim Kun7i Pulik Kepada Pengirim Pesan

    Melakukan enkripsi pada

    plaintext

    Mengetahui Kun7i

    @ahasia k

    Mendapatkan kun7i pulik

    Mendapat(laintext

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    90/133

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    91/133

    tetapi tidak dapat mengetahui isi dari pesan terseut( karena tidak memiliki kun7i

    rahasia)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    92/133

    Dalam proses enkripsi sendiri terdapat aturan enkripsi elECZp yaitu 5ungsi

    el 1.

    % yang memetakan setiapplaintext ke !)ipertext dengan 5ungsi ijekti5)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    93/133

    Karena *s, merupakan elemen sugrup siklik dalam kurva eliptik atas Zp

    maka terdapat invers *s,

    yaitu 8*s,

    sedemikian hingga

    * s , + ** s , = -

    Maka persamaan C/), menjadi)

    + * s , + ** s , = + * s , + + ** s ,

    + = +

    =

    'adi terukti ah0a elmerupakan 5ungsi injekti5)

    ii Diuktikan el merupakan 5ungsi surjekti5 yaitu harus diuktikan ah0a

    *!1!2 % . el C s = *!1!2

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    94/133

    $- Memilih ilangan ulats Zpse7ara a7ak)!- Menghitung !1= s , dan !2= Is+ -

    d- Mengirim plaintext

    dalam entuk !)ipertext J!1!2 kepada penerima

    pesan)

    Setelah dijelaskan tentang proses enkripsi( yaitu suatu proses yang menguah

    plaintext menjadi !)ipertext agar terjaga kerahasiaannya( maka erikut akan

    dijelaskan tentang proses dekripsi( yaitu suatu proses yang menguah !)ipertext

    menjadiplaintext)

    31 P'+ses De&'i(si

    Setiap penerima pesan menguah !)ipertext yang telah diterimanya menjadi

    plaintext dengan menggunakan kun7i priadi yang telah dimilikinya) Proses ini

    dinamakan proses dekripsi( sehingga penerima pesan dapat mengetahui isi dari pesan

    yang dikirim oleh pengirim pesan)Dalam sistem kriptogra5i terdapat aturan dekripsi yaitu 5ungsi dl 1 % .

    yang memetakan setiap !)ipertext ke plaintext 5ungsi ini merupakan 5ungsi invers

    dari 5ungsi el 1. % yang digunakan pada proses enkripsi)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    95/133

    Menurut de5inisi 5ungsi dekripsi diperoleh 1

    dlC!1!2 E !2 k , !1 dlC!1!2 E + s, 8 k , s,

    dlC!1!2 E *s, + **s,

    dlC!1!2 E

    dlC!1!2 E

    'adi terukti ah0a dl merupakan 5ungsi invers dari el

    Dari penjelasan yang telah dierikan tentang proses dekripsi( maka untuk melakukan

    dekripsi pesan harus melakukan algoritma dekripsi seagai erikut)

    a) Menggunakan kun7i priadi k untuk menghitung !25 k ,!1)) Mendapatkanplaintext dengan menghitung !25 k ,!1)

    Setelah dijelaskan mengenai sistem kriptogra5i kurva eliptik atasZp(erikut

    akan dijelaskan Pengiriman Pesan dengan Menggunakan Sistem Kriptogra5i Kurva

    6liptik atas Zpyang erisi 7ontoh87ontoh pengiriman pesan dengan menggunakan

    sistem kriptogra5i kurva eliptik atasZp

    #. Pen,i'i*-n Pes-n >en,-n Men,,un-&-n Sis)e* K'i()+,'-.i Ku'/- Eli()i&

    -)-sZp1

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    96/133

    Pengiriman pesan dengan menggunakan sistem kriptogra5i kurva eliptik atas

    Zp telah diper7aya dapat memerikan jaminan akan kerahasiaan pesan yang dikirim

    oleh pihak pengirim pesan) Pesan terseut dikirim kepada pihak8pihak penerima

    pesan yang resmi erkomunikasi dengan pihak pengirim pesan) Misalkan pihak8

    pihak yang erkomunikasi dalam 7ontoh pengiriman pesan dengan menggunakan

    sistem kriptogra5i kurva eliptik atas Zp telah menyepakati ilangan prima yang

    digunakan adalah ilangan ulatp E /,- dan kurva eliptik yang digunakan adalah

    E 1y2= x3+ x + 3-

    Pada *ontoh $)$% telah ditunjukkan ah0a ilangan p E /,- merupakan

    ilangan prima( selain itu juga dapat diuji dengan antuan program komputer) Untuk

    menguji apakah ilangan ulat p yang digunakan merupakan ilangan prima(

    menguji apakah kurva eliptik yang digunakan sesuai dengan De5inisi /)&( untuk

    men7ari titik8titik pada kurva eliptik terseut( menentukan generator dan sugrup

    siklik dalam kurva eliptik yang diangun serta operasi8operasi penjumlahan titik8titik

    pada kurva eliptik digunakan suatu program komputer( yaitu program Maple +)3

    dengan perintah8perintahnya terdapat pada ?ampiran &) Selain itu juga dierikan

    prosedur epoints( adde!( dan elgamal pada ?ampiran $) Prosedur8prosedur terseut

    disimpan seagai text file pada dire!tory( dimana Maple +)3 dijalankan) Sedangkan

    titik8titik pada kurva eliptik terseut dapat dilihat pada ?ampiran /)

    Setelah diperoleh generator dan sugrup siklik dalam kurva eliptik( yang

    dapat dilihat pada ?ampiran ,( maka pihak8pihak penerima pesan dapat melakukan

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    97/133

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    98/133

    :usein %)ipertext Aulia

    G-*5-' 31%1Pengiriman Pesan oleh :usein Kepada Aulia

    !1 P'+ses Pe*5en)u&-n Kuni

    Misalkan salah satu kun7i pulik yang dipilih oleh Aulia adalah E C%(+3 dan

    kun7i rahasia yang dipilih adalah k E /( maka E /E / )

    Untuk hasil perkalian /E /E C&-( &$#( dapat dilihat pada ?ampiran ,) Sugrup

    Siklik Dalam Kurva 6liptikE 1y2= x3+ x + 3 atasZ3Qdengan !enerator E C%(+3)

    Dari proses pementukan kun7i diperoleh kun7i pulik J( E JC%(+3(C&-(&$#

    dan kun7i rahasia kE /) Kemudian kun7i pulik terseut dikirim kepada :usein( agar

    :usein dapat melakukan proses enkripsi)

    %1 P'+ses En&'i(si

    :usein memperoleh kun7i pulik JC%(+3(C&-(&$#) Kemudian pesan CpassMord

    yang akan dikirim kepada Aulia adalah ;mat%.G( maka pesan terseut harus

    dienkripsi untuk menjaga kerahasiaannya) Seelum proses enkripsi( setiap karakter

    pesan terseut dikonversikan menjadi titik8titik pada kurva eliptik yang telah

    ditentukan) Pada ?ampiran 3 dapat dilihat konversi B konversi karakter terseut)

    T-5el 3131 K+n/e'si Pes-n *-)06

    Proses Dekripsi

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    99/133

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    100/133

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    101/133

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    102/133

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    103/133

    Penyelesaian)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    104/133

    Kholis proses pementukan kun7i( Kholis memilih $ E E C%(+3( dan

    kun7i rahasianya k2 E 3( maka diperoleh $ E 3E C+,($$3) Kemudian

    kun7i pulik J $ ( $ E JC%(+3( C+,($$3 dikirim kepada :usein)

    Setelah :usein menerima kun7i pulik dari !inanjar dan Kholis( maka proses

    selanjutnya adalah proses enkripsi) Proses enkripsi terseut dijelaskan seperti erikut)%1 P'+ses En&'i(si

    Seperti pada *ontoh /)$( karakter plaintextdikonversikan terleih dahulu(

    konversiplaintext terseut dapat dilihat pada "ael /)/( akan tetapi pada *ontoh

    /)/ :usein akan melakukan dua kali proses enkripsi( yang pertama yaitu proses

    enkripsi pada pesan yang akan dikirim kepada !inanjar( dalam proses enkripsi ini

    :usein memilih ilangan a7ak s1 E $( sedangkan yang kedua adalah proses

    enkripsi pada pesan yang akan dikirim kepada Kholis( dan pada proses enkripsi

    ini( :usein memilih ilangan a7aks2E ,) Proses8proses enkripsi pada pesan yang

    akan dikirim !inanjar dan Kholis erturut8turut dapat dilihat pada "ael /). dan

    "ael /)-)T-5el 3161 P'+ses En&'i(si Pes-n Un)u& Gin-n-'

    i (laintext i !1i =s1, s1 !2i E i s1

    %)ipertext R!1i!2i

    & C/$+(&&$ C$+(#$ C$--( $./ C$#-( -/ JC$+(#$( C$#-( -/

    $ C%(+3 C$+(#$ C$--( $./ C,#( &3+ JC$+(#$( C,#( &3+

    / C&$+($#/ C$+(#$ C$--( $./ C/&( /$ JC$+(#$( C/&( /$, C$#-(-/ C$+(#$ C$--( $./ C&&$( +- JC$+(#$( C&&$( +-

    3 C3#( $ C$+(#$ C$--( $./ C&33( /%3 JC$+(#$( C&33( /%3

    T-5el 31

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    105/133

    i (laintext i !1i =s2, s2 !2iE i s %)ipertext R!1i!2i

    & C/$+(&&$ C,$(,# C&$+( $#/ C3#( $ JC,$(,#( C3#( $$ C%(+3 C,$(,# C&$+( $#/ C//-( ,. JC,$(,#( C//-( ,.

    / C&$+($#/ C,$(,# C&$+( $#/ C$#.( &3& JC,$(,#( C$#.( &3&

    , C$#-(-/ C,$(,# C&$+( $#/ C&33( /%3 JC,$(,#( C&33( /%3

    3 C3#( $ C,$(,# C&$+( $#/ C&/#( /$% JC,$(,#( C&/#( /$%

    Setelah mendapatkan !)ipertext dari proses enkripsi( :usein mengirim

    !)ipertext terseut kepada !inanjar( dan :usein) %)ipertext terseut se7ara erturut8

    turut adalah %1 = JC$+(#$( C$#-( -/_ JC$+(#$( C,#( &3+_ JC$+(#$( C/&( /$_

    JC$+(#$( C&&$( +-_ JC$+(#$( C&33( /%3 dan %2 = JC,$(,#( C3#( $_ JC,$(,#(

    C//-( ,._ JC,$(,#( C$#.( &3&_ JC,$(,#( C&33( /%3_ JC,$(,#( C&33( /%3)

    Setelah !inanjar dan Kholis menerima !)ipertext yang dikirim oleh :usein(

    maka proses selanjutnya adalah proses dekripsi) Proses8proses dekripsi terseut

    dijelaskan seperti erikut)

    31 P'+ses De&'i(si

    Untuk mengetahuiplaintext yang dikirimkan oleh :usein( maka !inanjar dan

    Kholis harus melakukan proses dekripsi) Pada proses dekripsi( !inanjar

    menggunakan kun7i rahasia k1= Q sedangkan Kholis menggunakan kun7i rahasia

    k2= >- Proses8proses dekripsi yang dilakukan oleh !inanjar dan Kholis erturut8turut

    dapat dilihat pada "ael /)# dan /)+)

    T-5el 31=1 P'+ses De&'i(si Pes-n Oleh Gin-n-'

    i %)ipertext R!1i!2i k1,*!1i i E !2i C8 *!1i Karakter

    & JC$+(#$( C$#-( -/ C$--(#, C/$+(&&$ m

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    106/133

    $ JC$+(#$( C,#( &3+ C$--(#, C%(+3 a

    / JC$+(#$( C/&( /$ C$--(#, C&$+($#/ t

    i %)ipertext R!1i!2i k1,*!1i i E !2i C8 *!1i Karakter, JC$+(#$( C&&$( +- C$--(#, C$#-(-/ %

    3 JC$+(#$( C&33( /%3 C$--(#, C3#( $ .

    T-5el 31;1 P'+ses De&'i(si Pes-n Oleh Kh+lis

    i %)ipertext R!1i!2i k2,*!1i i E !2i C8 *!1i Karakter

    & JC,$(,#( C3#( $ C&$+( ., C/$+(&&$ m

    $ JC,$(,#( C//-( ,. C&$+( ., C%(+3 a/ JC,$(,#( C$#.( &3& C&$+( ., C&$+($#/ t

    , JC,$(,#( C&33( /%3 C&$+( ., C$#-(-/ %

    3 JC,$(,#( C&/#( /$% C&$+( ., C3#( $ .

    Dari proses8proses dekripsi yang dilakukan oleh !inanjar dan Kholis( maka

    diperoleh pesan yang sama yaitu ;mat%.G) Pesan terseut merupakan seuah

    passMord yang digunakan untuk menjalankan suatu program komputer yang diuat

    oleh :usein) *ontoh /)/ merupakan simulasi pengiriman pesan dengan

    menggunakan sistem kriptogra5i kurva eliptiky2= x3+ x + 3 atasZ3Q( pada 7ontoh

    terseut pengirim pesan erjumlah satu orang dan penerima pesan erjumlah dua

    orang( yaitu :usein seagai pihak pengirim pesan( sedangkan pihak penerima pesan

    adalah !inanjar dan Kholis) Se7ara singkat *ontoh /)$ dapat dijelaskan seperti

    erikut)

    :usein ingin mengirim pesan kepada !inanjar dan Kholis( pesan terseut

    sama dengan pesan pada *ontoh /)$( yaitu ;mat%.G yang dikonversikan menjadi

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    107/133

    plaintext. = C/$+(&&$_ C%(+3_ C&$+($#/_ C$#-(-/_ C3#( $) Seperti halnya

    pada *ontoh /)$( pihak penerima pesan( yaitu !inanjar dan Kholis mementuk kun7i)

    Kun7i pulik yang terentuk masing8masing adalah JC%(+3(C/$.($# dan JC%(+3(

    C+,($$3) Kun7i rahasia yang dientuk oleh !inanjar adalah k&E -( sedangkan kun7i

    rahasia yang dientuk oleh Kholis adalah k$E 3) Kemudian masing8masing kun7i

    pulik dikirim kepada :usein( agar :usein dapat melakukan proses enkripsi) Dengan

    menggunakan kun7i pulik yang dientuk oleh !inanjar( yaitu JC%(+3(C/$.($#(

    :usein menguahplaintext . = C/$+(&&$_ C%(+3_ C&$+($#/_ C$#-(-/_ C3#( $

    menjadi !)ipertext %1 = JC$+(#$( C$#-( -/_ JC$+(#$( C,#( &3+_ JC$+(#$( C/&(

    /$_ JC$+(#$( C&&$( +-_ JC$+(#$( C&33( /%3( kemudian !)ipertext terseut dikirim

    kepada !inanjar) Dengan menggunakan kun7i pulik yang dientuk oleh Kholis(

    yaitu JC%(+3(C+,($$3( :usein menguah plaintext . = C/$+(&&$_ C%(+3_

    C&$+($#/_ C$#-(-/_ C3#( $ menjadi !)ipertext %2 = JC,$(,#( C3#( $_

    JC,$(,#( C//-( ,._ JC,$(,#( C$#.( &3&_ JC,$(,#( C&33( /%3_ JC,$(,#( C&33(

    /%3( dan kemudian dikirim kepada Kholis) Dari proses enkripsi yang dilakukan

    oleh :usein dapat disimpulkan ah0a( apaila pada proses enkripsi menggunakan

    kun7i pulik yang ereda( maka diperoleh !)ipertext yang ereda( meskipun

    plaintext yang digunakan sama) Setelah menerima !)ipertext %1 = JC$+(#$( C$#-(

    -/_ JC$+(#$( C,#( &3+_ JC$+(#$( C/&( /$_ JC$+(#$( C&&$( +-_ JC$+(#$( C&33(

    /%3( maka !inanjar dapat melakukan proses dekripsi) Proses dekripsi yang

    dilakukan oleh !inanjar menggunakan kun7i rahasia k&E - dan diperolehplaintext .

    = C/$+(&&$_ C%(+3_ C&$+($#/_ C$#-(-/_ C3#( $) Sedangkan Proses dekripsi

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    108/133

    yang dilakukan oleh Kholis menggunakan kun7i rahasia k&E 3 menguah !)ipertext

    %2 = JC,$(,#( C3#( $_ JC,$(,#( C//-( ,._ JC,$(,#( C$#.( &3&_ JC,$(,#( C&33(

    /%3_ JC,$(,#( C&33( /%3 menjadi plaintext . = C/$+(&&$_ C%(+3_ C&$+($#/_

    C$#-(-/_ C3#( $) Dari proses dekripsi yang dilakukan oleh !inanjar dan Kholis

    diperoleh plaintext yang sama( meskipun !)ipertext yang dikirim oleh :usein

    ereda)

    Dari *ontoh /)$ dan *ontoh /)/ maka dapat disimpulkan ah0a apaila pihak

    penerima pesan hanya satu orang maka proses enkripsi hanya satu kali dengan

    menggunakan satu kun7i pulik yang telah dientuk oleh pihak penerima pesan)

    Apaila pihak penerima pesan erjumlah norang( maka proses enkripsi dilakukan

    seanyak n kali dengan menggunakan nkun7i pulik yang ereda) Dari proses

    enkripsi diperoleh n !)ipertext yang ereda- Akan tetapi dari proses dekripsi

    diperolehplaintextyang sama)

    Dengan menggunakan kurva eliptik dan ilangan prima yang sama seperti

    pada *ontoh /)$ dan *ontoh /)/ erikut akan dierikan *ontoh /),( dengan

    permasalahan dua erkomunikasi dan menjaga kerahasiaan komunikasi mereka

    dengan menggunakan sistem kriptogra5i kurva eliptikE 1y2= x3+ x + 3 atasZ3Q)

    Misalkan Dua orang yang erkomunikasi adalah dua orang @aja( yaitu King I

    dan King II) Kedua raja terseut seringkali menggunakan kekayaan kerajaan hanya

    untuk kepentingan priadinya( ukan untuk kepentingan rakyatnya)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    109/133

    4+n)+h 31"

    Pada suatu ketika( King I ingin mengirim pesan kepada King II) Pesan terseut

    erunyi ;

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    110/133

    !1 P'+ses Pe*5en)u&-n Kuni1

    -1 P'+ses Pe*5en)u&-n Kuni +leh Kin, I1

    Misalkan salah satu kun7i pulik yang dipilih oleh King I adalah & E E

    C%(+3 dan kun7i rahasia yang dipilih adalah k1E &%( maka & E &%E &% )

    Untuk hasil perkalian &%E &%E C&//( $-+( dapat dilihat pada ?ampiran ,)

    Sugrup Siklik Dalam Kurva 6liptik E 1 y2 = x3 + x + 3 atas Z3Q dengan

    !enerator E C%(+3)

    Dari proses pementukan kun7i diperoleh kun7i pulik J & ( & E JC%(+3( C&//(

    $-+ dan kun7i rahasia k&E &%) Kun7i pulik terseut dikirim kepada King II

    sedangkan kun7i rahasia tetap dirahasiakan oleh King I)

    51 P'+ses Pe*5en)u&-n Kuni +leh Kin, II1

    Misalkan salah satu kun7i pulik yang dipilih oleh King II adalah =$ E C%(+3

    dan kun7i rahasia yang dipilih adalah k2E &&( maka $ E && $ E && $ Untuk

    hasil perkalian &&E &&E C&,.( $--( dapat dilihat pada ?ampiran ,)

    Sugrup Siklik Dalam Kurva 6liptik E 1 y2 = x3 + x + 3 atas Z3Q dengan

    !enerator E C%(+3)

    Dari proses pementukan kun7i diperoleh kun7i pulik J $ ( $ E JC%(+3(

    C&,.( $-- dan kun7i rahasia k$E &&) Kun7i pulik terseut dikirim kepada King I

    sedangkan kun7i rahasia tetap dirahasiakan oleh King II)

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    111/133

    Setelah King I menerima kun7i pulik dari King II( maka King I dapat melakukan

    proses enkripsi pada pesan yang akan dikirim) Akan tetapi( seelum proses

    enkripsi( karakter pesan dikonversikan terleih dahulu( seperti ditunjukkan pada

    "ael /)+ erikut ini)

    T-5el 31!01 K+n/e'si K-'-&)e' 4+n)+h 31"

    i Karakter Plainte>t i&

    & < C$+( #$$ 6 C+,( $$3

    / @ C$#/( /%%

    , A C%( +3

    3 P C&%#( &%#

    . A C%( +3

    - Spasi C/%#( /$&

    # D C,$( ,#

    + U C//-( ,.

    &% I C$3/( &,#

    && " C&$+( $#/

    &$ Spasi C/%#( /$&

    &/ Y C%( $.-

    &, ! C/$.( $#

    i Karakter Plainte>t i&

    &3 Spasi C/%#( /$&

    &. M C/$+( &&$

    &- A C%( +3

    S C//+( /

    &+ U C//-( ,.

    $% K C&,.( $--$& Spasi C/%#( /$&

    $$ K C&,.( $--

    $/ A C%( +3

    $, N C$--( $./

    $3 " C&$+( $#/

    $. 9 C,#( &3+

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    112/133

    $- N C$--( $./

    $# ! C/$.( $#

    $+ M C/$+( &&$/% U C//-( ,.

    /& C&33( /%3

    %1 P'+ses En&'i(si Pes-n +leh Kin, I

    Dari "ael /)+ diperoleh plaintext erupa titik8titik pada kurva eliptik

    E 1 y2 = x3 + x + 3 atas Z3Q- Kemudian plaintext terseut dienkripsikan) Proses

    enkripsi yang dilakukan oleh King I dengan menggunakan kun7i pulik J

    $ ( $ E JC%(+3( C&,.( $-- dan ilangan a7ak s1E /( proses enkripsi terseut

    dapat dilihat pada "ael /)&% erikut ini)

    T-5el 31!!1 P'+ses En&'i(si +leh Kin, I

    i

    (laintext

    i& !1i =s1, $

    s1 $ !2iE i& s1

    $%)ipertext J!1i!2i

    & C$+( #$ C&-( &$# C3#( $ C$&%( $#- JC&-( &$#_C$&%( $#-

    $ C+,( $$3 C&-( &$# C3#( $ C/$$( #& JC&-( &$#_C/$$( #&

    / C$#/( /%% C&-( &$# C3#( $ C/( &/# JC&-( &$#_C/( &/#, C%( +3 C&-( &$# C3#( $ C/&( /$ JC&-( &$#_C/&( /$

    3 C&%#( &%# C&-( &$# C3#( $ C/%-( &/& JC&-( &$#_C/%-( &/&

    . C%( +3 C&-( &$# C3#( $ C/&( /$ JC&-( &$#_C/&( /$

    - C/%#( /$& C&-( &$# C3#( $ C+&( /- JC&-( &$#_C+&( /-

    # C,$( ,# C&-( &$# C3#( $ C#,( /, JC&-( &$#_C#,( /,

  • 8/10/2019 SISTEM KRIPTOGRAFI KURVA ELIPTIK ATAS Zp_PUGUH W P_063051410.doc

    113/133

    + C//-( ,. C&-( &$# C3#( $ C/%/( $$ JC&-( &$#_C/%/( $$

    &% C$3/( &,# C&-( &$# C3#( $ C&%-( . JC&-( &$#_C&%-( .

    && C&$+( $#/ C&-( &$# C3#( $ C&/#( /$% JC&-( &$#_C&/#( /$%&$ C/%#( /$& C&-( &$# C3#( $ C+&( /- JC&-( &$#_C+&( /-

    &/ C%( $.- C&-( &$# C3#( $ C/&-( $/$ JC&-( &$#_C/&-( $/$

    &, C/$.( $# C&-( &$# C3#( $ C$#.( &3& JC&-( &$#_C$#.( &3&

    &3 C/%#( /$& C&-( &$# C3#( $ C+&( /- JC&-( &$#_C+&( /-

    &. C/$+( &&$ C&-( &$# C3#( $ C&&$( +- JC&-( &$#_C&&$( +-

    &- C%( +3 C&-( &$# C3#( $ C/&( /$ JC&-( &$#_C/&( /$

    C//+( / C&-( &$# C3#( $ C&,-( +# JC&-( &$#_C&,-( +#

    &+ C//-( ,. C&-( &$# C3#( $ C/%/( $$ JC&-( &$#_C/%/( $$

    $% C&,.( $-- C&-( &$# C3#( $ C$%( $-- JC&-( &$#_C$%( $--

    $& C/%#( /$& C&-( &$# C