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

3 responses to “Kriptografi Berbasis “Chaos” (Bagian 1)

  1. Ferry

    Saya ada sedikit yg mengganjal…
    Pada contoh di atas, digunakan aplikasi numerik, yang tentunya menggunakan floating point dalam perhitungannya. Penggunaan floating point tentu menimbulkan galat hitung (akibat pembulatan), walaupun awalnya kecil, namun jika digunakan dalam fungsi rekursif bisa terus membesar. Apalagi jika fungsinya menggunakan floating point secara eksponensial.

    saya mencoba mencari hasil analitik (aljabar) dari fungsi diatas, dengan r = 4.0 dan x0 = 0.456 dengan bantuan wolframalpha. Didapat hasil:

    xn = sin^2(2^(-1+n) cos^(-1)(11/125))

    sehingga,

    x100 = 0.1755187963

    galatnya cukup besar jika dibandingkan dengan hasil perhitungan di atas.. cmiiw

    • Mas Ferry, perbedaan tersebut bisa disebabkan oleh beberapa faktor, misalnya tipe data yang digunakan, cara pembulatan yang dilakukan oleh mesin/compiler, dan lain-lain.

      Saya memprogramnya dengan bahasa C dengan compiler GCC. Kode programnya adalah sebagai berikut:

      #include stdio.h
      #include math.h

      main()
      {
      double x;
      int i;
      double r = 4.0;
      FILE *output;
      output = fopen(“hasil.txt”, “w”);
      x = 0.456;
      for (i = 1; i <= 100; i++) {
      x = r * x * (1 – x);
      fprintf(output, "%lf \n", x);
      }
      fclose(output);
      }

      Tipe data yang saya gunakan adalah double, dan hasilnya adalah seperti yang saya tulis di atas. Saya coba ulang lagi mengkompilasinya dan menjalankannya, hasilnya tetap sama.

      Untuk menjawab penasaran, saya coba bandingkan hasilnya jika dihitung dengan Microsoft Excel. Hasilnya berbeda, yaitu x100 = 0.996604982. Perbedaan dengan Excell sudah terlihat pada iterasi ke-45, di Excel x45 = 0.001347643, sedangkan hasil dari program saya x45 = 0.000956.

      Jika diprogram dengan Matlab, hasilnya sama seperti Excell. Saya kurang tahu kenapa hasil dengan Wolfram alpha tidak sama dengan hasil dari program C, Matlab, dan Excell.

  2. Ferry

    Mas Rinaldi,
    Benar, galat yg timbul diatas diakibatkan oleh pembulatan floating point. Sebagai perbandingan, saya menggunakan perkakas “Bc” (http://gnuwin32.sourceforge.net/packages/bc.htm). “Bc” mampu mengubah presisi perhitungan internal floating point sesuai dengan kebutuhan pengguna.

    Berikut kode yg saya jalankan di “Bc”:

    scale = 200
    x = 0.456
    for(i=1; i<=100; i=i+1) {
    x = 4 * x * (1-x)
    print "x", i, "= " , x , "\n"
    }

    kode di atas, menggunakan scale 200, artinya, perhitungan akan akurat sampai 200 angka dibelakang koma. Hasilnya x100= 0.1755187963164… Ini sesuai dengan hasil hanpiran dr solusi analitik (wolframalpha).

    Sedangkan jika scale-nya yg digunakan adalah 20 angka dibelakang koma, didapatkan hasil x100= 0.377180974…

    Dengan membandingkan 2 hasil diatas, tampak bahwa, baik excel, matlab maupun aplikasi C tidak cukup presisi untuk menghitung rekursif chaos ini secara langsung.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s