BAB II BAB II TINJAUAN PUSTAKA

BAB II

BAB II TINJAUAN PUSTAKA

Dalam penyusunan tesis ini perlu dilakukan tinjauan pustaka sebagai dasar untuk melakukan penelitian. Adapun hal-hal yang perlu ditinjau sebagai dasar penyusunannya ialah Kriptografi yaitu Algoritma Pohlig-Hellman, Algoritma RSA dan Algoritma RSA multiple-key. Sebagai dasar perancangan algoritma juga diperlukan penjelasan tentang Teori Bilangan dan Prime Number Generate (Pembangkitan Bilangan Prima).

2.1. Kriptografi Kriptografi adalah ilmu yang menggunakan cara tertentu untuk mengamankan data menggunakan teknik enkripsi dan proses lain yang berhubungan. Matematika merupakan dasar penting dalam kriptografi, karena hanya dengan pengetahuan matematis dapat dikembangkan prosedur yang dibutuhkan untuk mengenkripsi data secara aman (Munir, 2006).

Kriptografi saat ini menjadi hal yang paling penting dalam keamanan informasi. Banyak aspek keamanan seperti kerahasiaan data, keabsahan data, integritas data, dan autentifikasi menjadi cakupan dari tujuan kriptografi. Saat suatu pesan dikirimkan, isi pesan tersebut bisa saja disadap oleh pihak lain yang tidak berhak untuk mengetahui pesan. Supaya pesan tidak dapat diketahui oleh penyadap maka kriptografi menjadi sangat penting dengan cara mengubah pesan menjadi serangkaian kode yang hanya dapat diketahui oleh pihak yang ditentukan.

Universitas Sumatera Utara

2.1.1. Perkembangan dan Konsep Kriptografi Kriptografi berasal dari bahasa Yunani, yang terdiri dari kata crypto dan graphia. Crypto berarti rahasia dan graphia berarti tulisan. Kriptografi merupakan ilmu dan seni untuk menjaga keamanan pesan ketika dikirim dari sebuah sumber informasi ke suatu tujuan pengiriman informasi. Para sejarahwan percaya bahwa hieroglif Mesir, yang dimulai sekitar tahun 1900, merupakan contoh pengenkripsian yang paling awal ditemukan. Kunci yang dapat memecahkan rahasia hieroglif adalah Rosetta Stone, ditemukan tahun 1799 di Mesir dan sekarang berada di British Museum, London. Francois Champollion, menggunakan Rosetta Stone, mendekripsi hieroglif pada tahun 1822 (Konheim, 2007).

Dasar dari sistem kriptografi adalah untuk menyembunyikan informasi rahasia dengan cara yang tidak dapat dipahami oleh pihak lain yang tidak berhak mengetahui informasi tersebut. Dua manfaat umum kriptografi adalah untuk menyimpan data dengan aman dan untuk mengirimkan informasi melalui saluran yang tidak aman seperti internet (Diffie et al 2003). Pada kenyataannya pesan yang terenkripsi tetap dapat diakses oleh pihak lain, tetapi dapat dipastikan pihak lain tidak dapat mengerti isi utama pesan tersebut.

Pesan yang dikirimkan dapat berupa teks, data numerik, dan data jenis lain disebut dengan plaintext. Dengan melakukan proses enkripsi, plaintext tersebut berubah menjadi ciphertext. Proses untuk mengembalikan ciphertext menjadi plaintext disebut dengan proses dekripsi. Untuk melakukan proses dekripsi diperlukan adanya suatu kunci rahasia. Untuk lebih mengetahui konsep kriptografi dapat dilihat pada terminologi kriptografi.


2.1.2. Terminologi Kriptografi Ada beberapa terminologi yang berhubungan dengan kriptografi yaitu: 1. Confidentiality Yang dimaksud dengan confidentiality adalah dimana terdapat jaminan kerahasiaan suatu informasi sehingga tidak dapat diakses oleh pihak lain yang tidak berhak. 2. Privacy Pengertian privacy adalah kemampuan yang dimiliki oleh seseorang untuk mengontrol bagaimana informasi pribadinya supaya menyebar dalam suatu komunitas. Istilah ini merupakan sinonim dari secrecy. 3. Code Code merupakan sekumpulan simbol yang digunakan untuk dapat merepresentasikan informasi. 4. Coding theory Coding theory adalah ilmu yang mempelajari tentang transformasi kode yang memungkinkan adanya pengiriman informasi melalui saluran komunikasi dengan cara yang dapat diandalkan. Biasanya teori ini berfokus pada saluran jaringan yang ramai dan mencoba membuat agar informasi dapat diungkap oleh semua orang (istilah ini merupakan kebalikan dari kriptografi, dimana informasi hanya untuk pihak yang berhak). 5. Encode, Decode Encode dan decode merupakan proses dasar pada coding theory dimana untuk mentransformasi informasi menjadi kode, dan mengembalikan informasi dari kode tersebut. 6. Cryptography Cryptography adalah ilmu tentang kode rahasia memungkinkan kerahasiaan komunikasi melalui saluran yang tidak aman. Kriptografi juga didefinisikan sebagai ilmu tentang pengamanan informasi terhadap pihak yang tidak


