BAB II TINJAUAN PUSTAKA

5

BAB II TINJAUAN PUSTAKA

Bab II akan membahas teori-teori yang berhubungan dengan kriptografi, algoritma RSA dan Elliptic Curve Digital Signature Algorithm (ECDSA).

2.1.

Kriptografi

Kata kriptografi berasal dari bahasa Yunani yaitu kryptos yang berarti tersembunyi dan graphein yang berarti menulis. (Mollin, 2007). Kriptografi adalah ilmu mengenai teknik enkripsi dimana data diacak menggunakan suatu kunci enkripsi menjadi sesuatu yang sulit dibaca oleh seseorang yang tidak memiliki kunci dekripsi (Kromodimoeljo, 2010). Sistem kriptografi (cryptosystem) adalah istilah umum yang mengacu pada kumpulan operasi dasar yang digunakan pada kriptografi untuk memperoleh keamanan informasi. (Menezes et al, 1996). 2.1.1. Terminologi Beberapa istilah dasar yang terdapat dalam kriptografi : 1. Pengirim dan Penerima (Sender and Receiver) Pengirim dalam kriptografi adalah orang yang akan mengamankan pesan yang akan dikirimnya.Sedangkan penerima adalah pihak yang akan membaca pesan yang telah diterimanya (Schneier, 1996).

2. Pesan dan Enkripsi (Message and Encryption) Pesan yang belum diamankan disebut plaintext (P) sedangkan pesan yang sudah diamankan disebut ciphertext (C). Proses untuk mengamankan pesan adalah enkripsi (encryption). Sedangkan proses untuk mengembalikan pesan yang telah dienkripsi disebut dekripsi (decryption) (Schneier, 1996).

Universitas Sumatera Utara

6

3. Kunci (Key) Kunci (K) dalam kriptografi adalah parameter yang digunakan pada algoritma untuk menyembunyikan dan membaca sebuah pesan. Terdapat dua jenis kunci yaitu kunci privat (Kpriv) dan kunci publik (Kpub). Kunci privat adalah kunci yang digunakan untuk mendekripsi sebuah pesan dan hanya boleh diketahui oleh pihak tertentu saja sedangkan kunci publik adalah kunci yang digunakan untuk mengenkripsi sebuah pesan dan boleh diketahui oleh semua pihak (Schneier, 1996). Gambaran umum dari sebuah sistem kriptografi dapat dilihat pada gambar 2.1. K

K Pengirim

P

Enkripsi

P

C

Dekripsi

Penerima

Gambar 2.1. Skema sebuah sistem kriptografi (Schneier, 1996)

4. Tanda Tangan Digital (Digital Signature) Tanda tangan digital adalah data digital yang dapat menyatakan kepemilikan dari sebuah pesan (Batten, 2013). Skema tanda tangan digital terdiri dari proses pembangkitan tanda tangan digital dan proses verifikasi tanda tangan digital. Proses pembangkitan memerlukan plaintext (P) dan kunci publik (Kpub) pengirim (Alice) dengan menggunakan algoritma pembentuk tanda tangan sehingga menghasilkan tanda tangan digital dari plaintext (Psig), sedangkan pada proses verifikasi tanda tangan digital memerlukan plaintext (P), tanda tangan digital dari plaintext (Psig) serta kunci privat (Kpriv) dari penerima (Bob) untuk menentukan apakah plaintext berasal dari pengirim (Alice) (Mollin, 2007). Beberapa algoritma tanda tangan digital adalah Digital Signature Algorithm, ECDSA, ElGamal, FiatShamir, RSA, Schnorr dan lain-lain. Secara umum skema tanda tangan digital dapat dilihat pada gambar 2.2. Kpub

P

Algoritma Pembentukan Tanda tangan

Kpriv P Psig P

sig

Algoritma Verifikasi Tanda tangan

Benar Salah

Gambar 2.2. Skema Tanda Tangan Digital.


7

Contoh tanda tangan digital untuk pesan ”abc” dengan menggunakan algoritma tandatangan digital ECDSA berdasarkan standar FIPS.186-2 untuk kurva elips berukuran 256 bit (DSS, 2010)

dengan kunci privat dc51d386 6a15bacd

e33d96f9 92fca99d a7e6ef09 34e70975 59c27f16 14c88a7f adalah : cb28e099 9b9c7715 fd0a80d8 e47a7707 9716cbbf 917dd72e 97566ea1 c066957c 86fa3bb4 e26cad5b f90b7f81 899256ce 7594bb1e a0c89212 748bff3b 3d5b0315.

5.

