Kriptografi di Korea

Tahun lalu saya dan teman-teman di STEI mendapat kesempatan pelatihan cyber security ke Korea Selatan. Kami banyak mendapat pengalaman perkembangan cyber security di Korea. FYI, Korea Selatan adalah negara yang sangat maju dalam bidang keamanan informasi, termasuk bidang keamanan saiber. Hal ini bisa dimaklumi karena Korea Selatan memiliki musuh bebuyutan yang tidak pernah akur sampai sekarang, yaitu negara tetangga mereka sendiri, Korea Utara. Karena itu, rakyat dan Pemerintah Korea Selatan berusaha memproteksi dirinya dari berbagai usaha serangan saiber dari musuhnya itu, salah satunya melindungi data dan informasi rahasia mereka menggunakan kriptografi. Tulisan ini hanya akan membahas tentang kriptografi di Korea.

Pernah mendengar algoritma kriptografi bernama SEED? SEED adalah sebuah block cipher yang terkenal dari Korea. SEED dikembangkan oleh KISA (Korea Internet and Security Agency), yaitu sebuah badan yang menangani insiden terkait keamanan informasi atau CERT (Computer Emergency Response Team), dan sekarang perannya diperluas untuk menangani kebijakan dalam bidang Internet. SEED digunakan secara luas oleh industri di Korea, tetapi jarang ditemukan di luar Korea.

Di Korea kebijakan yang terkait penggunaan kriptografi sangat ketat. Mereka mempunyai aturan yang hirarkhi seperti yang tergambar pada diagram Venn di bawah ini.

InfoSecPolicy in Korea

Semua algoritma kriptografi yang akan diimplementasikan di dalam produk harus lulus uji program validasi algoritma kriptografi yang disebut CAVP (Cryptographic Algorithm Validation Program). Sekanjutnya, jika sudah lulus, maka modul yang menggunakan algoritma tersebut diuji dan divalidasi oleh K-CMVP (Korea Cryptographic Module Validation Program). Yang dimaksud dengan modul adalah perangkat lunak maupun perangkat keras yang memakai algoritma tersebut. K-CMVP sendiri pada awalnya dibentuk oleh NIST (National Institute of Standard and Technology) –sebuah lembaga standard dari Amerika– dan CSEC (Communications Security Establishment Canada), pada tahun 1995. Semua modul kriptografi yang digunakan oleh Pemerintah Korea untuk melindungi informasi rahasia melalui program validasi K-CMVP ini.

Setelah melewati uji validasi K-CMVP, maka semua fungsi keamanan dari produk IT (H/W maupun S/W) yang diimplentasikan di dalam produk security, dievaluasi oleh CC (Common Criteria). CC adalah standard internasional yang mengevaluasi dan mensertifikasi produk IT untuk memastikan apakah sudah diimplementasikan dengan benar dan sangkil (efektif). Evaluasi yang dilakukan adalah CC meliputi pemeriksaan apakah seorang pengembang (1) mengikuti semua proses rekayasa perangkat lunak, dan (2) membuat produk yang aman dari serangan.

Pengembang CC di negara-negara lain dalpat dilihat pada tabel di bawah ini:

CC

K-ISMS (Korea Information Security Management System), sebagai lingkungan yang menggunakan produk IT Security mendefinisikan bagaimana mengelola keamanan informasi dalam berbagai organisasi, baik organisasi berlaba atau nirlaba, swasta atau Pemerintah, kecil atau besar. K-ISMS mencakaup setiap aspek (fisik maupun logik) dari keamanan informasi, seperti peralatan, kebijakan manajemen, sumbersaya manusia, dan aspek hukum.

Semua yang saya ceritakan di atas menggambarkan betapa Korea sangat menaruh perhatian secara khusus terhadap bidang kriptografi di sana dan keamanan informasi pada umumnya. Mudaha-mudahan perkembangan kriptografi di Indonesia pun dapat mengikyi jejak Korea yang sudah sangat maju dalam bidang tersebut.

(Keterangan: semua gambar diambil dari presentasi dosen Korea University)

Tinggalkan komentar

Filed under Rupa-rupa

Proteksi Perangkat Lunak dengan Kriptografi dan Perangkat Keras

Wuaahh… sudah lama saya absen menulis di blog ini. Hari ini saya mulai lagi. Sebenarnya ini sudah agak telat, karena wisuda sarjana ITB sudah selesai. Kenapa wisuda? Karena yang saya bahas kali ini adalah Tugas Akhir mahasiswa saya di Informatika ITB.

Mahasiswa saya bernama Samudra Harapan Bekti, Informatika ITB Angkatan 2008, mengerjakan topik Tugas Akhir yang sangat menarik dan membuat saya angkat topi. Saya beri dia nilai A++ karena idenya orisinil dan hasilnya sangat bermanfaat buat industri perangkat lunak.

Dia mengangkat topik proteksi perangkat lunak dari penggandaan secara ilegal. Selama ini penggandaan perangkat lunak cukup sulit dicegah. Hal ini karena sifat data digital yang mudah digandakan. Memang sudah banyak dikembangkan orang proteksi berbasis perangkat lunak juga, tetapi tetap saja tidak berhasil menanggulangi masalah pembajakan.

Berangkat dari hobi dan ketertarikannya dengan elektronika sejak SMA, dia membuat sistem proteksi perangkat lunak berbasis perangkat keras. Idenya adalah perangkat keras sulit digandakan, dan inilah yang menjadi dasar sistem proteksinya itu.

Dia merancang sendiri pengendali mikro (microcontroller) untuk menyimpan kunci lisensi perangkat lunak. Perangkat lunak yang diproteksi dienkripsi terlebih dahulu dengan kunci tersebut. Perangkat lunak terenkripsi (misal disimpan di dalam CD atau DVD) didistribusikan (atau dijual) kepada konsumen bersama dengan pengendali mikro tadi. Sebuah antarmuka USB digunakan untuk menghubungkan perangkat keras dengan komputer pengguna. Di dalam CD/DVD terdapat perangkat lunak yang dienkripsi dan sebuah program loader yang diaktifkan pada waktu aktivasi produk pertama kali.