berhak. Algoritma kriptografi merupakan algoritma matematis yang menghasilkan suatu proteksi. 7. Cipher Cipher adalah kode rahasia yang merupakan kode publik yang berhubungan dengan informasi rahasia. 8. Cryptography system Cryptography system merupakan sekumpulan algoritma kriptografi yang terdiri atas sandi dan pola dalam kriptografi. 9. Cryptosystem Cryptosystem adalah singkatan dari cryptography system yang sering digunakan pada istilah ”public-key cryptosystem” yang merupakan algoritma kriptografi yang memiliki sepasang kunci. 10. Cleartext Cleartext adalah informasi yang dapat disandikan menggunakan kode publik. 11. Plaintext Plaintext adalah masukan pada algoritma enkripsi dan biasanya merupakan cleartext. 12. Ciphertext, cryptogram Ciphertext, cryptogram adalah informasi yang disandikan menggunakan sistem kriptografi. 13. Encryption, encipherment, decryption, decipherment Encryption, encipherment, decryption, decipherment merupakan proses dasar kriptografi

yaitu

mentransformasi

plainteks

menjadi

ciphertext

dan

sebaliknya. 14. Cryptanalysis, cryptographic analysis, cryptoanalysis Cryptanalysis, cryptographic analysis, cryptoanalysis adalah teori tentang analisis keamanan sistem kriptografi.


2.1.3. Penggunaan Kriptografi Terdapat beberapa media yang menggunakan teknik kriptografi melalui jalur internet (Schmeh, 2003) diantaranya adalah: 1. E-mail E-mail merupakan surat elektronik yang telah disandikan menjadi daya tarik utama dalam dunia internet. 2. World Wide Web (WWW) World Wide Web (WWW) telah banyak digunakan sebagai alat untuk mengakses basis data, administrasi sistem komputer dan pusat perbelanjaan. Pada masingmasing keadaan tersebut, teknik enkripsi sangat dibutuhkan. 3. Koneksi client-server Koneksi client-server merupakan perkembangan sistem komputer berdampak pada perkembangan komunikasi dan adanya aliran yang besar tentang informasi rahasia. 4. Jaringan rahasia virtual Perusahaan dengan beberapa cabang sering mengelompokan jaringan lokal dengan koneksi seperti ISDN. Semua data akan dienkripsi apabila berada diluar jaringan perusahaan dan kemudian akan didekripsi apabila telah berada di wilayah perusahaan. 5. Sistem pembayaran Kriptografi menjaga keamanan dalam melakukan transaksi berupa transfer uang melalui internet. 6. Remote access Beberapa layanan seperti Telnet atau SSH berfungsi untuk mengakses komputer dari jarak jauh menggunakan internet. Kriptografi berperan dalam mengenkripsi data selama proses berlangsung.


2.1.4. Kriptografi Kunci Publik Suatu sistem kriptografi terdiri atas kumpulan transformasi enkripsi dan dekripsi disebut dengan sistem kriptografi kunci publik atau suatu sistem kriptografi asimetris jika sepasang kunci yaitu kunci untuk proses enkripsi dinamakan kunci publik, disebarkan kepada publik, dan kunci untuk proses dekripsi dinamakan kunci privat, dijaga kerahasiaannya (Schmeh, 2003). Beberapa aspek penting pada sistem kriptografi kunci publik dapat dijelaskan sebagai berikut:

1. Keamanan. Dengan adanya sistem kriptografi kunci publik, hanya kunci privat yang harus dijaga kerahasiaannya sedangkan kunci publik disebarkan dengan bebas. 2. Usia pemakaian Sistem kriptografi kunci publik memiliki pasangan kunci yang dapat digunakan tanpa perlu adanya perubahan dalam waktu yang lama. 3. Manajemen kunci Pada jaringan multiuser, lebih sedikit kunci privat yang dibutuhkan. 4. Pertukaran kunci Pada Sistem kriptografi kunci publik, tidak dibutuhkan adanya pertukaran kunci privat antar entitas. 2.2. Teori Bilangan Teori bilangan menjadi dasar dalam kriptografi, khususnya sistem kriptografi kunci publik. Bilangan yang dimaksudkan dalam hal ini adalah bilangan bulat (integer) (Mollin, 2007). Beberapa teori bilangan yang digunakan dalam menganalisis algoritma yang digunakan adalah aritmatika modular, Greatest Common Divisor (GCD), Algoritma Euclidean, Kekongruenan, Invers Modulo, dan Euler Totient.


2.2.1. Aritmatika Modular Aritmetika modular digunakan dalam proses enkripsi dan dekripsi pada algoritma Pohlig-Hellman. Enkripsi dapat dilakukan menghitung nilai pesan dipangkatkan dengan nilai kunci enkripsi yang didapat kemudian dengan melakukan modulo pada nilai bilangan prima yang ditentukan sebelumnya. Aritmatika modular sering dicontohkan sebagai pemahaman aritmatika jam. (Kaisar,2004). Misalkan dalam operasi a mod m berarti menghasilkan sisa jika a dibagi dengan m. Bilangan m disebut modulus atau modulo, dan hasil arimetika modulo m terletak di dalam himpunan {0, 1, 2, …, n-1} sehingga dapat dinotasikan 𝑚 𝑚𝑜𝑑 𝑛 = 𝑟

sedemikian sehingga:

m = n * q + r, 0 ≤ r < n

(2.2.1)

2.2.2. Greatest Common Divisor (GCD) Pembagi bersama terbesar atau disingkat PBB (Greatest Common Divisor atau GCD) digunakan dalam rancangan algoritma Pohlig-Hellman pada saat penentuan kunci tambahan (multiple-key). Kunci tambahan bersyarat harus merupakan anggota dari bilangan ganjil yang mana GCD antara bilangan ganjil tersebut dengan nilai totient yang didapat harus bernilai 1. Dalam notasi dapat dituliskan 𝐾𝑒 ∈ 𝑂𝑑𝑑, K e ∈ 𝐺𝐶𝐷(𝐾𝑒, 𝜃) = 1. Greatest Common Divisor atau GCD dari bilangan suatu a dan b adalah bilangan bulat terbesar d sedemikian sehingga d | a dan d | b. Dalam hal ini kita nyatakan bahwa GCD (a,b) = d. Misalkan dalam menentukan GCD (5,2) = 1. Didapati bahwa nilai a adalah 5 dan nilai b adalah 2. Untuk mempermudah dapat dilihat pada algoritma berikut ini. 1.1.Algoritma Greatest Common Divisor (GCD) function gcd(a,b) while b ≠ 0 t := b b := a mod b a := t return a


