Elliptic Curve Cryptography (Ecc) Pada Proses Pertukaran Kunci Publik Diffie-Hellman. Metrilitna Br Sembiring 1

Metrilitna Br Sembiring, Elliptic Curve Cryptography…

Elliptic Curve Cryptography (Ecc) Pada Proses Pertukaran Kunci Publik Diffie-Hellman

Metrilitna Br Sembiring1

Abstrak Elliptic Curve Cryptography (ECC) pada Proses Pertukaran Kunci Publik Diffie-Hellman. Dalam tugas akhir ini dibahas mengenai algoritma kriptografi kurva elliptik untuk enkripsi dan dekripsi data. Metode yang digunakan adalah dengan menggunakan kunci publik Diffie-Hellman. Hasil yang telah dilakukan bahwa hasil pertukaran kunci antara dua user menggunakan pertukaran Diffie-Hellman memberikan titik ke tiga (kunci private bersama) yang sama antara ke dua user tersebut.

Kata kunci: Kriptografi, Kriptografi Kurva Eliptik, Diffie-Hellman

1

Metrilitna Br Sembiring, Mahasiswa S2 Matematika, FMIPA, Universitas Sumatera Utara, Email: [email protected]

ISSN 2086 – 1397

Volume VI Nomor 1. Januari – Juni 2015 | 25


Kelebihan algoritma asimetris ini adalah

Pendahuluan Kemajuan teknologi

dan

informasi

berpengaruh

pada

perkembangan

dewasa hampir

ini

telah

semua

aspek

proses pendistribusian kunci pada media yang tidak aman seperti internet, tidak memerlukan kerahasiaan.

Karena

kunci

yang

kehidupan manusia, tak terkecuali dalam hal

didistribusikan adalah kunci publik. Sehingga

berkomunikasi.

internet,

jika kunci ini sampai hilang atau diketahui

komunikasi jarak jauh dapat dilakukan dengan

oleh orang lain yang tidak berhak, maka pesan

cepat dan murah. Namun disisi lain, ternyata

sandi

internet tidak terlalu aman karena merupakan

Sedangkan kunci privat tetap disimpan (tidak

media

didistribusikan).

Dengan

komunikasi

adanya

umum

yang

dapat

yang

dikirim

akan

tetap

aman.

digunakan oleh siapapun sehingga sangat

Elliptic Curve Cryptography (ECC)

rawan terhadap penyadapan informasi oleh

mempunyai keuntungan jika dibandingkan

pihak-pihak yang tidak berhak mengetahui

dengan kriptografi asimetris lainnya yaitu

informasi tersebut. Oleh karena pengguna

dalam hal ukuran panjang kunci yang lebih

internet yang sangat luas seperti pada bisnis,

pendek tetapi memiliki tingkat keamanan yang

perdagangan, bank, industri, dan pemerintahan

sama. Sebagai perbandingan, 160 bit Elliptic

yang umumnya mengandung informasi yang

Curve

bersifat rahasia, keamanan informasi menjadi

keamanan (3.8.1010 MIPS/Million Instruction

faktor utama yang harus dipenuhi. Berbagai

per Second year) yang sama dengan 1024 bit

hal

mendapatkan

RSA mempunyai tingkat keamanan (3.1012

jaminan keamanan informasi menjadi suatu

MIPS year). Sehingga kecepatannya lebih

kode-kode yang tidak dimengerti. Apabila

tinggi, konsumsi daya yang lebih rendah,

disadap,

adanya penghematan bandwith. Keuntungan-

telah

dilakukan

maka

untuk

akan

kesulitan

untuk

memahami isi informasi yang sebenarnya.

Cryptography

aplikasi-aplikasi yang memiliki keterbatasan

dapat dimanfaatkan ialah sistem kriptografi

pada

kurva

ketersediaan

Kriptografi

kurva

tingkat

keuntungan tersebut sangat berguna untuk

Salah satu sistem pengamanan yang

eliptik.

mempunyai

eliptik

bandwith,

kapasitas

sumber

tenaga

pemrosesan, dan

ruang.

termasuk kedalam sistem kriptografi asimetris

Aplikasi-aplilkasi tersebut antara lain: kartu

yang

pada

chip, kartu kredit atau kartu debit, tiket

permasalahan matematis kurva eliptik. Pada

elektronik, telepon selular, pager dan kartu

sistem ini digunakan masalah logaritma diskrit

identitas.

mendasarkan

keamanannya

kurva eliptik dengan menggunakan grup kurva