Fungsi Hash satu arah (One Way Hash Functions) Fungsi hash satu-arah adalah fungsi hash dimana pesan yang sudah diubah menjadi hash value, dari hash value yang diperoleh kita tidak dapat mengubahnya kembali menjadi pesan semula. Masukkan pada fungsi hash satuarah adalah pesan dan hash value pada proses sebelumnya (Schneier, 1996). Hasil dari sebuah fungsi hash disebut sebagai nilai hash (hash value) atau pesanringkas (message digest) dari fungsi H untuk masukan M. Fungsi hash memiliki banyak istilah antara lain : 1. Fungsi kompresi/kontraksi (compression function). 2. Cetak jari (fingerprint). 3. Cryptography checksum. 4. Message Integrity Check (MIC). 5. Manipulation Detection Code (MDC). Penggunaan fungsi hash pada kriptografi adalah memverifikasi pesan yang dikirim merupakan pesan yang asli atau tidak mengalami proses modifikasi yang dilakukan oleh pihak yang tidak berhak. -

...................................................................................................(1)

Hash value dari sebuah pesan akan berbeda dengan hash value dari pesan jika memiliki string yang berbeda. Yang termasuk dalam algoritma fungsi hash satu arah adalah MD5, MD6, SHA-1, SHA-224, SHA-256, SHA-384 dan lain-lain.

6. Algoritma Simetris Algoritma simetris adalah algoritma yang dimana kunci privat dapat dihitung berdasarkan kunci publik dan sebaliknya. Algoritma ini juga disebut algoritma kunci rahasia, algoritma kunci tunggal, atau algoritma satu kunci. Untuk


8

melakukan komunikasi pengirim dan penerima harus menyetujui kunci yang akan digunakan. Yang termasuk algoritma kunci simetris adalah A5, AES (Rijndael), Blowfish, CAST, DES, FEAL, IDEA, Kasumi, LOKI, Magenta, dan lain-lain.

7.

Algoritma Asimetris Algoritma asimetris adalah algoritma yang menggunakan kunci publik untuk enkripsi berbeda dengan kunci untuk dekripsi. Algoritma disebut juga sebagai algoritma kunci publik karena kunci enkripsi yang digunakan dapat diketahui oleh publik. Beberapa contoh algoritma ini antara lain Diffie-Hellman, ElGamal, Knapsack, LUC, McEliece, Pohlig-Hellman, RSA, Rabin dan lain-lain.

2.1.2. Tujuan Kriptografi Penggunaan kriptografi ditujukan untuk mengamankan data yang meliputi aspek – aspek yaitu (Paar et al, 2010) : a.

Kerahasiaan (Confidentiality) Informasi hanya bisa diakses oleh orang yang berhak.

b.

Keutuhan Data (Integrity) Pesan tidak mengalami perubahan pada saat pengiriman hingga pesan diterima oleh penerima.

c.

Pembuktian (Authentication) Identitas dari pembuat pesan dapat dipastikan.

d.

Tidak dapat dibantah (Nonrepudiation) Setiap entitas yang berkomunikasi tidak dapat menolak atau menyangkal pesan yang dikirim atau diterima.

2.2. Grup Sebuah Grup adalah himpunan yang terdiri dari elemen dan sejumlah operasi yang menoperasikan dua elemen untuk memperoleh elemen ketiga. Beberapa ciri yang terdapat dalam grup antara lain (Judson & Austin, 2009): 1. Bersifat assosatif. (a b) c = a (b c)


9

2. Memiliki elemen identitas (e). e a=a e=a 3. Memiliki elemen inversi (a-1). a a-1 = a-1 a = e Jika sebuah grup memiliki sifat komutatif a b = b a disebut abelian, sebaliknya disebut non-abelian.

2.3. Teori Bilangan Bulat Salah satu teori sangat penting dan sering digunakan pada bidang kriptografi dan merupakan teori yang menjadi dasar bagi kriptografi kunci publik adalah teori bilangan bulat ( ) (Munir, 2006). Berikut teori bilangan bulat yang digunakan pada penelitian ini.

2.3.1. Kekongruenan Sebuah bilangan bulat a disebut kongruen terhadap bilangan b dalam modulus N jika N dapat habis membagi

. Kekongruenan a dan b dapat ditulis

(Batten, 2013). Contoh : 5 kongruen dengan 14 dalam modulus 9 karena 9 habis membagi -9.

2.3.2. Faktor Persekutuan Terbesar (Greatest Common Divisior) Faktor persekutuan terbesar pada bilangan bulat a dan bilangan bulat b adalah bilangan bulat terbesar yang dapat membagi habis a dan b (Mollin, 2007). Contoh : Faktor dari 24 adalah 1, 2, 3, 4, 6, 8, 12, 24 dan Faktor dari 18 adalah 1, 2, 3, 6, 9, 18, sehingga faktor persekutuan terbesar dari 24 dan 18 adalah 6 atau gcd(

)

2.3.3. Relatif Prima Bilangan bulat a dan b dikatakan relatif prima jika faktor persekutuan terbesar antara a dan b adalah 1 atau dapat ditulis sebagai berikut

(

)

(Schneier, 1996).


10