2.2.3. Algoritma Euclid Konsep pertama algoritma Euclid berasal dari Cina pada saat Dinasti Han sekitar tahun 200 SM dan 200 M. Algoritma Euclid adalah algoritma untuk mencari GCD dari dua buah bilangan bulat. Algoritma ini digunakan dalam menyederhanakan pecahan dengan membagikan pembilang dan penyebut dengan GCD dan juga untuk mencari penyelesaian bilangan bulat dari persamaan linear.

Euclid adalah matematikawan Yunani yang menuliskan algoritma Euclid dalam bukunya yang berjudul “Element” yang sangat terkenal. Algoritma ini akan digunakan dalam rancangan algoritma Pohlig-Hellman dalam penentuan nilai bilangan kunci tambahan. Misalkan ditentukan dua buah bilangan bulat bukan negatif m dan n dimana m ≥ n. Maka algoritma Eulidean dapat mencari pembagi bersama terbesar dari m dan n. (Mollin, 2007).

Misalkan m = 11 dan n = 7, maka langkah-langkah perhitungan yang dilakukan ada algoritma Euclid adalah sebagai berikut : 1. Menghitung nilai r berdasarkan perhitungan m mod n adalah 11 mod 7 = 4. Karena didapat nilai r tidak sama dengan nol, maka fungsi GCD dipanggil kembali dengan parameter n,r GCD (7,4) 2. Menghitung kembali nilai r berdasarkan perhitungan 7 mod 4 = 3. Karena r tidak sama dengan nol, maka fungsi GCD dipanggil kembali dengan parameter n,r = CGD (4,3) 3. Menghitung kembali nilai r berdasarkan perhitungan 4 mod 3. Karena r tidak sama dengan nol, maka fungsi GCD dipanggil kembali dengan parameter n,r = GCD(3,1) 4. Menghitung kembali nilai r, yaitu 3 mod 1 = 0. Karena r sama dengan nol, maka akan menghasilkan nilai n = 1. Karena GCD (11,7) sama dengan satu maka kedua bilangan tersebut adalah relatif prima.

Algoritma Euclid sangat efisien bahkan pada deretan angka yang panjang dan sering digunakan pada kriptografi. Berikut ini adalah algoritma untuk


Eucledian yang dapat menghitung faktor persekutuan terbesar dari dua buah bilangan bulat. 1.2. Algoritma Euclidean g =1 while (a mod 2=0) and (b mod 2=0) do a = a/2 b = b/2 g =2.g end while a 0 do while a mod 2=0 do a = a/2 while b mod 2=0 do b = b/2 if a b then a =(a-b)/2 else b =(b a)/2 end return g.b

2.2.4. Kekongruenan Notasi a ≡ b (mod n) dibaca a adalah kongruen ke b modulo n. Dimana untuk integer a, b dan n ≠ 0 jika dan hanya jika, untuk beberapa k, 𝑎 = 𝑏 + 𝑘 ∗ 𝑛. Oleh

sebab itu n | (a – b) yang mana disebut juga n dibagi (a - b). Jika a ≡ b (mod n), b disebut sisa dari a modulo n. Kekongruenan dalam perancangan algoritma berhubungan dengan perhitungan nilai GCD yang akan digunakan dalam penentuan kunci tambahan (multiple-key). Misalkan 17 ≡ 5 mod 12 dan 5 adalah sisa dari 17 modulo 12. a adalah himpunan {r 1 , r 2 , …,r n } disebut semua himpunan sisa mod n jika setiap bilangan bulat a, tepat berpasangan dengan satu r i di dalam himpunan yang memenuhi a ≡ r i (mod n). Kekongruenan a ≡ b (mod m) dapat pula dituliskan dalam hubungan, 𝑎 = 𝑏 + 𝑘 ∗ 𝑚, dalam hal ini k adalah bilangan bulat. Berdasarkan

definisi aritmetika modulo, kita juga dapat dinuliskan a 𝑚𝑜𝑑 𝑚 ≡ 𝑟 sebagai, 𝑎 ≡ 𝑟 (𝑚𝑜𝑑 𝑚)


Pembagian bilangan bulat n untuk penjumlahan dan perkalian dengan hukum assosiatif, komutatif, dan distributif terbentuk. Untuk faktanya kita dapat menurunkan modulo n dari yang lain dan kemudian dilakukan operasi dan kemudian dilakukan penurunan dari modulo n, karena sisa modulo n adalah homomorphism dari lingkaran bilangan bulat kelingkaran bilangan bulat mod n (Mollin, 2007). Maka dapat dituliskan bahwa, (𝑎 ± 𝑏) (𝑚𝑜𝑑 𝑛) ≡ [𝑎(𝑚𝑜𝑑 𝑛) ± 𝑏 (𝑚𝑜𝑑 𝑛)] (𝑚𝑜𝑑 𝑛)

(2.2.4)

(𝑎 ∗ 𝑏)(𝑚𝑜𝑑 𝑛)≡ [𝑎(𝑚𝑜𝑑 𝑛) ∗ 𝑏(𝑚𝑜𝑑 𝑛)] (𝑚𝑜𝑑 𝑛)