Diffie-Hellman

pertama

kali

eliptik. Struktur kurva eliptik digunakan

memperkenalkan algoritma kunci publik pada

sebagai

untuk

tahun 1976 atas hasil kerja sama antara

melangsungkan proses enkripsi dan dekripsi.

Whitfield Diffie dan Martin Hellman. Metode

grup

ISSN 2086 – 1397

operasi

matematis



ini merupakan metode partikal pertama untuk

Hasil dan Pembahasan

menciptkan sebuah rahasia bersama antara dua

Pendekatan yang dilakukan untuk

belah pihak melalui sebuah jalur komunikasi

menghasilkan algoritma kriptografi kurva

yang tidak terjaga. Algoritma Diffie-Hellman

eliptik (Elliptic Curve Cryptography) adalah

ini memiliki keamanannya dari kesulitan

dengan menggunakan struktur matematika

menghitung algoritma diskrit dalam finite

yang

field,

dalam

pemrosesan titik dengan memiliki dua buah

menghitung bentuk eksponensial dalam finite

titik dalam sebuah kurva eliptik dengan

field

dibandingkan

yang

digunakan publik

sama. dalam

yang

kemudahan

Algoritma

unik

yang

memungkinkan

ini

dapat

menghasilkan sebuah titik lain yang ada pada

mendistribusikan

kunci

kurva tersebut. Kriptografi kurva eliptik

protokol

(Elliptic Curve Cryptography) menggunakan

dikenal

dengan

pertukaran kunci. Kriptografi

sangat

dua kunci yaitu kunci publik dan kunci privat. kurva

eliptik(Elliptic

Kunci publik pada kriptografi kurva eliptik

Curve Cryptography) menggunakan dua kunci

adalah sebuah titik pada kurva eliptik dan

yaitu kunci publik dan kunci privat. Kunci

kunci privatnya adalah sebuah angka random.

publik pada kriptografi adalah sebuah titik

Kunci publik diperoleh dengan melakukan

pada kurva eliptik dan kunci privatnya adalah

operasi perkalian terhadap kunci privat dengan

sebuah angka random. Kunci publik diperoleh

titik generator G pada kurva eliptik. Titik

dengan melakukan opersai perkalian terhadap

generator G digunakan untuk melakukan

kunci privat dengan titik generator G pada

pertukaran kunci Diffie-Hellman.

kurva eliptik. Titik generator G digunakan

Algoritma

untuk melakukan pertukaran kunci Diffie-

Hellman

Hellman. Sehingga menjadi dasar untuk

Pertukaran

Diffie-Hellman

Kunci

Diffie

merupakan

-

suatu

memilih pertukaran kunci Diffie-Hellman.

algoritma kunci publik yang pertama kali

Metode Penelitian

ditemukan pada tahun 1976, meskipun NSA

Langkah-langkah yang dilakukan peneliti dalam penelitian ini adalah sebagai berikut. 1. Menguraikan

teori-teori

dasar

kriptografi.

telah

menemukan

asimetrik

jauh-jauh

hari

algoritma sebelumnya.

Algoritma ini memperoleh keamanannya dari sulitnya menghitung logaritma diskrit pada

2. Menyajikan masalah Elliptic Curve Cryptography

mengaku

(ECC)

pada

proses

bilangan yang sangat besar. Algoritma DiffieHellman

hanya

dapat

digunakan

untuk

pertukaran kunci publik Diffie-Hellman.

pertukaran kunci (simetri) dan tidak dapat

3. Menganalisa proses pertukaran kunci

digunakan untuk enkripsi dan dekripsi maupun

publik Diffie-Hellman. 4. Mengambil kesimpulan. ISSN 2086 – 1397

untuk tanda tangan digital. (Dony Ariyus, 2006) Volume VI Nomor 1. Januari – Juni 2015 | 27


Diffie-Hellman

pertama

kali

Mulai

memperkenalkan algoritma kunci publik pada

Base Point, Bits(g,n,x,y)

tahun 1976 dan sebelumnya ditemukan oleh Malcolm

Williamson

pada

tahun

Kurva Elips

1974. Cante (User1)

Algoritma ini memiliki keamanannya dari kesulitan menghitung logaritma diskrit dalam

Private Key(a)

Private Key(a)

Public Key(X,Y)

Public Key(X,Y)

Gante (User2)

finite field, dibandingkan kemudahan dalam Generate Key

menghitung bentuk eksponensial dalam finite field

yang

digunakan publik

sama. dalam

yang

Algoritma

ini

dapat

