Archive for the ‘Artikel’ Category

Apa itu Web Service?

Friday, July 15th, 2011

Web service menurut W3.org mendefinisikan web service sebagai “sebuah software aplikasi yang dapat teridentifikasi oleh URI dan memiliki interface yang didefiniskan, dideskripsikan, dan dimengerti oleh XML dan juga mendukung interaksi langsung dengan software aplikasi yang lain dengan menggunakan message berbasis XML melalui protokol internet”.

Web service adalah sebuah sofware aplikasi yang tidak terpengaruh oleh platform, ia akan menyediakan method-method yang dapat diakses oleh network. Ia juga akan menggunakan XML untuk pertukaran data, khususnya pada dua entities bisnis yang berbeda.

Definisi lain : Web service  adalah sistem software yang dirancang untuk mendukung interopabilitas mesin-ke-mesin yang dapat berinteraksi melalui jaringan.  Web service memiliki antarmuka yang dijelaskan dalam format mesin-processable (khusus WSDL). Sistem lain berinteraksi dengan  Web service dalam cara ditentukan oleh deskripsi dengan menggunakan pesan SOAP, biasanya disampaikan menggunakan HTTP dengan serialisasi XML dalam hubungannya dengan Web lainnya yang terkait standar.

Dalam pengertian yang sederhana , XML Web Services dapat di definisikan sebagai aplikasi yang diakses oleh aplikasi yang lain. Mungkin orang berpendapat itu semacam web site, tetapi itu bukan demikian. Ada perbedaan – perbedaan yang membedakan dengan web site.

Perbedaan tersebut dapat dilihat dibawah ini :

WEB SITE

  1. Memiliki web interface
  2. Dibuat untuk ber interaksi langsung dengan user
  3. Dibuat untuk bekerja pada web browser.

WEB SERVICES

  1. Tidak memiliki interface yang bagus
  2. Dibuat untuk ber interaksi langsung dengan applikasi yang lain baik beda OS / Konsep sekalipun.
  3. Dibuat untuk bekerja pada semua tipe client applikasi / perangkat device

Beberapa karakteristik dari web service adalah:

  • Message-based
  • Standards-based
  • Programming language independent
  • Platform-neutral

Beberapa key standard didalam web service adalah: XML, SOAP, WSDL and UDDI.

SOAP (Simple Object Access Protocol) adalah sebuah XML-based mark-up language untuk pergantian pesan diantara aplikasi-aplikasi. SOAP berguna seperti sebuah amplop yang digunakan untuk pertukaran data object didalam network. SOAP mendefinisikan empat aspek didalam komunikasi: Message envelope, Encoding, RPC call convention, dan bagaimana menyatukan sebuah message didalam protokol transport.

Sebuah SOAP message terdiri dari SOAP Envelop dan bisa terdiri dari attachments atau tidak memiliki attachment. SOAP envelop tersusun dari SOAP header dan SOAP body, sedangkan SOAP attachment membolehkan non-XML data untuk dimasukkan kedalam SOAP message, di-encoded, dan diletakkan kedalam SOAP message dengan menggunakan MIME-multipart.

WSDL (Web Services Description Language) adalah sebuah XML-based language untuk mendeskripsikan XML. WSDL menyediakan service atau layanan yang mendeskripsikan service request dengan menggunakan protokol-protokol yang berbeda dan juga encoding. WSDL memfasilitasi komunikasi antar aplikasi. WSDL akan mendeskripsikan apa yang akan dilakukan oleh web service, bagaimana menemukannya dan bagaimana untuk mengoperasikannya.
Spesifikasi WSDL mendefinisikan tujuh tipe element:

  1. Types – element untuk mendefinisikan tipe data. Mereka akan mendefinisikan tipe data (seperti string atau integer) dari element didalam sebuah message.
  2. Message – abstract, pendefinisian tipe data yang akan dikomunikasikan.
  3. Operation – sebuah deskripsi abstract dari sebuah action yang didukung oleh service.
  4. Port Type – sebuah koleksi abstract dari operations yang didukung oleh lebih dari satu endpoints.
  5. Binding – mendefinisikan penyatuan dari tipe port (koleksi dari operasioperasi) menjadi sebuah protokol transport dan data format (ex. SOAP 1.1 pada HTTP). Ini adalah sebuah protokol konkret dan sebuah spesifikasi data format didalam tipe port tertentu.
  6. Port – mendefinisikan sebuah komunikasi endpoint sebagai kombinasi dari binding dan alamat network. Bagi protokol HTTP,  sebuah bentuk dari URL sedangkan bagi protokol SMTP, ini adalah sebuah form dari email address.
  7. Service – satu set port yang terkorelasi atau suatu endpoints.