Ilustrasi: Contoh sebuah USB microcontroller (Sumber: https://www.olimex.com/dev/mod-mma7260q.html)

USB Microcontroller yang dirancang Samudra Harapan Bekti (Sumber: laman fesbuk ybs di http://www.facebook.com/photo.php?fbid=4008407243732&set=a.4008358162505.2163560.1087712270&type=3&theater)

Dikutip dari laporan TA Samudera Harapan Bekti, pengendali mikro adalah sistem komputer yang terintegrasi di dalam sebuah chip. Chip tersebut disusun oleh prosesor, memori, dan perangkat masukan/keluaran yang dapat diprogram untuk menjalankan fungsi tertentu. Pengendali mikro dapat dimanfaatkan sebagai bagian dari sistem proteksi perangkat lunak untuk menggantikan peran server aktivasi sehingga proses aktivasi perangkat lunak dapat dilakukan di luar jaringan (offline).

Saya tidak akan membahas mengenai rancangan pengendali mikronya, karena saya tidak punya keahlian disitu. Yang ingin saya bahas adalah penggunaan kriptografi di dalam sistem proteksi tersebut.

Perangkat lunak yang diproteksi dienkripsi dengan sebuah algoritma kriptografi (dia memakai algoritma AES) dan kunci rahasia. Kunci rahasia ditanam di dalam USB. Kunci akan dikirim oleh program loader ke komputer pengguna ketika pengguna melakukan aktivasi produk. Kunci dipakai untuk mendekripsi perangkat lunak yang telah dienkripsi.

Kunci yang dipakai untuk mengenkripsi perangkat lunak dienkripsi lagi dengan sebuah session key. Session key ini dihitung dengan algoritma kunci-publik Diffie-Hellman. Kunci privat (private key) yang digunakan di dalam algoritma Diffie-Hellman diambil dari ID hardware yang bersifat unik untuk setiap komputer, sedangkan kunci publiknya (public key) ditentukan oleh pengembang perangkat lunak dan disimpan di dalam USB microcontroller.

Ketika pengguna mengaktivasi produk, program loader meminta pengguna memasukkan USB ke komputer. Selanjutnya terjadi proses perhitungan session key dengan algoritma Diffie-Hellman dengan menggunakan kunci privat (ID hardware) dan kunci publik yang tersimpan di dalam USB tadi.

Session key mendekripsi kunci master, selanjutnya kunci master digunakan untuk mendekripsi perangkat lunak yang diproteksi.

Yang menarik adalah di dalam USB juga dapat disertakan jumlah lisensi yang memungkinkan pengguna menginstalasi produk pada lebih dari satu komputer. Setiap kali aktivasi maka lisensi berkurang satu. Selain itu aktivasi produk dilakukan satu kali saja, tetapi setiap kali menjalankan perangkat lunak program loader akan memeriksa validitas nilai tertentu yang disimpan di dalam sebauh berkas eksternal.

Saya berharap karya TA-nya ini dapat dikembangkan dan diproduksi secara massal untuk mencegah penggandaan ilegal. USB dapat dibuat secara massal di pabrik dengan sebuah kunci lisensi tertentu. Pengembang dapat menyimpan kunci lisensi di dalam USB dan menentukan jumlah lisensi yang dibeli. Perangkat lunak dijual dalam satu paket yang berisi CD/DVD program dan USB tersebut.

4 Komentar

Filed under Aplikasi kriptografi, Kriptografi nirsimetri

Enkripsi Selektif Citra Digital dalam Ranah Spasial

Saya sedang melakukan riset pengembangan beberapa algoritma enkripsi khusus untuk citra digital. Teknik enkripsi yang diinginkan adalah enkripsi selektif. Enkripsi selektif adalah mengenkripsi hanya sebagian elemen citra namun efeknya keseluruhan citra terenkripsi.  Di bawah ini saya paparkan sebuah teknik enkripsi selektif dalam ranah spasial.  Tulisan ini saya ambil sebagian dari makalah yang saya presentasikan di dalam konferensi SITIA 2012 di Kampus ITS Surabaya beberapa waktu yang lalu.

~~~~~~~~~~~~~~~~~~

1. PENDAHULUAN

Enkripsi citra bertujuan melindungi konten di dalam citra dari pengaksesan ilegal. Obyektif dari enkripsi citra adalah mentransformasikan citra ke dalam bentuk lain yang tidak bermakna sehingga konten di dalam citra tidak dapat dipahami lagi secara visual.

Mengenkripsi citra dengan algoritma enkripsi konvensional untuk data teks seperti DES, AES, Blowfish, dan lain-lain kurang cocok untuk aplikasi komunikasi yang real-time, sebab citra umumnya bervolume data sangat besar sehingga proses enkripsinya menjadi lambat. Oleh karena itu, solusi untuk masalah ini adalah dengan menggunakan konsep enkripsi selektif (atau sebagian) sebagai lawan dari enkripsi total [2]. Dengan teknik enkripsi selektif hanya sebagian komponen citra yang perlu dienkripsi namun sebagai efeknya citra dienkripsi secara keseluruhan. Tujuan enkripsi selektif jelas untuk meminimalkan volume komputasi selama proses enkripsi dan dekripsi.

Enkripsi selektif dapat dilakukan dalam ranah spasial atau dalam ranah frekuensi. Klasifikasi dan ringkasan beberapa algoritma enkripsi selektif dapat ditemukan di dalam [5], sedangkan performansi algoritmanya dapat dibaca di dalam [3].

Menurut [6], kebanyakan algoritma enkripsi citra dapat dikelompokkan menjadi dua golongan: (a) algoritma enkripsi selektif non-chaos, dan (b) algoritma enkripsi selektif atau non-selektif yang berbasis chaos. Chaos menjadi topik yang atraktif di dalam kriptografi karena tiga alasan: (1) sensitivitas terhadap kondisi awal, (2) berkelakuan acak, dan (3) tidak memiliki periode berulang. Penggunaan chaos di dalam kriptografi dapat menghasilkan efek confusion dan diffusion seperti yang disyaratkan oleh Shanon [8].

Kebanyakan skema enkripsi berbasis chaos menggunakan fungsi chaos (chaotic map) sebagai pembangkit barisan bilangan semi-acak (pseudo-random) yang panjang, kemudian barisan bilangan acak tersebut digunakan untuk mengenkripsi plainteks. Review beberapa algoritma enkripsi citra yang berbasis chaos dapat ditemukan di dalam [4].

Makalah ini membahas sebuah algoritma enkripsi selektif citra digital pada ranah spasial berbasis chaos. Sistematika makalah disusun menjadi tiga. Yang pertama adalah pendahuluan, bagian kedua adalah enkripsi selektif pada bit-bit MSB, dan bagian ketiga adalah eksperimen dan pembahasan hasil.

2. ENKRIPSI SELEKTIF PADA BIT-BIT MSB

Nilai pixel pada koordinat (x, y) menyatakan intensitas nilai keabuan pada posisi tersebut. Pada citra grayscale nilai keabuan itu dinyatakan dalam integer berukuran 1 byte sehingga rentang nilainya antara 0 sampai 255. Pada citra berwarna 24-bit setiap pixel tediri atas kanal red, green, dan blue (RGB) sehingga setiap pixel berukuran 3 byte (24 bit).

Di dalam setiap byte bit-bitnya tersusun dari kiri ke kanan dalam urutan yang kurang berarti (least significant bits atau LSB) hingga bit-bit yang berarti (most significant bits atau MSB).  Susunan bit pada setiap byte adalah b7b6b5b4b3b2b1b0. Jika setiap bit ke-i dari MSB ke LSB pada setiap pixel diekstrak dan diplot ke dalam setiap bitplane image maka diperoleh delapan buah citra biner. Misalnya bila dilakukan pada citra ‘cameraman’ (Gambar 1(a)) maka setiap bitplane image ditunjukkan pada Gambar 1(b) hingga 1(i). Gambar 1(b) hingga 1(f) yang diambil dari bit-bit MSB masih dapat memperlihatkan wujud objek di dalam citra sedangkan Gambar 1(g) hingga 1(i) yang diambil dari bit-bit LSB sudah terlihat seperti citra acak.

Gambar 1: Bitplane pada citra cameraman

Berdasarkan hasil ekstraksi bit-bit tersebut dapat disimpulkan bahwa pengubahan bit-bit MSB dapat membuat citra menjadi “rusak” atau tidak dapat dikenali lagi, sedangkan pengubahan bit-bit LSB tidak mempengaruhi citra secara keseluruhan. Oleh karena itu hanya bit-bit MSB saja yang dipilih untuk dienkripsi sebab dengan hanya mengenkripsi bit-bit tersebut maka keseluruhan citra menjadi tidak dapat dikenali lagi.

Jumlah bit MSB yang dienkripsi mempengaruhi tingkat keamanan. Jika hanya satu bit yang dienkripsi, maka tujuh bit sisanya (yang tidak ikut dienkripsi) masih dapat memperlihatkan wujud objek di dalam citra, sehingga tingkat keamanannya rendah. Oleh karena itu setelah enkripsi 1-bit MSB masih diperlukan prosedur permutasi tambahan untuk mengacak pixel agar diperoleh efek confusion [7].

Tao Xiang di dalam makalahnya menyebutkan bahkan enkripsi lebih dari dua bit MSB (tanpa prosedur pengacakan sesudahnya) masih tetap belum menjamin confidentiality citra. Untuk memperoleh keseimbangan antara tingkat keamanan dan pertimbangan performansi komputasi, maka enkripsi empat bit MSB (yaitu b7b6b5b4 )merupakan pemilihan yang optimal [1]. Dengan mengenkripsi hanya 4-bit MSB berarti cukup hanya dienkripsi 50% saja dari keseluruhan citra untuk memperoleh citra terenkripsi namun tingkat keamanannya tetap terjamin.

3. EKSPERIMEN DAN PEMBAHASAN HASIL

Setelah membahas teknik enkripsi selektif dalam ranah spasial, selanjutnya dilakukan implementasi algoritma tersebut. Algoritma enkripsinya seperti stream cipher namun enkripsi dilakukan per 4-bit setiap kali. Sebagai keystream generator adalah pembangkit bilangan acak berbasis chaos. Dalam hal ini, setiap 4-bit MSB dari setiap pixel di-XOR-kan dengan 4-bit keystream. Pada proses dekripsi, setiap 4-bit pixel dari cipher-image di-XOR-kan dengan 4-bit keystream. Untuk citra berwarna prosesnya dilakukan tiga kali, masing-masing untuk kanal red (R), green (G), dan blue (B).

Selanjutnya dilakukan simulasi enkripsi selektif pada citra uji, baik citra graysscale maupun citra berwarna. Dua buah citra standard yang digunakan adalah ‘Barbara’ (grayscale) dan ‘Lena’ (berwarna) yang keduanya berukuran 512 x 512 (Gambar 2), dan citra ketiga adalah ‘Taj Mahal’ yang berukuran 768 x 573.

Gambar 2. Tiga buah citra uji yang digunakan di dalam simulasi enkripsi dan dekripsi.

Citra hasil enkripsi (cipher-image) untuk ketiga citra uji di atas diperlihatkan pada Gambar 3. Citra hasil enkripsi terlihat sebagai citra acak dan sudah tidak bisa dikenali lagi. Dekripsi terhadap cipher-image menghasilkan kembali tepat seperti citra paad Gambar 1.

Gambar 3. Citra hasil enkripsi. Ketiga buah citra plain-image sudah tidak dapat dikenali lagi.

Analisis Histogram

Histogram merupakan properti citra yang penting sebab sebuah histogram memperlihatkan distribusi intensitas pixel di dalam citra tersebut. Untuk citra plain-image histogramnya membentuk suatu pola yang khas, yaitu ada puncak-puncak dan lembah-lembah. Untuk mencegah penyerang menggunakan histogram untuk melakukan analisis freluensi, maka histogram plain-image dan histogram cipher-image seharusnya tidak memiliki kemiripan secara statistik. Oleh karena itu, histogram cipher-image seharusnya relatif datar (flat) sehingga tahan terhadap serangan statistik. Distribusi yang relatif uniform pada cipher-image adalah sebuah indikasi bahwa algoritma enkripsi citra memiliki kualitas yang bagus [9].

Gambar 4(a) memperlihatkan histogram citra ‘Barbara’ sebelum dienkripsi, dan Gambar 4(b) adalah histogram cipher-image-nya. Dapat dilihat bahwa histogram cipher-image memiliki distribusi uniform yang mana berbeda dengan histogram plain-image.

Gambar 4. (a) Histogram citra ‘Barbara’ (plain-image) dan (b) histogram cipher-image.

Gambar 5(a) sampai 5(c) memperlihatkan histogram citra ‘Lena’ (plain-image) untuk setiap kanal warna RGB dan Gambar 5(d) sampai 5(f) adalah histogram masing-masang kanal warna pada cipher-image. Sama seperti citra ‘Barbara’, histogram cipher-image pada setiap kanal RGB juga terlihat flat atau terdistribusi uniform.

Gambar 5. (a)-(c) Histogram citra ‘Lena’ (plain-image) untuk masing-masing kanal RGB dan (d)-(f) histogram cipher-image untuk setiap kanal RGB.

Gambar 6(a) memperlihatkan histogram citra ‘Taj Mahal’ (plain-image) dan Gambar 8(b) adalah histogram cipher-image-nya. Sedikit berbeda dengan histogram cipher-image dari dua citra sebelumnya, histogram cipher-image dari ‘Taj Mahal’ memiliki distribusi yang relatif uniform.

Gambar 6 (a) Histogram citra ‘Taj Mahal’ (plain-image) dan (b) histogram cipher-image.

Berdasarkan hasil-hasil analisis histogram di atas dapat disimpulkan bahwa cipher-image memiliki histogram yang (relatif) flat sehingga menyulitkan penyerang melakukan analisis statistik untuk mendeduksi pixel atau kunci. Hasil ini menunjukkan bahwa algoritma enkripsi citra yang diusulkan ini memiliki keamanan yang bagus.

DAFTAR REFERENSI

[1] Tao Xiang, Kwok-wo Wong, Xiaofeng Liao, Selective Image Encryption Using a Spatiotemporal Chaotic System, Chaos Volume 17, 2007.
[2] Nidhi S Kulkarni, Balasubrmanian Raman, Indra Gupta, Selevtive Encryption of Multimedia Images, Proc. Of XXXII National Systems Conference, NSC 2008, December 17-19, 2008.
[3] Jolly Shah, Vikas Saxena, Performance Study on Image Encryption Schemes, International Journal of Computer Science Issues, Vol 8, Issue 4, No 1, July 2011.
[4] Monisha Sharma, Manoj Kumar Kowar, Image Encryption Techniques Using Chaotic Schemes: A Review, International Journal of Engineering Science and Technology, Vol. 2(6), 2010
[5] Xiliang Liu, Selective Encryption of Multimedia Contentn in Distribution Networks: Challenges and New Directions, Proc. of Conference of Communications, Internet, and Information Technology, 2003.
[6] Mohammad Ali Bani Younes, Aman Jantan, Image Encryption Using Block-based Transformation Algorithm, IAENG International Journal of Computer Science, 35: 1, IJCS_32_1_03, 2008.
[7] Rinaldi Munir, Enkripsi Selektif Citra Digital dengan Stream Cipher Berbasiskan pada Fungsi Chaotik Logistic Map, Seminar Nasional dan Expo Teknik Elektro Univeristas Syiah Kuala, Banda Aceh, Oktober 2011.
[8] Bruce Schneier, Applied Cryptography 2nd Edition, Wiley & Sons, 1996.
[9] Alireza Jolfaei, Abdul Rasoul Mirghadri, An Image Encryption Approach Using Chaos and Stream Cipher, Journal of Theoretical and Applied Information Technology, 2010.
[10] James Lampton, Chaos Cryptography: Protecting data Using Chaos, Missisippi School for Mathematics and Science.

3 Komentar

Filed under Enkripsi citra

Skema Pembagian Data Rahasia dari Shamir (Bagian 2)

Selain menggunakan metode eliminasi Gauss untuk menemukan solusi polinom interpolasi, metode lain yang dipakai untuk membentuk polinom secara langsung adalah dengan menggunakan metode interpolasi. Jika anda pernah mengambil kuliah metode numerik, anda tentu pernah mempelajari metode-metode meninterpolasi sejumlah titik data dengan polinom.

Salah satu metode interpolasi polinom adalah Polinom Lagrange. Misalkan diberikan t buah titik yaitu (x1, y1), (x2, y2), …, (xt, yt). Polinom Lagrange, dalam modulo p, yang melalui t titik adalah polinom derajat t– 1:

                                        p(x)  = y1L1(x1) + y2L2(x2) + … + ytLt(xt) (mod p),

yang dalam hal ini:

Polinom Lagrange ini harus dirahasiakan supaya pihak lawan tidak bisa menghitung secret M. Untuk memperoleh secret M caranya mudah, yaitu bila diketahui polinom p(x) maka hitung p(x) pada x = 0.

Misalkan partisipan 2, 3, dan 7 menggunakan interpolasi Lagrange, mereka mengumpulkan semua share mereka:
(x1, y1) = (2, 1045116192326)
(x2, y2) = (3, 154400023692)
(x3, y3) = (7, 973441680328)

Mereka kemudian membentuk polinom Lagrange derajat dua:p(x) = y1L1(x1) + y2L2(x2) + y3L3(x3) (mod p), dan diperoleh hasilnya sebagai berikut:

p(x) =  20705602144728/5 – 1986192751427x + (1095476582793/5)x2 (mod p)

Karena polinom  dihitung dalam modulus p dan dengan mengingat 740740734080  dikali 5 kongruen dengan 1 (mod p), maka 1/5 dapat diganti dengan 740740734080, sehingga kita memperoleh polinom tanpa modulo p:

p(x) = 190503180520 + 482943028839x +120674920705602144728x2

Untuk memproleh M, hitung p(0), dan diperoleh p(0) = 190503180520 = M, yaitu secret semula.

 

Referensi

1. Trappe, W., Washington, L. (2006): Introduction to Cryptography with Coding Theory, Prentice Hall.

Tinggalkan komentar

Filed under Secret sharing

Skema Pembagian Data Rahasia dari Shamir (Bagian 1)

Ada segerombolan perompak kapal yang beranggotakan 6 orang. Mereka sepakat  untuk menyimpan uang hasil rampasan mereka di bank. Untuk itu mereka perlu membuka rekening baru di sebuah bank. Pihak bank akan memberikan PIN kartu ATM kepada para perompak tadi. Masalah muncul karena keenam perompak kapal itu tidak saling percaya satu sama lain.  Mereka tidak mau salah seorang dari mereka berkhianat lalu menarik uang dengan PIN tersebut tanpa sepengetahuan yang lain. Oleh karena itu, para perompak meminta anda sebagai orang yang adil untuk menyelesaikan masalah mereka. Anda meminta pihak bank untuk membagi PIN menjadi enam bagian (share), tetapi untuk merangkainya menjadi PIN yang utuh dibutuhkan paling sedikit  tiga buah share dari  tiga orang perompak. Bagaimana bank dapat melakukan pembagian ini?

Persoalan di atas ditemukan jawabannya oleh Adi Shamir dari MIT di dalam makalahnya yang berjudul How to Share a Secret. Makalah tersebut dimuat di dalam majalah Communication of the ACM 22 (11):  612-613 pada tahun 1979. Secret  adalah istilah untuk data atau informasi rahasia seperti kunci kriptografi, password, PIN,  dan sebagainya. Secret sharing adalah metode membagi a secret menjadi sejumlah bagian (share), masing-masing bagian diberikan kepada sejumlah partisipan (orang atau pihak yang memperoleh share). Setiap bagian adalah unik satu sama lain dan untuk merekonstruksi secret semula diperlukan beberapa (atau semua) bagian.

Misalnya jika anda memiliki kunci enkripsi “1234abcd” dan membaginya kepada beberapa orang yang dipercaya, bagaimana cara membagi kunci ini kepada orang-orang tersebut menjadi setiap bagian? Cara yang sederhana adalah memotong-motong kunci tersebut, misalnya “12”, “34”, “ab”, dan “cd” dan memberikan setiap bagian kepada setiap orang. Namun, metode ini tidak dapat digunakan jika hanya beberapa share saja yang diperlukan untuk merekonstruksi kunci  semula. Diperlukan semua share dari semua orang untuk merekonstruksi kunci semula.  Lagipula, jika jumlah parstisipan banyak sedangkan ukuran secret relatif pendek, metode pembagian sederhana seperti itu tidak dapat diterapkan.  Bagaimana anda membagi PIN “1234” kepada 20 orang?

Pada tahun 1979 Adi Shamir, di dalam makalah yang saya sebutkan di atas, mengemukakan skema pembagian secret yang dinamakan skema ambang Shamir (Shamir threshold scheme). Skema pembagian tersebut berbunyi:

Misalkan t dan w adalah bilangan bulat positif dengan t <= w. Skema ambang (t, w) adalah metode pembagian secret M kepada w partisipan sedemikian sehingga sembarang himpunan bagian yang terdiri dari t partisipan dapat merekonstruksi M, tetapi jika kurang dari t maka M tidak dapat direkonstruksi.

Untuk dapat menggunakan skema ambang Shamir tersebut maka secret harus direpresentasikan dengan integer M. Misalnya secret  ‘ABCD’  dinyatakan sebagai M = 102030405 dengan mengkodekan A = 01, B = 02, C = 03, dan seterusnya. Orang yang melakukan pembagian secret dinamakan dealer. Dealer haruslah orang yang dipercaya oleh semua parstisipan.

Secara teknis, pembagian secret M menjadi sejumlah share menggunakan konsep interpolasi polinom yang dikenal di dalam metode numerik. Di dalam teori interpolasi, untuk membentuk persamaan linier y = a0 + a1x diperlukan  2 buah titik yaitu (x1, y1) dan (x2, y2). Selanjutnya, untuk membentuk persamaan kuadratik y = a0 + a1x + a2x2 diperlukan 3 buah titik, untuk membentuk persamaan kubik diperlukan empat titik, dan seterusnya.  Secara umum untuk membentuk polinomial y = a0 + a1x + a2x2 + … + anxn diperlukan n + 1 titik.

Titik-titik tersebut disulihkan ke dalam persamaan polinom y, selanjutnya kita memperoleh sistem persamaan linier dan menyelesaikannya dengan metode eliminasi Gauss untuk memperoleh koefisien-koefisien polinom. Misalkan untuk menginterpolasi dua buah titik dengan sebuah garis lurus y = a0 + a1x, maka dua buah titik yaitu (x0, yo) dan (x1, y1) disulihkan ke dalam persamaan garis menjadi:

y1 = a0 + a1x1
y2 = a0 + a1x2

Lihat ilustrasinya pada Gambar 1 di bawah ini.

Gambar 1. Interpolasi linier

Selanjutnya sistem persamaan linier diselesaikan dengan metode eliminasi untuk menentukan a0 dan a1. Semakin banyak jumlah titiknya maka sistem persamaan linier menjadi besar, namun metode eliminasi Gauss dapat diterapkan untuk mencari solusi sistem tersebut.

Skema (t, w) yang ditemukan oleh Adi Shamir dapat dituliskan algoritmanya sebagai berikut (Trapper, 2006):

1. Pilih bilangan prima p, yang harus lebih besar dari semua kemungkinan nilai pesan M dan juga lebih besar dari jumlah w partisipan. Semua komputasi dihasilkan dalam modulus p.

2. Pilih secara acak t – 1 buah bilangan bulat dalam modulus p, misalkan s1, s2, …, st– 1, dan nyatakan polinomial:

        s(x) =  M + s1x + s2x2 + … + st – 1 xt -1 (mod p)

sedemikian sehingga s(0) =  M (mod p). Sebagai catatan, p tidak perlu rahasia, tetapi polinom s(x) harus dirahasiakan.

3. Untuk w partisipan, kita pilih integer berbeda, x1, x2, …, xw (mod p),dan setiap orang memperoleh share (xi, yi) yang dalam hal ini yi = s(xi) (mod p). Untuk memudahkan perhitungan, misalkan untuk w orang kita memilih x1 = 1, x2 = 2, …, xw = w.

4. Misalkan t orang partisipan akan merekonstruksi M, dengan share masing-masing (x1, y1), (x2, y2) …, (xt, yt). Sulihkan setiap (xk, yk) ke dalam polinomial   s(x) = M + s1x + s2x2 + … + st – 1 xt – 1 (mod p).  Ini berarti:

5. Jika dimisalkan M = s0 maka kita dapat menulis ulang sistem persamaan ke dalam bentuk matriks:

Selesaikan sistem persamaan linier di atas dengan metode eliminasi Gauss untukmemperoleh s0 = M.

Untuk mengilustrasikan skema di atas, ambil contoh sebagai berikut. Misalkan ada w = 8 partisipan akan membagi secret M = 190503180520 dan mereka sepakat bahwa  diperlukan t = 3 partisipan untuk melakukan rekonstruksi M.  Misalkan dipilih bilangan prima p = 190503180520. Selanjutnya pilih 3 – 1 = 2 buah bilangan acak,  sebut s1 = 482943028839 dan s2 = 1206749628665, untuk membentuk polinom  s(x) =  M + s1x + s2x2 (mod p), yaitu

                s(x) = 190503180520 + 482943028839x + 1206749628665x2 (mod 1234567890133 )

Setiap partisipan memperoleh (x, s(x)). Misakan x1 = 1, x2 = 2, …, x8 = 8, maka, setiap orang memperoleh share:

(1, 645627947891)
(2, 1045116192326)
(3, 154400023692)
(4, 442615222255)
(5, 675193897882)
(6, 852136050573)
(7, 973441680328)
(8, 1039110787147)

Untuk merekonstruksi kembali secret M dibutuhkan paling sedikit 3 partisipan. Misalkan partisipan 2, 3, dan 7 ingin merekonstruksi M. Mereka perlu memecahkan sistem persamaan linier:

Dengan metode eliminasi Gauss sistem persamaan linier tersebut dapat dipecahkan dan solusinya adalah  (M, s1, s2) = (190503180520, 482943028839, 1206749628665). Dengan kata lain secret M = 190503180520 dapat diperoleh kembali.

Apa yang terjadi jika 2 orang partisipan mencoba merekonstruksi M? Nilai M tidak dapat ditemukan karena  mustahil dua buah buah titik dapat membentuk polinom kuadratik  s(x) =  M + s1x + s2x2 (mod p). Misalkan mereka mencoba menggunakan titik ketiga yaitu (0, c) dengan c adalah sembarang secret, maka polinom unik yang melalui ketiga titik tersebut tetap tidak berhasil menemukan nilai M.

Apa yang terjadi jika > 3 orang partisipan mencoba merekonsruksi M? Sistem persamaan linier yang terbetuk memiliki lebih dari 3 persamaan dengan tiga peubah yang tidak diketahui, pada kondisi seperti ini sistem persamaan linier tetap dapat dipecahkan dan polinom interpolasi tetap bisa ditemukan! Dengan kata lain, minimal dibutuhkan 3 partisipan untuk bisa merekonstruksi M dengan skema (3, 8) tersebut.

Referensi

1. Trappe, W., Washington, L. (2006): Introduction to Cryptography with Coding Theory, Prentice Hall.

1 Komentar

Filed under Secret sharing

Kriptografi Berbasis “Chaos” (Bagian 2)

(Lanjutan tulisan sebelumnya)

Properti chaos yang paling bernilai bagi kriptografi adalah kepekaannya pada nilai awal.  Sebagaimana dijelaskan oleh Schneier (1996), salah satu dari dua prinsip Shannon yang dijadikan panduan dalam perancangan algoritma kriptografi adalah difusi (diffusion), yaitu menyebar pengaruh 1 bit (atau digit) data (plainteks atau kunci) ke seluruh bit cipherteks dengan maksud untuk menyembunyikan hubungan statistik antara plainteks dan cipherteks.  Prinsip difusi ini relevan dengan properti  chaos di atas, sebab jika nilai awal yang digunakan untuk membangkitkan nilai acak diubah sedikit, misalnya 1 bit, lalu nilai-nilai acak itu digunakan untuk mengenkripsi plainteks, maka cipherteks yang dihasilkan akan berbeda secara signifikan. Sifat peka menjamin bahwa jika pihak lawan mencoba mendekripsi data dengan kondisi awal berbeda dan mencari pola hubungan plainteks dan cipherteks, cara itu akan gagal (Roskin, 1999).

Pada dasarnya, terdapat dua cara umum untuk merancang algoritma kriptografi dengan chaos (Li, 2003):

  1. Menggunakan chaos untuk membangkitkan barisan kunci bilangan acak, yang digunakan untuk me-“mask” plainteks. Cara ini berkoresponden dengan  stream cipher
  2. Menggunakan plainteks dan/atau kunci rahasia sebagai kondisi awal dan/atau parameter kendali, dengan mengiterasikan sistem chaos sejumlah kali untuk memperoleh cipherteks. Cara ini berkoresponden dengan block cipher.

Kebanyakan stream cipher menggunakan pembangkit bilangan acak untuk menghasilkan keystream.  Pembangkit bilangan acak terdapat pada dua sisi, sisi pengirim dan sisi penerima. Dalam hal ini,  chaos dapat digunakan untuk membangkitkan keystream, selanjutnya kesytream ini digunakan untuk me-“mask” plainteks.

 Rancangan Algoritma Stream Cipher dengan Chaos

Algoritma stream cipher yang dibahas  di dalam tulisan ini me-mask karakter-karakter plainteks pi dengan kesystream ki yang dibangkitkan dari sistem. Algoritma stream cipher yang dirancang terdiri atas beberapa bagian:

i)  Fungsi pemotongan
ii) Pembangkitan keystream dengan chaos
iii) Enkripsi plainteks dengan kunci
iv) Dekripsi cipherteks dengan kunci

