ANALISIS TEORITIS DAN PENERAPAN UJI AUTOKORELASI DARI FIVE BASIC TEST UNTUK MENGUJI KEACAKAN BARISAN BIT
Sari Agustini Hafman dan Arif Fachru Rozi Lembaga Sandi Negara E-mail:
[email protected],
[email protected] Abstrak: uji autokorelasi adalah salah satu uji yang terdapat dalam five basic test yang bertujuan untuk memeriksa korelasi antara barisan bit dengan versi pergeserannya. Untuk membuktikan seberapa baik uji autokorelasi dapat memeriksa korelasi yang terdapat dalam suatu barisan bit maka dilakukan analisis baik secara teoritis maupun empiris. Analisis teoritis dilakukan dengan menerapkan berbagai teori statistik terhadap proses pembentukan statistik uji sedangkan analisis secara empiris dilakukan dengan menerapkan uji tersebut pada barisan bit yang dihasilkan oleh suatu pseudorandon number generator (PRNG). Kata kunci: barisan bit, korelasi, five basic test, uji autokorelasi.
Keamanan sistem kriptografi harus hanya bergantung pada kunci yang digunakan dalam sistem tersebut (Kerckhoffs, 1883). Terdapat tiga tipe keacakan barisan kunci yang dihasilkan oleh Pseudo Random Number Generator (PRNG) atau Random Number Generator (RNG) yaitu pseudorandom sequence (barisan acak semu), cryptographically secure pseudorandom sequences (barisan acaksemu yang aman secara kriptografi) dan real random sequences (barisan yang acak nyata). Untuk menguji tipe keacakan barisan kunci yang dihasilkan oleh suatu PRNG/RNG, pendekatan yang umum dilakukan adalah dengan membangkitkan barisan kunci dalam jumlah besar dan mengaplikasikan berbagai uji statistik. Jika barisan yang dihasilkan PRNG/RNG tersebut lulus dari berbagai uji statistik, hal ini berarti barisan tersebut tidak dapat dibedakan dengan barisan yang acak nyata. Henry Beker dan Fred Piper (1982) mengajukan lima uji statistik untuk menganalisis keacakan barisan kunci yang dihasilkan oleh suatu PRNG/RNG. Kelima
uji statistik tersebut dinamakan five basic test. Jika suatu barisan bit lulus five basic test maka barisan bit tersebut dinyatakan acak secara lokal atau local randomness (Henry Beker dan Fred Piper, 1982). Kelima uji tersebut adalah uji frekuensi, uji serial, uji poker, uji run dan uji autokorelasi. Analisis teoritis dengan menggunakan pendekatan matematis terhadap uji frekuensi, uji serial dan uji poker telah dilakukan pada tahun 2008 (Hafman, S.A. & Yulianingsih, N., 2008). Oleh karena itu, pada tulisan ini akan dibahas uji lainnya yaitu uji autokorelasi. Untuk membuktikan seberapa baik uji autokorelasi dapat memeriksa korelasi yang terdapat dalam suatu barisan bit maka dilakukan analisis baik secara teoritis maupun empiris. Analisis teoritis dilakukan dengan menerapkan berbagai teori statistik terhadap proses pembentukan statistik uji sedangkan analisis secara empiris dilakukan dengan menerapkan uji tersebut pada barisan bit yang dihasilkan oleh suatu PRNG.
825
Hafman dan Rozi, Analisis Teoritis,826
KAJIAN PUSTAKA Distribusi Bernoulli Suatu distribusi Bernoulli dibentuk oleh suatu percobaan Bernoulli (Bernoulli trial). Sebuah percobaan Bernoulli harus memenuhi syarat: 1. Keluaran (outcome) yang mungkin hanya salah satu dari “sukses” atau “gagal” 2. Jika probabilitas sukses p, maka probabilitas gagal q = 1 – p. Dalam sebuah percobaan Bernoulli, dengan p adalah probabilitas “sukses” dan q = 1 – p adalah probabilitas gagal, dan jika X adalah variabel acak yang menyatakan sukses, maka dapat dibentuk sebuah distribusi probabilitas Bernoulli sebagai fungsi probabilitas sebagai berikut: ( ) ( ) dengan dan . Distribusi Binomial Distribusi binomial berasal dari percobaan binomial yaitu suatu proses Bernoulli yang diulang sebanyak n kali dan saling bebas. Secara langsung, percobaan binomial memiliki ciri-ciri sebagai berikut : 1. Percobaan Bernoulli dilakukan berulang-ulang sebanyak n kali. 2. Setiap percobaan menghasilkan keluaran yang dapat dikatagorikan sebagai gagal dan sukses. 3. Probabilitas sukses p tetap konstan dari satu percobaan ke percobaan lain. 4. Percobaan yang berulang adalah saling bebas. Percobaan Bernoulli dapat menghasilkan suatu sukses dengan probabilitas p dan gagal dengan probabilitas q = 1 – p maka distribusi probabilitas variabel acak binomial X dengan jumlah sukses di dalam n percobaan diberikan oleh ( dengan ( )
)
( )
(
)
.
Distribusi Normal Distribusi Normal adalah model distribusi kontinu yang penting dalam teori probabilitas. Distribusi normal memiliki kurva berbentuk lonceng yang simetris. Dua parameter yang menentukan distribusi normal adalah mean ( ) dan variansi ( ). Fungsi kerapatan probabilitas dari distribusi normal adalah: (
( )
)
√ dengan adalah rata-rata, adalah variansi dan Teorema Limit Pusat : Jika ̅ adalah mean dari sampel acak berukuran n yang diambil dari suatu populasi dengan mean dan variansi maka bentuk limit dari distibusi ̅ ⁄ dengan adalah berdistribusi ( ). Pseudorandom Number Generator (PRNG) Definisi 1 (Schneier,1996): PRNG adalah pembangkit barisan bilangan acaksemu, yang membutuhkan seed (input) dengan proses pembangkitan tiap elemen tergantung dari formulasi matematis yang digunakan pada PRNG tersebut. Proses pembangkitan tiap elemen dari PRNG memiliki hubungan linier sesuai fungsi matematis yang digunakan, sehingga untuk meminimalisir kelinierannya, digunakan fungsi non-linier dan pengaturan parameter inputnya. Untuk memenuhi sifat unpredictable, pada umumnya PRNG menggunakan input berupa barisan bit acak yang berasal dari suatu RNG (Random Number Generator). Uji Autokorelasi Uji autokorelasi merupakan salah satu uji statistik yang terdapat dalam five basic test. Pada uji ini, diasumsikan bahwa adalah barisan bit dengan panjang n dan merupakan variabel acak
827, KNPM V Universitas Negeri Malang, Juni Tahun 2013
karena merupakan kejadian saling bebas dimana . Tujuan dari uji autokorelasi adalah untuk memeriksa korelasi antara barisan bit dengan versi pergeserannya (Menezes,dkk., 1996). Misalkan d adalah bilangan bulat dengan ⌊ ⌋. Jumlah bit dalam barisan s yang tidak sama dengan barisan s yang telah ( ) digeser sejauh d adalah ∑ dengan adalah operasi XOR. Operasi XOR merupakan operasi logika bitwise yang bekerja dengan membandingkan dua buah bit yang apabila pada salah satu bitnya bernilai benar (dinotasikan dengan bit 1) maka hasil akhir operasi XOR tersebut adalah benar. Namun, bila kedua bit yang akan dibandingkan bernilai salah (dinotasikan dengan bit 0) atau benar maka hasil akhirnya adalah salah. Statistik ujinya adalah : ( ( ) ) √ mendekati distribusi .
(
) jika
METODE Penelitian ini terdiri atas dua tahap yaitu penelitian secara teoritis dan secara empiris. Berikut penjelasan dari kedua metode tersebut. Penelitian Secara Teoritis Penelitian secara teoritis dilakukan dengan menerapkan berbagai teori statistik untuk membuktikan proses pembentukan statistik uji autokorelasi dan panjang barisan minimal yang harus dipenuhi agar hasil uji autokorelasi valid. Penelitian Secara Empiris Untuk membuktikan seberapa baik uji autokorelasi dapat memeriksa korelasi yang terdapat dalam suatu barisan bit maka dilakukan analisis secara empiris dengan menerapkan uji autokorelasi pada 30 barisan bit yang dihasilkan oleh PRNG Mersenne
Twister dengan menggunakan d yang berbeda baik d acak maupun terurut. Jumlah d yang dipilih secara acak adalah 70 buah atau sekitar 1,4 % dari 5000 kemungkinan nilai d. Untuk d terurut digunakan sebanyak 9 buah mulai dari d = 2 s.d. d = 10. Panjang barisan bit yang dibangkitkan adalah 10.000 bit dengan tingkat kepercayaan ( ) yang digunakan adalah 0,05 dan hipotesis nol ( ) pada uji ini adalah barisan acak atau tidak ada korelasi antara barisan bit dengan versi pergeserannya. Jika maka diterima atau barisan dikatakan acak. Jika tidak demikian maka ditolak atau barisan dikatakan tidak acak. HASIL DAN PEMBAHASAN Analisis Teoritis Pembentukan Statistik Uji Pada tahap ini dengan menerapkan berbagai teori statistik akan ditunjukkan ( ( )
bahwa
)
√
mendekati (
).
Berikut ini adalah hasil analisis teoritisnya. Misalkan s adalah barisan bit yang dibangkitkan oleh PRNG dengan ( ) adalah jumlah bit dalam barisan s yang tidak sama dengan barisan s yang telah digeser sejauh d. adalah bit ke-i dari barisan yang bernilai 0 atau 1 merupakan kejadian bernoulli sehingga ( )
.
Misalkan bila
maka : atau
dan
bila
(
)
(
Nilai harapan dari ( )
∑
atau ) sama dengan
karena
( )
Untuk menghitung ragam dari x terlebih ( ) karena dahulu dihitung nilai ( )
(
)
( ( )) .
Hafman dan Rozi, Analisis Teoritis,828
Karena x merupakan variabel acak diskrit maka (
)
( )
∑
( )
sehingga
( )
( ) ∑ Misalkan ∑ maka ( ) merupakan kejadian binomial sehingga nilai harapan dari ( ) adalah ( ( ))
( ∑
)
( ( ( ))
dengan ( )
∑
) ( )
( ∑
∑
)
( )
Untuk mencari statistik uji dari uji ( ) distandarisasi autokorelasi maka sehingga ( ) ( ) ( ( )) √
( ( ))
( ( )
√
)
√ Berdasarkan Central Limit Theorem (CLT), untuk distribusi dari ( ( ) √
)
mendekati (
agar pendekatan tersebut valid, ukuran sampelnya paling sedikit adalah 20. 2. Banyaknya pergeseran (d) pada uji autokorelasi maksimal hanya sebanyak ⌊ ⌋. Dengan menggunakan pernyataan pada poin 1 dan 2 akan ditunjukkan panjang minimal yang harus dipenuhi agar suatu barisan dapat diuji dengan menggunakan uji autokorelasi. Berdasarkan poin 1 diperoleh pertidaksamaan . Pertidaksamaan tersebut dapat dinyatakan juga dengan pertidaksamaan yang sama nilainya
).
Panjang Barisan Minimal Pada subbab ini akan ditunjukkan bahwa mendekati distribusi ( ) jika . Berikut adalah penjelasannya. Pada uji autokorelasi terdapat beberapa hal yang harus dipenuhi yaitu : 1. Uji autokorelasi berdasarkan atas distribusi pendekatan normal sehingga
. Karena
merupakan
nilai maksimal yang diperbolehkan dari d maka dapat dinyatakan dengan d sehingga diperoleh . Atau dengan kata lain, panjang barisan bit minimal agar hasil uji autokorelasi valid adalah . Analisis Empiris Hasil pengujian dengan menggunakan uji autokorelasi pada barisan yang dihasilkan oleh PRNG Mersenne Twister ditampilkan dalam bentuk tabel. Tabel 1 memperlihatkan hasil uji autokorelasi dengan 70 buah d yang dipilih secara acak pada sebuah barisan bit berukuran 10000 bit yang dibangkitkan PRNG Mersenne Twister. Tabel 1 Hasil Uji Autokorelasi dengan 70 d Berbeda
829, KNPM V Universitas Negeri Malang, Juni Tahun 2013
Berdasarkan informasi dari Tabel 1, terdapat 5 barisan bit yang memiliki korelasi dengan versi pergeserannya yaitu ketika d = 2,3,4,321 dan 909 atau sebesar 7,143%. Selain menerapkan uji autokorelasi dengan menggunakan d acak, dilakukan juga pengujian terhadap 30 barisan bit lain yang dihasilkan oleh PRNG Mersenne Twister. Ke-30 barisan tersebut selanjutnya diuji dengan menggunakan nilai d terurut, mulai dari d = 2 s.d. d = 10. Hasil uji beserta kesimpulan terhadap ke-30 barisan bit tersebut disajikan pada Tabel 2 dan Tabel 3.
Tabel 3 Kesimpulan Hasil Uji Autokorelasi pada 30 Barisan Bit dengan
Tabel 2 Hasil Uji Autokorelasi pada 30 Barisan Bit dengan 10 d Berbeda
Pada Tabel 3 terlihat bahwa terdapat 9 barisan bit yang tidak lulus uji ketika di seluruh d, diantaranya barisan 1, 2,7. Berdasarkan Tabel 1 dan Tabel 3 dapat disimpulkan bahwa uji autokorelasi cukup efektif untuk mendeteksi adanya korelasi antara barisan bit dengan versi pergeserannya baik ketika pergeserannya kecil maupun ketika pergeseran bitnya besar (mendekati ⌊ ⌋). PENUTUP Kesimpulan Berdasarkan hasil penelitian dapat disimpulkan bahwa : 1. Pada uji autokorelasi, jumlah bit dalam barisan yang tidak sama dengan versi pergeserannya merupakan kejadian binomial sehingga dengan menggunakan central limit theorem diperoleh bahwa statistik uji autokorelasi mendekati distribusi normal baku. 2. Panjang barisan bit minimal agar hasil uji autokorelasi valid dan jumlah pergeseran maksimal adalah sebesar dengan n adalah panjang
Hafman dan Rozi, Analisis Teoritis,830
barisan bit dan d adalah banyaknya pergeseran. . 3. Hasil uji autokorelasi terhadap satu barisan bit yang berasal dari PRNG Mersenne Twister dengan 70 d acak maupun terhadap 30 barisan bit dengan menggunakan d terurut menunjukkan uji
autokorelasi cukup efektif untuk mendeteksi adanya korelasi antara barisan bit dengan versi pergeserannya baik ketika pergeserannya kecil ( ) maupun ketika pergeseran bitnya besar ( ⌊ ⌋).
DAFTAR RUJUKAN Beker, H. & Piper. 1982. Cipher System The Protection of Communications. London. Northwood Books Hafman,S.A. & Yulianingsih, N. 2008. Analisis Matematis Terhadap Tiga Uji Keacakan Pada Five Basic test dengan Menggunakan Teori-Teori Statistika. Prosiding Konferensi Nasional Matematika XIV. Universitas Sriwijaya Palembang.
Kerckhoffs,A. 1883. La Cryptographic Militaire. Journal des Sciences Militaires IX, 5-38. Menezes, dkk. 1996. Handbook of Applied Cryptogaphy. CRC Press Inc. Schneier B. 1996. Applied Cryptography : Protocols, Algorithms and Source Code in C 2nd Edition. Canada. John Wiley & Sons.