WSDL mendefinisikan service sebagai sebuah koleksi dari endpoints network. Sebuah definisi abstrak dari endpoints dan messages adalah ia bersifat terpisah dari pembangunan network atau penyatuan data format. Pembagian ini menyebabkan penggunaan kembali abstract description dari data yang akan dipertukarkan (message exchange) dan abstract collection dari operasi (ports) Protokol konkret dan spesfikasi data format bagi tipe port tertentu menentukan binding yang dapat digunakan kembali(reusable). Sebuah port adalah sebuah network address yang dikombinasikan reusable binding; sebuah service adalah koleksi dari port-port.

Sedangkan UDDI (Universal Description, Discovery and Integration) adalah sebuah service registry bagi pengalokasian web service. UDDI mengkombinasikan SOAP dan WSDL untuk pembentukan sebuah registry API bagi pendaftaran dan pengenalan service. Ia menyediakan sebuah area umum dimana sebuah organisasi dapat mengiklankan keberadaan mereka dan service yang diberikan (web service).

Semantik pada Web service adalah harapan bersama tentang perilaku layanan, khususnya dalam menanggapi pesan yang dikirim ke tujuan. Akibatnya, ini adalah “kontrak” antara entitas pemohon dan badan penyedia tentang tujuan dan konsekuensi dari interaksi. Meskipun kontrak ini merupakan keseluruhan perjanjian antara entitas penanya dan entitas penyedia tentang bagaimana dan mengapa masing-masing agen akan berinteraksi, itu belum tentu tertulis atau eksplisit dinegosiasikan. Ini mungkin eksplisit atau implisit, lisan atau tertulis, mesin processable atau manusia berorientasi, dan mungkin suatu perjanjian hukum atau kesepakatan informal (non-hukum).

Ada banyak cara bahwa entitas penanya mungkin terlibat dan menggunakan Web service. Secara umum, langkah-langkah yang luas berikut yang diperlukan, seperti yang diilustrasikan pada Gambar 1.  (1) pemohon dan penyedia entitas menjadi dikenal satu sama lain (atau setidaknya satu menjadi tahu untuk yang lain); (2) peminta dan penyedia entitas entah bagaimana setuju pada deskripsi layanan dan semantik yang akan mengatur interaksi antara pemohon dan agen penyedia; (3) deskripsi layanan dan semantik direalisasikan oleh pemohon dan agen penyedia, dan (4) pemohon dan agen penyedia bertukar pesan, sehingga melakukan beberapa tugas atas nama pemohon dan badan penyedia. (Ie, pertukaran pesan dengan agen penyedia merupakan wujud nyata dari berinteraksi dengan layanan Web penyedia entitas.)

Gambar 1. Proses Umum Web Service

Arsitektur Web service melibatkan teknologi berlapis banyak dan saling terkait. Ada banyak cara untuk memvisualisasikan teknologi ini, seperti halnya ada banyak cara untuk membangun dan menggunakan Web service. Gambar 2 di bawah ini memberikan sebuah ilustrasi dari beberapa keluarga teknologi.

Gambar 2. Arsitektur Web Service

Kapan Kita Gunakan Web Services ?
Web Services itu digunakan saat kita akan mentransformasi sebuat bisnis logik / sebuah class dan object yang terpisah dalam 1 ruang lingkup yang menjadi satu, sehingga tingkat keamanan dan security dapat di tangani dengan baik. Selain itu Web Service juga lebih mudah dalam process deploymentnya, karena tidak memerlukan registrasi khusus ke dalam sistem operasi. Web Service cukup diupload ke Web Server dan siap diakses oleh pihak-pihak yang telah diberikan otorisasi. Web Service berjalan di port 80 yang merupakan protokol standar HTTP, dengan demikian mengurangi resiko terblokir oleh firewall. Kendala arsitektur COM/DCOM adalah memerlukan konfigurasi khusus di sisi firewall, dan  ini tidak perlu dilakukan untuk mengakses Web Service.

Beberapa vendor luar negeri mulai berkolaborasi satu sama lain dengan konsep web services , diantaranya : IBM, Microsoft , SUN , ORACLE Diantaranya contoh web services yang sudah jadi dan dipakai adalah web services keluaran Microsoft ( Microsoft Passport ) – web services untuk user name dan password yang sudah dipasang di web site  Microsoft dan HOTMAIL.

Mau contoh aplikasi sederhana web service, tunggu artikel berikutnya..!

Sumber : ilmukomputer.com, w3.org dan berbagai sumber.

SPK dan Contoh Program

Saturday, July 9th, 2011

Sistem Penunjang Pengambilan Keputusan didefinisikan sebagai interaktif berbasis komputer yang membantu pengambilan suatu keputusan memanfaatkan data dan model untuk menyelesaikan masalah yang tidak terstruktur, Scoot-Morton (Turban, 2000).

