BAB 2
LANDASAN TEORI
2.1
Kriptografi
Berikut ini akan dijelaskan sejarah, pengertian, tujuan, dan jenis kriptografi.
2.1.1
Pengertian Kriptografi
Kriptografi (cryptography) berasal dari bahasa yunani yaitu “cryptos” yang artinya “secret” (rahasia) dan “graphein” yang artinya “writing” (tulisan). Jadi kriptografi berarti “secret writing” (tulisan rahasia)[2]. Kriptografi adalah suatu ilmu yang mempelajari bagaimana cara menjaga agar data atau pesan tetap aman saat dikirimkan, dari pengirim ke penerima tanpa mengalami gangguan dari pihak ketiga. Kriptografi adalah ilmu dan seni untuk menjaga keamanan pesan (Cryptography is the art and science of keeping message secure)[5].
Dalam kamus bahasa Inggris Oxford diberikan pengertian kriptografi sebagai berikut:
“ Sebuah teknik rahasia dalam penulisan, dengan karakter khusus, dengan mengguanakan huruf dan karakter di luar bentuk aslinya, atau dengan metode-metode lain yang hanya dapat dipahami oleh pihak-pihak yang memproses kunci, juga semua hal yang ditulis dengan cara seperti ini.”
Jadi, secara umun dapat diartikan sebagai seni menulis atau memecahkan cipher[12].
Menezes, van Oorschot dan Vanstone (1996) menyatakan bahwa kriptografi adalah suatu studi teknik matematika yang berhubungan dengan aspek keamanan
informasi seperi kerahasiaan, integritas data, otentikasi entitas dan otentikasi keaslian data. Kriptografi tidak hanya berarti penyediaan keamanan informasi, melainkan sebuah himpunan teknik-teknik.
Dalam menjaga kerahasiaan data dengan kriptografi, data sederhana yang dikirim (plainteks) diubah ke dalam bentuk data sandi (cipherteks), kemudian data sandi tersebut hanya dapat dikembalikan ke bentuk data sebenarnya hanya dengan menggunakan kunci (key) tertentu yang dimiliki oleh pihak yang sah saja. Tentunya hal ini menyebabkan pihak lain yang tidak memiliki kunci tersebut tidak akan dapat membaca data yang sebenarnya sehingga dengan kata lain data akan tetap terjaga.
2.1.2
Terminologi Kriptografi
Di dalam kriptografi, sering ditemukan istilah-istilah (terminologi). Berikut ini adalah beberapa istilah yang sering digunakan dalam kriptografi yaitu: a. Pesan, plainteks, dan cipherteks Pesan adalah data ataupun suatu informasi yang dapat dibaca dan dimengerti maknanya, nama lain dari pesan adalah plainteks. Cipherteks adalah suatu bentuk pesan yang sudah disandikan agar pesan tersebut tidak dapat dibaca oleh pihak lainnya. b. Pengirim dan penerima Suatu aktifitas komunikasi data melibatkan pertukaran antara dua entitas, pengirim dan penerima. Pengirim adalah entitas yang mengirimkan pesan kepada entitas lainnya Penerima adalah entitas yang menerima pesan.[7]. c. Enkripsi dan dekripsi Suatu proses untuk menyandikan plainteks menjadi cipherteks adalah enkripsi (encryption), sedangkan proses pengembalian dari cipherteks menjadi plainteks disebut dekripsi (decryption). Enkripsi dan dekripsi merupakan suatu pesan yang memetakan elemen-elemen antara kedua himpunan tersebut. Misalnya P adalah plainteks dan C adalah cipherteks, maka fungsi enkripsi E untuk memetakan P ke C ditulis E(P) = C dan fungsi dekripsi D memetakan C ke P ditulis D(C) = P[7].
d. Cipher dan kunci Algoritma kriptografi disebut juga cipher, yaitu aturan atau fungsi matematika yang digunakan untuk enkripsi dan dekripsi. Beberapa cipher memerlukan algoritma yang berbeda untuk proses enkripsi dan dekripsi. Untuk menjaga kerahasiaan pengiriman pesan, di dalam kriptografi dibutuhkan suatu kunci (key). Kunci adalah parameter yang digunakan untuk mentransformasi proses enkripsi dan dekripsi pesan. Dengan menggunakan kunci K maka proses enkripsi dan dekripsi dapat ditulis sebagai berikut: E K (P) = C dan D K (C) = P dan keduanya memenuhi D K (E K (P)) = P.
2.1.3
Jenis Algoritma Kriptografi
Berdasarkan jenis kunci yang
digunakannya, algoritma kriptografi dikelompokan
menjadi dua bagian, yaitu: algoritma simetris (algoritma konvensional) dan algoritma asimetris (algoritma kunci publik)[1][7].
2.1.3.1 Algoritma Simetris
Pada sistem algoritma simetris, kunci untuk proses enkripsi sama dengan kunci untuk proses dekripsi. Keamanan sistem algoritma simetris terletak pada kerahasiaan kunci. Istilah lain untuk algoritma simetris adalah kriptografi kunci privat (private key cryptography) atau kriptografi konvensional (conventional cryptography).
Kriptografi simetri merupakan satu-satunya jenis kriptografi yang dikenal dalam catatan sejarah hingga tahun 1976. termasuk ke dalam sistem kriptografi simetri.
Semua algoritma kriptografi klasik
Plainteks, P
Enkripsi Ek (P) = C
Chiperteks, C
Kunci Privat, K
Dekripsi Dk (C) = P
Plainteks, P
Kunci Privat, K
Gambar 2.1 Skema Kriptografi Simetri
Kriptografi simetri adalah kunci enkripsi sama dengan kunci dekripsi, yaitu K. Sebelum melakukan pengiriman pesan, pengirim dan penerima harus memilih suatu suatu kunci tertentu yang sama untuk dipakai bersama, dan kunci ini haruslah rahasia bagi pihak yang tidak berkepentingan sehingga algoritma ini disebut juga algoritma kunci rahasia (secret-key algorithm)[7].
Kelebihan kriptografi simetri: 1. Algoritma kriptografi simetri dirancang sehingga proses
enkripsi/dekripsi
membutuhkan waktu yang singkat; 2. Karena kecepatannya yang cukup tinggi, maka dapat digunakan pada sistem real-time; 3. Ukuran kunci simetri relatif pendek; 4. Algorima kriptografi simetri dapat disusun untuk menghasilkan cipher yang lebih kuat; 5. Otentikasi pengirim pesan langsung diketahui dari cipherteks yang diterima, karena kunci hanya diketahui oleh pengirim dan penerima pesan saja.
Kelemahan kriptografi simetri: 1. Kunci simetri harus dikirim melalui saluran yang aman. Kedua entitas yang berkomunikasi harus menjaga kerahasisan kunci ini; 2. Kunci harus sering diubah, mungkin pada setiap sesi komunikasi.
Contoh untuk algoritma simetris adalah algoritma TwoFish, Rijndael, dan Camellia.
2.1.3.2
Algoritma Asimetris
Pada sistem algoritma asimetri, kunci untuk proses enkripsi tidak sama dengan kunci untuk proses dekripsi. Istilah
lain untuk algoritma kriptografi asimetri adalah
kriptografi kunci publik (public key cryptography), sebab kunci untuk enkripsi tidak rahasia dan dapat diketahui oleh siapapun, sementara kunci untuk dekripsi hanya diketahui oleh penerima pesan.
Pada kriptografi jenis ini, setiap orang yang berkomunikasi mempunyai sepasang kunci, yaitu kunci privat dan kunci publik. Pengirim mengenkripsi pesan dengan menggunakan kunci publik si penerima pesan. Hanya penerima pesan yang dapat mendekripsi pesan karena hanya ia yang mengetahui kunci privatnya sendiri.
Plainteks, P
Enkripsi Epk (P) =C
Chiperteks, C
Dekripsi Dsk (C) = P
Kunci Publik, PK
Plainteks, P
Kunci Privat, SK
Gambar 2.2 Skema Kriptografi Asimetri
Kriptografi asimetri adalah kunci enkripsi tidak sama dengan kunci dekripsi. Kriptografi kunci-publik dapat dianalogikan seperti kotak surat yang terkunci dan memiliki lubang untuk memasukkan surat. Setiap orang dapat memasukkan surat ke dalam kotak surat tersebut, tetapi hanya pemilik kotak yang dapat membuka kotak dan membaca surat di dalamnya karena ia yang memiliki kunci. Keuntungan sistem ini ada dua. Pertama,
tidak ada kebutuhan untuk mendistribusikan kunci privat
sebagaimana pada sistem kriptografi simetri. Kunci publik dapat dikirim ke penerima melalui saluran yang sama dengan saluran yang digunakan untuk mengirim pesan. Saluran untuk mengirim pesan umumnya tidak aman[7].
Kedua, jumlah kunci dapat ditekan. Untuk berkomunikasi secara rahasia dengan banyak orang tidak perlu kunci rahasia sebanyak jumlah orang tersebut, cukup membuat dua buah
kunci, yaitu kunci publik bagi para koresponden untuk
mengenkripsi pesan, dan kunci
privat untuk mendekripsi pesan. Berbeda
dengankriptografi kunci-simetris dimana jumlah kunci yang dibuat adalah sebanyak jumlah pihak yang diajak berkorespondensi.
Meski berusia relatif muda (sejak 1976), kriptografi kunci-publik mempunyai kontribusi yang luar biasa dibandingkan dengan sistem kriptografi simetri. Kontribusi yang paling penting adalah tanda-tangan digital pada pesan untuk memberikan aspek keamanan
otentikasi, integritas data, dan nir-penyangkalan. Tanda-tangan digital
adalah nilai kriptografis yang bergantung pada isi pesan dan kunci yang digunakan. Pengirim pesan mengenkripsi pesan (yang sudah diringkas) dengan kunci privatnya, hasil enkripsi inilah
yang dinamakan tanda-tangan digital. Tanda-tangan digital
dilekatkan (embed) pada pesan
asli. Penerima pesan memverifikasi tanda-tangan
digital dengan menggunakan kunci publik.
Kelebihan kriptografi kunci-publik (asimetri) yaitu: 1. Hanya kunci privat yang perlu dijaga kerahasiaannya oleh setiap entitas yang berkomuniaksi (tetapi, otentikasi kunci publik tetap harus terjamin). Tidak ada kebutuhan mengirim kunci privat sebagaimana pada sistem simetri; 2. Pasangan kunci publik/kunci privat tidak perlu diubah, bahkan dalam periode waktu yang panjang; 3. Dapat digunakan untuk mengamankan pengiriman kunci simetri; 4. Beberapa algoritma kunci-publik dapat digunakan untuk memberi tanda tangan digital pada pesan.
Kelemahan kriptografi kunci-publik (asimetri): 1. Enkripsi dan dekripsi data umumnya lebih lambat daripada sistem simetri, karena enkripsi dan dekripsi
menggunakan bilangan yang besar dan
melibatkan operasi perpangkatan yang besar; 2. Ukuran cipherteks lebih besar daripada plainteks (bisa dua sampai empat kali ukuran plainteks); 3. Ukuran kunci relatif lebih besar daripada ukuran kunci simetri; 4. Karena kunci publik diketahui secara luas dan dapat digunakan setiap orang, maka cipherteks tidak memberikan informasi mengenai otentikasi pengirim;
5. Tidak ada algoritma kunci-publik yang terbukti aman (sama seperti block cipher). Kebanyakan algoritma
mendasarkan keamanannya pada sulitnya
memecahkan persoalan-persoalan aritmetik (pemfaktoran, logaritmik, dan sebagainya) yang menjadi dasar pembangkitan kunci.
Contoh algoritma asimetris adalahAlgoritma RivestShamirAdleman (RSA), Digital Signature Algorithm (DSA), dan Algoritma ElGamal.
2.1.4
Tujuan Kriptografi
Tujuan dari kriptografi yang juga merupakan aspek keamanan informasi adalah sebagai berikut:[1]
1. Kerahasiaan (Confidentiality)
adalah
layanan
yang
digunakan
untuk
menjagaisi informasi dari semua pihak kecuali pihak yang memiliki otoritas terhadap informasi. Ada beberapa pendekatan untuk menjaga kerahasiaan, dari pengamanan secara fisik hingga penggunaan algoritma matematika yang membuat data tidak dapat dipahami. Istilah lain yang senada dengan confidentiality adalah secrecy dan privacy.
2. Keutuhan data (Data integrity) adalah layanan penjagaan pengubahan data dari pihak yang tidak berwenang. Untuk menjaga integritas data, sistem harus memiliki kemampuan untuk mendeteksi manipulasi pesan oleh pihak-pihak yang tidak berhak, antara lain penyisipan, penghapusan, dan pensubsitusian data lain kedalam pesan yang sebenarnya. Di dalam kriptografi, layanan ini direalisasikan dengan menggunakan tanda-tangan digital. Pesan yang telah ditandatangani menyiratkan bahwa pesan yang dikirim adalah asli.
3. Otentikasi (Authentication) adalah layanan yang berhubungan dengan identifikasi, baik mengidentifikasi kebenaran pihak-pihak yang berkomunikasi (user authentication atau entity authentication) maupun mengidentifikasi kebenaran sumber pesan (data origin authentication). Dua pihak yang saling
berkomunikasi harus dapat mengotentikasi satu sama lain sehingga ia dapat memastikan sumber pesan. Pesan yang dikirim melalui saluran komunikasi juga harus diotentikasi asalnya. Otentikasi sumber pesan secara implisit juga memberikan kepastian integritas data, sebab jika pesan telah dimodifikasi berarti sumber pesan sudah tidak benar. Oleh karena itu, layanan integritas data selalu dikombinasikan dengan layanan otentikasi sumber pesan. Di dalam kriptografi, layanan ini direalisasikan dengan menggunakan tanda-tangan digital (digital signature). Tanda-tangan digital menyatakan sumber pesan.
4. Anti-penyangkalan (Non-repudiation) adalah layanan untuk mencegah entitas yang berkomunikasi melakukan penyangkalan, yaitu pengirim pesan menyangkal melakukan pengiriman atau penerima pesan menyangkal telah menerima pesan.
2.2
Algoritma ElGamal
Algoritma ElGamal merupakan algoritma enkripsi kunci asimetris yang berdasarkan pada pertukaran kunci Diffe-Hellman. Algoritma ini diusulkan Taher Elgamal pada tahun 1984. Keamanan algoritma ini didasarkan pada kesulitan memecahkan masalah logaritma diskrit dalam grup.Sampai akhir tahun 1970, hanya ada sistem kriptografi simetri. Karena sistem kriptografi simetri menggunakan kunci yang sama untuk enkripsi dan dekripsi, maka hal ini mengimplikasikan dua pihak yang berkomunikasi saling mempercayai. Konsep sistem kriptografi kunci-publik ditemukan oleh Diffie dan Hellman yang mempresentasikan konsep ini pada Tahun 1976. Ide dasar dari sistem kriptografi kunci-publik adalah bahwa kunci kriptografi dibuat sepasang, satu kunci untuk enkripsi dan satu kunci untuk dekripsi. Kunci untuk enkripsi bersifat publik (tidak rahasia), sehingga dinamakan kunci publik (public-key). Sedangkan kunci dekripsi bersifat rahasia sehingga dinamakan kunci rahasia (private key atau secret key)[1].
Logaritma ini disebut logaritma diskrit karena nilainya berhingga dan bergantung pada bilangan prima yang digunakan. Karena bilangan prima yang
digunakan adalah bilangan prima yang besar, maka sangat sulit bahkan tidak mungkin menurunkan kunci privat dari kunci publik yang diketahui walaupun serangan dilakukan dengan menggunakan sumberdaya komputer yang sangat besar.
Algoritma ElGamal mempunyai kunci publik berupa tiga pasang bilangan dankunci rahasia berupa satu bilangan. Algoritma ini mempunyai kerugian pada cipherteksnya yang mempunyai panjang dua kali lipat dari plainteksnya. Akan tetapi, algoritma ini mempunyai kelebihan pada enkripsi. Untuk plainteks yang sama, algoritma ini memberikan cipherteks yang berbeda (dengan kepastian yang dekat) setiap kali plainteks dienkripsi. Algoritma ElGamal terdiri dari tiga proses, yaitu proses pembentukan kunci, proses enkripsi dan proses dekripsi. Algoritma ini merupakan cipher blok, yaitu melakukan proses enkripsi pada blok-blok plainteks dan menghasilkan blok-blok cipherteks yang kemudian dilakukan proses dekripsi dan hasilnya digabungkan[10].
2.2.1
Proses Pembentukan Kunci
Proses pertama pada algoritma ElGamal adalah pembentukan kunci yang terdiri dari kunci rahasia dan kunci publik. Pada proses ini dibutuhkan sebuah bilangan prima aman p yang digunakan untuk membentuk grup Z p *, elemen primitif α yang merupakan elemen pembangun grup dan sembarang a Є {0,1,..., p-2}. Kunci publik algoritma ElGamal berupa pasangan 3 bilangan, yaitu (p, α , β ), dengan: β = αa( mod p )…………………………………………….. ……...(2.1) dimana a merupakan kunci rahasia dan harus prima[9].
2.2.1.1 Bilangan Prima Aman
Untuk memperoleh keamanan pada algoritma ElGamal, maka bilangan prima yang digunakan haruslah bilangan prima yang aman. Untuk melakukan pengujian apakah
suatu bilangan merupakan bilangan prima yang aman atau tidak dapat dilakukan dengan langkah-langkah berikut: 1. Input bilangan prima p ≥ 5 2. Hitung 𝑞 =
𝑝−1 2
3. Jika q adalah bilangan prima, maka output (”prima aman”) 4. Jika q komposit, maka output (”bukan prima aman”)
Sementara untuk mengetahui apakah suatu bilangan merupakan bilangan prima atau bukan dapat dilakukan pengujian. Ada pun langkah-langkah tes untuk menentukan suatu bilangan merupakan bilangan prima atau tidak adalah sebagai berikut : 1. Input p ≥ 3 2. b = 1 3. Repeat 3.1 b = b+1 3.2 c = p mod b 3.3 Until c = 0 4. Jika p = b maka output (”prima”) 5. Jika tidak, maka output (”bukan bilangan prima”)
2.2.1.2
Elemen Primitif
Selain bilangan prima, dalam kriptografi ElGamal juga digunakan elemen primitif yang merupakan elemen pembangun dari grup Z p . Untuk mencari elemen ini digunakan p=2q+1, dimana q merupakan bilangan prima. Jika elemen α memenuhi α2 mod p ≠ 1 dan αq mod p ≠ 1, maka α merupakan elemen primitif. Untuk mengetahui suatu bilangan merupakan elemen primitif atau tidak dapat dilakukan langkah-langkah sebagai berikut : 1. Input bilangan prima aman p ≥ 5.
2. Hitung 𝑞 =
𝑝−1 2
3. Hitung α mod p dan αq mod p. 2
4. Jika α2mod p= 1, maka α bukan elemen primitif. 5. Jika αqmod p= 1, maka α bukan elemen primitif. 6. Jika tidak terpenuhi dua persyaratan di atas maka q merupakan elemen primitif.
2.2.1.3 Proses Pembentukan Kunci
Langkah-langkah dalam pembentukan kunci sebagai berikut: 1. Input bilangan prima aman p > 255 2. Input sebuah bilangan α yang merupakan elemen primitif dimana α Є Z p * 3. Input sebuah bilangan prima a Є {0,1,..., p-2} 4. Hitung β = αa (mod p) 5. Publikasikan nilai p, α , dan β , serta rahasiakan nilai a. Pihak yang membuat kunci publik dan kunci rahasia adalah penerima, sedangkan pihak pengirim hanya mengetahui kunci publik yang diberikan oleh penerima, dan kunci publik tersebut digunakan untuk mengenkripsi pesan. Jadi, kentungan menggunakan algoritma kriptografi kunci publik adalah tidak ada permasalahan pada distribusi kunci apabila jumlah pengirim sangat banyak serta tidak ada kepastian keamanan jalur yang digunakan.
Misalkan Andi dan Budi saling berkomunikasi. Pada suatu saat, Andi akan mengirimkan pesan rahasia kepada Budi. Oleh karena itu, Budi harus membuat kunci publik dan kunci rahasia. Misalkan Budi ingin membangkitkan pasangan kuncinya. Budi memilih bilangan prima p=2099, α=975 sebagai elemen pembangun dan kunci rahasia a = 225. Andi menghitung: β = αamod p = 975225mod 2099 = 469
Jadi, kunci publik Budi adalah (p = 2099, α = 975 dan β = 469) dan kunci rahasianya 225. Budi mengirimkan pasangan kunci publik (2099, 975, 469) pada Andi dan menyimpan kunci rahasianya.
2.2.2 Proses Enkripsi
Karena pada algoritma ElGamal menggunakan bilangan bulat dalam proses perhitungannya, maka pesan harus dikonversi ke dalam suatu bilangan bulat. Untuk mengubah pesan menjadi bilangan bulat, digunakan kode ASCII (American Standard for Information Interchange). Kode ASCII merupakan representasi numerik dari karakter-karakter yang digunakan pada komputer, serta mempunyai nilai minimal 0 dan maksimal 255. Oleh karena itu, berdasarkan sistem kriptografi ElGamal di atas maka harus digunakan bilangan prima yang lebih besar dari 255 sehingga kode ASCII berkorespondensi 1-1 dengan karakter pesan. Pada proses enkripsi pesan dienkripsi menggunakan kunci publik ( p, α, β ) dan sembarang bilangan acak rahasia k Є {0,1,..., p-2}. Misalkan m adalah pesan yang akan dikirim. Selanjutnya, m diubah ke dalam blok-blok karakter dan setiap karakter dikonversikan ke dalam kode ASCII, sehingga diperoleh plainteks m 1 , m 2 , m 3 , ..., m n dengan m i Є {1, 2,..., p-1} dan i =1, 2,..., n. Proses enkripsi pada algoritma ElGamal dilakukan dengan menghitung γ i = 𝛼 𝑘𝑖 ( mod p )……………………………………………............ (2.2)
dan δ i =𝛽 𝑘𝑖 .m
(mod
p)………………………………………………….
dengan k Є {0,1,..., p-2} acak, diperoleh cipherteks ( γ , δ ).
(2.3)
Bilangan acak k ditentukan oleh pihak pengirim dan harus dirahasiakan, jadi hanya pengirim saja yang mengetahuinya, tetapi nilai k
hanya digunakan saat
melakukan enkripsi saja dan tidak perlu disimpan.
Langkah-langkah proses enkripsi: 1. Pesan dipotong-potong ke dalam bentuk blok-blok pesan dengan setiap blok adalah satu karakter pesan.
2. Konversikan masing-masing karakter ke dalam kode ASCII, maka diperoleh plainteks sebanyak n bilangan, yaitu m 1 , m 2 , ..., m n . 3. Untuk i dari 1 sampai n kerjakan: 3.1 Pilih bilangan acak k i dimana 1 < k ≤ p-2 3.2 Hitung γ i = 𝛼 𝑘𝑖 (modp)
3.3 Hitung δ i = 𝛽 𝑘𝑖 .m i (mod p)
4. Diperoleh cipherteks ( γ i , δ i ), dimana i = 1,2,...,n. Andi memperoleh kunci publik ( p, α, β ) = (2099, 975, 469) . Pada suatu hari, Andi akan mengirimkan pesan rahasia ”ILMU KOMPUTER” kepada Budi. Oleh karena sifat pesan yang rahasia, maka pesan tersebut harus dienkripsi, dan Andi akan mengenkripsi menggunakan kunci publik (2099, 975, 469) yang telah diberikan Budi. Selanjutnya, Andi melakukan proses berikut. Pertama, pesan dipotong-potong menjadi blok-blok karakter dan setiap karakter dikonversi ke dalam kode ASCII. Perhatikan tabel di bawah ini:
Tabel 2.1 Konversi Karakter Pesan Ke Kode ASCII i
Karakter
Plainteks m i
ASCII
1
I
m1
73
2
L
m2
76
3
M
m3
77
i
Karakter
Plainteks m i
ASCII
4
U
m4
85
5
<spasi>
m5
32
6
K
m6
75
7
O
m7
79
8
M
m8
77
9
P
m9
80
10
U
m 10
85
11
T
m 11
84
12
E
m 12
69
13
R
m 13
82
Berdasarkan Tabel 2.1 sebelumnya, diperoleh banyaknya karakter pada pesan tersebut adalah n = 13. Proses selanjutnya adalah menentukan bilangan acak rahasia dimana k i € {0,1,...,2097}. Kemudian dihitung γ i = 975𝑘𝑖 .(mod 2099) dan δ i =
469𝑘𝑖 .m i (mod 2099).
Tabel 2.2 Proses Enkripsi 469 𝑘𝑖 . . m i ( mod 2099 )
i
mi
ki
γ i = 975 𝑘𝑖 . ( mod 2099 )
1
73
1414
61
121
2
76
1527
228
349
3
77
1843
1480
1836
4
85
2175
2040
1185
5
32
1553
395
980
6
75
2210
908
1582
7
79
1404
534
1676
8
77
2183
1005
209
9
80
1091
1686
521
10
85
1606
1566
1524
11
84
1664
2004
736
12
69
990
474
1734
13
82
1127
852
83
Berdasarkan Tabel 2.2, diperoleh cipherteks ( γ i , δ i ), i =1, 2,...,13 sebagai berikut : (61, 121)
(228, 349)
(1480, 1836)
(2040, 1185)
(395, 980)
(908, 1582)
(534, 1676)
(1005,209)
(1686, 521)
(1566, 1524)
(2004, 736)
(474, 1734)
(852, 83).
Selanjutnya, Andi mengirimkan cipherteks ini kepada Budi.
Salah satu kelebihan algoritma ElGamal adalah bahwa suatu plainteks yang sama akan dienkripsi menjadi cipherteks yang berbeda-beda. Hal ini dikarenakan pemilihan bilangan k yang acak. Akan tetapi, walaupun cipherteks yang diperoleh berbeda-beda, tetapi pada proses dekripsi akan diperoleh plainteks yang sama, seperti dijelaskan berikut ini.
2.2.3
Proses Dekripsi
Setelah menerima cipherteks ( γ, δ ), proses selanjutnya adalah mendekripsikan cipherteks menggunakan kunci publik p dan kunci rahasia a. Dapat ditunjukkan bahwa plainteks m dapat diperoleh dari cipherteks menggunakan kunci rahasia a. Diberikan (p, α, β) sebagai kunci publik dan a sebagai kunci rahasia pada algoritma ElGamal. Jika diberikan cipherteks ( γ , δ ), maka: m = ( γa)-1.(mod p)…………………………………………............ (2.4) dengan m adalah plainteks.
Diketahui kunci publik ( p, α, β ) dan kunci rahasia
a
pada algoritma
ElGamal. Diberikan cipherteks ( γ, δ ) dari persamaan (2.1), (2.2), dan (2.3) diperoleh bahwa: δ ( γa )-1
≡ (βk. m ) ( γa )-1 ( mod p ) ≡ βk. m.γ–a(mod p) ≡ (αa )k. m ( αk ) –a (mod p) ≡ αak. m.α–ak ( mod p) ≡ m.α0 ( mod p ) ≡ m (mod p)
Dengan demikian terbukti bahwa: m = ( γa )-1 ( mod p ) Langakah-langkah proses dekripsi: 1. Input cipherteks. 2. Potong cipherteks ke dalam blok-blok cipherteks. 3. Untuk i dari 1 sampai n kerjakan: 3.1 Hitung γ i p-1-a ( mod p ) 3.2 Hitung m i = δ i γ i p-1-a ( mod p ) 4. Diperoleh plainteks m 1 , m 2 , ..., m n 5. Konversikan masing-masing bilangan m 1 , m 2 , ..., m n ke dalam karakter sesuai dengan kode ASCII-nya, kemudian hasilnya digabungkan kembali.
Contoh:
Andi telah mengirimkan cipherteks kepada Budi. Cipherteks yang diperoleh Budi adalah sebagai berikut:
(61, 121)
(228, 349)
(1480, 1836)
(2040, 1185)
(395, 980)
(908, 1582)
(534, 1676)
(1005,209)
(1686, 521)
(1566, 1524)
(2004, 736)
(474, 1734)
(852, 83).
Budi mempunyai kunci publik p = 2099 dan kunci rahasia a = 225 Selanjutnya, untuk mendapatkan pesan asli yang dikirimkan Andi, Budi melakukan perhitungan sebagai berikut:
Tabel 2.3 Proses Dekripsi
1
γi 61
δi 121
γ i 1873( mod 2099 ) 920
δ i γ i 1873( mod 2099 ) 73
Karakter m i I
2
228
349
1588
76
L
3
1480
1836
1556
77
M
4
2040
1185
1054
85
U
5
395
980
1268
32
<spasi>
6
908
1582
1567
75
K
7
534
1676
1156
79
O
8
1005
209
1547
77
M
9
1686
521
1378
80
P
10 1566 11 2004
1524
1241
85
U
736
1928
84
T
12
474
1734
1587
69
E
13
852
83
1139
82
R
i
Berdasarkan perhitungan pada Tabel 2.3, Andi mengetahui pesan rahasia yang dikirimkan oleh Budi, yaitu ”ILMU KOMPUTER”.
2.3
Metode Pembangkit Bilangan Prima Fermat
Bilangan prima adalah bilangan yang tepat memiliki dua faktor yaitu 1 dan bilangan itu sendiri. Semua anggota bilangan prima adalah bilangan ganjil kecuali 2.
Contoh bilangan prima: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, …}.
Bilangan prima jumlahnya tak terhingga banyaknya, bilangan prima terbesar yang ditemukan oleh para ahli adalah:
232.582.657-1 Salah satu perhitungan matematis yang digunakan untuk menghasilkan bilangan prima adalah metode Fermat yang dapat dirumuskan sebagai berikut:
Bila p adalah bilangan prima maka berlaku a p-1 mod p = 1
untuk 1≤a
Contoh penerapan metode Fermat adalah sebagai berikut: a. Bila p = 4 Maka 1 ≤a< 4, didapat a = {1, 2, 3} a p-1 mod p
14-1 mod 4 = 13 mod 4 = 1 24-1 mod 4 = 23 mod 4 = 0 34-1 mod 4 = 33 mod 4 = 1 Jadi, angka 4 bukan merupakan bilangan prima sebab dalam pengecekan menggunakan metode Fermat didapat semua hasil dari urutan bilangan yang lebih kecil dari 4 terdapat nilai yang 0.
b. Bila p = 5 Maka 1 ≤a< 5, jadi didapat a = {1, 2, 3, 4} a p-1 mod p
15-1 mod 5 = 14 mod 5 = 1 25-1 mod 5 = 24 mod 5 = 1 35-1 mod 5 = 34 mod 5 = 1
45-1 mod 5 = 44 mod 5 = 1 Jadi, angka 5 merupakan bilangan prima sebab dalam pengecekan menggunakan metode Fermat didapat semua hasil dari urutan bilangan yang lebih kecil dari 5 adalah 1.
c. Bila p = 28 Maka 1 ≤a< 28, didapat a = {1,2,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19, 20,21,22,24,25,26,27} a p-1 mod p 128-1 mod 28 = 127 mod 28 = 1 228-1 mod 28 = 227 mod 28 = 8 1228-1 mod 28 = 1227 mod 28 = 20 2528-1 mod 28 = 2527 mod 28 = 1 Untuk angka yang besar dengan jumlah nilai a yang banyak, disini hanya diambil 4 angka sebagai contoh. Jadi, menurut pengecekan menggunakan metode Fermat didapat bahwa angka 28 bukan bilangan prima karena didapat hasil yang tidak semuanya 1.
d. Bila p = 29 Maka 1 ≤a< 28, didapat a = {1,2,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19, 20,21,22,24,25,26,27,28} a p-1 mod p 129-1 mod 29 = 128 mod 29 = 1 229-1 mod 29 = 228 mod 29 = 1 1229-1 mod 29 = 1228 mod 29 = 1 2529-1 mod 29 = 2528 mod 29 = 1 Untuk angka yang besar dengan jumlah nilai a yang banyak, disini hanya diambil 4 angka sebagai contoh. Jadi, angka 29 merupakan bilangan prima sebab dalam pengecekan menggunakan metode Fermat didapat hasil dari urutan bilangan yang lebih kecil dari 29 adalah 1.
e. Bila p = 2099 Maka 1 ≤a< 2099, didapat a = {1,2,4,5,6,7,8,9,10,11,12,,,2098}
a p-1 mod p 12099-1 mod 2099 = 1 22099-1 mod 2099 = 1 32099-1 mod 2099 = 1 42099-1 mod 2099 = 1 52099-1 mod 2099 = 1 62099-1 mod 2099 = 1 72099-1 mod 2099 = 1 82099-1 mod 2099 = 1 92099-1 mod 2099 = 1 102099-1 mod 2099 = 1 Untuk angka yang besar dengan jumlah nilai a yang banyak, disini hanya diambil beberapa angka sebagai contoh. Jadi, angka 2099 merupakan bilangan prima sebab dalam pengecekan menggunakan metode Fermat didapat hasil dari urutan bilangan yang lebih kecil dari 2099 adalah 1.
2.4
Metode Pembangkit Bilangan Prima Lucas-Lehmer
Metode pembangkit bilangan prima Fermat adalah salah satu metode pembangkit bilangan prima yang awalnya dikembangkan oleh Édouard Lucas pada tahun 1856 dan kemudian diperbaiki oleh Lucas pada tahun 1878 dan Derrick Henry Lehmer pada 1930-an. Metode Lucas-Lehmer ini hanya bisa dilakukan pada bilangan yang termasuk dalam bilangan Mersenne. Kebanyakan bilangan-bilangan prima besar diketahui merupakan bilangan prima Mersenne. Bilangan prima Mersenne terbesar, sekaligus bilangan prima terbesar yang diketahui saat ini memiliki 9.808.358 digit angka. Bilangan Mersenne dapat dirumuskan dengan: M p = (2p-1) Di mana M p adalah bilangan prima Mersenne dan p adalah bilangan prima[6]. Contoh penerapan bilangan Mersenne adalah sebagai berikut:
1. p = 2 M 2 = (22-1)M 2 = 3 2. p = 3 M 3 = (23-1)M 3 = 7 3. p = 5 M 5 = (25-1)M 5 = 31 4. p = 7 M 7 = (27-1)M 7 = 127 5. p = 11 M 11 = (211-1) M 11 = 2047, bukan prima sebab 2047 = (23 x 89) 6. p = 13 M 13 = (213-1)M 13 = 8191 7. p = 17 M 17 = (217-1)M 17 = 131071 Berdasarkan contoh di atas dapat disimpulkan bahwa tidak semua bilangan prima termasuk dalam bilangan prima Mersenne. Bilangan prima yang termasuk dalam bilangan Mersenne adalah 3, 7, 31, 127, 8191, 131071,… dan bilangan 2047 termasuk bilangan prima tanpa atribut bilangan prima Mersenne.
Metode Lucas-Lehmer memiliki algoritma sebagai berikut: 1. Tentukan nilai awal s := 4; 2. Untuk i from 3 to p do s := s2 – 2 mod Mp; 3. Jika s = 0, return prime; otherwise return composite[4].
Contoh penerapan metode Lucas-Lehmer adalah sebagai berikut: a. p
= 3 M P = (23-1)M P = 7
dari 3 hingga 3, maka lakukan: s n = s2 – 2 mod Mp s 1 = s2 – 2 mod Mp = (42 – 2) mod 7 = 14 mod 7 =0 Jadi, angka M P = 2P – 1 = 7 merupakan bilangan prima. b. p
= 7 M P = (27-1)M P = 127
dari 3 hingga 7, maka lakukan: s n = s2 – 2 mod Mp s 1 = s2 – 2 mod Mp
= (42 – 2) mod 127 = 14 mod 127 = 14 s 2 = (142 – 2) mod 127 = 194 mod 127 = 67 s 3 = (672 – 2) mod 127 = 4487 mod 127 = 42 s 4 = (422 – 2) mod 127 = 1762 mod 127 = 111 s 5 = (1112 – 2) mod 127 = 12319 mod 127 =0 Jadi, angka M P = 2P – 1 = 127 merupakan bilangan prima.
