One Time Pad (OTP) Cipher

<<Vigenere Cipher

One Time Pad ini ditemukan pada tahun 1917 oleh Major Yoseph Mouborgnedan Gilbert Vernam pada perang dunia ke dua. Metode ini telah diklaim sebagai satu-satunya algoritma kriptografi sempurna yang tidak dapat dipecahkan. Suatu algoritma dikatakan aman, apabila tidak ada cara untuk menemukan plaintext-nya. Sampai detik ini, ya detik sekarang, mungkin sampai akhir dari dunia ini, hanya algoritma One Time Pad (OTP) yang dinyatakan tidak dapat dipecahkan meskipun diberikan sumber daya yang tidak terbatas. Algoritma One Time Pad adalah salah satu jenis algoritma simetri (kriptografi konvensional dimana kunci yang digunakan enkripsi sama dangan kunci yang digunakan untuk dekripsi). Baru-baru ini algoritma OTP sudah dapat diimplementasikan dengan menggunakan teknologi Quantum Computer oleh China untuk mengamankan video call/conference.

Pada kriptografi OTP, jumlah kunci sama panjangnya dengan jumlah plainteks. Jika anda ingin agar cipherteks sulit untuk di pecahkan maka pemakaian kunci seharusnya :

• Jangan gunakan kunci yang berulang
• Pilihkan kunci yang random

Pemakaian One Time Pad digunakan pada sederetan abjad A..Z dengan memberikan nilai urutan abjad yaitu A=0, B=1, C=2, D=3, E=4…..sampai Z.

Rumus melakukan One Time Pad ini yaitu :

Enkripsi : \(E_{i}=\left(P_{i}+K_{i}\right)\bmod 26\)

Dekripsi : \(P_{i}=\left(E_{i}-K_{i}\right)\bmod 26\)

Atau, pada hardware biasanya menggunakan  operasi XOR (\(\oplus\)) dengan data biner (plaintext dan key dirubah ke dalam format biner). Operasi ini tentu lebih cepat pada hardware :

Enkripsi : \(E_{i}=P_{i}\oplus K_{i}\)

Dekripsi : \(P_{i}=E_{i}\oplus K_{i}\)

• Kelebihan One-Time Pad

Beberapa kelebihan One-time pad adalah sebagai berikut :

1.  Sistem OTP tidak dapat dipecahkan karena: 

• Barisan kunci acak + plaintext yang tidak acak menghasilkan ciphertext yang seluruhnya acak (Artinya, plaintext yang dienkripsi dengan kunci yang panjangnya sama dengan plaintext dan kuncinya acak akan menghasilkan chipertext yang seluruhnya acak).
• Mendekripsi ciphertext dengan beberapa kunci berbeda dapat menghasilkan plaintext yang bermakna (punya arti) sehingga kriptanalis bingung untuk menentukan plaintext mana yang benar.

2.  Algoritma Vernam atau One-time pad merupakan algoritma pengenkripsian data dan informasi yang relatif sederhana dan mudah digunakan namun cukup aman dalam menjamin kerahasiaan informasi atau data yang ingin dikirimkan. 

• Kelemahan One-Time Pad

1.  Algoritma ini tidak efesien karena panjang kunci = panjang pesan sehingga ada beberapa permasalahan yang timbul yaitu jika pesannya sangat besar maka : 

• Pembangkitan kunci acak yang besar sangat akan membutuhkan kerja berat pada sistem, 
• Penyimpanan juga membutuhkan memori yang besar, karena datanya secara otomatis menjadi dua kali lipat yaitu kunci dan chipertext yang sama panjang. 
• Pendistribusian kunci juga menjadi kendala yang sangat berarti. Untuk menjaga keamanan OTP maka secara otomatis kita tidak bisa mengirimkan kunci dan chipertext pada kanal yang sama, harus digunakan kanal yang berbeda saat pengiriman kunci dan chipertext agar jika terjadi penyadapan oleh serangan Man In The Middle maka kunci dan chipertext tidak didapatkan. (Contoh penggunaan kanal berbeda misal data chipertext dikirim lewat media 4G maka chipertext bisa dikirim melalui media lain seperti Satelit dll).

