Tugas TBO

Pada kesempatan kali ini saya akan membahas penyelesaian game river iq game tentunya dengan teori penyelesaian, game ini adalah sebuah game sederhana menyebrangkan semua orang melalui sungai dengan beberapa batasan maslah seperti berikut :

Seorang polisi ingin menyebrangkan 2 keluarga yang terdiri 1 ayah dan dua anak yang satu berambut coklat dan yang satu berambut hijau, 1 ibu dan dua anak yang satu berambut coklat sedagkan yang satu berambut ungu dan juga seorang penjahat, perahu hanya bisa memuat 2 penumpag, anak-anak dan penjahat tidak bisa menjalankan perahu, jika anak-anak di tinggalkan orangtuanya menyebarang maka anak akan di pukul oleh orang tua lainya, jika anak tetangga di ajak menyebrang maka anak tersebut akan di pukul oleh orang tua tetangga, (tidak boleh meningalkan anak dengan orangtua lain) jika polisi mengantar anak dan penjahat masih dalam 1 area maka anak akan di pukul oleh penjahat, jika orang tua bertemu dengan penjahat tanpa ada polis maka orang tua akan dipukul

1. Identifikasi ruang keadaan

Permasalahan ini dapat dilambangkan dengan (jumlah polisi, jumlah penjahat, jumlah bapak, jumlah anak laki-laki berambut coklat, jumlah anak laki laki berambut hijau, jumlah ibu, jumlah anak perempuan berambut coklat, jumlah anak perempuan berambut ungu).

2. Aturan aturan

Aturan ke-	Aturan
1	Polisi menyeberang
2	Bapak menyeberang
3	Ibu menyeberang
4	Polisi kembali
5	Bapak kembali
6	Ibu kembali
7	Polisi dan penjahat menyeberang
8	Polisi dan penjahat kembali
9	Polisi dan bapak menyeberang
10	Polisi dan bapak kembali
11	Polisi dan ibu menyeberang
12	Polisi dan ibu kembali
13	Polisi dan anak laki-laki berambut coklat menyeberang
14	Polisi dan anak laki-laki berambut coklat kembali
15	Polisi dan anak laki-laki berambut hijau menyeberang
16	Polisi dan anak laki-laki berambut hijau kembali
17	Polisi dan anak perempuan berambut coklat menyeberang
18	Polisi dan anak perempuan berambut coklat kembali
19	Polisi dan anak perempuan berambut ungu menyeberang
20	Polisi dan anak perempuan berambut ungu kembali
21	Bapak dan ibu menyeberang
22	Bapak dan ibu kembali
23	Bapak dan anak laki-laki berambut coklat menyeberang
24	Bapak dan anak laki-laki berambut coklat kembali
25	Bapak dan anak laki-laki berambut hijau menyeberang
26	Bapak dan anak laki-laki berambut hijau kembali
27	Ibu dan anak perempuan berambut coklat menyeberang
28	Ibu dan anak perempuan berambut coklat kembali
29	Ibu dan anak perempuan berambut ungu menyeberang
30	Ibu dan anak perempuan berambut ungu kembali

Penjelasan langkah demi langkah

1. Sebrangkan polisi dan penjahat.

2. Polisi kembali.

3. Polisi dengan anak perempuan beramut ungu menyebrang.

4. Polisi dan penjahat kembali.

5. Ibu dan anak permpuan coklat menyebrang.

6. Ibu kembali.

7. Bapak dan ibu menyebrang

8. Bapak kembali

9. Polisi dan penjahat menyebrang

10. Ibu kembali

11. Bapak dan ibu menyebrang

12. Bapak kembali

13. Bapak dan anak laki-laki berambut hijau menyeberang

14. Polisi dan penjahat kembali

15. Polisi dan anak laki-laki berambut coklat menyeberang

16. Polisi kembali

17. Polisi dan penjahat kembali

18. Selesai

Algoritma RSA

RSA merupakan algoritma kriptografi asimetri, dimana kunci yang digunakan untuk mengenkripsi berbeda dengan yang digunakan untuk mendekripsi. Kunci yang digunakan untuk mengenkripsi disebut dengan kunci public, dan yang digunakan untuk mendekripsi disebut dengan kunci privat. RSA adalah salah satu algoritma kriptografi yang menggunakan konsep kriptografi kunci publik. RSA membutuhkan tiga langkah dalam prosesnya, yaitu pembangkitan kunci, enkripsi, dan dekripsi. Proses enkripsi dan dekripsi merupakan proses yang hampir sama. Jika bilangan acak yang dibangkitkan kuat, maka akan lebih sulit untuk melakukan cracking terhadap pesan. Parameter kuat tidaknya suatu kunci terdapat pada besarnya bilangan acak yang digunakan.