Setiap bagian yang disebutkan di atas dijelaskan secara rinci atu per satu di bawah ini.

 (i) Fungsi Pemotongan

Enkripsi dan dekripsi beroperasi dalam himpunan bilangan bulat yang nilainya dari 0 sampai 255, sedangkan barisan nilai chaos yang digunakan sebagai kesytream adalah bilangan riil antara 0 dan 1. Agar barisan nilai chaos dapat dipakai untuk enkripsi dan dekripsi, maka nilai chaos harus dikonversi ke nilai integer. Ada beberapa teknik konversi yang dapat digunakan, teknik yang umum misalnya mengambil 3 angka terakhir pada bagian mantissa bilangan riil. Sebagai contoh, dari 0.024568 diambil 3 angka terakhir dari bagian mantissanya yaitu 568.

Di dalam tulisan ini, konversi nilai chaos ke integer dilakukan dengan menggunakan fungsi pemotongan yang diusulkan oleh Lampton (xxxx). Caranya, nilai chaos dikalikan dengan 10 berulangkali sampai ia mencapai panjang angka (size) yang diinginkan, lalu memotong hasil perkalian tersebut untuk mengambil bagian integer-nya saja. Secara matematis, nilai chaos x dikonversi ke  integer dengan menggunakan persamaan berikut:

yang dalam hal ini count mulai dari 1 dan bertambah 1 sampai x * 10count > 10size – 1 . Hasilnya kemudian diambil bagian integer saja (dilambangkan dengan pasangan garis ganda pada persamaan 11). Sebagai contoh, misalkan x = 0.003176501 dan size = 4, maka dimulai dari count = 1 sampai count = 6 diperoleh

0.003176501 * 106 = 3176.501 > 103

kemudian ambil bagian integer-nya dengan

Jadi, diperoleh sebuah elemen dari barisan kunci yaitu 3176. Cara yang sama dilakukan untuk nilai-nilai chaos lainnya. Algoritma konversi nilai chaos ke integer dinyatakan dengan kode program C berikut ini:

(ii) Pembangkitan keystream dengan chaos

Kunci yang digunakan untuk me-mask plainteks dihasilkan dari konversi nilai chaos ke integer, seperti yang sudah diterangkan di atas. Nilai-nilai chaos dibangkitkan dari persamaan Logistic Map dengan mengambil konstanta r = 4.0. Normalnya, nilai xi dihitung langsung dari nilai chaos sebelumnya, xi – 1. Ini berarti bila seseorang mengetahui sebuah nilai xi dari barisan nilai chaos, maka ia dapat menggunakan xi untuk membangkitkan xi + 1, xi + 2, …, yang selanjutnya digunakan untuk mendekripsi cipherteks.

