Teori quasigroup telah dikembangkan sangat luas dan telah diaplikasikan dalam berbagai bidang kriptologi, steganografi, dan teori pengkodean. Salah satunya dalam hal enkripsi dan dekripsi. Salah satu algoritma enkripsi dan dekripsi yang menggunakan teori quasigroup adalah sistem Vigenere. Proses enkripsi menggunakan kombinasi dari operasi biner tersebut, kemudian dekripsi dengan menggunakan invers dari operasi tersebut baik invers kiri maupun kanan.
Algoritma kriptografi dengan menggunakan quasigroup ini dapat bekerja pada mode karakter dan mode bit. Untuk mengubah algoritma agar bekerja pada mode bit, cukup mengubah masukan yang diterima menjadi mode bit.
Quasigroup dapat didefinisikan sebagai himpunan berhingga Q bersama-sama dengan operasi biner * pada G dimana invers kiri dan kanan selalu ada dan tunggal. Dengan demikian, persamaan dalam operasi biner tersebut selalu memiliki solusi tunggal. Sifat inilah yang digunakan untuk membangun proses enkripsi dengan menggunakan quasigroup. Proses enkripsi dilakukan dengan melakukan operasi biner * terhadap anggota-anggota quasigroup tersebut dan proses dekripsi dilakukan dengan menggunakan inversnya, bisa menggunakan invers kiri maupun invers kanan.
Dalam teori kombinatorika, quasigroup direpresentasikan dengan sebuah Latin square, yaitu sebuah matriks berukuran n × n dimana setiap baris dan kolom adalah permutasi dari anggota-anggota quasigroup. Tabel yang digunakan dalam Vigenere cipher termasuk salah bentuk Latin square, dengan huruf-huruf alfabet sebagai anggota-anggota quasigroup. Dengan menggunakan Latin square secara umum, algoritma kriptografi Vigenere cipher dapat dibuat lebih general. Hal ini dapat mempersulit proses kriptanalis pada algoritma Vigenere cipher.
Landasan matematika Quasigroup
1. Groupoid
Sebuah groupoid adalah sebuah himpunan berhingga Q bersama-sama dengan sebuah operasi biner * pada Q yang memenuhi a*b ∈Q untuk semua a,b ∈Q. Dengan kata lain, Q tertutup sebagai operasi *. Sebuah grupoid yang memiliki n anggota dapat dinyatakan sebagai sebuah matriks n× n yang anggotanya merupakan anggota grupoid tersebut. Misalnya sebuah grupoid yang memiliki anggota {1,2,3,4} dapat dinyatakan dengan matriks suatu matriks M sebagai berikut
[■(1&3&2&4@2&1&3&4@3&4&1&2@1&2&3&4)]
Dari baris pertama matriks di atas, dapat diketahui bahwa groupoid di atas memenuhi
1*1=1, 1*2=3, 1*3=2, dan 1*4=4
Dan dari baris kedua, dapat diketahui bahwa 2*1=2, 2*2=1, 2*3=3, 2*4=5, dst
Jika bilangan-bilangan 1,2,..,n diasosiasikan dengan setiap anggota groupoid a_1,a_2,…,a_n maka matriks M yang merupakan representasi groupoid tersebut memiliki anggota
M[i,j]=a_i*a_j
Demikian juga sebaliknya. Jika diketahui representasi matriks dari sebuah groupoid, maka hasil operasi tiap anggota groupoid tersebut juga dapat diketahui.
Groupoid tidak memiliki aksioma apapun selain sifat ketertutupan. Operasi pada groupoid tidak harus memiliki sifat asosiatif, komutatif maupun distributif.
2. Quasigroup
Sebuah quasigroup Q adalah grupoid yang memiliki invers kiri dan kanan, yaitu untuk setiap u, v∈Q ada x, y∈Q yang tunggal sehingga x ∗ u = v dan u ∗ y = v. Hal ini berarti juga bahwa operasi pada quasigroup dapat dibalik dan memiliki solusi tunggal. Dengan demikian, kedua operasi invers terhadap operasi pada quasigroup dapat didefinisikan, yaitu invers kiri (left inverse) dan invers kanan (right inverse). Notasi invers kiri adalah \ dan notasi untuk invers kanan adalah /. Karena ketunggalan ini, dapat juga dikatakan bahwa operator \ bersama-sama dengan himpunan berhingga Q mendefinisikan sebuah quasigroup (Q, \) dan untuk aljabar (Q, \, ∗ ). Dalam hal ini berlaku persamaan
x ∗ (x \ y) = y = x \ (x ∗ y)
3. Latin Square
Dengan demikian, representasi matriks dari sebuah quasigroup juga harus memiliki sebuah sifat tambahan, yaitu setiap kolom dan baris pada matriks harus merupakan permutasi dari angota-anggota quasigroup. Dengan kata lain, setiap kolom dan baris pada matris harus mengandung semua anggota-anggota quasigroup. Dalam kombinatorika, matriks semacam ini disebut juga sebagai Latin Square. Contoh sebuah latin square yang paling sederhana adalah sebagai berikut
[■(1&2&3&4@2&3&4&1@3&4&1&2@4&1&2&3)]
Dari matriks tersebut terlihat bahwa setiap kolom dan baris merupakan permutasi dari 1,2,3,4. Kedua matriks pada bagian 2.1 di atas tidak merepresentasikan sebuah quasigroup. Matriks pertama pada bagian 2.1 mengandung tiga buah angka 4 dan sebuah angka 2 pada kolom keempat dan matriks kedua pada bagian 2.1 tidak mengandung angka 3 dan 4 sama sekali.
Pehatikan matriks pada contoh tersebut. Pada baris ketiga terlihat bahwa 1 ∗ 1 = 3, 1 ∗ 2 = 4, 1 ∗ 3 = 1 dan 1 ∗ 4 = 2.
Dengan demikian, 1 \ 3 = 1, 1 \ 4 = 2, 1 \ 1 = 3 dan 1 \ 2 = 4, dan seterusnya.
Aplikasi Quasigroup dalam Kriptografi
Quasigroup memiiiki sifat yang diperlukan dalam proses enkripsi dan dekripsi, yaitu invers yang tunggal. Dengan adanya invers yang tunggal plainteks yang telah dienkripsi dengan menggunakan operasi pada quasigroup selalu dapat dikembalikan dengan proses dekripsi menggunakan invers dari operasi pada quasigroup. Secara matematis, hal ini dapat dinyatakan sebagai D(E(P)) = P, dimana D dan E masing-masing menyatakan fungsi-fungsi dekripsi dan enkripsi. Dengan menggunakan parameter tambahan berupa kunci K, persamaan yang baru dapat dituliskan sebagai DK(EK(P)) = P.
Vigenere cipher merupakan salah satu bentuk khusus dari sebuah algoritma kriptografi yang menggunakan teori quasigroup. Vigenere dapat dibuat dengan mengubah bujur sangkar vigenere yang digunakan dalam proses enkripsi dan dekripsi. Bujursangkar dapat menggunakan Latin Square. Dengan bentuk ini, beberapa sifat vulnerable pada vigenere yang asli dapat dihilangkan, misalnya kesimetrian bujursangkar terhadap diagonal yang ditarik dari sudut kiri atas ke kanan bawah.
Selain vigenere, ada banyak algoritma lain yang menggunakan teori quasigroup. Algoritma-algoritma ini memanfaatkan sifat khusus quasigroup yaitu operasi biner * pada quasigroup selalu memiliki invers kiri dan kanan yang tunggal. Operasi biner yang dikombinasikan tersebut dapat membentuk sebuah fungsi enkripsi E dan invers dari operasi biner tersebut (baik kiri maupun kanan) dapat membentuk sebuah fungsi dekripsi D. Untuk membuat sebuah algorima enkripsi yang lebih kuat dengan quasigroup, fungsi-fungsi tersebut dapat dikomposisikan. Dalam teori quasigroup, dapat dibuktikan bahwa komposisi-komposisi fungsi tersebut tetap memenuhi persamaan enkripsi dan dekripsi yang benar D(E(P))=P
0 komentar:
Posting Komentar