Dalam teoremanya dapat dimisalkan m adalah bilangan bulat positif 1. Jika a ≡ b (mod m) dan c adalah sembarang bilangan bulat maka: -

(𝑎 + 𝑐)≡(𝑏 + 𝑐) 𝑚𝑜𝑑 𝑚

(𝑎 ∗ 𝑐 )≡ (𝑏 ∗ 𝑐) 𝑚𝑜𝑑 𝑚

𝑎𝑝 ≡𝑏 𝑝 𝑚𝑜𝑑 𝑚 ; p = bilangan bulat tak negatif)

2. Jika a ≡ b (mod m) dan c ≡ d (mod m), maka -

(𝑎 + 𝑐) ≡ (𝑏 + 𝑑) (𝑚𝑜𝑑 𝑚)

𝑎 ∗ 𝑐 ≡𝑏 ∗ 𝑑 (𝑚𝑜𝑑 𝑚)

2.2.5. Invers Modulo Jika a dan m relatif prima dan m > 1, maka kita dapat menemukan inversi dari a modulo m. Inversi dari a (mod m), disebut juga inversi perkalian, adalah bilangan bulat a-1, sedemikian sehingga : 𝑎 ∗ 𝑎 − 1≡1 (𝑚𝑜𝑑 𝑚)

(2.2.5)

dari definisi relatif prima diketahui bahwa GCD (a,m)=1, dan menurut persamaan terdapat bilangan bulat p dan q, sedemikian sehingga: 𝑝 ∗ 𝑎 + 𝑞 ∗ 𝑚 = 1 yang mengimplikasikan bahwa : 𝑝 ∗ 𝑎 + 𝑞 ∗ 𝑚 ≡1 (𝑚𝑜𝑑 𝑚)

Karena qm ≡ 0 (mod m ) maka nilai 𝑝 ∗ 𝑎 ≡ 1 (𝑚𝑜𝑑 𝑚)

Kekongruenan yang terakhir ini berarti bahwa p adalah invers dari a (mod m). Pembuktian diatas juga menceritakan bahwa, untuk mencari invers


dari a (mod m), kita harus membuat kombinasi lanjar dari a dan m = 1. Koefisien a dari kombinasi lanjar tersebut merupakan, invers dari a mod m (Mollin, 2007).

2.2.6. Euler Totien Function Fungsi Euler dalam rancangan algoritma Pohlig-Hellman digunakan dalam penentuan nilai relatif prima dari pembangkitan kunci. Untuk setiap bilangan bulat positif n, nilai φ (n ) pada fungsi Euler Totient adalah jumlah bilangan bulat positif < n yang mana relatif prima ke-n. 1. Jika n adalah prima maka φ(n) = n – 1 2. Jika n adalah hasil kali dari 2 prima, dimana : n = p * q maka φ(n)=(p-1) * (q-1) 3. Jika p bilangan prima dimana k > 0, maka :

φ(pk) = pk - pk-1 = pk-1 (p – 1) Fungsi ini digunakan pada kriptografi pada penggunaan Theorema Euler. Theorema Euler menyatakan bahwa jika GCD(a,n) = 1 maka:

a φ ( n ) = 1(mod n)

(2.2.6)

2.3. Pembangkitan Bilangan Prima Pembangkitan bilangan prima (Prime Number Generate) merupakan cara dalam penentuan bilangan prima yang sudah diformula dan akan digunakan dalam pembangkitan kunci bilangan prima. Terdapat beberapa teori tentang pengujian bilangan prima seperti algoritma Primality Proving, Pengujian Bilangan Prima Lucas-Lehmer dalam Bilangan Mersenne, Teorema Pocklington, Teorema Proth, Pengujian Prima Pepin, Proofs Via the Converse of Fermat’s Theorem, Prima P, Sophie Germain’s Prime Density Conjecture dan beberapa pengujian bilangan prima lainnya.


2.3.1. Teorema Fermat Pierre de Fermat (dibaca Fair-ma) merupakan seorang matematikawan berkebangsaan Perancis (1607-1665). Fermat megikuti pendidikan di Universitas Toulouse dan kemudian mempelajari ilmu hukum di Universitas Orleans. Setelah mendapatkan gelar sarjana hukum Fermat menjadi pengajar di kantor pemerintahan di Toulose. Namun sepanjang hidupnya dia memiliki ketertarikan yang dalam terhadap teori angka dan matematika. (Mollin, 2007).

2.3.2. Konsep Teorema Fermat Pada teori Fermat dinyatakan suatu bilangan prima p dapat dipastikan keprimaannya. Jika bilangan p adalah sebuah bilangan prima dan a bukan merupakan kelipatan dari p, dan 1 ≤ 𝑎 < 𝑝. Maka dapat dinotasikan dalam t dengan rumus : 𝑎𝑝−1 ≡ 1 𝑚𝑜𝑑 𝑝 ; 1 ≤ 𝑎 < 𝑝, atau dapat dituliskan juga sebagai: 𝑎𝑝−1 𝑚𝑜𝑑 𝑝 ≡ 1 ; 1 ≤ 𝑎 < 𝑝

(2.3.2)

Penggunaan terorema Fermat pada rancangan algoritma Pohlig-Hellman sangat penting karena pembangkitan bilangan prima merupakan awal proses algoritma. Dengan rumus tersebut dapat dinyatakan suatu bilangan prima atau tidak prima. Misalkan sebuah bilangan bernilai 5, dapat dibuktikan keprimaannya dengan nilai p = 3. Berdasarkan syarat bahwa 1 ≤ 𝑎 < 3, didapat nilai a yang

