Waktu aku ditulis, penulisku sedang mendapatkan tugas kecil membuat implementasi algoritma RSA mungkin sebab itulah aku ditulis. Bagi yang masih asing dengan kriptografi, RSA adalah sebuah algoritma kriptografi (baca: penyandian) yang memiliki kunci enkripsi (pengunci) dan dekripsi (pembuka) yang berbeda. Algoritma ini mendasarkan diri pada masalah matematika klasik: mengalikan dua bilangan lebih mudah dibanding mencari faktor nya. RSA kini banyak dipakai dalam skema otentifikasi hubungan antara dua aplikasi di dunia internet.

Summer Wars adalah anime yang di dalamnya terdapat kental dengan unsur teknologi dan juga kriptografi. Penulisku menyukai  summer wars karena kekuatan super tokoh utamanya, Kenji, adalah matematika. Okay, dia jago matematika, terus? Banyak yang pesimis tentang kemungkinan dunia Oz yang ada di anime ini, tetapi bagi yang memahami sedikit tentang kriptografi pasti akan mengernyitkan alis saat melihat aksi kenji. Mari kita lihat mengapa kenji bisa dibilang adalah wizard (atau dewa?).

Kita telah membicarakan tentang perkalian dua buah bilangan bukan? Mari kita bahas dulu sebentar tentang modular aritmatik, yang dibicarakan Kenji ke Ueda pas di kereta. Saat membagi sebuah bilangan, kita pasti mendapatkan sisa pembagian. Misalkan kita membagi bilangan k dengan N, kita akan mendapat bilangan r. Maka kita katakan bahwa k dan r ekivalen pada mod N dengan notasi k = r (mod N). Untuk sembarang bilangan k, nilai r pasti akan di antara 0, 1, …, atau N-1. Pada situasi modular ini, semua operasi dasar seperti penjumlahan, pengurangan, dan perkalian berlaku sama seperti biasa, bedanya hasil dari operasi ini dilakukan modulus lagi dengan N dan kita akan mendapat hasilnya.

Akan tetapi, pembagian tidak semudah biasanya. Kita harus membaliknya, dengan kata lain memikirkan pembagian seperti perkalian. Hal ini biasa disebut invers. Misalkan pada penjumlahan, inverse dari sebuah bilangan k adalah –k, dengan kata lain jika kedua bilangan dijumlahkan akan menghasilkan identitas penjumlahan yakni 0. Angka 0 adalah identitas penjumlahan karena k+0 adalah k itu sendiri. Dengan cara yang sama, pada perkalian kita akan memakai identitas angka 1 karena bilangan apapun dikalikan 1 adalah bilangan itu sendiri. Sehingga, pembagian dalam modular tadi adalah mencari bilangan invers perkalian k, sebut saja k^-1, diantara 0 sampai N-1 sehingga k.k^-1 ≡ 1 (mod N).

Masalahnya, tidak semua bilangan memiliki invers dalam modular aritmatik. Lebih jelasnya, bilangan k akan memiliki invers jika dan hanya jika k dan N relatif prima, alias pembagi pembesarnya 1. Jika tidak, k tidak akan memiliki invers. Hal ini menarik karena jika N yang menjadi bilangan modulus tadi adalah bilangan prima, artinya semua kemungkinan k pasti memiliki invers, karena semua angka dari 0 sampai N-1 tidak akan ada yang memiliki FPB bukan 1. Jumlah bilangan yang relatif prima dengan sembarang bilangan N disebut Fungsi Totient Euler, dilambangkan dengan φ(n).

Jika bilangan A relatif prima dengan B, artinya A ≡ 1 (mod B). Jika kedua sisi persamaan dipangkatkan Z, kita memperoleh A^Z ≡ 1 (mod B), karena semua orang tahu satu dipangkatkan berapa pun ya tetap satu. Persamaan terakhir berarti bahwa bilangan A^Z juga relatif prima dengan B.

Dengan mengetahui semua hal di atas, algoritma RSA bisa dipahami sebagai berikut. Misalkan Alice ingin mengirim pesan atau file rahasia ke Bob. Bob kemudian akan memilih sembarang bilangan prima p dan q berbeda lalu menghitung N = p.q. Kemudian Bob menghitung φ(N) yang ternyata sama dengan (p-1).(q-1). Akhirnya dia memilih integer E sebagai kunci Enkripsi yang relatif prima dengan φ(N). Integer E dan N lalu dipublikasikan oleh Bob ke semua orang, tetapi p,q,dan φ(N) disimpan baik-baik di lemari.