mendistribusikan

kunci

dikenal

dengan

Kunci Rahasia Bersama Untuk Cante(k)

protokol

Gambar 1. Struktur Kunci DiffieHellman

ini

dipakai

untuk

menyandikan pertukaran pesan antar dua pihak

Parameter umum:

secara interaktif. Pada awalnya, masing-

1. Misalkan

masing pihak

Kunci Rahasia Bersama Untuk Gante(k)

Selesai

pertukaran kunci. Sistem

Waktu Proses 4 Kali

Waktu Proses

mempunyai

sebuah

kunci

rahasia yang tidak diketahui pihak lawan

dua

orang

user

yang

berkomunikasi: user1 dan user2. 2. Mula-mula

user1

dan

user2

bicara. Dengan berdasar pada masing-masing

menyepakati bilangan prima yang besar,

kunci rahasia ini, ke dua pihak dapat membuat

n dan g sedemikian sehingga g < n.

sebuah kunci sesi (session key/kunci rahasia

3. Bilangan n dan g tidak perlu rahasia.

untuk komunikasi dengan kriptografi simetri)

Bahkan,

yang

membicarakannya melalui saluran yang

akan

dipakai

untuk

pembicaraan

selanjutnya.

user1

dan

user2

dapat

tidak aman sekalipun.

Pembuatan kunci sesi ini dilakukan

Berikut ini algoritma pertukaran kunci

seperti halnya suatu tanya jawab matematis,

Difiie-Hellman yang diilustrasikan dua orang

hanya pihak yang secara aktif ikut dalam tanya

user (user1 dan user2):

jawab ini sajalah yang bisa mengetahui kunci

1.

User1 memilih secara acak sebuah

sesinya. Penyadap yang secara aktif mengikuti

bilangan integer x yang besar dan

tanya jawab ini tidak akan bisa mengetahui

mengirimkannya ke user2.

kunci sesi ini. (Andri Kristanto, 2003).

X = gx mod p 2.

User2 memilih secara acak sebuah bilangan integer y yang besar dan mengirimkannya ke user1. Y = gy mod p

3. ISSN 2086 – 1397

User1 menghitung nilai k1 = Yx mod p Volume VI Nomor 1. Januari – Juni 2015 | 28


4.

User2 menghitung nilai k2 = Xy mod p

Dari gambar 2 penulis dapat menjabarkan

Jika perhitungan dengan benar, maka k1 =

langkah-langkah sebagai berikut:

k2.

1. Menentukan bilangan prima (p) dengan

5.

xy

Baik k1 dan k2 sama dengan g mod

syarat p > 3 untuk Fp

p. 6.

Misalkan diambil sembarang bilangan

Penyadap

yang

menyadap

prima = 13 bilangan prima atau bukan.

pembicaraan antara user1 dan user2

Kemudian diambil nilai n = 2 karena PBB atau

tidak dapat menghitung k. Ia hanya

pembagi bersama terbesar (13, 2) = 1 np-1 ≡ 1 (mod p) = 213-1 = 8191 ≡ 1

memiliki informasi n, g, X dan Y, tetapi ia tidak mempunyai informasi nilai x dan y. 7.

(mod 13) Dengan demikian 13 adalah bilangan

Untuk mengetahui x dan y, ia perlu melakukan diskrit,

yang

perhitungan mana

logaritma

sangat

prima karena tidak habis dibagi, sehingga didapat p = 13.

sulit

dikerjakan.

2. Menentukan bentuk persamaan kurva

Proses Pertukaran Kunci Diffie-Hellman

eliptik Persamaan kurva eliptik y2 = x3 + ax +

pada Elliptic Curve Cryptography Tahapan-tahapan pertukaran

kunci

dalam

Diffie-Hellman

prosedur

b (mod p) dan nilai a, b dibuat secara acak

untuk

(random) untuk koefisiennya. Misalkan a = 4,

memperoleh kunci privat bersama:

b = 9 dan p = 13, persamaan kurva eliptik menjadi:

Bilangan bulat prima (p) Persamaan kurva elliptik

y2 = x3 + 4x + 9 (mod 13) Sehingga: 4a3 + 27b2 ≠ 0 (mod p) 4.43 + 27.92 (mod 13)

Pilih titik random

= 2443 (mod 13) = 12 ≠ 0 (mod 13).

Buat privat 1 dan privat 2

Cara mencari kurva dengan persamaan diatas Hitung publik 1 dan publik 2

adalah: Misalkan diambil sembarang titik:

Hitung kunci 1 dan kunci 2 Misalkan: x = 0 Gambar 2 Diagram dari proses pertukaran

y2 = x3 + 4x + 9

kunci Diffie-Hellman

y2 = 03 + 4.0 + 9

ISSN 2086 – 1397



Proses

untuk

menentukan

bentuk

eliptik

dengan

2

y = 9y = ±

persamaan

y1 = 3 dan y2 = -3

mengembangkan koefisien a, b secara acak

misalkan: x = 1

dengan a = acak (p) dan b = acak (p), bilangan

kurva

2

3

2

3

pada (Gambar 3) di mana a, b € Fp dan a, b ≠

y =1+4+9

0. Kemudian melakukan pengecekan dengan

y = x + 4x + 9

prima (p) di sini telah dihitung sebelumnya

y = 1 + 4.1 + 9 2 2

y = 14

memasukkan ke dua koefisien tersebut ke dalam persamaan diskriminan. Jika hasil 4a3 +

y=±

27b2 = 0 (mod p), maka akan dilakukan proses

y1 =

perulangan

dan y2 = -

mengembangkan

misalkan: x = 2

nilai

mulai a

dan

b

dari sampai

didapatkan hasil dari nilai diskriminannya

y2 = x3 + 4x + 9

tidak sama dengan nol.

y2 = 23 + 4.2 + 9

3. Menentukan titik utama pada kurva

y2 = 8 + 8 + 9

Menentukan titik-titik utama pada

y2 = 25

kurva, kemudian pilih satu titik p secara sembarang pada kurva E(Fp). Bilangan prima p

y=±

= 13. Selanjutnya dicari elemen-elemen grup

y1 = 5 dan y2 = -5 dengan

kembali

cara

yang

sama

untuk

menghitung nilai x dan y nya sehingga dalam bentuk kurva ditunjukkan dalam gambar

eliptik

E13

atas

Fp,

dengan

{0,1,2,3,4,5,6,7,8,9,10,11,12}.

Fp

=

Sebelum

menentukan elemen-elemen E13 (4,9), terlebih dahulu mencari quadratic residue 13 (QR13).

berikut ; Gambar kurva eliptik pada persamaan y2 = x3 + 4x + 9

Gambar 3. Kurva eliptik dengan persamaan y2=x3+4x+9 ISSN 2086 – 1397



Tabel 1 QR13 Fp 0 1 2 3 4 5 6 7 8 9 10 11 12

y2 (mod 13) 02 (mod 13) 12 (mod 13) 22 (mod 13) 32 (mod 13) 42 (mod 13) 52 (mod 13) 62 (mod 13) 72 (mod 13) 82 (mod 13) 92 (mod 13) 102 (mod 13) 112 (mod 13) 122 (mod 13)

QR13 0 1 4 9 3 12 10 10 12 3 9 4 1

Berdasarkan Tabel 1 himpunan QR13 =

penyelesaian dari persamaan y2 = x3 + 4x + 9

{0,1,3,4,9,10,12}.

(mod 13). Untuk x € F13 dan y2 € QR13.

Kemudian

menentukan

elemen grup eliptik E13 (4,9) yang merupakan Tabel 2. Untuk Mencari Elemen E13 (4,9) X € F13

y2 = x3 + 4x + 9 (mod 13)

y2 € QR13

(x,y) x € E13(4,9)

0 1 2 3 4 5 6 7 8 9 10 11 12

9 1 12 9 11 11 2 3 7 7 9 6 4

Ya Ya Ya Ya Bukan Bukan Bukan Ya Bukan Bukan Ya Bukan Ya

(0,1) dan (0,10) (1,1) dan (1,12) (2,5) dan (2,8) (3,3) dan (3,10) (7,4) dan (7,9) (10,3) dan (10,10) (12,2) dan (12,11)

Berdasarkan Tabel 2 untuk x = 0,

dan 102 (mod 13) = 9. Perhitungan untuk nilai

diperoleh y2= 0 + 0 + 0 + 4.0 + 9 (mod 13) =

x dan y yang lain, dilakukan dengan cara yang

9. Sehingga diperoleh nilai y = 3 dan y = 10.

sama. Sehingga didapatkan elemen-elemen

Karena berdasarkan Tabel 4.1, 32 (mod 13) = 9

grup eliptik modulo 13 atas F13, yaitu F13 (4,9)

ISSN 2086 – 1397