Contoh : Faktor dari 24 adalah 1,2,3,4,6,8,12,24 dan Faktor dari 25 adalah 1,5 ,25. Faktor Persekutuan Terbesar dari 24 dan 25 adalah 1 sehingga 24 relatif prima terhadap 25 atau gcd(24, 25) = 1.

2.3.4. Fungsi Phi Euler Fungsi Phi Euler adalah banyak bilangan bulat yang lebih besar dari satu dan lebih kecil dari n yang relatif prima terhadap n dengan

. Simbol dari fungsi Phi Euler

dari sebuah bilangan n adalah ( ). Untuk mencari nilai fungsi Phi Euler terdapat beberapa cara aturan (Menezes et al, 1996) : 1. Jika p adalah bilangan prima. – .............................................................................................................. (2)

( ) (

2. Jika (

)

) ( )

3. Jika n =

( ) ................................................................................................... (3) adalah faktorisasi prima dari n, maka

( )

................................................................... (4)

Contoh : Faktorisasi prima dari 10 adalah 2, 5 sehingga ( )

2.3.5. Algoritma Extended Euclidean Extended Euclidean adalah algoritma untuk mencari faktor persekutuan terbesar dari dua bilangan bulat positif serta nilai pengali setiap bilangan. Langkah-langkah untuk algoritma adalah sebagai berikut (Kromodimoeljo, 2010): 1. 2. 3.

. . .

4.

.

5. 6. Jika 7.

. kembali ke langkah 2. , berhenti.


11

(

), u dan v dengan

.

Contoh : (

), a = 10 , b = 4

Inisialisasi A = 10, B = 4, u = 1, v = 0, s = 0, t = 1 Perhitungan gcd(10, 4) secara ringkas dapat dilihat pada tabel 2.1 Tabel 2.1. Algoritma Extended Euclidean. Iterasi

q

R

A

B

U

V

u

v

s

T

1

2

2

4

2

1

0

0

1

1

-2

2

2

0

2

0

0

1

1

-2

-2

5

(

Berdasarkan perhitungan pada tabel 2.1

) adalah 2

2.3.6. Inversi Modulo Suatu bilangan bulat a mempunyai inversi modulo n jika dan hanya jika Inversi modulo dari a mod n adalah

.

(Menezes et al, 1996). Untuk menentukan

inversi modulo dapat menggunakan algoritma Extended Euclidean (Kromodimoeljo, 2010). Bentuk inversi modulo dapat ditulis dalam persamaan linear yaitu , dengan u sebagai nilai inversi modulo. Contoh : Inversi modulo dari

(

) dengan menggunakan algoritma Extended

Euclidean adalah : Inisialisasi : a = 20, b = 17, A = 20, B = 17, u = 1, v = 0, s = 0, t = 1 Untuk menentukan inversi modulo dari 20 (mod 17) secara ringkas dapat dilihat pada tabel 2.2. Tabel 2.2. Inversi modulo dengan menggunakan algoritma Extended Euclidean. Iterasi

q

R

A

B

U

V

u

v

s

t

1

1

3

17

3

1

0

0

1

1

-1

2

5

2

3

2

0

1

1

-1

-5

6

3

1

1

2

1

1

-1

-5

6

6

-7

4

2

0

1

0

-5

6

6

-7

7

20


12

Berdasarkan perhitungan pada tabel 2.2, 20 memiliki inversi modulo terhadap 17 karena

dan inversi modulo dari 20 mod 17 adalah 6.

2.3.7. Eksponensial Modulo Operasi eksponensial pada modulo merupakan salah operasi yang paling sering digunakan pada kriptografi. Bentuk umum dari eksponensial modulo adalah dengan a merupakan basis, x merupakan ekponen dan n adalah modulus. Penggunaan operasi eksponensial akan memerlukan waktu yang lama jika nilai eksponen yang digunakan sangat besar, sehingga ada beberapa cara untuk mempercepat proses perhitungan ekponensial dan salah satu metode yang dapat digunakan adalah metode Binary Square and Multiply (Schneier, 1996). Metode Binary Square and Multiply antara lain : 1. Mengubah eksponen menjadi bit. 2. Insialisasi s = 1, t = basis. 3. Ambil satu bit dari kanan, jika bernilai 1 maka dihitung s = s t mod n. 4. Dihitung t = t t mod n. 5. Lakukan langkah ke 2 pada semua bit. 6. Hasil dari metode ini adalah s. Contoh : Eksponen = 5, basis = 14 dan modulus = 31 5=

, Inisialisasi s = 1, t = 14, Secara ringkas perhitungan dapat dilihat

pada tabel 2.3. Tabel 2.3. Perhitungan modulus eksponensial dengan menggunakan metode Binary Square and Multiply. i

Digit

s

t

1

1

14

10

2

0

14

7

3

1

5

18

Berdasarkan perhitungan pada tabel 2.3.

.


13