Sistem Pendukung Keputusan yang dikemukakan oleh Raymond Mclood. Jr dalam buku Sistem Informasi Manajemen (McLeod, 2001) menekankan bahwa Sistem Pendukung Keputusan adalah suatu sistem informasi yang ditujukan untuk membantu manajemen dalam memecahkan masalah yang dihadapinya. Definisi selengkapnya adalah sistem penghasil informasi spesifik yang ditujukan untuk memecahkan suatu masalah tertentu  yang harus dipecahkan oleh menejer ada berbagai tingkatan. Sedangkan menurut Litlle (McLeod, 2001) mengemukakan bahwa sistem pendukung  keputusan adalah suatu sistem informasi berbasis komputer yang menghasilkan berbagai alternatif keputusan untuk membantu manajemen dalam menangani berbagai permasalahan yang terstruktur ataupun tidak terstruktur dengan menggunakan data atau model.

Sebagaimana diketahui bahwa salah satu tugas utama manajemen adalah mempertahankan (existensi) dan menghasilkan kinerja (performance) organisasi yang dikelolanya. Untuk  itulah manajemen harus mengambil keputusan mengenai langkah-langkah yang akan diambilnya, baik pada tingkatan strategi, taktik maupun operasional.

Keputusan-keputusan dibuat untuk memecahkan masalah. Dalam memecahkan suatu masalah, pemecahan masalah mungkin membuat banyak keputusan. Keputusan merupakan rangkaian tindakan yang perlu diikuti dalam memecahkan masalah untuk menghindari dan mengurangi dampak negatif atau untuk memanfaatkan kesempatan.

Agar kualitas keputusan yang diambil lebih baik maka diperlukan sistem pendukung keputusan yaitu yang berbasis komputer interaktif, yang mambantu pembuat keputusan memanfaatkan data dan model untuk menyelesaikan permasalahan yang tak terstruktur (Garry dan Morton,1971).

Jenis-Jenis Keputusan

Jenis–jenis keputusan menurut Simon dibedakan menjadi dua macam yaitu keputusan terprogram dan keputusan tidak terprogram dalam buku Sistem Informasi Manajemen (McLeod, 2001).

a. Keputusan Terprogram

Keputusan–keputusan yang bersifat berulang dan rutin, sedemikian hingga suatu prosedur pasti telah dibuat untuk menanganinya sehingga keputusan tersebut tidak perlu diperlakukan sebagai sesuatu yang baru tiap kali terjadi.

b.   Keputusan Tak Terprogram

Keputusan–keputusan yang berkaitan dengan berbagai persoalan baru, tidak terstruktur dan tidak konsisten. Tidak ada metode yang pasti untuk menangani masalah ini karena belum  pernah ada sebelumnya, atau karena sifat dan struktur persisnya tidak terlihat atau rumit.

Proses Pengambilan Keputusan.

Untuk memahami dengan lebih baik mengenai permodelan, dapat mengikuti proses pengambilan keputusan yang melibatkan tiga hal tahap utama : tahap intelegensi (intelligent phase), tahap perancangan (design phase), dan tahap pilihan (choice phase). Tahap keempat yaitu implementasi (implementation) ditambahkan kemudian. Sebuah gambaran konseptual mengenai proses pembuatan keputusan ditunjukkan pada gambar 1. Ada aliran aktifitas yang  berkesinambungan dari tahap intelegensi ke tahap perancangan dan tahap perancangan ke tahap pilihan (garis tebal), tetapi pada beberapa tahap mungkin menjadi arus balik ke tahap sebelumnya.

Subsistem–subsistem sistem pendukung keputusan terdiri dari 4 yaitu subsistem manajemen data, subsistem manajemen model, subsistem manajemen pengetahuan dan subsistem antar muka pengguna. Seperti pada gambar dibawah  (Turban, 2000).

Gambar 1. Skema SPK

Dalam pembuatan aplikasi sistem pendukung keputusan umumnya sistem dapat hasil keputusan yang dapat mengeluarkan output beberapa alternatif lain yang dapat direkomendasikan. Adapun contoh bentuk aplikasi sistem pendukung keputusan pada wisata kuliner dibawah menunjukkan mengeluarkan ketupusan berdasarkan rangking dan memiliki alternatif pilihan lain yang dapat direkomendasikan oleh manajer/user.

Contoh Program SPK

Contoh data inputan dengan mengisi data kriteria dan bobot sesuai kebutuhan pemakai. Kriteria diantaranya adalah jenis makanan, waktu buka, lokasi kuliner, budget, fasilitas, dan khas makanan. Peta di ambil dari google eart untuk memvisualisasi data ruang geografi agar lebih baik dengan bentuk yang lebih nyata. Sedangkan bobot dapat diatur oleh pemakai sistem dan tidak dilakukan pemobobotan dalam koding. Perhatikan gambar 2 dibawah;

Gambar 2. Proses SPK Kuliner

Pada gambar 2 di atas suatu hasil keputusan sistem berdasarkan data inputan yang didapatkan untuk pencarian adalah Pondok Cabe jenis makanan Ayam Goreng dengan total skor persentase 98% dari total keseluruhan resto yang didapatkan yaitu 96 resto yang memiliki pendekatan data yang dicari baik jenis makanan, waktu buka, khas makanan, budget, suasana, fasilitas atau data lokasi.