mungkin adalah 1 dan 2. Kedua bilangan akan diuji dengan teorema Fermat yaitu: -

-

Untuk nilai a = 1, maka dapat dilakukan pengujian 𝑎𝑝−1 𝑚𝑜𝑑 𝑝 ≡ 1, = 13-1 mod 3 ≡ 12 mod 3 ≡ 1

(memenuhi teorema Fermat)

= 23-1 mod 3 ≡ 22 mod 3 ≡ 1

(memenuhi teorema Fermat)

Untuk nilai a = 2 , maka dapat dilakukan pengujian 𝑎𝑝−1 𝑚𝑜𝑑 𝑝 ≡ 1,

Dari pengujian setiap batas nilai a didapati bahwa nilai 3 merupakan bilangan prima karena memenuhi syarat yang ada pada teorema Fermat. Dan konsep Fermat dapat digunakan untuk pengujian bilangan prima lainnya.


2.4. Algoritma Pohlig-Hellman 2.4.1. Perkembangan Algoritma Pohlig-Hellman Pada awalnya algoritma Pohlig-Hellman ditemukan oleh Roland Silver, namun untuk pertama kalinya diterbitkan oleh Stephen Pohlig dan Martin Hellman. Algoritma Pohlig-Hellman dipatenkan di Amerika Serikat dan Kanada. Konsep enkripsi pada Algoritma Pohlig-Hellman hampir sama dengan algoritma RSA. Pada dasarnya algoritma ini adalah salah satu algoritma asimetris karena menggunakan kunci yang berbeda untuk enkripsi dan dekripsi (Mollin, 2007).

Dalam algoritma Pohlig-Hellman tidak mengguna konsep kunci publik karena kuncinya dapat digunakan pada saat enkripsi dan dekripsi sehingga harus terjaga kerahasiaannya (Shcneider, 1996). Sama seperti dalam algoritma RSA untuk dapat melakukan enkripsi dan dekripsi dalam dihitung dengan rumus: C = Pe mod n

(untuk melakukan enkripsi)

P = Cd mod n

(untuk melakukan dekripsi)

dengan ketentuan bahwa nilai 𝑒 ∗ 𝑑 ≡ 1 2.4.2. Proses Algoritma Pohlig-Hellman Proses kerja algoritma Pohlig-Hellman dituliskan sebagai berikut: 1. Menentukan sebuah bilangan prima p yang besar (bersifat rahasia hanya diketahui pengirim pesan dan penerima pesan); 2. Menentukan nilai ϕ(p) = p - 1 3. Menghitung nilai e dengan syarat bahwa nilai 1<e<ϕ(p) dan juga nilai e relatif prima dengan ϕ(p) 4. Menghitung nilai d sebagai invers dari e modulo ϕ(p) atau dapat dituliskandengan notasi: d*e mod ϕ (p)=1 5. Melakukan enkripsi dari suatu plainteks. Untuk enkripsi dapat dilakukan dengan rumus: C = me mod p 6. Dekripsi dapat dilakukan dengan rumus: M=Cd mod p


2.4.3. Contoh Kasus Algoritma Pohlig-Hellman Penggunaan algoritma Pohlig-Hellman dalam sebuah simulasi pengiriman pesan yang dilakukan antara Alice dan Bob. Misalkan Alice mengizinkan Bob untuk mengirimkan sebuah pesan pribadi (private message) kepadanya melalui media transmisi yang tidak aman (insecure). Dalam algoritma Pohlig-Hellman, Alice dan Bob akan melakukan langkah-langkah pada sebagai berikut : 1. Alice (penerima) dan Bob (pengirim) menyepakati sebuah bilangan prima sebagai kunci privat dari pesan yang akan dikirimkan. Misalkan kunci tersebut adalah p bernilai 487. 2. Setelah disepakati bilangan prima tersebut kemudian digunakan untuk menghitung nilai totient dengan rumus ϕ(p) =p–1, sehingga didapat nilai: ϕ(p) = 487 – 1 = 486. 3. Dengan nilai totient, maka Bob dapat menghitung nilai kunci enkripsi e yang digunakan dalam program dengan syarat bahwa nilai 1<e<ϕ(p) dan juga nilai e relatif prima dengan ϕ(p). Hal ini dapat dihitung dengan menghitung GCD (ϕ(p),e)=1. Dalam perhitungan didapati: GCD (486, e) = 1 , 1<e<486 e = 145 Didapat nilai e yang memungkinkan dan disepakati oleh keduanya adalah e = 145. Dengan nilai kunci enkripsi ini makan selanjutnya dapat dilakukan proses enkripsi. 4. Kunci dekripsi juga langsung ditetapkan oleh kedua belah pihak dengan syarat rumusan d = e-1 mod ϕ (p). Dari nilai e yang didapat sebelumnya maka dapat dihitung nilai d dengan langkah sebagai berikut : d = e-1 mod ϕ (p) d = 145-1 mod 486 d = 181 Kunci dekripsi digunakan untuk mengembalikan nilai ciphertext ke dalam bentuk plaintext. 5. Proses enkripsi merupakan proses dimana pesan yang sebelumnya berupa plaintext dikodekan menjadi berupa ciphertext. Terlebih dahulu Bob akan


membuat pesan rahasia berupa text. Dalam contoh pesan yang akan digunakan adalan ECIL. Dari rumus perhitungan enkripsi C = me mod p, maka dapat dihitung kode ciphertext dari setiap pesan tersebut sebagai berikut: Pesan yang akan dikirim M = ECIL Nilai dari setiap Plaintext : P 1 = E, nilai dalam kode ASCII adalah 5 (huruf kelima) P 2 = C, nilai dalam kode ASCII adalah 3 (huruf ketiga) P 3 = I, nilai dalam kode ASCII adalah 9 (huruf kesembilan) P 4 = L, nilai dalam kode ASCII adalah 12 (huruf keduabelas) Maka nilai ciphertext dari setiap pesan adalah : C 1 = M e mod p