2.3.8. Pengujian Bilangan Prima Miller-Rabin Algoritma Miller-Rabin adalah algoritma pengujian bilangan prima probabilistik untuk menentukan sebuah bilangan prima atau komposit (Smart, 2004). Bilangan yang akan diuji adalah n. Maka ubah

– dalam bentuk

dengan t bilangan bulat lebih

besar daripada 1 dan u bilangan bulat ganjil. Selanjutnya dilakukan pengujian berdasarkan pseudocode (Cormen et al, 2009). Miller-Rabin (n, s) for j = 1 to s a = Random(1, n-1) if Witness(a, n) return composite return prime Witness (a, n) = Modular-Exponentiation(a, u, n) for i = 1 to t

if

and

and

return true if return true return false

Contoh : n = 81 ,t=4u=5 Pengujian menggunakan a = 2. Secara ringkas dapat dilihat pada tabel 2.4. Tabel 2.4. Perhitungan Algoritma Miller-Rabin untuk membuktikan keprimaan 81 dengan angka penguji 2. i 1

52

32

tidak

tidak

tidak

2

31

52

tidak

tidak

tidak

3

70

31

tidak

tidak

tidak


14

Berdasarkan perhitungan tabel 2.4 serta perhitungan pada i = t = 4 yaitu xt = 702 mod 81 = 40 dan xt ≠ maka 81 merupakan bilangan komposit Pengujian menggunakan a = 3. Secara ringkas dapat dilihat pada tabel 2.5.

Tabel 2.5. Perhitungan Algoritma Miller-Rabin untuk membuktikan keprimaan 81 dengan angka penguji 3. i 1

0

0

tidak

tidak

tidak

2

0

0

tidak

tidak

tidak

3

0

0

tidak

tidak

tidak

Berdasarkan perhitungan pada tabel 2.5 serta perhitungan pada i = t = 4 yaitu xt = 02 mod 81 = 0 dan xt ≠ maka 81 merupakan bilangan komposit. n = 89 , t = 3, u = 11 Pengujian menggunakan a = 2. Secara ringkas dapat dilihat pada tabel 2.6. Tabel 2.6. Perhitungan Algoritma Miller-Rabin untuk membuktikan keprimaan 89 dengan angka penguji 2. i 1

1

1

ya

tidak

tidak

2

1

1

ya

tidak

tidak

Berdasarkan perhitungan pada tabel 2.6 serta perhitungan pada i = t = 3 yaitu xt = 12 mod 81 = 1 dan xt = 1 maka 89 merupakan bilangan prima. Pengujian menggunakan a = 3. Secara ringkas dapat dilihat pada tabel 2.7. Tabel 2.7. Perhitungan Algoritma Miller-Rabin untuk membuktikan keprimaan 89 dengan angka penguji 3. i 1

34

37

tidak

tidak

tidak

2

88

34

tidak

tidak

tidak

Berdasarkan perhitungan pada tabel 2.7 serta perhitungan pada i = t = 3 yaitu xt = 882 mod 89 = 1 dan xt = 1 maka 89 merupakan bilangan prima


15

Fungsi Random() merupakan fungsi pembangkit bilangan acak dengan menggunakan algoritma SHA1 (Secure Hash Algorithm 1).

2.4. Algoritma SHA-1 Algoritma SHA-1 merupakan salah satu jenis algoritma dengan fungsi hash satu – arah. SHA-1 dikembangkan oleh NSA pada tahun 1995 dan distandarisasi oleh NIST. SHA-1 merupakan algoritma hash searah dengan panjang hash-value 160-bit. Maksimal pesan yang dapat diproses adalah

bit. Proses pada algoritma ini antara

lain (Mollin, 2007): 1. Pesan diubah menjadi bitstream. 2. Hitung g = Panjang bitstream mod 512 jika. g < 448 bit tambahkan sebuah bit 1 dan

bit 0 pada data.

g >= 448 bit tambahkan sebuah bit 1 dan 3.

bit 0 pada data.

Ubah panjang pesan dalam bentuk 64bit kemudian tambahkan pada akhir data yang akan di hash.

4.

Data yang akan dihash dipecah-pecah menjadi bagian – bagian dengan panjang sebesar 512 bit.

5.

Inisialiasasi variabel, nilai variabel

6.

Setiap blok berukuran 512 bit dipecah menjadi 16 bagian masing-masing

.

berukuran 32-bit (bitword). Dari 16 bitword tersebut akan dihasilkan bitword ke 17 sampai bitword ke 80 dengan menggunakan algoritma sesuai dengan gambar 2.4 : for i 16 to 79 data 7. Initialisasi varaibel . 8. Untuk setiap bitword dilakukan perubahan variabel A, B, C, D, E sesuai dengan gambar 2.3  Jika bitword ke-0 sampai bitword ke-19 : (

)

(

( )

)

.

Hapus bit paling kiri sampai t berukuran 32 bit. E = D, D = C, C =