Adapun resto yang memiliki total skor terkecil adalah Jimbaran Resto dengan total skor 40% yang memiliki perbedaan Jenis makanan, khas makanan, harga yang sangat jauh dari budget, dan memiliki persamaan suasana indoor dan memungkin jarak masih terjangkau.

Sistem ini dibuat dengan metode rule of thumb untuk mendukung keputusan serta google earth untuk visualisasi geografinya.

Untuk lebih jelas dapat mengemail saya..semoga bermanfaat terimakasih.

danifn[at]mail.ugm.ac.id

Kriptografi Menggunakan Metode Affine

Thursday, July 7th, 2011

Kriptonologi

Kriptografi merupakan suatu ilmu seni dengan filosofinya the art of war, dimana waktu itu pernah digunakan untuk mengirim pesan rahasia pada jaman romawi pada era raja Caesar. Tujuannya agar pembajak surat rahasia tidak dapat membaca pesannya secara langsung oleh orang lain jika belum dideskripsikan dengan metode tertentu. Kritografi adalah studi mengenai ilmu dan seni dalam rangka menjaga keamanan data atau informasi yang dikirim dan juga merupakan ilmu untuk bagaimana memecahkan pesan yang terenkripsi (tersamar).

Dalam kriptografi terdapat dua konsep utama yakni enkripsi dan dekripsi. Enkripsi adalah proses dimana informasi/data yang hendak dikirim diubah menjadi bentuk yang hampir tidak dikenali sebagai informasi awalnya dengan menggunakan algoritma tertentu. Dekripsi adalah kebalikan dari enkripsi yaitu mengubah kembali bentuk tersamar tersebut menjadi informasi awal. Ada beberapa contoh macam-macam metode kriptografi untuk membuat pesan rahasia antara lain: Caesar, Affine, Monoalphabetic, Polyalphabetic, Vigenere, Beaufort, Playfair, Transposisi, MD5, DES, RSA, DSA, ElGamal, dan SHA. Metode pertama kriptografi adalah Caesar, yang mana metode mengikuti pola pesan rahasia yang dikirim oleh raja Caesar pada jaman romawi, kini banyak model untuk dapat diterapkan dalam kriptografi, diantaranya adalah affineAffine sudah cukup baik untuk mengirim pesan rahasia berupa pesan teks rahasia.

Pesan (message) adalah data atau informasi yang dapat dibaca dan dimengerti maknanya. Nama lain untuk pesan adalah plainteks (plaintext) atau teks jelas (cleartext). Maka diperlukan membuat aplikasi pesan rahasia berupa teks menggunakan metode Affine yang merupakan perluasan dari caesar yang mengalihkan plainteks dengan sebuah nilai dan menambahkannya dengan sebuah pergeseran.

Di dalam kriptografi sering ditemukan berbagai istilah atau terminologi, beberapa istilah yang penting untuk diketahui diantaranya adalah (Munir, 2006):

  • Pesan (message) adalah data atau informasi yang dapat dibaca atau dimengerti maknanya. Nama lainnya untuk pesan adalah plainteks (plaintext) atau teks jelas (clear text).
  • Pengirim (sender) adalah entitas yang melakukan pengiriman pesan kepada entitas lainnya.
  • Kunci (cipher) adalah aturan atau fungsi matematika yang digunakan untuk melakukan proses enkripsi dan dekripsi pada plaintext dan ciphertext.
  • Enkripsi adalah mekanisme yang dilakukan untuk merubah plaintext menjadi ciphertext.
  • Dekripsi adalah mekanisme yang dilakukan untuk merubah ciphertext menjadi plaintext.
  • Penerima (recipient) adalah entitas yang menerima pesan dari pengirim/entitas yang berhak atas pesan yang dikirim.

Pengubahan plainteks ke cipherteks agar suatu pesan rahasia tidak mudah dibaca.

Gambar 1. Proses Enskripsi Teks

Gambar 1. memperlihatkan contoh dua buah plainteks serta cipherteks berkoresponden. Yang mana suatu proses pesan yang dikembalikan, cipherteks dapat ditransformasikan kembali ke plainteks semula, (Munir, 2006). Kriptografi itu sendiri terdiri dari dua proses utama yakni proses enkripsi dan proses dekripsi. Seperti yang telah dijelaskan di atas, proses enkripsi mengubah plaintext menjadi ciphertext (dengan menggunakan kunci tertentu) sehingga isi informasi pada pesan tersebut sukar dimengerti. Adapun gambar diagram proses plainteks ke enkripsi dan cipterteks ke deskipsi dapat dilihat pada gambar 2.

Gambar 2. Diagram prosesenkripsi dan dekripsi