Untuk menambah kekuatan algoritma, maka nilai xi dibangkitkan setelah sejumlah iterasi tertentu. Tujuannya adalah untuk menghilangkan korelasi antara nilai-nilai chaos yang berturutan. Jumlah iterasi yang dibutuhkan untuk menghitung nilai chaos pertama, x1, ditentukan oleh nilai awal, x0. Nilai awal ini dikonversi ke integer dengan algoritma yang sudah dijelaskan di atas, hasilnya adalah jumlah iterasi yang diperlukan untuk mengiterasi persamaan Logistic Map. Nilai x yang diperoleh pada akhir iterasi berlaku sebagai “x0” yang baru untuk menghitung x1. Untuk x2, x3, dan seterusnya, jumlah iterasinya ditentukan dari jumlah iterasi untuk nilai chaos sebelumnya ditambah dengan size.

Dengan cara ini, seseorang yang mengetahui suatu nilai xi tertentu tidak mungkin dapat menghitung xi + 1 tanpa mengetahui jumlah iterasi yang diperlukan untuk mengiterasi persamaan (8).  Jumlah iterasi awal ditentukan oleh x0. Jadi, nilai awal merupakan nilai yang sangat menentukan keamanan stream cipher. Terdapat sejumlah tidak berhingga nilai-nilai antara 0 dan 1, oleh karena itu exhaustive key search untuk menemukan x0 menjadi sesuatu yang tidak mungkin dilalukan. Selain itu, seperti yang sudah dijelaskan di bagian 6, fungsi chaos peka terhadap perubahan kecil pada nilai awal, sehingga jika nilai awal yang dicoba pihak lawan sangat dekat dengan nilai awal yang digunakan untuk mengenkripsi data, pihak lawan masih akan memperoleh keluaran yang salah.