(B), B = A, A = t.


16

 Jika bitword ke-20 sampai bitword ke-39 : (

)

.


(B), B = A, A = t.

 Jika bitword ke-40 sampai bitword ke-59 : (A)

)

(

(

)

(

)

.


(B), B = A, A = t.

 Jika bitword ke-60 sampai bitword ke-79 : (

)

.


(B), B = A, A = t.

9. Ubah variabel

dengan rumus

. Hapus bit paling kiri sampai

berukuran 32 bit.


berukuran 32 bit.


berukuran 32 bit.


berukuran 32 bit.


berukuran 32 bit.

10. Lakukan pada blok 512-bit lainnya. 11. Hasil dari proses diatas yaitu

kemudian di gabung. .

Gambar 2.3. Proses SHA-1 untuk setiap bitword


17

Gambar 2.4. Proses SHA-1 untuk setiap 512 bit blok 2.5. Algoritma SHA-2 Algoritma SHA-2 merupakan salah satu jenis algoritma dengan fungsi hash satu – arah. Algoritma yang termasuk dalam kelas SHA-2 adalah SHA-224 (224 bit), SHA256 (256 bit), SHA-384 (384 bit), SHA-512 (512 bit) dan lain-lain. Pada tugas akhir ini panjang hash value yang digunakan. Fungsi logika yang digunakan pada SHA-256 antara lain : ( A D ) ( A D )

(

( ) A D ) ...................................................... (5) ( A D )

( A D ) ................................... (6)

( )

( )

( )

( )....................................................... (7)

( )

( )

( )

( )....................................................... (8)

( )

( )

( )

( ) Dengan

( ) dan

( )

S S

( )......................................................... (9) ( ) ................................................... (10)

merupakan operasi bitwise untuk rotate right dan shift right

sebanyak x.


18

Setiap operasi penjumlahan pada SHA-256 dilakukan dalam modulus Maksimal panjang pesan yang dapat diproses adalah

.

bit. Proses pada algoritma ini

antara lain (SHS, 2015): 1. Pesan diubah menjadi bitstream. 2. Hitung tambahkan sebuah bit 1 dan beberapa bit 0 pada data hingga ukuran pesan 448 (mod 512). 3. Ubah panjang pesan dalam bentuk 64 bit kemudian disisipkan pada akhir data yang akan di hash. 4. Data yang akan dihash dipecah – pecah menjadi berberapa bagian kecil dengan panjang sebesar 512 bit. 5. Inisialiasasi variabel, nilai variabel

.

6. Setiap blok berukuran 512 bit dipecah menjadi 16 bagian masing-masing berukuran 32-bit (bitword). Dari 16 bitword tersebut akan dihasilkan bitword ke 16 sampai bitword ke 63 dengan menggunakan algoritma sbb : for t 16 to 63 (

)

(

7. Initialisasi variabel

) . .

8. Untuk setiap bitword dilakukan pengubahan variabel A, B, C, D, E, F, G, H. for i 0 to 63 data( ). Variabel memiliki nilai sesuai dengan tabel 2.8.

H = G, G = F, F = E,

, D = C, C = B, B = A,

9. Ubah variabel

dengan rumus :

10. Lakukan pada blok 512-bit lainnya. 11. Hasil dari proses diatas yaitu

kemudian di gabung

sehingga menghasilkan hash value (h). S

( )

S ( )

S

( )

S ( )

S

( )

S

( )

S

( )

.


19

Tabel 2.8. Nilai konstanta dari variabel

428a2f98

71374491

b5c0fbcf

e9b5dba5

3956c25b

59f111f1

923f82a4

ab1c5ed5

d807aa98

12835b01

243185be

550c7dc3

72be5d74

80deb1fe

9bdc06a7

c19bf174

e49b69c1

efbe4786

0fc19dc6

240ca1cc

2de92c6f

4a7484aa

5cb0a9dc

76f988da

983e5152

a831c66d

b00327c8

bf597fc7

c6e00bf3

d5a79147

06ca6351

14292967

27b70a85

2e1b2138

4d2c6dfc

53380d13

650a7354

766a0abb

81c2c92e

92722c85

a2bfe8a1

a81a664b

c24b8b70

c76c51a3

d192e819

d6990624

f40e3585

106aa070

19a4c116

1e376c08

2748774c

34b0bcb5

391c0cb3

4ed8aa4a

5b9cca4f

682e6ff3

748f82ee

78a5636f

84c87814

8cc70208

90befffa

a4506ceb

bef9a3f7

c67178f2

Gambar 2.5. Proses SHA-2 pada setiap iterasi, dengan untuk penjumlahan dengan modulus

merupakan simbol .

2.6. Kurva Elips Kurva elips adalah kurva yang memiliki persamaan Weierstrass yaitu : .................................................................. (11) Himpunan titik pada kurva elips bisa merupakan anggota dari sebuah daerah berhingga, bilangan real, bilangan rasional, dan bilangan kompleks serta titik identitas serta titik indentitas yaitu O yang disebut sebagai titik tak berhingga.


20

2.6.1. Kriptografi Kurva Elips Kriptografi kurva elips adalah kriptografi logaritma diskrit dengan menggunakan grup titik kurva elips yang berada pada daerah berhingga. Dibandingkan dengan kriptografi non kurva elips, kriptografi kurva elips memiliki tingkat keamanan yang sama dengan ukuran kunci yang lebih kecil (Hankerson et al, 2004). Penggunaan kurva ellips dalam kriptografi dapat dikombinasikan dengan algoritma kriptografi non kurva elips. Beberapa algoritma tersebut antara lain : 1.

Skema enkripsi (ElGamal ECC).

2.

Tanda tangan digital (ECDSA – Elliptic Curves Digital Signature).

3. Protokol pertukaran kunci (Diffie Hellman ECC). Operasi yang digunakan dalam kriptografi kurva elips adalah operasi grup untuk kurva elips

penjumlahan, dan disebut operasi perkalian pada grup

tabel 2.9 memberikan hubungan antara

dengan ( ) (Hankerson et al, 2004).

Tabel 2.9. Hubungan antara Grup Grup Elemen

Discrete Logarithm Problem

dengan kurva Grup Kurva

Integer

p-1}