Peranan kunci sangatlah penting dalam proses enkripsi dan dekripsi (disamping pula algoritma yang digunakan) sehingga kerahasiaannya sangatlah penting, apabila kerahasiaannya terbongkar, maka isi dari pesan dapat diketahui. Secara matematis, proses enkripsi merupakan pengoperasian fungsi E (enkripsi) menggunakan e (kunci enkripsi) pada M (plaintext) sehingga dihasilkan C (ciphertext), notasinya :

Ee(M) – C (1)

Sedangkan untuk proses dekripsi, merupakan pengoperasian fungsi D (desciption) menggunakan d (kunci dekripsi) pada C (ciphertext) sehingga dihasilkan M (plaintext), notasinya :

Dd(C) = M(2)

Sehingga dari dua hubungan diatas berlaku :

Dd(Ee(M)) = M(3)

Affine Cipher

Affine cipher pada metode affine adalah perluasan dari metode Caesar Cipher, yang mengalihkan plainteks dengan sebuah nilai dan menambahkannya dengan sebuah pergeseran P menghasilkan cipherteks C dinyatakan dengan fungsi kongruen:

C ≡ m P + b (mod n)(4)

Yang mana n adalah ukuran alphabet, m adalah bilangan bulat yang harus relatif prima dengan n (jika tidak relatif prima, maka dekripsi tidak bisa dilakukan) dan b adalah jumlah pergeseran (Caesar cipher adalah khusus dari affine cipher dengan m=1). Untuk melakukan deskripsi, persamaan (4) herus dipecahkan untuk memperoleh P. Solusi kekongruenan tersebut hanya ada jika inver m (mod n), dinyatakan dengan m -1. Jikam -1 ada maka dekripsi dilakukan dengan persamaan sebagai berikut:

P ≡ m -1(C – b ) (mod n)(5)

Gambaran Umum Sistem

Hasil penelitian yang didapatkan adalah dapat diterapkan ilmu kriptografi dengan metode Affineuntuk menghasilkan pesan teks rahasia. Teks asli dapat di ubah menjadi teks yang disamarkan dengan suatu metode Affine, dan teks yang telah di enksripsi dapat dikembalikan kembali menjadi teks asli (plainteks).

Tabel 1. Penginisialan Alfabet Huruf A-Z menjadi Angka 0 – 26

Huruf

A

B

C

X

Y

Z

Angka

0

1

2

23

24

25

Pengujian Plainteks

Pengujian data plainteks digunakan agar teks asli dapat di enskripsi menjadi cipherteks. Contoh data plainteks untuk pengujian pertama dibutuhkan adalah sebagai berikut:

Tabel 2. Teks Inputan Plainteks

D

A

N

I

D

I

T

A

3

0

13

8

3

8

19

0

Plainteks:

D A N I D I T A

Ekivalen:

3 0 13 8 3 8 19 0

N = 26

K = Relatif Prima (1,3,5,7,9,11,15,17,19,21,23,25)

Kunci pertama = 5

Kunci kedua= 7

Gambar 3. Proses Enskripsi

affine cipher dengan mengambil m = 5 (karena 5 relatif prima dengan 26) dan b= 7. Karena alphabet yang digunakan 26 huruf, maka n = 26. Enkripsi plainteks dihitung dengan kekongruenan:

C≡5P + 7 (mod 26)(6)

Perhitungannya adalah sebagai berikut:

P1= 3 –> c1 ≡ 5.3 + 7≡ 22 (mod 26) ≡ 22 = W

P2= 0–> c2 ≡ 5.0 + 7≡ 7(mod 26) ≡ 7= H

P3= 13 –> c3 ≡ 5.13 + 7 ≡ 72 (mod 26) ≡ 20 = U

P4= 8–> c4 ≡ 5.8 + 7≡ 47 (mod 26) ≡ 21 = V

P5= 3–> c5 ≡ 5.3 + 7≡ 22 (mod 26) ≡ 22 = W

P6= 8–> c6 ≡ 5.8 + 7≡ 47 (mod 26) ≡ 21 = V

P7= 19 –> c7 ≡ 5.19 + 7 ≡ 102 (mod 26) ≡ 24 = Y

P8= 0–> c8 ≡ 5.0 + 7≡ 7(mod 26) ≡ 7= H

Maka menghasilkan Cipherteks sebagai berikut : W H U V W V Y H

Pengujian Cipherteks

Pengujian data cipherteks digunakan teks yang telah di enskripsi dapat dideskripsikan kembali menjadi plainteks. Contoh datacipherteks yang telah di enskripsi untuk pengujiansebelumnya adalah, sebagai berikut:

Tabel 2. Teks Inputan Plainteks

W

H

U

V

W

V

Y

H

22

7

20

21

22

21

24

7

Cipherteks:

W H U V W V Y H

Ekivalen:

22 7 20 21 22 21 24 7

N = 26

K = RelatifPrima (1,3,5,7,9,11,15,17,19,21,23,25)

Kunci pertama = 5

Kunci kedua= 7

Gambar 4. Proses Deskripsi