= P 1 e mod p

= 5145 mod 487 C 1 = 269 C 2 = M e mod p

= P 2 e mod p

= 3145 mod 487 C 2 = 354 C 3 = M e mod p

= P 3 e mod p

= 9145 mod 487 C 3 = 314 C 4 = M e mod p

= P 3 e mod p

= 12145 mod 487 C 4 = 107 6. Setelah mendapatkan semua kode ciphertext maka dapat dirangkai seluruh kode dan menghasilkan ciphertext 269, 354, 314 dan 107. Pesan inilah yang akan dikirimkan kepada Alice, sehingga pihak lain tidak akan mengetahui makna pesan sebenarnya. 7. Alice dapat mendapatkan pesan sebenarnya dengan melakukan proses dekripsi. Dari rumus perhitungan dekripsi P = Cd mod p, maka dapat dihitung kode plaintext dari setiap chipertext tersebut sebagai berikut: C = 269

354

314

107


Nilai dari setiap Plaintext : P 1 = C d mod p

= C 1 d mod p

= 269181 mod 487 P1 = 5

plaintext = E

P 2 = C d mod p

= C 2 d mod p

= 354181 mod 487 P2 = 3

plaintext = C d

P 3 = C mod p

= C 3 d mod p

= 314181 mod 487 P3 = 9

plaintext = I

P 4 = C d mod p

= C 4 d mod p

= 107181 mod 487 P 1 = 12

plaintext = L

Setelah mendapatkan semua plaintext terhitung maka dapat dirangkai seluruh kode dan menghasilkan plaintext : ECIL 8. Dari contoh didapat bahwa Alice dapat membuka kembali pesan yang sudah dienkripsi dengan melakukan proses dekripsi.

2.5. Algoritma RSA 2.5.1. Perkembangan Algoritma RSA Algortima RSA dijabarkan pada tahun 1977 oleh tiga orang yaitu Ron Rivest, Adi Shamir dan Len Adleman yang berasal dari Massachusetts Institute of Technology. Huruf RSA itu sendiri berasal dari inisial nama mereka (Rivest Shamir Adleman). Algoritma ini dipatenkan oleh Massachusetts Institute of Technology pada tahun 1983 di Amerika Serikat (Stallings, 2005).

Algoritma RSA adalah sebuah algoritma pada enkripsi kunci publik. RSA merupakan

algoritma

pertama

yang

cocok

digunakan

untuk digital

signature karena kehandalannya dalam proses enkripsi. Hal ini menjadikan algoritma yang lebih banyak dikembangkan dalam bidang kriptografi public key.


2.5.2. Proses Algoritma RSA Proses atau cara kerja dari algoritma RSA dapat dilihat sebagai berikut: 1. Menentukan dua bilangan prima p ≠ q secara acak dan terpisah untuk tiaptiap p dan q. 2. Melakukan perhitungan n = p*q. (n merupakan hasil perkalian dari p dikalikan dengan q) 3. Melakukan perhitungan nilai totient φ (n)= (p-1)(q-1). 4. Menentukan nilai kunci enkripsi e dengan syarat bahwa nilangan tersebut merupakan bilangan bulat (integer) 1 < e < φ(n) dimana nilai GCD (φ(n), e)=1. 5. Menghitung kunci enkripsi yang dilakukan dengan perhitungan kunci dekripsi dengan rumus d ≡ e -1 mod φ(n). 6. Setelah mendapatkan kunci-kunci tersebut maka dapat dilakukan proses enkripsi maupun proses dekripsi. 7. Rumus untuk melakukan proses enkripsi adalah C = M e mod n 8. Rumus untuk melakukan proses dekripsi adalah P = C d mod n

2.5.3. Contoh Kasus Algoritma RSA Algoritma RSA disimulasikan dalam sebuah simulasi pengiriman pesan yang dilakukan antara Alice dan Bob. Alice mengizinkan Bob untuk mengirimkan sebuah pesan pribadi (private message). Dalam algoritma RSA multiple-key, Alice dan Bob akan melakukan langkah-langkah pada sebagai berikut : 1. Alice (penerima) dan Bob (pengirim) menyepakati dua buah bilangan prima sebagai kunci privat dari pesan yang akan dikirimkan. Misalkan kunci tersebut adalah bernilai p=631 dan q=311. 2. Setelah disepakati kedua bilangan prima tersebut kemudian digunakan untuk menghitung nilai totient dengan rumus n =p*q, sehingga didapat nilai: n = (631)*(311)= 196241 3. Langkah selanjutnya adalah menghitung nilai totient dengan rumus ϕ(n) =(p–1)(q-1), sehingga didapat nilai: ϕ(n) = (631-1)*(311-1))= 195300. Nilai n dan nilai totient akan digunakan dalam perhitungan nilai kunci enkripsi.