= {(0,3), (0,10), (1,1), (1,12), (2,5), (2,8),

Publik2 = privat2*p = 4*(0,10) = (0,10) +

(3,3), (3,10), (7,4), (7,9), (10,3), (10,10),

(0,10) + (0,10) = (12,11) + (0,10)

(12,2), (12,11), O}. Jumlah titik utama pada

Karena titiknya berbeda, maka P ≠ Q. λ=

kurva = 14 titik selain dari titik infinity (O). Misal titik yang dipilih adalah p = (0,10). 4. Menghitung privat1 dan privat2. Menentukan nilai acak kunci privat

λ=

= 1*(12-1) = 12 (mod 13)

x3 = λ2 – x1 – x2

user1(privat1) dan user2(privat2), dengan

x3 = 122 – 0 – 12 = 132 = 2 (mod 13)

privat1, privat2 elemen {2,3,...p-1} dalam Fp.

y3 = λ(x1 – x3) – y1

Misal privat1 = 3 dan privar2 = 4. Prosedur

y3 = 12(0 – 2) – 10 = -34 = 5 (mod 13)

untuk menentukan kunci privat ke dua user

Jadi, publik2 = (x3,y3) = (2,5).

dengan menentukan nilai dari privat1 =

6. Menghitung kunci1 dan kunci2 Ke dua user saling menukar kunci

random (p-1) + 3 dan privat2 = random (p-1) + 4 secara random. Jka privat1, privat2 < 1,

publik

mereka

masing-masing

untuk

maka akan terus terjadi perulangan mulai dari

menghasilkan kunci privat yang sama. Pada

awal sampai didapatkan privat1, privat2 ≥ 1.

tahapan ini dibuktikan bahwa kunci1 = kunci2. User1 menghasilkan,

5. Menghitung publik1 dan publik2

Key1 = privat1*publik2

Pembangkitan kunci publik oleh ke

= 3*(2.5) = (10,10)

dua user dan menghitung kunci publik masingmasing.

User2 menghasilkan,

User1 menghasilkan publik1 = privat1*p.

Key2 = privat2*publik1 = 4*(12,11) = (10,10)

Publik1 = privat1*p = 3 * (0,10) + (0,10) + (0,10) = ...

Sehingga nilai kunci1 = kunci2 = (10,10).

P = (0,10), karena titiknya sama, maka P = Q.

Penutup Adapun kesimpulan yang dapat diperoleh

λ=

adalah:

λ=

= 4*(20-1) = 8 (mod 13)

1. Keunggulan dari kriptigrafi kurva eliptik adalah proses transformasi

x3 = λ – x1 – x2

plaintext menjadi titik-titik dalam

x3 = 8 – 0 – 0 = 64 = 12 (mod 13)

kurva

y3 = λ(x1 – x3) – y1

enkripsi. Proses enkripsinya dilakukan

2

2

eliptik sebelum dilkakukan

y3 = 8(0 – 12) – 10 = -106 = -2 = 11 (mod 13)

dengan

jadi publik1 = (x3,y3) = (12,11)

penjumlahan

User2 menghasilkan kunci publik (publik2) =

Proses ini tentunya akan memberikan

privat2*p.

tingkat keamanan yang lebih baik.

ISSN 2086 – 1397

menggunakan pada

kurva

aturan eliptik.



2. Hasil yang telah dilakukan bahwa hasil pertukaran kunci antara dua user menggunakan

pertukaran

(kunci private bersama) yang sama antara ke dua user tersebut.

Diffie-

Hellman memberikan titik ke tiga Daftar Pustaka

Ariyus, Dony, 2006, Kriptografi Keamanan Data dan Komunikasi. Yogyakarta: Penerbit Graha Ilmu. Ariyus, Dony, 2008, Pengantar Ilmu Kriptografi Teori, Analisis dan Implementasi. Yogyakarta: Penerbit Andi. Juhana, Nana, 2005, Implementasi Elliptic Curves Cryptosystem (ECC) Pada Proses Pertukaran Kunci Diffie-Hellman dan Skema Enkripsi ElGamal, Institut Teknologi Bandung, Bandung. Kristanto, Andri, 2003, Keamanan Data pada Jaringan Komputer. Yogyakarta: Gava Media. Triwiinarko, Andi, 2004, Elliptic Curve Signature Algorithm (ECDSA). Departemen Teknik Informatika, Institut Teknologi Bandung, Bandung.

ISSN 2086 – 1397


Elliptic Curve Cryptography (Ecc) Pada Proses Pertukaran Kunci Publik Diffie-Hellman. Metrilitna Br Sembiring 1

Recommend Documents