Ketika Alice ingin mengirim file, dia tinggal melihat blognya Bob dan mengambil bilangan E dan N yang dipublikasikannya. File asli, disebutplain teks, yang akan dikirim diubah ke dalam representasi integer P dengan nilai diantara 0 sampai N-1. Jika ternyata representasi integer dari file ini terlalu besar, Alice tinggal memecahnya menjadi beberapa bagian. Pesan ini kemudian dienkripsi oleh Alice dengan memangkatkan bagian tadi dengan E dalam modulus N, sehingga ia mendapat cipherteks C = P^E (mod N). Hasil deretan C ini kemudian dikirim ke Bob.

Gimana Bob membuka pesannya? Karena Bob memiliki nilai E dan φ(N), ia dapat menemukan kunci dekripsi D dengan mudah yakni menghitung D ≡ E^-1 (mod φ(N)) atau D.E ≡ 1 (mod φ(N)). Setelah mendapat nilai D, Bob bisa menguak pesan asli dengan menghitung C^D = (P^E)^D ≡ P¹ (mod φ(N)) karena kita tahu E×D = 1 (mod φ(N)).

Hal yang menarik disini adalah Alice bisa mengirim pesan rahasia ke Bob dan hanya Bob yang dapat membukanya. Hal ini karena bilangan prima p dan q hanyalah Bob yang mengetahuinya, orang lain hanya mengetahui nilai N = p×q. Wellm jika orang lain tahu nilai p dan q, ia juga bisa membuka pesan tersebut karena dengan mengetahui p dan q ia akan mengetahui φ(N). Akan tetapi mencari nilai p dan q dari N ternyata sangatlah sulit. Kembali ke awal pembuka kita tadi, mengalikan p dan q menjadi N sangat lah mudah. Akan tetapi mencari p dan q prima dari N adalah super sulit.

Mungkin anda terpikir bahwa hal terakhir tadi tidaklah benar. Oke, untuk bilangan N kecil seperti 39 tidaklah sulit menemukan bahwa p dan q adalah 3 dan 13. Untuk bilangan lain pun kita dapat mencoba mencari faktornya dengan membagi dengan bilangan lebih kecil satu persatu dan mencoba semua kemungkinan faktor yang diperoleh. Akan tetapi, pada implementasi RSA bilangan p dan q bisa mencapai ratusan digit. Algoritma tercepat yang diketahui untuk memecahkan hal ini adalah puny akompleksitas e^{O(log N log log N)1/2}. Kunci RSA sekarang adalah sebesar 1024 bit. Artinya kita memerlukan 4.4 x 10²⁹ operasi untuk memfaktorkannya. Dengan komputer Core i7 dengan kekuatan 3 GHz per keping, hal ini membutuhkan waktu 581 milyar tahun. Hal ini bisa diatasi dengan komputer yang lebih banyak dan lebih cepat. Tetapi mereka tinggal menggandakan kuncinya dan tiba-tiba operasi yang butuh dilakukan sebanyak 10^44 operasi.

Well, itu tidak sepenuhnya benar. Salah satu dobrakan dalam dunia komputer saat ini adalah quantum komputer. Kuantum komputer menggunakan perilaku partikel atomik dan subatomik dalam melakukan operasinya. Dikatakan bahwa algoritma kuantum, Shor Algorithm dapat memecahkan masalah faktorisasi dengan kompleksitas polinomial yakni sekitar O((log N)³). Artinya dengan jumlah N sebesar  4.4 x 10²⁹ dalan 1024 bit kunci RSA, dibutuhkan hanya sekitar 60 operasi untuk memecahkannya. Jika panjang kunci digandakan, efeknya hanya kecil sekitar menambah 20 operasi saja. Sayangnya (atau untungnya? Jika iya, komputer sekarang, perbankan online, paypal, dan lain-lain tidak akan aman lagi gan), komputer kuantum skala besar belum dibuat manusia dan manusia belum mempunyai kemampuan untuk itu dalam waktu dekat ini.

Singkat cerita, Kenji adalah komputer kuantum.

Diadaptasi dari blkmage.net