Aturan operasi Perkalian modulo p

Notasi

Titik (x,y) pada kurva E + O Penjumlahan 2 titik

Elemen : g,h

Elemen : P,Q

Perkalian :

Perkalian : P + Q

Invers :

. Pada

-

Invers : -P

Pembagian :

Pembagian : P – Q

Pemangkatan :

Perkalian : aP

Diberikan

Diberikan ( ) dan , cari a

dan , cari a

Persamaan kurva elips yang paling sering digunakan dalam kriptografi kurva elips adalah ......................................................................................... (12) , p > 3 dan

(

).

Untuk menentukan titik yang terdapat dalam kurva elips dapat menggunakan algoritma Euler Criterion (Galbraith, 2012).


21

.....................................................................................................................................................

(13)

Jika hasilnya 1 maka titik terdapat dalam kurva elips sedangkan -1 maka titik tidak terdapat dalam kurva elips. Contoh : Himpunan

dengan

pada kurva elips . Nilai

, dengan

, sehingga

merupakan

persamaan kurva elips. Untuk menentukan titik yang merupakan anggota dapat dilihat pada tabel 2.10. Tabel 2.10. Perhitungan Euler Criterion pada setiap kemungkinan titik x 0 1 2 3 4 5 6 7

Euler Criterion 0 1 -1 1 0 1 1 1

x 8 9 10 11 12 13 14 15

Euler Criterion -1 1 -1 1 1 1 -1 -1

x 16 17 18 19 20 21 22

Euler Criterion -1 1 1 1 -1 -1 -1

Pasangan koordinat titik x dan y dapat dilihat pada tabel 2.11 dan secara geometris dapat dilihat pada gambar 2.6.

Tabel 2.11. Pasangan koordinat pada kurva elips x 0 0 1 1 3 3 4 5 5

Y 1 22 7 16 10 13 0 4 19

x 6 6 7 7 9 9 11 11 12

y 4 19 11 12 7 16 3 20 4

x 12 13 13 17 17 18 18 19 19

y 19 7 16 3 20 3 20 5 18


22

24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

Gambar 2.6. Sebaran titik-titik pada kurva elips

18

19

20

untuk

2.6.2. Aturan Penjumlahan Dua Titik pada Kurva Elips Aturan pada penjumlahan dua titik pada kurva elips

akan menghasilkan titik ke

tiga yang juga berada dalam kurva elips. Secara geometris aturan penjumlahan pada kurva elips (Hankerson et al, 2004): 1.

untuk setiap

2.

Jika

3.

Jika

(

)

. dan ( ).

maka Maka

. (

)

diperoleh dengan menarik garis L yang melewati titik P dan Q atau garis singgung antara titik P dan Q. Kemiringan garis L adalah (

) .................................................................................. (14) (

Jika

)............................................................................. (15)

maka (

Jika

di mana :

≠

) ............................................................................................... (16)

maka (

) ............................................................................................... (17)

Secara geometris, penjumlahan pada kurva elips dapat dilihat pada gambar 2.7 dan gambar 2.8.


23

Gambar 2.7. Gambaran secara

Gambar 2.8. Gambaran secara

geometri penjumlahan dua titik

geometri penjumlahan dua titik

berbeda

sama

Contoh : (

1. Dari persamaan (

dan

) penjumlahan antara titik

(

)

) adalah:

(

)

(inversi modulo 17 terhadap 23 adalah 19)

(

) (mod

(

Sehingga

)

)