Untuk pembangkitan pasangan kunci RSA, digunakan algoritma sebagai berikut: 

1. Dipilih dua buah bilangan prima sembarang yang besar, p dan q. Nilai p dan q harus dirahasiakan. 
2. Dihitung n = p x q. Besaran n tidak perlu dirahasiakan. 
3. Dihitung m = (p – 1)(q – 1). Besaran m perlu dirahasiakan. 
4. Dipilih sebuah bilangan bulat sebagai kunci publik, disebut namanya e, yang relatif prima terhadap m. e relatif prima terhadap m artinya faktor pembagi terbesar keduanya adalah 1, secara matematis disebut gcd (e,m) = 1. Untuk mencarinya dapat digunakan algoritma Euclid. Nilai e bersifat tidak rahasia. 
5. Dihitung kunci privat, disebut namanya d sedemikian agar (d x e) mod m = 1. Untuk mencari nilai d yang sesuai dapat juga digunakan algoritma Extended Euclid. Nilai D bersifat rahasia.

Maka hasil dari algoritma tersebut diperoleh : 

1. kunci publik adalah pasangan (e,n). Bersifat tidak rahasia. 
2. kunci private adalah pasangan (d,n). Bersifat rahasia 

Algoritma Enkripsi/Dekripsi 

Enkripsi 

• Ambil kunci publik penerima pesan, e, dan n 
• Nyatakan plainteks M menjadi blok-blok M1, M2, …, sedemikian sehingga setiap blok merepresentasikan nilai di dalam selang [0, n – 1]. 
• Setiap blok Mi dienkripsi menjadi blok Ci dengan rumus Ci = Mi ^ e mod n 

Dekripsi 

• Setiap blok cipherteks Ci didekripsi kembali menjadi blok Mi dengan rumus Mi = Ci ^ d mod n

Algoritma Euclid

Algoritma ini mencari FPB dengan cara melakukan pembagian berulang-ulang dimulai dari kedua bilangan yang hendak kita cari FPBnya sampai kita mendapatkan sisa 0 dari hasil pembagian.

Marilah kita lihat contoh yang lain, cari FPB dari 40 dan 64 :

• 64 ÷ 40 = 1 dengan sisa 24 
• 40 ÷ 24 = 1 dengan sisa 16 
• 24 ÷ 16 = 1 dengan sisa 8 
• 16 ÷ 8 = 2 dengan sisa 0.

Kita berhenti di sini sebab kita sudah mendapat sisa 0. Bilangan terakhir yang kita gunakan untuk membagi adalah 8, jadi FPB dari 40 dan 64 adalah 8 

Contoh lain, cari FPB 3337 dan 79 :

• 3337 ÷ 79 = 42 dengan sisa 19 
• 79 ÷ 19 = 4 dengan sisa 3 
• 19 ÷ 3 = 6 dengan sisa 1 

Kita berhenti karena sudah mendapatkan sisa 1.

Contoh RSA Sederhana 

1. p = 47 dan q = 71 (keduanya prima). 
2. n = p ⋅ q = 3337 
3. m = (p – 1)(q – 1) = 3220 
4. Pilih e yg relativ prime terhadap m, gcd(e,m) = 1.
   e = 79 => gcd(79, 3337) = 1 
5. Cari nilai d, d*e = 1 mod (m) 

          d*79 = 1 mod 3220
          d*79 mod 3220 = 1

          d = 1019

Sehingga didapatkan : 

1. Public key : (79, 3337) 
2. Private key : (1019, 3337) 

Proses Enkripsi

Setelah didapat perhitungan di atas, maka akan dilakukan enkripsi plaintext M = AKU. Pertama-tama plaintext tersebut diubah menjadi format ASCII sebagai berikut : 

Karakter          A                K           U 

ASCII             65               75          85 

M1 = 657 M2 = 585

Setelah dibagi perblock, maka akan dihitung menggunakan rumus Ci = Mi ^ e mod n. 

• C1 = 657 ^ 79 mod 3337 = 2349 
• C2 = 585 ^ 79 mod 3337 = 685 

Maka, chipertext yang didapatkan adalah C = 320328

Proses Dekripsi

Setelah chipertext dari kata AKU didapat, untuk mengubahnya kembali jadi plaintext menggunakan dekripsi dengan rumus Mi = Ci ^ d mod n. 

• M1 = 2349 ^ 1019 mod 3337 = 657 
• M2 = 685 ^ 1019 mod 3337 = 585 

Maka, setelah di dekripsi hasilnya akan sama. Yaitu 657585.