2.  Jika sebuah kunci sudah digunakan maka kunci tersebut tidak bisa digunakan kembali, penggunaan kunci yang sama akan berpengaruh terhadap kerahasiaan pesan. Dengan demikian semakin sering OTP digunakan, jumlah kunci semakin berkurang.

3. Kerahasiaan dalam pendistribusian kunci menjadi hal yang penting dimana untuk mengirimkan kunci membutuhkan saluran komunikasi kedua agar keamanan lebih terjamin. Akan tetapi biasanya saluran komunikasi kedua lebih lambat dan mahal sehingga untuk mengirimkan kunci yang berukuran besar akan menjadi tidak efesien.

Berikut adalah contoh OTP dengan menggunakan modulo 26 :
One-time pad algoritma sebagai berikut:

Vigenere Cipher

<<Hill Cipher
Vigenere Cipher merupakan polyalphabetic substitution cipher yang paling sederhana dan paling banyak dikenal. Sandi Vigenere sebenarnya merupakan pengembangan dari sandi Caesar. Pada sandi Caesar, setiap huruf teks terang digantikan dengan huruf lain yang memiliki perbedaan tertentu pada urutan alfabet. Misalnya pada sandi Caesar dengan geseran 3, A menjadi D, B menjadi E and dan seterusnya. Sandi Vigenère terdiri dari beberapa sandi Caesar dengan nilai geseran yang berbeda. Kelebihannya dibanding Caesar Cipher dan cipher monoalfabetik lainnya adalah cipher ini tidak begitu rentan terhadap metode pemecahan cipher yang disebut analisis frekuensi.

• CARA KERJA VIGENERE CIPHER

Untuk menyandikan suatu pesan, digunakan sebuah tabel alfabet yang disebut tabel Vigenère (gambar di samping kanan). Tabel Vigenere berisi alfabet yang dituliskan dalam 26 baris, masing-masing baris digeser satu urutan ke kiri dari baris sebelumnya, membentuk ke-26 kemungkinan sandi Caesar. Setiap huruf disandikan dengan menggunakan baris yang berbeda-beda, sesuai kata kunci yang diulang

Misalnya, plaintext yang hendak disandikan adalah perintah "SERBU BERLIN", sedangkan kata kunci antara pengirim dan penerima adalah "PIZZA". Maka kata kunci "PIZZA" diulang sehingga jumlah hurufnya sama banyak dengan plaintext-nya: "PIZZAPIZZAP".

Huruf pertama pada plaintext, yaitu huruf S, disandikan dengan menggunakan huruf pertama pada kata kunci yaitu huruf P. Pada baris P dan kolom S di tabel Vigenere, terdapat huruf H sehingga ciphertext huruf pertama adalah huruf H. Demikian pula untuk huruf kedua, digunakan huruf yang terletak pada baris I (huruf kedua kata kunci) dan kolom E (huruf kedua plaintext), yaitu huruf M. Proses ini dijalankan terus sampai selesai. Sehingga menjadi seperti ini :

Plaintext         : S  E  R B U B E  R  L  I   N

Kata kunci      : P  I   Z Z  A P I   Z  Z  A P

Ciphertext      : H M Q A U Q M Q K  I  C

Proses dekripsi dilakukan dengan mencari huruf ciphertect pada baris huruf dari kata kunci. Misalnya, pada contoh di atas, untuk huruf pertama, kita mencari huruf H (huruf pertama ciphertext) pada baris P (huruf pertama pada kata kunci), yang terdapat pada kolom S, sehingga huruf pertama adalah S. Lalu M terdapat pada baris I di kolom E, sehingga diketahui huruf kedua plaintext adalah E, dan seterusnya hingga selesai. Maka akan didapatkan plaintext  "SERBU BERLIN".

Enkripsi dengan Vigenere Cipher juga dapat dituliskan secara matematis, dengan menggunakan penjumlahan dan operasi modulus, yaitu: \[C_{i}\equiv \left(P_{i}+K_{i} \right)\bmod26\] Dekripsinya dapat dituliskan sebagai berikut : \[P_{i}\equiv \left(C_{i}-K_{i} \right)\bmod26\]

Berikut adalah contoh implementasinya pada Sagemath:

Berikut ini adalah contoh Enkripsi dan Dekripsi Vigenere Cipher dengan Kunci Acak.

Berikut adalah contoh implementasi Vigenere Cipher menggunakan Bahasa Python yang telah di-parse dengan Sage.

One-time pad Cipher>>

Hill Cipher

<<Affine Cipher

• HILL OR MATRIX CIPHER. 

Hill Cipher diciptakan oleh Lester S. Hill pada tahun 1929 [2]. Teknik kriptografi ini diciptakan dengan maksud untuk dapat menciptakan cipher (kode) yang tidak dapat dipecahkan menggunakan teknik analisis frekuensi. Hill Cipher tidak mengganti setiap abjad yang sama pada plaintext dengan abjad lainnya yang sama pada ciphertext karena menggunakan perkalian matriks pada dasar enkripsi dan dekripsinya.

Hill Cipher yang merupakan polyalphabetic cipher dapat dikategorikan sebagai block cipher [2] karena teks yang akan diproses akan dibagi menjadi blok-blok dengan ukuran tertentu. Setiap karakter dalam satu blok akan saling mempengaruhi karakter lainnya dalam proses enkripsi dan dekripsinya, sehingga karakter yang sama tidak dipetakan menjadi karakter yang sama pula.

Hill Cipher termasuk algoritma kriptografi klasik yang sangat sulit dipecahkan oleh kriptanalis apabila kriptanalisis-nya hanya dengan mengetahui berkas ciphertext saja. Namun, teknik ini dapat dipecahkan dengan cukup mudah apabila seorang kriptanalis memiliki berkas ciphertext dan potongan berkas plaintext. Teknik kriptanalisis ini disebut known-plaintext attack [1].

• ALGORITMA HILL CIPHER.

Algoritmanya yaitu Hill Cipher mengenkripsi plaintext sepanjang m menjadi ciphertext dengan panjang yang sama (m). Substitusinya ditentukan oleh persamaan linier m dimana masing-masing karakter diganti dengan nilai nominal (a=0, b=1, ..., z=25). Untuk m=3, sistemnya seperti berikut :

\[c_{1}=(k_{11}p_{1}+k_{21}p_{2}+k_{31}p_{3})\bmod 26\]

\[c_{2}=(k_{12}p_{1}+k_{22}p_{2}+k_{32}p_{3})\bmod 26\]

\[c_{3}=(k_{13}p_{1}+k_{23}p_{2}+k_{33}p_{3})\bmod 26\]

Jika digambarkan dalam vektor baris dan matriks adalah sebagai berikut :

\[(c_{1}c_{2}c_{3})=(p_{1}p_{2}p_{3})\begin{bmatrix}k_{11} & k_{12} & k_{13} \\k_{21} & k_{22} & k_{23}\\k_{31} & k_{32} & k_{33} \end{bmatrix}\bmod 26\]

\[C=PK\bmod26\]

dimana C dan P adalah vektor baris dengan panjang 3 dan K adalah kunci enkripsi berupa matriks berukuran 3 x 3. Operasi dilakukan dengan modulo 26.

Berikut adalah contoh Enkripsi & Dekripsi  Hill Cipher dengan menggunakan library pada Sagemath. Pembuat library Hill Cipher pada Sage adalah David Kohel (2007) [3]. 

Membuat cryptosystem Hill Cipher yang didefinisikan oleh ruang matriks m x m pada Z/NZ, di mana N adalah ukuran alfabet dari string monoid S.

Berikut adalah contoh Enkripsi dan Dekripsi Hill Cipher dengan menggunakan Random Key.

Catatan:

1. Plaintext yang akan dienkripsi panjangnya harus merupakan kelipatan m (ukuran matrix yg digunakan sebagai kunci).
2.  Plaintext harus sudah dalam format encoding (tidak ada lagi spasi, huruf kecil dan tanda baca).

Berikut ini adalah contoh Hill Cipher tanpa menggunakan library dari Sage. Hill Cipher di bawah ini dibuat menggunakan Bahasa Pemrograman Python yang sudah disesuaikan (preparse) dengan Sage[4]:

• KRIPTANALISIS HILL CIPHER.