Secara geometris dapat dilihat pada gambar 2.9. 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

(17,20)

(3,10)

(9,7)

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

Gambar 2.9. Gambaran geometris untuk (3,10) + (9,7) = (17,20)


24

2. Dari persamaan sebelumnya penjumlahan P=(3,10) terhadap dirinya sendiri yaitu

adalah :

(

( ))

(inversi modulo 20 terhadap 23 adalah 15)

(

) (

)

Jadi 2 P = (7,12) Hasil ini diperlihatkan secara geometris dalam gambar 2.10. 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

(7,12)

(3,10)

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

Gambar 2.10. Gambaran geometris untuk (3,10) + (3,10) = (7,12)

Aturan perkalian pada titik kurva elips dapat dijabarkan dengan menggunakan aturan penjumlahan kurva elips. Contoh : , dengan

.

2.7. Sistem Kriptografi RSA (RSA Cryptosystem) Sistem kriptografi RSA merupakan dibangun dengan menggunakan fungsi eksponensial.

Seperti

kriptosistem

pada

umumnya,

RSA

memiliki

proses

pembangkitan kunci, enkripsi, dan dekripsi.


25

2.7.1. Pembangkitan Kunci RSA Langkah – langkah untuk membangkitkan kunci pada RSA adalah (Mollin, 2007): 1.

Pengguna memilih p dan q yang merupakan bilangan prima acak dan

.

2.

Hitung

3.

Hitung

4.

Pilih bilangan acak ganjil e dalam rentang

5.

Hitung

6.

Kunci publik pengguna adalah e dan n dan kunci privat pengguna adalah d.

. n disebut juga sebagai modulus RSA. ( – ) ( – ). ( ) dan

(

( ))

.

( ).

Algoritma pembangkit kunci pada RSA yang sudah dimodfikasi dirubah menjadi (Malhotra, 2014): 1.

Pengguna memilih p, q, dan r yang merupakan bilangan prima yang besar dan .

2.

Menghitung

3.

Menghitung

4.

Memilih

5.

Hitung

. n disebut juga sebagai modulus RSA. ( – )

–

(

).

bilangan acak ganjil dalam rentang

( )

(

( ))

.

.

Kunci publik adalah e dan n dan kunci privat adalah d.

2.7.2.

Enkripsi RSA

Proses enkripsi pada RSA yang dimodifikasi memiliki metode enkripsi yang sama dengan metode enkripsi RSA biasa. Enkripsi dilakukan dengan menggunakan kunci publik yang telah dibangkitkan sebelumnya. Tahap-tahap dalam algoritma enkripsi RSA antara lain: 1. Pengirim pesan mengubah pesan (P) menjadi bitstream. 2. Pengirim pesan mendapatkan kunci publik dari penerima pesan (e dan n). 3.

Menghitung ciphertext (C) dari pesan dengan persamaan berikut : ........................................................................................................... (18)

4.

Ciphertext dikirim.


26

2.7.3.

Dekripsi RSA

Untuk menghasilkan kembali plain text dari ciphertext yang sudah dienkripsi, digunakan fungsi eksponensial modular n dengan menggunakan kunci privat. Algoritma dekripsi RSA yang telah dimodofikasi sama dengan algoritma dekripsi RSA biasa yaitu : 1. Penerima pesan mengubah pesan yang diterima (C) menjadi bitstream. 2.

Menghitung pesan asli (P) dengan menggunakan persamaan berikut : .......................................................................................................... (19)

2.8. Algoritma Tanda Tangan Digital Kurva Elips Elliptic Curve Digital Signature Algorithm (ECDSA) Elliptic Curve Digital Signature Algorithm (ECDSA) merupakan tanda tangan digital dengan menggunakan kriptografi kunci publik dan fungsi hash searah. Beberapa proses yang terdapat pada algoritma ECDSA adalah pembangkitan kunci, pembentukan tanda tangan dan proses verifikasi tanda tangan.

2.8.1. Pembangkitan Kunci ECDSA Langkah – langkah dalam pembangkitan kunci pada ECDSA antara lain : 1.

Menentukan domain kurva elips yang digunakan yaitu D = (q, FR, S, a, b, P, n, h), dengan q adalah ukuran bidang berhingga, jika bidang berhingga FR (field representation) adalah indikator basis yang digunakan, S adalah konstanta yang digunakan untuk memverifikasi bahwa a dan b dihasilkan melalui proses yang acak, a dan b adalah dua parameter yang digunakan kurva elips, P adalah titik pada kurva yang dijadikan sebagai titik acuan dalam operasi kurva elips yang merupakan bilangan prima ganjil. n adalah orde dari kurva elips dan h adalah kofaktor yang merupakan hasil pembagian jumlah titik yang terdapat dalam kurva elips (

) dengan n.

2. Pengguna memilih secara acak sebuah bilangan bulat d yang berada diantara 1 sampai dengan n