Untuk mengembalikan teks yang telah dienskripsi menjadi pesan rahasia dapat dilakukan pendekripsian, pertama-tama dapat dihitung 5-1 (mod 26), yang dapat dihitung dengan memecahkan kekongruenan lanjar.

5x ≡ 1 (mod 26)(7)

Untuk deskripsi dengan hasil 1 maka solusinya adalah x =21(mod 26) dikarenakan 5.21 = 105 mod 26 menghasilkan = 1.

P ≡ 21 (C – 7) (mod 26)(8)

P1=22–> c1 ≡ 21.(22 – 7) ≡ 315(mod 26) ≡ 3 = D

P2= 7 –> c2 ≡ 21.(7 – 7)≡ 0 (mod 26) ≡ 0 = A

P3=20 –> c3 ≡ 21.(20 – 7) ≡ 273(mod 26)≡ 13 = N

P4=21–> c4 ≡ 21.(21 – 7)≡ 294(mod 26) ≡ 8 = I

P5=22–> c5 ≡ 21.(22 – 7) ≡ 315(mod 26)≡ 3 = D

P6=21–> c6 ≡ 21.(21 – 7) ≡ 294 (mod 26) ≡ 8 = I

P7=24–> c7 ≡ 21.(24 – 7) ≡357(mod 26) ≡ 19 = T

P8=7–> c8 ≡ 21.(7 – 7)≡ 0 (mod 26) ≡ 0 = A

Maka menghasilkan Plainteks sebagai berikut : D A N I D I T A

Semoga bermanfaat…Silahkan email apabila perlu diskusi ke danifn[at]mail.ugm.ac.id


Gambar 1. Proses Enskripsi Teks

Algoritma Knapsack-Kriptografi

Monday, July 4th, 2011

Algoritma Knapsack

Algoritma ini didasarkan pada persoalan 1/0 Knapsack Problem yang berbunyi:

 Diberikan bobot knapsack adalah M. Diketahui n buah objek yang masing-masing bobotnya adalah w1, w2, …, wn. Tentukan nilai bi sedemikian sehingga

M = b1w1 + b2w2 + … + bnwn (1)

yang dalam hal ini, bi bernilai 0 atau 1. Jika bi = 1, berarti objek i dimasukkan ke dalam knapsack, sebaliknya jika bi = 0, objek i tidak dimasukkan.

Dalam teori algoritma, persoalan knapsack termasuk ke dalam kelompok NP-complete. Persoalan yang termasuk NP-complete tidak dapat dipecahkan dalam orde waktu polinomial.

Ide dasar dari algoritma knapsack adalah mengkodekan pesan sebagai rangkaian solusi dari dari persoalan knapsack. Setiap bobot wi di dalam persoalan knapsack merupakan kunci rahasia, sedangkan bit-bit plainteks menyatakan bi.

Contoh 1:  Misalkan n = 6 dan w1 = 1, w2 = 5, w3 = 6,

w4 = 11, w5 = 14, dan w6 = 20.

Plainteks: 111001010110000000011000

Plainteks dibagi menjadi blok yang panjangnya n, kemudian setiap bit di dalam blok dikalikan dengan wi yang berkorepsonden sesuai dengan persamaan (1):

Blok plainteks ke-1     : 111001

Knapsack : 1, 5, 6, 11, 14, 20

Kriptogram                   : (1 ´ 1) + (1 ´ 5) + (1 ´ 6) + (1 ´ 20)

= 32

Blok plainteks ke-2     : 010110

Knapsack : 1, 5, 6, 11, 14, 20

Kriptogram                   : (1 ´ 5) + (1 ´ 11) + (1 ´ 14) = 30

Blok plainteks ke-3     : 000000

Knapsack : 1, 5, 6, 11, 14, 20

Kriptogram                   : 0

Blok plainteks ke-4     : 011000

Knapsack : 1, 5, 6, 11, 14, 20

Kriptogram                   : (1 ´ 5) + (1 ´ 6) = 11

Jadi, cipherteks yang dihasilkan:  32  30  0  11

Sayangnya, algoritma knapsack sederhana di atas hanya dapat digunakan untuk enkripsi, tetapi tidak dirancang untuk dekripsi. Misalnya, jika diberikan kriptogram = 32, maka tentukan b1, b2, …, b6 sedemikian sehingga

32= b1 + 5b2 + 6b3 + 11b4 + 14b5 + 20b6 (2)

Solusi persamaan (2) ini tidak dapat dipecahkan dalam orde waktu polinomial dengan semakin besarnya n (dengan catatan barisan bobot tidak dalam urutan menaik). Namun, hal inilah yang dijadikan sebagai kekuatan  algoritma knapsack.