Kriptanalisis terhadap Hill Cipher sangat sulit jika dilakukan dengan ciphertext-only attack, apalagi jika matriks kunci yang digunakan berukuran besar. Kesulitan ini disebabkan oleh ciphertext Hill Cipher tidak memiliki pola dan setiap karakter dalam satu blok saling mempengaruhi karakter lainnya.

Teknik yang dapat digunakan untuk melakukan kriptanalisis terhadap Hill Cipher adalah known-plaintext attack. Jika kriptanalisis memiliki pecahan plaintext dan ciphertext yang saling berkorespondensi, maka Hill Cipher dapat dipecahkan. Namun proses yang cukup sulit adalah untuk menentukan panjang kunci yang digunakan. Hal ini menjadi salah satu kekuatan yang dimiliki oleh Hill Cipher. Cara yang dapat dilakukan hanya dengan mencari tahu panjang kunci atau dengan melakukan perkiraan dan percobaan.

Referensi:

1. Anton, Howard, Rorres, Chris, Elementary linear algebra, John Wiley & Sons, 2011
2. Forouzan, Behrouz, Cryptography and Network Security, McGraw-Hill, 2006
3. Stalling, William, Cryptography and Network Security, Pearson, 2014
4. https://github.com/rhtyd/hacklab/blob/master/labwork/Security/hill-cipher.py

Vigenere Cipher>>

Interact pada Sage

Interact.

Aritmatika Polinomial pada Finite Field (GF)

<<Teori Bilangan
Berikut adalah contoh artimatika polinomial (penjumlahan, perkalian dan invers) pada Galois Field (GF) menggunakan Sage:

• \(GF(2^{3})\)

Pertama-tama kita definisikan kembali x dalam \(GF(2^{3})\), setelah itu kita bisa melakukan operasi penjumlahan dan perkalian pada polinomial tersebut seperti di bawah ini:

Setelah kita definisikan x dalam \(GF(2^{3})\), kita bisa melakukan operasi penjumlahan dan perkalian pada polinomial tersebut seperti di bawah ini:

Jika kita hitung secara manual hasil perkalian adalah sebagai berikut:
\(\Rightarrow\)  \((x^{2}+x+1)*(x^{2}+x+1)\)
\(\Rightarrow\)      \((x^{4}+x^{3}+x^{2}\)
                       \(x^{3}+x^{2}+x\)
                                 \(x^{2}+x+1\)
          ----------------------------------------  \(\oplus\)
             \(x^{4}+    0    +x^{2}+0+1\)

Setelah kita dapat \(x^{4}+x^{2}+1\), kita mod m(x) dimana m(x) untuk \(GF(2^{3})\) adalah \(x^{3}+x+1\).

                                    \(x\)
\(\Rightarrow\) \(x^{3}+x+1\sqrt{x^{4}+x^{2}+1}\)
                                  \(x^{4}+x^{2}+x\)
                               ---------------------------  -
                                           \(-x+1\)
                                         = \(x+1\)

• \(GF(2^{8})\)

Pertama-tama kita definisikan kembali x dalam \(GF(2^{8})\), setelah itu kita bisa melakukan operasi penjumlahan dan perkalian pada polinomial tersebut seperti di bawah ini:

Untuk mencari invers maka kita perlu pendefinisian tambahan seperti di bawah ini:

Ada beberapa hal yang perlu diperhatikan di sini bahwa:

1. Sage menggunakan modulus default pada operasi Polinomal pada Finite Field. Modulus default dapat dilihat dengan perintah: R.modulus(). Modulus yang berbeda akan menghasilkan hasil operasai yang berbeda. Be careful!
2. Jika ingin menggunakan modulus buatan sendiri, gunakan perintah seperti di atas.

Next>>

Pengenalan tentang Kriptografi

Kriptografi bukan hanya ilmu untuk membuat sebuah kode atau memecahkan sebuah kode. Kriptografi adalah analisis matematis dari sebuah tool yang digunakan untuk menjaga kerahasiaan, baik dari sudut pandang seseorang yang menyimpan rahasia dan orang yang berusaha mengetahuinya. Terkadang disebut juga Kriptologi yaitu gabungan dari ilmu kriptografi dan analisis sandi (Cryptanalysis).  Ada dua jenis pengkodean yang kita kenal yaitu :

1. Pengkodean yang digunakan untuk menyamarkan informasi dan dimaksudkan untuk tetap dirahasiakan. (khusus untuk mereka yang membutuhkan komunikasi yang bersifat pribadi/rahasia.) 
2. Pengkodean  yang digunakan untuk merangkum/meringkas informasi dalam format yang mudah digunakan, tidak memerlukan kerahasiaan. (terutama untuk memungkinkan pemeriksaan kesalahan.).

Encoding and decoding

Ada banyak cara untuk mengkodekan sebuah pesan. Yang paling mudah bagi kita adalah dengan hanya mewakili setiap huruf alfabet dalam Bahasa Inggris dengan bilangan bulat dari 1 sampai 26. Kita akan menggunakan Interactive Shell di bawah ini untuk mengubah pesan menjadi angka dan sebaliknya. Kita menyandikan pesan plaintext (tidak menggunakan spasi dan tanda petik), yang sebelumnya dirubah dulu menjadi huruf kapital kemudian kita bisa men-decode bilangan bulat positif (positive integer) tersebut kembali menjadi plaintext-nya.

Sekarang kita coba meng-encode dan men-decode huruf r, (Sebelum menjalankan interactive shell yang menggunakan fungsi encode dan decode, jangan lupa untuk menjalankan interactive shell yang berisi definisi encode dan decode seperti di atas, karena fungsi tersebut tidak termasuk ke dalam library Sage).

Berikutnya kita coba meng-encode kalimat dalam bahasa Ingris seperti di bawah ini (tentunya tanpa spasi dan tanda baca apapun).

Dari hasil encode di atas, dapat kita lihat bahwa terjadi banyak pengulangan angka seperti angka 5 untuk huruf E dan angka 1 untuk huruf A. Bandingkan dengan encoding dengan menggunakan 2 (dua) blok huruf dan 3 (tiga) blok huruf seperti di bawah ini.

Encode menggunakan 2 (dua) blok huruf, kita hanya melihat sekali pengulangan angka 228 yaitu pengulangan untuk huruf 'th' (kombinasi dua huruf yang paling sering muncul dalam bahasa Inggris). Dengan encode 2 (dua) blok huruf ini akan ada \(26^{2}=676\) kemungkinan kita bisa mengkombinasikan huruf-huruf tersebut. Bagaimana dengan encode menggunakan 3 (tiga) blok huruf? Akan ada \(26^{3}=17.576\) kombinasi. Akan tetapi perlu diingat bahwa saat ini kita hanya mengkodekan, belum membuat sesuatu yang sifatnya rahasia.

Encode menggunakan 3 (tiga) blok huruf sebagai berikut:

Sudah tidak terlihat lagi adanya pengulangan angka hasil encoding.

Caesar Cipher>>

Teori Bilangan

<<Finite Groups & Abelian Groups

Number Theory.  Sage memiliki fungsionalitas yang luas untuk teori bilangan. Misalnya, kita bisa melakukan aritmatika di \(Z/NZ\) sebagai berikut:

Sage berisi fungsi teori bilangan. Berikut beberapa contohnya :

Fungsi Sage sigma (n, k) menambahkan power \(k^{th}\) dari pembagi n:

Selanjutnya akan digambarkan penggunaan algoritma Extended Euclidean, fungsi Euler, dan Chinese remainder theorem:

Aritmatika Polinomial pada Finite Field>>

Finite Groups, Abelian Groups

<<Polinomial

Sage memiliki beberapa dukungan untuk permutasi groups, finite classical groups (seperti \(SU(n,q)\)), finite matrix groups(dengan generator buatan kita sendiri), dan abelian groups (bahkan sampai infinite). Sebagian besar ini diimplementasikan dengan menggunakan antarmuka GAP packages. Misalnya, untuk membuat permutasi group, diberikan daftar generator, seperti pada contoh berikut.

Sage juga mendukung classical dan matrix groups pada bidang yang  terbatas (finite field) :

Kita juga bisa menghitung menggunakan abelian groups (infinite dan finite):

Teori Bilangan>>