1, kemudian dilakukan perkalian skalar dengan titik P sesuai

dengan aturan penjumlahan kurva elips sehingga menghasilkan kunci publik yaitu Q dan kunci privat yaitu bilangan acak yang digunakan yaitu d.


27

2.8.2.

Pembentukan Tanda Tangan Digital ECDSA

Proses pembentukan tanda tangan digital antara lain (Hankerson et al, 2004): 1.

Dipilihlah sebuah bilangan bulat acak k yang berada diantara 1 sampai dengan .

2. Menghitung 3.

. mod . Jika r = 0 kembali

Mengambil koordinat x kemudian hitung kelangkah pertama.

4.

Menghitung e = H(m), H merupakan fungsi hash.

5. Menghitung s =

-

. Jika s = 0 kembali kelangkah 1.

6. Tanda tangan digital untuk pesan adalah r dan s.

2.8.3. Proses Verifikasi Tanda Tangan ECDSA Untuk memverifikasi tanda tangan dari pesan (m) yang dikirim yaitu (r, s) (Hankerson et al, 2004). 1.

Dicek apakah r dan s berada dalam interval 1 sampai n 1.

2.

Menghitung e = H(m).

3. Menghitung 4.

-

-

Menghitung

dan

. mod , dengan P adalah titik awal

kurva dan Q merupakan kunci publik pengirim pesan. 5.

Pesan valid jika hanya jika

.

Pada tugas akhir ini, standar ECDSA yang digunakan adalah FIPS.186-2 untuk kurva elips berukuran 256 bit (DSS, 2010). Berikut parameter yang digunakan : p=1579208921035624876269744694940757353008614341529031419553363130887 097853951 n= 157920892103562487626974469494075735299969552241357603424222590 6108512044369 S = c49d360886e704936a6678e1139d26b7819f7e90 c = 7efba1662985be9403cb055c75d4f7e0ce8d84a9c5114abcaf3177680104fa0d b = 5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b = 6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296 = 4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5


28

Pretty Good Privacy (PGP)

2.9.

PGP adalah program freeware yang berfungsi untuk mengamankan e-mail. PGP dibuat oleh Philip Zimmerman (1991). PGP menggunakan konsep hybrid cryptosystem yang mengabungkan kriptografi kunci publik (RSA, ElGamal) dan kriptografi konvensional (IDEA, DES, Blowfish). PGP menggunakan kriptografi konvensional untuk mengenkripsi data, kriptografi kunci publik untuk manajemen kunci dan tangan tangan digital dan fungsi hash satu arah (MD5). Kunci publik acak PGP menggunakan algoritma probabilistik untuk pengecekan bilangan prima dengan menggunakan bilangan acak yang diperoleh dari penggunaan keyboard dan mouse (Schneier, 1996). Skema pengamanan (enkripsi) data dalam PGP adalah : 1.

PGP membangkitkan kunci acak (session key).

2. Data

dienkripsi

dengan

menggunakan

algoritma

kunci

konvensional

menghasilkan ciphertext. 3.

Kemudian session key dienkripsi dengan menggunakan kunci publik penerima pesan dengan menggunakan algoritma kunci publik.

4.

Session key yang sudah dienkripsi serta ciphertext dikirim. Skema pembacaan (dekripsi) data dalam PGP adalah :

1.

Penerima mendekripsi session key yang terenkripsi dari pengirim dengan menggunakan kunci privat penerima pada algoritma kunci publik.

2.

Kemudian penerima mendekripsi ciphertext dengan menggunakan session key sehingga data dapat dibaca menjadi pesan.

2.10.

Penelitian yang Relevan

Beberapa penelitian yang berkaitan dengan penelitian akan dilakukan oleh penulis antara lain : 1.

Penelitian yang dilakukan oleh Malhotra (2014) dengan judul A New Encryption Scheme Based on Enhanced RSA and ElGamal menyimpulkan algoritma RSA yang dimodifikasi memiliki waktu enkripsi dan throughput yang lebih baik dibandingkan dengan algoritma RSA biasa.

2.

Penelitian yang dilakukan oleh Tripathi dan Agrawal (2014) dengan judul Critical Analysis of RSA Public Key Cryptosystem menyebutkan penggunaan beberapa


29

bilangan prima dalam RSA dapat meningkatkan kesulitan dalam memfaktoran nilai n sehingga keamanan RSA menjadi lebih baik. 3.

Penelitian yang dilakukan oleh Putra (2013) yang berjudul ”Implementasi Kriptografi Kurva Eliptik Dengan Algoritma Elgamal Dan Metode Pembangkitan Bilangan Prima Rabin-Miller Untuk Pengamanan File

eks” men impulkan

bahwa penggunaan parameter yang kecil pada kurva elips dapat mempercepat proses pembangkitan kunci, proses enkripsi dan proses dekripsi.


BAB II TINJAUAN PUSTAKA

Recommend Documents