Superincreasing Knapsack

  • Superincreasing knapsack adalah persoalan knapsack yang dapat dipecahkan dalam orde O(n) (jadi, polinomial). Ini adalah persoalan knapsack yang mudah sehingga tidak disukai untuk dijadikan sebagai algoritma kriptografi yang kuat.
  • Jika senarai bobot disebut barisan superincreasing, maka kita dapat membentuk superincreasing knapsack. Barisan superincreasing adalah suatu barisan di mana setiap nilai  di dalam barisan lebih besar daripada jumlah semua nilai  sebelumnya. Misalnya {1, 3, 6, 13, 27, 52} adalah barisan superincreasing, tetapi {1, 3, 4, 9, 15, 25} bukan.
  • Solusi dari superincreasing knapsack (yaitu b1, b2, …, bn) mudah dicari sebagai berikut (berarti sama dengan mendekripsikan cipherteks mnejadi plainteks semula):
  • Jumlahkan semua bobot di dalam barisan.
    1. Bandingkan bobot total dengan bobot terbesar di dalam barisan. Jika bobot terbesar lebih kecil atau sama dengan bobot total, maka ia dimasukkan ke dalam knapsack, jika tidak, maka ia tidak dimasukkan.
    2. Kurangi bobot total dengan bobot yang telah dimasukkan, kemudian bandingkan bobot total sekarang dengan bobot terbesar selanjutnya. Demikian seterusnya sampai seluruh bobot di dalam barisan selesai dibandingkan.
    3. Jika bobot total menjadi nol, maka terdapat solusi persoalan superincreasing knapsack , tetapi jika tidak nol, maka tidak ada solusinya.

Contoh 2: Misalkan bobot-bobot yang membentuk barisan superincreasing adalah {2, 3, 6, 13, 27, 52}, dan diketahui bobot knapsack (M) = 70. Kita akan mencari b1, b2, …, b6 sedemikian sehingga

70= 2b1 + 3b2 + 6b3 + 13b4 + 27b5 + 52b6

Caranya sebagai berikut:

  1. Bandingkan 70 dengan bobot terbesar, yaitu 52. Karena 52 £ 70, maka 52 dimasukkan ke dalam knapsack.
  2. Bobot total sekarang menjadi 70 – 52 = 18. Bandingkan 18 dengan bobot terbesar kedua, yaitu 27. Karena 27 > 18, maka 27 tidak dimasukkan ke dalam knapsack.
  3. Bandingkan 18 dengan bobot terbesar berikutnya, yaitu 13. Karena 13 £ 18, maka 13 dimasukkan ke dalam knapsack.
    Bobot total sekarang menjadi 18 – 13 = 5.
  4. Bandingkan 5 dengan bobot terbesar kedua, yaitu 6. Karena 6 > 5, maka 6 tidak dimasukkan ke dalam knapsack.
  5. Bandingkan 5 dengan bobot terbesar berikutnya, yaitu 3.  Karena 3 £ 5, maka 3 dimasukkan ke dalam knapsack.
  6. Bobot total sekarang menjadi 5 – 3 = 2.
  7. Bandingkan 2 dengan bobot terbesar berikutnya, yaitu 2. Karena 2 £ 2, maka 2 dimasukkan ke dalam knapsack.
  8. Bobot total sekarang menjadi 2 – 2 = 0.

Karena bobot total tersisa = 0, maka solusi persoalan superincreasing knapsack ditemukan. Barisan bobot yang dimasukkan ke dalam knapsack adalah  {2, 3, – , 13, – , 52}

sehingga

70 = (1 ´ 2) + (1 ´ 3) + (0 ´ 6) + (1 ´ 13) + (0 ´ 27) + (1 ´ 52)

Dengan kata lain, plainteks dari kriptogram 70 adalah 110101.

Algoritma Knapsack Kunci-Publik

  • Algoritma superincreasing knapsack adalah algoritma yang lemah, karena cipherteks dapat didekripsi menjadi plainteksnya secara mudah dalam waktu lanjar.
  • Algoritma non-superincreasing knapsack atau normal knapsack adalah kelompok algoritma knapsack yang sulit (dari segi komputasi) karena membutuhkan waktu dalam orde eksponensial untuk memecahkannya.
  • Namun, superincreasing knapsack dapat dimodifikasi menjadi non-superincreasing knapsack dengan menggunakan kunci publik (untuk enkripsi) dan kunci rahasia (untuk dekripsi). Kunci publik merupakan barisan non-superincreasing sedangkan kunci rahasia tetap merupakan barisan superincreasing. Modifikasi ini ditemukan oleh Martin Hellman dan Ralph Merkle.
  • Cara membuat kunci publik dan kunci rahasia:
  1. Tentukan barisan superincreasing.
    1. Kalikan setiap elemen di dalam barisan tersebut dengan n modulo m. Modulus m seharusnya angka yang lebih besar daripada jumlah semua elemen di dalam barisan, sedangkan pengali n seharusnya tidak mempunyai faktor persekutuan dengan m.
    2. Hasil perkalian akan menjadi kunci publik sedangkan barisan superincreasing semula menjadi kunci rahasia.

 Contoh 3: Misalkan barisan superincreasing adalah {2, 3, 6, 13, 27, 52), m = 105, dan n = 31.