4. Dari nilai totient yang didapat, maka Bob dapat menghitung nilai kunci enkripsi e yang digunakan dalam program dengan syarat bahwa nilai 1<e<ϕ(n) dan juga nilai e relatif prima dengan ϕ(n). Hal ini dapat dihitung dengan menghitung GCD (ϕ(n),e)=1. Dalam perhitungan didapati: GCD (195300, e) = 1 , 1<e<195300 e = 78899 Didapat nilai e yang memungkinkan dan disepakati oleh keduanya adalah e = 78899. Dengan nilai kunci enkripsi ini makan selanjutnya dapat dilakukan proses enkripsi. 5. Kunci dekripsi juga langsung ditetapkan oleh kedua belah pihak dengan syarat rumusan d = e-1 mod ϕ (n). Dari nilai e yang didapat sebelumnya maka dapat dihitung nilai d dengan langkah sebagai berikut : d = e-1 mod ϕ (n) d = 78899-1 mod 195300 d = 17399 Kunci dekripsi digunakan untuk mengembalikan nilai ciphertext ke dalam bentuk plaintext. 6. Proses enkripsi merupakan proses dimana pesan yang sebelumnya berupa plaintext yang dikodekan menjadi ciphertext. Terlebih dahulu Bob akan membuat pesan rahasia berupa teks. Dalam kasus ini pesan yang akan digunakan adalah kode 100. Dari rumus perhitungan enkripsi C = me mod n, maka dapat dihitung kode ciphertext dari setiap pesan tersebut sebagai berikut: Pesan yang akan dikirim M = 100 Nilai dari setiap Plaintext P 1 = 100, maka nilai ciphertext dari setiap pesan dengan perhitungan : C

= M e mod n = 10078899 mod 196241

C

= 31538

7. Setelah mendapatkan semua kode ciphertext maka dapat dirangkai seluruh kode yang menghasilkan ciphertext sebesar 31538. Pesan inilah yang akan


dikirimkan kepada Alice, sehingga pihak lain tidak akan mengetahui makna pesan sebenarnya. 8. Alice dapat mendapatkan pesan sebenarnya dengan melakukan proses dekripsi. Dari rumus perhitungan dekripsi P = Cd mod n, maka dapat dihitung kode plaintext dari setiap chipertext tersebut sebagai berikut: C = 31538 Nilai dari setiap Plaintext : P 1 = C d mod n

= C 1 d mod n

= 3153817399 mod 196241 P 1 = 100 Setelah mendapatkan semua plaintext terhitung maka dapat dirangkai seluruh kode dan menghasilkan plaintext adalah 100 9. Dari contoh didapat bahwa Alice dapat membuka kembali pesan yang sudah dienkripsi dengan melakukan proses dekripsi.