(iii)  Enkripsi plainteks dengan kunci

Enkripsi dikerjakan dengan menjumlahkan plainteks pi dan ki dalam modulo 256, seperti yang dituliskan dalam persamaan berikut:

        ci = (pi + ki) mod 256

Alasan pemilihan modulus 256 karena stream cipher mengenkripsi plainteks menjadi chiperteks satu karakter (1 byte) setiap kali.

(iv)  Dekripsi cipherteks dengan kunci

Dekripsi dikerjakan dengan mengurangkan cipherteks ci dengan pad ki dalam modulo 256, seperti yang dituliskan dalam persamaan berikut:

        pi = (ciki) mod 256

Contoh Enkripsi/Dekripsi Sederhana

Penulis mengilustrasikan contoh enkripsi dan dekripsi sederhana dengan program stream cipher yang sudah dibuat. Nilai awal yang digunakan untuk pembangkitan aliran kunci adalah 0.021503. Plainteks yang akan dienkripsi adalah string “selamat pagi”. Nilai ASCII yang berasosiasi dengan plainteks tersebut adalah

{115, 101, 108, 97, 109, 97, 116, 32, 112, 97, 103, 105}

yang dalam hal ini setiap karakter diepresentasikan dengan angka, misalnya 115 untuk ‘s’, 105 untuk ‘e’, dan seterusnya. String terebut disimpan di dalam berkas plainteks dan cipherteksnya disimpan di dalam berkas cipherteks.  Keystream yang dibangkitkan dengan Logistic Map misalkan adalah

{644, 296, 453, 376, 711, 929, 877, 659, 368, 865, 843, 286}

Kunci ini diperoleh dengan membangkitkan bilangan tiga-angka dari nilai-nilai chaos yang dihasilkan.  Selanjutnya, enkripsi dilakukan dengan cara menjumlahkan plainteks dengan kunci dalam modulo 256. Operasi ini diperlihatkan sebagai berikut:

Perhatikan bahwa semua karakter cipherteks adalah acak (semuanya berbeda) karena kita menjumlahkan barisan nilai acak (kunci) dengan barisan nilai tidak acak (plainteks). Selain itu, karakter plainteks yang sama tidak selalu menghasilkan karakter cipherteks yang sama pula (misalnya 97 tidak selalu menghasilkan 217, tetapi untuk 97 yang kedua menghasilkan 2, sedangkan 97 yang ketiga menghasilkan 194).

Penerima pesan membangkitkan kembali barisan kunci dengan menggunakan nilai awal chaos yang sama, lalu mengurangkan barisan cipherteks (setelah ditambah dengan 256 sejumlah kali sampai nilainya lebih besar dari elemen kunci)  dengan barisan kunci untuk memperoleh kembali plainteks semula:

Hasil-hasil  Eksperimen