Barisan non-superincreasing (atau normal) knapsack dihitung sbb:

2 × 31 mod 105 = 62

3 × 31 mod 105 = 93

6 × 31 mod 105 = 81

13 × 31 mod 105 = 88

27 × 31 mod 105 = 102

52 × 31 mod 105 = 37

Jadi, kunci publik adalah {62, 93, 81, 88, 102, 37}, sedangkan kunci rahasia adalah {2, 3, 6, 13, 27, 52}.

Enkripsi

  • Enkripsi dilakukan dengan cara yang sama seperti algoritma knapsack sebelumnya.
  • Mula-mula plainteks dipecah menjadi blok bit yang panjangnya sama dengan kardinalitas barisan kunci publik.
  • Kalikan setiap bit di dalam blok dengan elemen yang berkoresponden di dalam kunci publik.

Contoh 4:  Misalkan

Plainteks: 011000110101101110

dan kunci publik yang digunakan seperti pada Contoh 3.

Plainteks dibagi menjadi blok yang panjangnya 6, kemudian setiap bit di dalam blok dikalikan dengan elemen yang berkorepsonden di dalam kunci publik:

Blok plainteks ke-1     : 011000

Kunci publik                : 62, 93, 81, 88, 102, 37

Kriptogram                   : (1 ´ 93) + (1 ´ 81)  = 174

Blok plainteks ke-2     : 110101

Kunci publik                : 62, 93, 81, 88, 102, 37

Kriptogram                   : (1 ´ 62) + (1 ´ 93) + (1 ´ 88) +

(1 ´ 37)  = 280

Blok plainteks ke-3     : 101110

Kunci publik                : 62, 93, 81, 88, 102, 37

Kriptogram                   : (1 ´ 62) + (1 ´ 81) + (1 ´ 88) +

(1 ´ 102)  = 333

Jadi, cipherteks yang dihasilkan : 174, 280, 333

Dekripsi

  • Dekripsi dilakukan dengan menggunakan kunci rahasia.
  • Mula-mula penerima pesan menghitung n–1 , yaitu balikan n modulo m, sedemikian sehingga n × n–1 º 1 (mod m).  Kekongruenan ini dapat dihitung dengan cara yang sederhana sebagai berikut (disamping dengan cara yang sudah pernah diberikan pada Teori Bilangan Bulat):

n × n–1 º 1 (mod m)

Û     n × n–1 = 1 + km

Û     n–1 = (1 + km)/n , k sembarang bilangan bulat

·       Kalikan setiap kriptogram dengan n–1 mod m, lalu nyatakan hasil kalinya sebagai penjumlahan elemen-elemen kunci rahasia  untuk memperoleh plainteks  dengan menggunakan algoritma pencarian solusi superincreasing knapsack.

Contoh 5:  Kita akan mendekripsikan cipherteks dari Contoh 4 dengan menggunakan kunci rahasia  {2, 3, 6, 13, 27, 52}. Di sini, n = 31 dan m = 105. Nilai n–1 diperoleh sbb:

n–1 = (1 + 105k)/31

Dengan mencoba k = 0, 1, 2, …, maka untuk k = 18 diperoleh n–1 bilangan bulat, yaitu

n–1 = (1 + 105 × 18)/31          = 61

Cipherteks dari Contoh 4 adalah 174, 280, 222. Plainteks yang berkoresponden diperoleh kembali sebagai berikut:

174 × 61 mod 105 = 9 = 3 + 6, berkoresponden dengan 011000

280 × 61 mod 105 = 70 = 2 + 3 + 13 + 52, berkoresponden dengan 011000

333 × 61 mod 105 = 48 = 2 + 6 + 13 + 27, berkoresponden dengan 101110

Jadi, plainteks yang dihasilkan kembali adalah:

011000 011000 101110

Implementasi Knapsack

  • Ukuran cipherteks yang dihasilkan lebih besar daripada plainteksnya, karena enkripsi dapat menghasilkan kriptogram yang nilai desimalnya lebih besar daripada nilai desimal blok plainteks yang dienkripsikan.
  • Untuk menambah kekuatan algoritma knapsack, kunci publik maupun kunci rahasia seharusnya paling sedikit 250 elemen, nilai setiap elemen antara 200 sampai 400 bit panjangnya, nilai modulus antara 100 sampai 200 bit.
  • Dengan nilai-nilai knapsack sepanjang itu, dibutuhkan 1046 tahun untuk menemukan kunci secara brute force, dengan asumsi satu juta percobaan setiap detik.

Keamanan Knapsack

  • Sayangnya, algoritma knapsack dinyatakan sudah tidak aman, karena knapsack dapat dipecahkan oleh pasangan  kriptografer  Shamir dan Zippel. Mereka merumuskan transformasi yang memungkinkan mereka merekonstruksi superincreasing knapsack dari normal knapsack.

Sumber : Rinaldi Munir/IF-ITB dan berbagai sumber