2.5.4. Algoritma RSA Multiple Key Algoritma RSA Multiple-key merupakan pengembangan dari Algoritma RSA sebelumnya. Untuk pengembangannya dilakukan penambahan beberapa atau banyak kunci untuk meningkatkan kemampuan algoritma dalam keamanan datanya. (Schneider,1996). Sama seperti pada proses algoritma RSA, yaitu melakukan pembangkitan dua buah bilangan prima p dan q, menentukan nilai n (merupakan perkalian p dan q), selanjutnya mencari nilai φ (merupakan hasil perhitungan (p-1)(q-1).

Namun pada algoritma RSA multiple-key dilakukan penambahan prosedur dengan menambahkan kunci enkripsi (dengan syarat bahwa bilangan tersebut adalah bilangan ganjil dan dapat dibuat sebanyak sejumlah n-kunci). Demikian juga untuk dekripsinya, dilakukan penambahan kunci dekripsi yang syaratnya sama dengan kunci enkripsi sehingga dengan rumusan tersebut maka dapat dihitung nilai dari e (kunci untuk enkripsi) yang didapat dari perkalian semua kunci enkripsi yang dibuat sebelumnya. Demikian halnya untuk melakukan


dekripsi dengan menghitung nilai d (kunci untuk dekripsi) yang didapat dari perkalian semua kunci dekripsi yang dibuat sebelumnya. Untuk mempermudah penyampaian algoritma RSA Multiple-key berikut ini disajikan dalam konsep: 1.

Membangkitkan Bilangan Prima Menentukan dua bilangan prima p dan q dimana 𝑝 ≠ 𝑞. Untuk

pembangkitannya menggunakan teorema Fermat. 2.

Menghitung nilai n. Nilai n didapat dari perkalian p dan q, dapat dinotasikan : n = p * q.

3.

4.

Menghitung nilai totient. Nilai totient 𝜑(𝑛) = (𝑝 − 1)(𝑞 − 1)

Menghitung Kunci Tambahan Enkripsi Menentukan berapa banyak kunci tambahan enkripsi sebanyak -x (K e1, K e2, K e3 … K ex ). Setelah itu menentukan nilai setiap K e dengan syarat bahwa

nilai: K e1 ∈ bilangan ganjil dan GCD(K 𝑒1 , 𝜑(n)) = 1

K e2 ∈ bilangan ganjil dan GCD (K 𝑒1 ∗ K 𝑒2 , 𝜑(n)) = 1 . . . K ex ∈ bilangan ganjil dan GCD (K 𝑒1 ∗ K 𝑒2 ∗ … … ∗ K 𝑒x , 𝜑(n)) = 1 5.

Setelah didapat nilai K e , dapat dihitung nilai 𝑒 = (K 𝑒1 ∗ K 𝑒2 . .∗ K 𝑒x , 𝜑(n) Enkripsi

Enkripsi merupakan proses pengubahan plaintext menjadi ciphertext. Untuk melakukan enkripsi dapat dilakukan dengan rumus 𝐶 = 𝑚𝑒 𝑚𝑜𝑑 𝑛 dimana

pada plaintext m < n 6.

Menghitung Kunci tambahan Dekripsi Menentukan berapa banyak kunci tambahan dekripsi sebanyak –x (K d1, K d2, K d3 … K dx ). Setelah itu menentukan nilai setiap K d dengan syarat bahwa nilai: K d1 ∈ bilangan ganjil dan GCD(K 𝑑1 , 𝜑(n)) = 1

K d2 ∈ bilangan ganjil dan GCD (K 𝑑1 ∗ K 𝑑2 , 𝜑(n)) = 1 Universitas Sumatera Utara

. . K dx ∈ bilangan ganjil dan GCD (K 𝑑1 ∗ K 𝑑2 ∗ … … ∗ K 𝑑x , 𝜑(n)) = 1 7.

Setelah didapat nilai K d , dapat dihitung nilai 𝑑 = (K 𝑑1 ∗ K 𝑑2 . .∗ K 𝑑x , 𝜑(n) Dekripsi

Dekripsi merupakan kebalikan dari enkripsi. Masukannya adalah ciphertext dan keluarannya adalah plaintext. Untuk melakukan dekripsi dapat dilakukan dengan rumus 𝑚 = 𝐶 𝑑 𝑚𝑜𝑑 𝑛 2.5.5. Contoh Kasus RSA Multiple Key

Algoritma RSA multiple-key dapat disimulasikan dalam sebuah simulasi pengiriman pesan yang dilakukan antara Alice dan Bob. Alice mengizinkan Bob untuk mengirimkan sebuah pesan pribadi (private message). Dalam algoritma RSA multiple-key, Alice dan Bob akan melakukan langkah-langkah pada sebagai berikut : 1. Alice (penerima) dan Bob (pengirim) menyepakati dua buah bilangan prima sebagai kunci privat dari pesan yang akan dikirimkan. Misalkan kunci tersebut adalah bernilai p=631 dan q=311. 2. Setelah disepakati kedua bilangan prima tersebut kemudian digunakan untuk menghitung nilai totient dengan rumus n =p*q, sehingga didapat nilai: n = (631)*(311)= 196241 3. Langkah selanjutnya adalah menghitung nilai totient dengan rumus ϕ(n) =(p–1)(q-1), sehingga didapat nilai: ϕ(n) = (631-1)*(311-1))= 195300. Nilai n dan nilai totient akan digunakan dalam perhitungan nilai kunci enkripsi. 4. Dari nilai totient yang didapat selanjutnya Bob akan melakukan perhitungan kunci-kunci tambahan untuk enkripsi dan untuk dekripsinya. Kunci tambahan tersebut haru memenuhi syarat bahwa setiap kunci yang ditentukan adalah K dx ∈ bilangan ganjil dan GCD (K 𝑑1 ∗ K 𝑑2 ∗ … … ∗ K 𝑑x , 𝜑(n)) = 1. Dengar syarat

tersebut Bob dapat menentukan secara acak nilai kunci tambahan tersebut.


Dalam kasus ini digunakan tiga kunci tambahan enkripsi dan dua kunci tambahan untuk dekripsi. KUnci yang digunakan adalah: K e1 = 41213,

K e2 = 44969, K e3 = 50483

K d1 = 7313,K d2 = 8983 5. Berdsarkan kunci enkripsi yang didapat selanjutnya dapat dihitung nilai kunci enkripsi e yang digunakan dalam program dengan perkalian dari setiap kunci tambahan enkripsinya e = K e1 * K e2 * K e3 e = 41213 * 44969 * 50483 e = 93560517322751 Didapat nilai e yang memungkinkan dan disepakati oleh keduanya adalah e = 93560517322751. Dengan nilai kunci enkripsi ini makan selanjutnya dapat dilakukan proses enkripsi. 6. Kunci dekripsi juga langsung ditetapkan oleh kedua belah pihak dengan syarat rumusan d = K d1 *K d2 …*K dx . Dari nilai kunci tambahan dekripsi yang didapat sebelumnya maka dapat dihitung nilai d dengan langkah sebagai berikut : d = K d1 *K d2 d = 7313 * 8983 d = 65692679 Kunci dekripsi digunakan untuk mengembalikan nilai ciphertext ke dalam bentuk plaintext. 7. Proses enkripsi merupakan proses dimana pesan yang sebelumnya berupa plaintext dikodekan menjadi berupa ciphertext. Terlebih dahulu Bob akan membuat pesan rahasia berupa text. Dalam contoh pesan yang akan digunakan adalah kode 100. Dari rumus perhitungan enkripsi C = me mod n, maka dapat dihitung kode ciphertext dari setiap pesan tersebut sebagai berikut: Pesan yang akan dikirim M = 100, nilai dari setiap Plaintext P 1 = 100, ,maka nilai ciphertext dari setiap pesan adalah : C

= M e mod n = 10093560517322751 mod 196241

C

= 113452


8. Setelah mendapatkan semua kode ciphertext selanjutnya seluruh kode dirangkai dan menghasilkan ciphertext sebesar 113452. Pesan ini kemudian dikirimkan kepada Alice, sehingga pihak lain tidak akan mengetahui makna pesan sebenarnya. 9. Alice dapat mendapatkan pesan sebenarnya dengan melakukan proses dekripsi. Dari rumus perhitungan dekripsi P = Cd mod n, maka dapat dihitung kode plaintext dari setiap chipertext tersebut sebagai berikut: C = 113452 Nilai dari setiap Plaintext : P 1 = C d mod n

= C 1 d mod n

= 11345265692679 mod 196241 P 1 = 100 Setelah mendapatkan semua plaintext terhitung maka dapat dirangkai seluruh kode dan menghasilkan plaintext adalah 100 10. Dari kasus didapat bahwa Alice dapat membuka kembali pesan yang sudah dienkripsi dengan melakukan proses dekripsi.


BAB II BAB II TINJAUAN PUSTAKA

Recommend Documents