Program stream cipher berbasis chaos diujicoba dengan sebuah berkas teks  yang berukuran sedang. Plainteks dapat dilihat di bawah ini. Plainteks dienkripsi dengan menggunakan nilai awal r = 4.0, size = 3,  dan x0 = 0.00230872. Jika cipherteks didekripsi dengan nilai awal yang sama seperti pada waktu enkripsi, plainteks yang dihasilkan tepat sama seperti semula. Namun, jika cipherteks didekripsi dengan nilai awal yang sedikit berbeda, yaitu x0 = 0.002308716, maka plainteks yang dihasilkan salah karena barisan nilai chaos yang dihasilkan berbeda (peka terhadap perubahan kecil pada nilai awal).

———— Plainteks ————————————————————————————————————

Seorang wartawan mewawancarai seorang petani untuk mengetahui rahasia di balik buah jagungnya yang selama bertahun-tahun selalu berhasil memenangkan kontes perlombaan hasil pertanian. Petani itu mengaku ia sama sekali tidak mempunyai rahasia khusus karena ia selalu membagi-bagikan bibit jagung terbaiknya pada tetangga-tetangga di sekitar perkebunannya.

“Mengapa anda membagi-bagikan bibit jagung terbaik itu pada tetangga-tetangga anda? Bukankah mereka mengikuti kontes ini juga setiap tahunnya?” tanya sang wartawan.

 “Tak tahukah anda?,” jawab petani itu. “Bahwa angin menerbangkan serbuk sari dari bunga-bunga yang masak dan menebarkannya dari satu ladang ke ladang yang lain. Bila tanaman jagung tetangga saya buruk, maka serbuk sari yang ditebarkan ke ladang saya juga buruk. Ini tentu menurunkan kualitas jagung saya. Bila saya ingin mendapatkan hasil jagung yang baik, saya harus menolong tetangga saya mendapatkan jagung yang baik pula.”

Moral cerita ini: Begitu pula dengan hidup kita. Mereka yang ingin meraih keberhasilan harus menolong tetangganya menjadi berhasil pula. Mereka yang menginginkan hidup dengan baik harus menolong tetangganya hidup dengan baik pula. Nilai dari hidup kita diukur dari kehidupan-kehidupan yang disentuhnya.

——– Cipherteks ————————————————————————————————————

Ì~Rd+<‚­ € ¥ÃE£‰nê8äHX¾¢ˆDWƒÌJ·WK¼ Ox絘:>czPµ?HCÆtîÌá¬Bw§îk~>è0žJ’›Sk¾&á*Ó5ÅT¢–´}78£/ùüâÖ9m‚ ºO ¼ 4¶c,>\t&>ëÿÀ: ™ Füt }L˜LüU Ê!Ñ9ÛÌιRds±ùDDÐ×S’ˆOCð¸·F wý¬ð±Á¬ÄS:  íL¢Îßë‘#ÕGi™Ë~Bñ_ƒß×äÝãI×€PÌI?¿têÌ8Ó“g¹/1”{Zµ÷3„ðë,ÄT;%K˜×ý;’ïGEa÷Nâ(Üb©R L«wMëQ9Ž¶Y¤!ínÿIKOöà @Ò­Iô©„;Šñáoì§ß-“Õ$Ž 5Ÿú÷ø ·!_²wyÕÒ@Ó¯ñJ+ó•OÚ=}™ò¥o[„¢Ò¸ /ì šÞ¬EÛçWQ5I (õª¼\D?@ýΆ$ëä;™öÕ ô^¤iú|C±ê·@%é6|ÂX%”<TÀÉÒ·[óG<KpÈîŒF #ìÄÞ>rŒ‰*&)bâï[1]ôsä?5_цMM!àç8HÏê±O1Am~“ØCEü‹÷KuÙ!î[Ê‘Q(5Gž!¨VêSß_QµíFZRFë!ËU ’LÈ®?2Ë öÑÌfI’?ùçzÙí9OòªŽEÎÜ€Øð « ,>i¦»„OÊ1[1]\#çÍV@‹Ë`Ðï7ñ›ÜÛÅ 6ŽZ8ðÜ÷71Ü,›äòN€¿JÐ:ž\CÀ!»Ig)ŠÒ61 ö ˆ<+ÝÞސ±ÇšEHK=¢‹ &× ¬ø‰¹w>˜9 uï$SºË”àŠh åù4ÚL­ “°÷PN×Æ,s=<þ>š¿·’U€5 ­ùùó >”®G›¾•ÊÛQƾCàsÉNj F&Iƒv¼#eû ÄŠÝðÝYKèö;<*ÄLSÉ£H$ØCGé‑¸. ·òçèþC7§Ì$ä…H WM­k…ô;3ò˜˜k:Dåý× û­-  ¦í8_XÔäÞ¼päW¸(Pö‘Q =ƒÞ5ÚŪ’wæË•ÙGõêÏè8‹-KátG­ð­þ%[1]•0e+ÈWñÔ¿jX$r‚ePbLõ1­ß Þp¶UEð/’þ}Õ%.0ôWó¡àV‹1ì EÝ.“óÂ8/gõ„|?•…J Íò_[î ±ê;·Õ—ÿR‰§Hлzìëz ª½Yƒ¶íï}­£±sVŒkÑöÞ76]_þÞT-жáÜV¦ófOKs¹_Ñbù7› aÉú§¼G1{sZÛFmÃ]ì`Åÿíám»[1]=ŠðØE Ž­rýWîJïHNíÊ& L¾OÌVš’À]×zrO6¢F3Í] ÓõÜÍ䞃gp½{¶3pS5TŸFôP’غ ïõÏ Þ-|Mþ]ÎTxÈpKzd …3B0³`NIé\Kuæ¶ì>rh[1]Õˆ[(8à˜:—š¸«AîmL*”nû?ÚsRêð‘N·_°à1Îå@gô.Ꮙõè-YF· 42þn ȧ   ìLúÃ:ÊÄËß÷”å[1]ò|ÿK×0áû§K-=¡Z©3þ–ÊYcn×Õ˜áÕIÌfÛ’ó ­¥à%„ß]T/ul      MšeóÒ

Referensi

1. Schneier, B., (1996): Aplied Cryptography 2nd, John Wiley & Sons.

2. Roskin, K., Casper, J., (1999): From Chaos to Cryptography.

3. Li, S. (2003): Analysis and New Designs of Digital Chaotic Chipers, Disertasi Ph.D University of Beijing.

4. Lampton, J., (xxxx): Chaos Cryptography: Protecting Data Using Chaos, Mississippi School for Mathematics and Science.

Tinggalkan komentar

Filed under Chaos, Stream Cipher

Kriptografi Berbasis “Chaos” (Bagian 1)

Teori chaosberasal dari teori sistem yang memperlihatkan kemunculan yang tidak teratur, meskipun sebenarnya teori ini digunakan untuk menjelaskan kemunculan data acak. Penemu teori chaos adalah seorang ahli meteorologi, Edward Lorentz, pada tahun 1960 ketika ia membuat model perkiraan cuaca. Model matematis cuaca diiterasi untuk memperoleh perkiraan cuaca pada waktu yang akan datang. Semakin lama waktu perkiraan cuaca yang dihitung, semakin panjang iterasi yang harus dilakukan. Dengan mengubah sedikit nilai awal iterasi sebesar 0.000127, ia menemukan fenomena bahwa prediksi cuaca yang dihasilkan mengalami divergensi yang besar. Gambar 1 memperlihatkan plot kurva dari iterasi terhadap model cuaca tesrebut dengan menggunakan nilai awal kurva yang berbeda sebesar 0.000127. Fenomena ini dinamakan sebagai efek sayap kupu-kupu (butterfly effect), yang  menyatakan bahwa perbedaan kecil pada nilai awal iterasi dari dua kurva dapat diperbandingkan dengan kepak sayap kupu-kupu:

The flapping of a single butterfly’s wing today produces a tiny change in the state of the atmosphere. Over a period of time, what the atmosphere actually does diverges from what it would have done. So, in a month’s time, a tornado that would have devastated the Indonesian coast doesn’t happen. Or maybe one that wasn’t going to happen, does. (Ian Stewart, Does God Play Dice? The Mathematics of Chaos, pg. 141)

Gambar 1.  Eksperimen Lorentz: perbedaan antara nilai awal kurva hanya 0.000127  (Sumber gambar: Chaos Theory: A Brief Introduction)

Fenomena seperti ini umum di dalam teori chaos, yaitu peka terhadap perubahan nilai awal (sensitive dependence on initial condition). Kepekaan ini berarti bahwa perbedaan kecil pada nilai awal fungsi, misalnya perubahan sebesar 10^-100, setelah fungsi diiterasi sejumlah kali, akan menghasilkan perbedaan yang sangat besar pada nilai fungsinya. Sebagai contoh, jika persamaan chaos dimulai dengan nilai awal 32, dan pada kali yang lain 32.000001, maka setelah 100 kali iterasi nilai persamaan dengan nilai awal pertama mungkin 137.54, sedangkan nilai persamaan dengan nilai awal kedua mungkin 1160.934.

Salah satu fungsi chaos yang sederhana adalah persamaan logistik di dalam ekologi yang digunakan untuk mensimulasikan pertumbuhan populasi spesies, yaitu

f(x) = r x(1 – x)                               (1)

Fungsi ini dapat dinyatakan dalam bentuk iteratif

xi+1 = r xi (1 – xi)                          (2)

Di dalam persamaan (1) dan (2) di atas x adalah populasi spesies pada interval waktu yang ditentukan dengan x0 adalah nilai awal iterasi. Daerah asal x adalah dari 0 sampai 1, yang dalam hal ini 1 menyatakan populasi maksimum yang dan 0 menyatakan kepunahan, sedangkan 0 <= r <= 4. Konstanta r menyatakan laju pertumbuhan.

Pertanyaannya adalah bagaimana r mempengaruhi persamaan? Konstanta r juga menyatakan bagian nirlanjar dari persamaan. Ketika r meningkat, maka kenirlanjaran sistem juga naik. Gambar 2 memperlihatkan kelakuan fungsi yang dalam hal ini sumbu-x menyatakan nilai r sedangkan sumbu y menyatakan status sistem, yaitu nilai-nilai x. Bila 0 < < 1, nilai awal berapapun akan menghasilkan kepunahan (yaitu nilai x pada akhir iterasi adalah 0). Bila 1 < < 3, fungsi konvergen ke sebuah nilai (fixed-point), yaitu nilai r yang menghasilkan sistem mempunyai periode satu siklus. Misalnya jika r = 1.5 dan x0 = 0.25, maka persamaan iterasi akan konvergen ke nilai titik-tetap 1/3 (atau 0.3333….) (Robinson, 2004). Ketika r = 3, kurva fungsi terpecah menjadi dua (diistilahkan dengan bifurcation) menghasilkan dua nilai populasi berbeda, yang berarti nilai x secara periodik berosilasi dari status tinggi ke status rendah. Periode sistem pada nilai r ini adalah dua. Ketika r meningkat lagi, kurva fungsi  terpecah lagi menjadi empat, yang berarti nilai-nilai x yang dihasilkan berosilasi di antara 4 nilai. Periode sistem pada nilai r ini adalah empat.

Gambar 2.  Diagram bifurcation untuk persamaan logistik xi+1 = r xi (1 – xi) (Sumber gambar: Wikipedia)

Demikianlah seterusnya bifurcation menjadi lebih cepat lagi menjadi 4, 8, dan 32 dengan meningkatnya nilai r sampai tiba pada suatu nilai r tertentu sifat chaos pun mucul. Pada titik ini tidak mungkin lagi memprediksi kelakuan sistem. Kita dapat melihat bahwa ketika r > 3.75  sistem mulai melaju dengan cepat menuju area chaos (di dalam Gambar 2 area tersebut diarsir hitam). Akhirnya, ketika r = 4, iterasi bergantung sepenuhnya pada nilai awal x0 dan nilai-nilai yang dihasilkan muncul acak meskipun sistem ini deterministik (Robinson, 2004). Nilai-nilai chaos yang dihasilkan akan berada di dalam rentang yang lengkap antara 0 dan 1.

Sebagai contoh, jika kita menggunakan r = 4.0 dan nilai awal x0 = 0.456, maka kita memperoleh barisan bilangan acak:

x1 = 4.0×0(1 – x0 ) = 0.992256
x2 = 4.0×1(1 – x1 ) = 0.030736
x3 = 4.0×2(1 – x2 ) = 0.119166

x99 = 4.0×98(1 – x98 ) = 0.914379
x100 = 4.0×99(1 – x99 ) = 0.313162

Sebaran 100 buah nilai-nilai chaos di atas diperlihatkan di dalam grafik pada Gambar 2. Nilai-nilai chaos tersebut teletak di antara 0 dan 1 dan tersebar secara merata serta tidak ada dua nilai yang sama. Sebagai referensi, bahasa pemrograman yang digunakan untuk membangkitkan barisan bilangan chaos di atas adalah Bahasa C dengan compiler GCC (GNU C Compiler).

Gambar 3.  Nilai-nilai chaos yang dibangkitkan dari fungsi chaos xi+1 = 4.0 xi (1 – xi)  dengan x0 = 0.456

Jika nilai awal diubah sebesar 0.00001 menjadi x0 = 0.45601, maka setelah iterasi ke-14 nilai chaos mulai lebih besar dari 0.0625 dan semakin lama nilainya  mengalami divergensi dari nilai-nilai chaos ketika x0 = 0.456. Gambar 4 memperlihatkan nilai-nilai chaos yang dibangkitkan setelah iterasi ke-14.

Gambar 4.  Nilai-nilai chaos yang dibangkitkan (setelah iterasi ke-14) dari fungsi chaos xi+1 = 4.0 xi (1 – xi)  dengan x0 = 0.456001

 

Meskipun sistem chaos muncul dengan ketidakteraturan yang tinggi, tetapi ia deterministik artinya dimungkinkan membangkitkan nilai-nilai chaos dengan kepastian (Philip, 2001). Hal ini adalah fitur yang menjanjikan untuk komunikasi secara aman.

(Bersambung pada tulisan selanjutnya)

 

Referensi
1. Sun, T., Cui L., Wang, S., (2002): Research on Technology of Chaos Secrecy Comunication in Digital Watermarking, Spinger-Verlag Berlin Heidelberg.
2. Philip, N., Joseph, K., (2001): Chaos for Stream Cipher, Department of Physics, Cochin University of Science and Technology.
3. Roskin, K., Casper, J., (1999): From Chaos to Cryptography.
4. Robinson, C., (2004): An Introduction to Dynamical Systems, Continuous and Discrete, Pearson Prentice Hall.

3 Komentar

Filed under Chaos