4 Kriptologi

Mungkin suatu bentuk tipu daya sudah ada sebelum bahasa. Banyak hewan peliharaan tentu pernah berpura-pura tidak bersalah meskipun bukti keterlibatannya dalam pencurian kudapan sangat jelas. Bahkan ahli apiologi mungkin tidak tahu apakah sejumlah lebah malas mengarang cerita tentang perjalanan jauh menuju hamparan bunga baru ketika sang ratu meminta pertanggungjawaban.

Namun, di antara Homo sapiens, kebohongan mungkin sudah muncul segera setelah bahasa muncul. Tentu saja, ketika dua orang bertatap muka, kedua pihak masih mempunyai kendali tertentu: pendengar dapat mencoba menilai apakah pembicara dapat dipercaya; keduanya dapat menilai sendiri identitas lawan bicaranya lalu memilih apa yang ingin dibagikan; dan kata-kata pembicara bergerak langsung dari bibirnya ke telinga pendengar tanpa dapat diubah maknanya di tengah jalan (jika kita mengabaikan kebisingan sekitar dan sebagainya).

Banyak hal berubah setelah tulisan ditemukan lebih dari 5.000 tahun yang lalu. Kata-kata yang dibekukan dalam bentuk fisik, beserta gagasan yang diwakilinya, dapat diambil dan dibagikan kepada berbagai pihak selain pihak yang semula hendak dihubungi penulis. Selain itu, jika penulis tidak dapat menyerahkan karyanya langsung kepada pembaca yang dituju dan tulisan tersebut harus beredar sendiri untuk sementara waktu, kedua pihak tidak lagi dapat memastikan bahwa lawan komunikasinya benar-benar memiliki identitas yang dinyatakan dalam tulisan, ataupun bahwa simbol-simbol tertulis itu tidak berubah sejak dituliskan oleh pihak lainnya.

Mari kita merumuskan beberapa persoalan keamanan informasi (sebutannya sekarang) dalam konteks sebuah pesan yang hendak dikirim oleh seseorang bernama Alice kepada seseorang bernama Bob. Dalam drama kecil kita, lingkungan yang mungkin mengganggu dan terlalu mencampuri urusan orang lain diperankan oleh Eve. Secara tradisi, kita langsung memilih tokoh dengan nama yang diawali huruf E untuk melambangkan environment (lingkungan) sekaligus seseorang yang mungkin menjadi eavesdropper (penyadap)¹.

Berikut adalah beberapa istilah dasar.

Perhatikan bahwa Alice dan Bob sebenarnya dapat merupakan orang yang sama, yang mengirim pesan dari dirinya pada masa lalu kepada dirinya pada masa depan. Misalnya, seseorang mungkin ingin menyimpan catatan yang harus tetap rahasia dan dapat diandalkan integritasnya, bahkan jika tempat penyimpanan catatan tersebut dibobol.

 

Salah satu skema paling awal yang berusaha mencapai kerahasiaan mungkin digunakan sekitar abad ke-7 SM di Yunani. Para panglima militer ingin menerima laporan dari prajurit yang berada jauh dan mengirimkan perintah kepada mereka sedemikian rupa sehingga, sekalipun pembawa pesan tertangkap, pesan yang dibawanya tidak dapat dibaca musuh. Mereka menggunakan alat bernama scytale (dalam pelafalan Inggris, huruf “c” dibaca keras dan katanya berima dengan “Italy”). Alat ini berupa tongkat silindris—mungkin batang tombak—($\sigma\kappa\upsilon\tau\acute{\alpha}\lambda\eta$ berarti tongkat dalam bahasa Yunani Kuno), yang dililit secara spiral dengan selembar perkamen panjang.

Sebelum melanjutkan, kita memerlukan beberapa istilah teknis lagi.

Secara grafis:

 

Andaikan seorang mata-mata melihat para pengintai di lapangan melilitkan lembaran perkamen pada tombak dan menulis sepanjang tombak itu. Artinya, Eve mengetahui algoritme enkripsinya. Meskipun algoritmenya diketahui, kerahasiaan masih mungkin dipertahankan.

Dalam enkripsi menggunakan scytale, diameter scytale merupakan kuncinya. Bahkan, ada dugaan bahwa scytale juga berfungsi sebagai bentuk autentikasi sederhana: hanya Alice yang mempunyai scytale yang cocok dengan milik Bob. Jadi, jika Bob dapat membaca rangkaian huruf yang bermakna di sepanjang scytale miliknya, ia mengetahui bahwa Alice-lah yang mengirimkannya.

Bahkan dengan kunci, kelemahan kriptosistem ini cukup jelas. Dan Athena memang kalah dalam Perang Peloponnesos.

 

Pengalaman kriptologi selama berabad-abad menunjukkan bahwa algoritme suatu kriptosistem justru sebaiknya dibuka kepada publik, sedangkan hanya kunci bagi saluran komunikasi tertentu (misalnya antara Alice dan Bob) yang dirahasiakan. Ada banyak alasan untuk pendekatan ini. Alasan utamanya barangkali adalah bahwa pembuat kriptosistem tidak pernah dapat memastikan bahwa ia telah memikirkan semua metode kriptanalisis yang mungkin digunakan untuk menyerang sistemnya. Karena itu, lebih baik pembuat sistem membiarkan komunitas kripto seluas-luasnya menguji sistem tersebut, dan hanya sistem yang telah bertahan terhadap serangan semacam itu yang patut digunakan. Bagaimanapun, inilah dasar metode ilmiah: ilmuwan menerbitkan seluruh rincian eksperimennya agar orang lain dapat mencobanya, memberikan verifikasi independen, atau menemukan sesuatu yang perlu dikritik.

Sistem lain yang berasal dari zaman kuno konon digunakan oleh Julius Caesar.

Julius Caesar tampaknya biasa menggunakan nilai kunci $k=3$. Octavian, cucu dari saudari Julius Caesar, kemudian menjadi Kaisar Augustus dan suka menggunakan $k=-1$.

Jika kita menggunakan apa yang disebut alfabet Latin (meskipun alfabet ini bukan alfabet yang digunakan di Romawi kuno) dengan 26 huruf, ada satu nilai kunci yang sangat menarik: 13. Dengan nilai itu, enkripsi dan dekripsi merupakan transformasi yang persis sama. Pada zaman modern, transformasi ini disebut ROT13, dan pernah memainkan peran kecil dalam sejarah modern Internet. Misalnya, kiriman di ruang obrolan dan papan buletin awal kadang-kadang memuat bagian yang tidak boleh langsung terlihat oleh siapa saja yang membaca kiriman, tetapi tetap dapat dibuka oleh pembaca yang bersungguh-sungguh (seperti bocoran alur dalam ulasan gim, buku, atau film baru yang populer). Bagian semacam itu sering disertakan setelah terlebih dahulu diproses dengan ROT13.

Walaupun sebenarnya sama sekali tidak aman, ROT13 bahkan pernah digunakan untuk tujuan keamanan yang sesungguhnya dalam beberapa produk komersial, termasuk pada bagian tertentu dari beberapa versi sistem operasi Windows.

 

Cipher Caesar sudah berhasil dipecahkan sepenuhnya (dengan beberapa cara; lihat §4.3 di bawah) sebelum tahun 1000 M, tetapi salah satu turunannya dikembangkan pada akhir Abad Pertengahan dan dianggap sebagai teknologi kriptologi termaju hingga awal zaman modern.

Secara tradisional, kunci Vigenère berupa sebuah kata yang dituliskan, dihafalkan, dan dimiliki bersama oleh Alice dan Bob. Ketika mengenkripsi atau mendekripsi, huruf-huruf kata kunci itu “ditambahkan” pada huruf-huruf pesan seperti dijelaskan di atas, dengan konvensi $A=1$, $B=2$, dan seterusnya.

Perhatikan bahwa Vigenère dengan panjang kunci $\ell$ pada dasarnya merupakan $\ell$ cipher Caesar yang berjalan paralel. Bahkan, jika $\ell=1$, keduanya merupakan kriptosistem yang persis sama. Karena itu, Vigenère pada dasarnya $\ell+1$ kali lebih sulit dipecahkan daripada Caesar; suku “${}+1$” muncul karena Eve bahkan tidak mengetahui $\ell$. Meskipun demikian, setelah beberapa ratus tahun dianggap tidak dapat dipecahkan dan digunakan sebagai cipher diplomatik utama di istana-istana Eropa, metode untuk memecahkan Vigenère akhirnya dikembangkan.

 

Sebagai varian terakhir cipher Vigenère, andaikan kita bergerak ke arah yang berlawanan dari kasus ekstrem $\ell=1$ dan memilih $\ell$ sepanjang mungkin.

(Pad sekali pakai kadang-kadang disebut Cipher Vernam . Sebutan ini tidak tepat jika dilihat dari sejarah intelektual kriptosistem yang sebenarnya.)

Barisan kunci yang baik sangat penting dalam kriptosistem pad sekali pakai. Kabar baiknya, dapat dibuktikan bahwa jika pad sekali pakai benar-benar acak, kriptosistem yang dihasilkan memang aman secara sempurna. Dalam ilmu komputer, sifat ini disebut aman secara teori informasi , sebab bukti keamanannya tidak bergantung pada asumsi apa pun tentang sumber daya komputasi yang tersedia bagi penyerang. [Lihat (Shannon 1949) dan (Shannon 1948) untuk bukti tersebut.] Kriptosistem lain yang akan kita jumpai di bawah hanya aman jika kita mengandaikan bahwa penyerang mempunyai akses ke komputer jenis tertentu (asumsi yang lazim ialah sebuah mesin Turing waktu-polinomial probabilistik; bidang ilmu komputer yang membahas hal ini disebut kompleksitas komputasi; lihat, misalnya, (Arora dan Barak 2009)).

Pad yang sama juga tidak boleh digunakan lebih dari sekali. Jika digunakan kembali, penyerang dapat mengambil selisih kedua cipherteks huruf demi huruf, yang akan meniadakan pad sepenuhnya dari perhitungan. Setelah itu, pesan biasanya dapat ditentukan dengan cepat.

Pada zaman modern, setelah munculnya jaringan komunikasi digital, pesan ditulis sebagai data komputer. Dengan demikian, semuanya disimpan (dan dikirimkan) sebagai bit, yaitu $1$ dan $0$. Untuk bit, padanan penggeseran huruf dalam alfabet dengan kembali dari Z ke A bila perlu adalah: tidak melakukan apa pun jika besar pergeserannya genap, atau menukar $0$ dan $1$ jika pergeserannya ganjil.

Dengan kata lain, jika pesan dan kunci sama-sama dituliskan seluruhnya sebagai bit—anggap setiap bit sebagai salah satu dari elemen $[0],[1]\in{\mathbb Z}/2{\mathbb Z}$—enkripsi tepat berupa penjumlahan bit-bit yang bersesuaian modulo $2$. Karena itu, pad sekali pakai yang baik merupakan untaian bit (kelas-kelas kongruensi dalam ${\mathbb Z}/2{\mathbb Z}$) yang sangat acak dan sangat panjang.

Masalah besar pad sekali pakai adalah distribusi kunci: Alice dan Bob harus sudah memiliki bersama pad sekali pakai yang sangat besar sebelum mulai berkomunikasi. Panjangnya harus sekurang-kurangnya sama dengan jumlah seluruh huruf (atau bit pada zaman komputer) dalam semua pesan yang akan mereka kirim pada masa depan.

Hal ini menyarankan pendekatan menarik terhadap kriptografi: carilah cara agar Alice dan Bob dapat berbagi sebuah rahasia kecil yang memungkinkan keduanya menghasilkan barisan bit sepanjang apa pun, memperoleh barisan yang sama, tetapi barisan itu tampak sepenuhnya acak bagi setiap penyerang. Jika hal ini mungkin, mereka dapat menggunakan barisan acak semu tersebut sebagai pad sekali pakai. Disebut acak semu karena barisan itu sebenarnya tidak acak—Alice dan Bob dapat menentukannya terlebih dahulu dari rahasia awal yang kecil—tetapi bagi semua penyerang barisan itu tampak acak. [Lihat (Luby 1996) untuk pembahasan lebih lanjut tentang keacakan semu.]

Cipher Caesar tampak sangat lemah. Namun, ketika kita melihat suatu cipherteks, seperti

            wrehruqrwwrehwkdwlvwkhtxhvwlrq
            zkhwkhuwlvqreohulqwkhplqgwrvxiihu
            wkhvolqjvdqgduurzvrirxwudjhrxviruwxqh
            ruwrwdnhdupvdjdlqvwdvhdriwurxeohv
            dqgebrssrvlqjhqgwkhp

sulit untuk mengetahui harus mulai dari mana—teks itu nyaris sama sekali tidak tampak seperti bahasa Inggris.

Mungkin kita perlu mulai dari cipher Caesar itu sendiri, dengan mengandaikan (secara anakronistis) bahwa Caesar mengikuti Prinsip Kerckhoffs, atau (lebih sesuai dengan zamannya) bahwa para mata-mata telah mengetahui kriptosistemnya tetapi belum mengetahui kuncinya.

Kita segera menyadari bahwa hal yang tidak diketahui, yaitu kunci, begitu kecil dibandingkan dengan kesulitan yang ditimbulkannya. Bahkan, jika kita memilih kunci secara acak, hampir empat dari 100 percobaan akan menghasilkan dekripsi yang benar semata-mata karena keberuntungan. Perhitungan ini menggunakan “alfabet Latin” modern yang terdiri atas 26 huruf; pada zaman Caesar, alfabet Latin yang sebenarnya hanya memiliki 23 huruf, sehingga peluangnya bahkan lebih baik. Secara formal, kita membicarakan konsep berikut.

Kita menghitung ukuran berbagai ruang kunci tersebut karena salah satu kelemahan cipher Caesar adalah ruang kuncinya yang begitu kecil. Strategi yang lebih baik daripada menebak secara acak ialah mencoba semua kunci yang mungkin dan melihat kunci mana yang menghasilkan dekripsi yang benar. Hanya ada 26 kunci (atau 23 pada zaman Julius)! Pendekatan ini disebut serangan brute force [atau pencarian menyeluruh]. Bahkan pada zaman Caesar, ruang kunci cipher Caesar sudah begitu kecil sehingga Eve dapat memeriksa semua kunci dan melihat kunci mana yang menghasilkan teks terang pesan Alice kepada Bob.

Cipher Vigenère sedikit lebih sulit. Sebagai contoh, jika panjang kunci diketahui sama dengan lima, hampir 12 juta kunci harus dicoba. Sebelum zaman komputer, pekerjaan ini sama sekali tidak mungkin ditangani. Bahkan pada abad ke-21, ketika komputer dapat menghasilkan semua kemungkinan dekripsi itu dalam waktu yang bagi manusia tampak seketika, masih ada masalah: manusia harus memeriksa 12 juta kemungkinan tersebut dan memilih dekripsi yang sah.

Mechanical Turk milik Amazon (lihat https://www.mturk.com/mturk/welcome) mungkin dapat menghimpun cukup banyak tenaga manusia untuk menyelesaikan satu dekripsi Vigenère dengan brute force. Namun, pendekatan yang lebih baik ialah menulis program komputer yang dapat membedakan teks tanpa makna dari pesan nyata yang mungkin dikirim Alice kepada Bob. Dengan begitu, serangan brute force dapat berhasil dalam beberapa saat.

Untuk membedakan teks tanpa makna dari pesan nyata, kita perlu mengetahui pesan-pesan nyata apa saja yang mungkin. Hal ini memotivasi definisi berikut.

Tanpa suatu struktur pada ruang pesan, kriptanalisis dapat menjadi nyaris mustahil. Misalnya, jika Alice mengirimkan kode kombinasi sebuah brankas kepada Bob melalui surel dalam bentuk terenkripsi, ruang pesannya tidak terlalu besar tetapi tidak mempunyai ciri yang dapat dikenali. Serangan brute force tidak memiliki cara untuk menentukan hasil dekripsi mana yang merupakan kode kombinasi sebenarnya.

Namun, andaikan ruang pesan komunikasi Alice dan Bob berupa himpunan teks pendek (atau panjang, yang lebih baik) dalam bahasa Inggris. Teks bahasa Inggris mempunyai cukup banyak struktur; manusia penutur bahasa Inggris tentu dapat mengenali bahasa Inggris yang wajar. Pertanyaannya ialah apakah proses mendeteksi teks bahasa Inggris yang wajar dapat diotomatisasi.

Mari kita lihat kembali contoh enkripsi Caesar pada awal bagian ini. Kita sudah melihat bahwa hasilnya tidak tampak seperti bahasa Inggris—tetapi dalam hal apa? Salah satunya tentu karena teks itu tidak memuat kata bahasa Inggris. Orang yang mengetahui bahasa Inggris mengenal sebagian besar kosakatanya dan dapat melihat bahwa teks tersebut tidak memuat kata-kata itu, kecuali mungkin “up” dan “i” (beberapa kali).

Hal ini menyarankan sebuah pendekatan: ambil daftar semua kata bahasa Inggris beserta semua bentuk varian dan turunannya; tambahkan beberapa barisan acak pendek yang mungkin muncul di dalam bahasa Inggris baku (misalnya ketika Alice mengutip ucapan tanpa makna yang didengarnya atau menyalin grafiti pada sisi gerbong kereta bawah tanah); lalu bandingkan daftar itu dengan semua kemungkinan dekripsi cipherteks. Skema ini tidak terlalu praktis. Namun, jika ruang pesannya cukup kecil, pendekatan semacam ini masuk akal.

Jika kita kembali melihat pesan tersebut, pembaca bahasa Inggris juga segera merasa bahwa huruf atau kombinasi hurufnya tidak tepat. Misalnya, tampaknya tidak ada cukup banyak vokal. Pemeriksaan seberapa sering huruf muncul dalam sebuah teks dibandingkan dengan frekuensi yang diharapkan disebut analisis frekuensi. Penggunaannya dalam kriptanalisis tampaknya pertama kali dijelaskan oleh filsuf dan matematikawan Muslim al-Kindi ⁴ dalam karyanya pada abad ke-9, Manuskrip tentang Penguraian Pesan Kriptografis.

Berikut adalah tabel frekuensi huruf dalam sejumlah teks bahasa Inggris baku (beberapa drama Shakespeare):

Perhatikan bahwa huruf ‘e’ merupakan huruf yang paling sering muncul, meskipun hanya dengan selisih kecil. Jadi, pendekatan kriptanalisis pertama menggunakan analisis frekuensi dapat dilakukan dengan memilih kunci dekripsi Caesar yang menggeser huruf paling sering dalam cipherteks menjadi ‘e’. Untuk cipherteks pada awal bagian ini, pendekatan tersebut menghasilkan dekripsi:

            ezmpzcyzeezmpesletdespbfpdetzy
            hspespcetdyzmwpctyespxtyoezdfqqpc
            espdwtyrdlyolcczhdzqzfeclrpzfdqzcefyp
            zcezelvplcxdlrltydeldplzqeczfmwpd
            lyomjzaazdtyrpyoespx

Hasilnya kurang baik. Rupanya, hanya memperhatikan huruf yang paling sering belum cukup: huruf paling sering dalam plainteks pesan ini bukan ‘e’.

Sebagai gantinya, mari kita lihat seluruh tabel frekuensi cipherteks ini.

Sayangnya, hasil ini tidak persis sama dengan distribusi frekuensi bahasa Inggris baku (berdasarkan Shakespeare), bahkan bukan sekadar versi distribusi Shakespeare yang digeser (dengan kembali dari 25 ke 0). Namun, mungkin salah satu pergeserannya cukup dekat dengan distribusi Shakespeare.

Hal ini menyarankan pendekatan kriptanalisis yang lebih halus: coba semua kemungkinan dekripsi (tidak terlalu berat untuk cipher Caesar karena ruang kuncinya kecil), lalu pilih hasil yang seluruh tabel frekuensi hurufnya paling dekat dengan tabel frekuensi bahasa Inggris baku. Jadi, kita tidak hanya melihat huruf yang paling sering, melainkan seluruh distribusi frekuensinya; dan kita tidak mencari kecocokan persis, melainkan kecocokan hampiran terbaik.

Pertanyaan berikutnya ialah cara terbaik untuk mengukur jarak antara dua distribusi. Salah satu pendekatan yang lazim ialah mengukur besaran berikut.

Meminimumkan jarak ini ekuivalen dengan metode kuadrat terkecil dalam statistika atau aljabar linear.

Dengan menerapkan strategi ini pada cipherteks dari awal bagian, kita memperoleh hasil berikut.

Galat kuadrat minimum diperoleh dari kunci dekripsi 23 (yang bersesuaian dengan kunci enkripsi awal 3; secara anakronistis, enkripsi ini dilakukan oleh Julius sendiri). Teks terang yang bersesuaian adalah

            tobeornottobethatisthequestion
            whethertisnoblerinthemindtosuffer
            theslingsandarrowsofoutrageousfortune
            ortotakearmsagainstaseaoftroubles
            andbyopposingendthem

yang tampak cukup meyakinkan.

Menariknya, pendekatan untuk mendeteksi teks bermakna ini cukup tangguh, bahkan untuk teks sangat pendek yang distribusi frekuensinya mungkin cukup jauh dari standar bahasa Inggris. Sebagai contoh, untuk cipherteks

kita memperoleh

yang menunjukkan bahwa kunci dekripsinya adalah 9 dan bersesuaian dengan kunci enkripsi 17. Jadi, teks terangnya pasti

yang tampak seperti sesuatu yang mungkin dikatakan Julius.

 

Cukup sampai di sini kriptanalisis cipher Caesar. Ketika beralih ke Vigenère, persoalan pertama adalah menentukan panjang kunci. Jika panjang kunci $\ell$ diketahui, kita dapat membagi cipherteks menjadi $\ell$ teks yang lebih pendek: teks pertama memuat karakter-karakter berselang $\ell$ posisi mulai dari karakter pertama, teks kedua mulai dari karakter kedua, dan seterusnya, hingga teks yang dimulai dari karakter ke-$\ell$. Dengan menerapkan pemecah Caesar otomatis yang dijelaskan di atas, kita memperoleh $\ell$ komponen kunci dan kemudian plainteksnya.

Untuk mempermudah, andaikan kita mengambil seluruh Hamlet dan mengenkripsinya dengan Vigenère menggunakan kata kunci hippopotomonstrosesquipedaliophobia, yang bersesuaian dengan kunci numerik $$\begin{align*} k=(7,8,15,15,14,15,14,19,14,12,14,13,18,19,17,14,\\ 18,4,18,16,20,8,15,4,3,0,11,8,14,15,7,14,1,8,0) \end{align*}$$ Sebagai contoh, bagian cipherteks yang bersesuaian dengan kutipan untuk memecahkan cipher Caesar di atas adalah

            hdxajnioomjvdtfvstrqitmfozlxjj
            kcmiosgpenjjbgxmcmtfzltmaudofpmwg
            odsntxuuhwjywmrjpnieosoqlfbpjoqyyljia
            cmbdaozawminabtdhrtyndlncugkflswh
            vjrwgdwddoeicznymcyl

Jika Eve berharap teks ini hanya dienkripsi dengan Caesar, sehingga panjang kunci Vigenère adalah $\ell=1$, ia akan memperoleh frekuensi huruf berikut.

Dibandingkan dengan Gambar 4.3, nilai-nilai ini menunjukkan variasi yang jauh lebih kecil. Bahkan, tidak ada nilai nol maupun nilai yang jauh lebih besar daripada semua nilai lainnya. Alasannya, secara hampiran distribusi ini merupakan campuran dari 35 pergeseran distribusi baku bahasa Inggris dalam Gambar 4.2, satu untuk setiap posisi kata kunci hippopotomonstrosesquipedaliophobia; jika pergeseran yang sama digabungkan, hasilnya adalah campuran berbobot dari 16 nilai pergeseran berbeda. Pencampuran ini menghaluskan seluruh bentuk khas distribusi yang berguna untuk mengenali pergeseran dekripsi yang benar.

Meskipun demikian, pemecah Caesar akan menghasilkan suatu nilai kunci untuk setiap kemungkinan nilai $\ell$ yang dicoba Eve. Untuk setiap posisi kunci, selalu ada nilai pergeseran yang meminimumkan galat kuadrat. Jika tebakan panjang kunci $\ell$ salah dan pengelompokan yang dihasilkan mencampurkan beberapa pergeseran berbeda, nilai minimum ini biasanya tidak terlalu kecil: distribusi frekuensi huruf pada posisi-posisi cipherteks yang kongruen dengan $k\pmod{\ell}$, untuk $k\in{\mathbb N}$ dan $k\le\ell$, biasanya lebih datar, sehingga jauh (menurut jarak galat kuadrat) dari distribusi bahasa Inggris baku.

Sebagai contoh, pada enkripsi Hamlet yang sedang kita kaji, andaikan Eve menebak $\ell=5$ dan mengambil semua huruf pada posisi yang kongruen dengan $1\pmod{5}$. Pemecah Caesar akan menghasilkan grafik galat kuadrat berikut:

Nilai minimum jelas terdapat pada kunci dekripsi 23, tetapi tidak jauh lebih kecil daripada kemungkinan lain. Selain itu, semua galatnya sekitar sepuluh kali lebih besar daripada yang tampak pada grafik sebelumnya, seperti Gambar 4.4.

Jadi, berikut adalah pendekatan kriptanalisis Vigenère. Coba semua panjang kunci $\ell$ hingga suatu batas $L$. Batas ini ditentukan oleh waktu komputasi yang tersedia dan tidak boleh begitu besar sehingga pengambilan huruf-huruf berselang $\ell$ posisi dari cipherteks menyisakan terlalu sedikit huruf untuk analisis frekuensi yang wajar. Untuk setiap $\ell$ anak untaian yang terdiri atas huruf-huruf berselang $\ell$ posisi dan masing-masing dimulai pada posisi $1,\dots,\ell$, terapkan pemecah Caesar. Hasilnya adalah kunci Vigenère optimal $\vec{k}_\ell=(k_{\ell,1},\dots,k_{\ell,\ell})$ sepanjang $\ell$. Kemudian, untuk setiap $\ell=1,\dots,L$ dan kunci $\vec{k}_\ell$ yang bersesuaian, hitung jarak galat kuadrat $d_\ell$ antara cipherteks yang didekripsi menggunakan $\vec{k}_\ell$ dan distribusi huruf bahasa Inggris baku. Laporkan $\ell$ dan $\vec{k}_\ell$ sebagai panjang kunci dan kunci Vigenère jika $d_\ell$ merupakan galat kuadrat terkecil yang diperoleh.

Andaikan Alice dan Bob tidak pernah berkesempatan bertemu langsung, tetapi tetap ingin bertukar pesan yang dirahasiakan dari Eve. Apa yang dapat mereka lakukan?

Hal ini tampak mustahil dalam konteks kriptosistem yang telah kita bahas. Mari kita uraikan bagian penting yang membuatnya begitu sulit.

Secara grafis:

  Demi keamanan kriptosistem di atas, ruang kunci ${\mathcal K}$ harus cukup besar, atau keseluruhan sistem harus disusun sedemikian rupa sehingga sulit menentukan apakah suatu kemungkinan dekripsi tertentu sah (atau keduanya). Jika tidak, Eve dapat melakukan serangan brute force dengan mencoba semua kemungkinan kunci $k\in{\mathcal K}$ dan melihat hasil $d_k(c)$ mana yang masuk akal sebagai dekripsi.

Bagaimanapun, karena memerlukan pertukaran kunci privat di awal, kriptosistem simetris tidak cocok untuk situasi yang diajukan pada awal bagian ini. Kita memerlukan jenis kriptosistem yang berbeda.

Secara grafis:

  Seperti sebelumnya, keamanan kriptosistem ini terhadap serangan brute force bergantung pada ukuran ${\mathcal K}_d$. Selain itu, karena kunci dan algoritme enkripsi diketahui Eve, ruang pesan ${\mathcal M}$ tidak boleh terlalu kecil. Jika ${\mathcal M}$ kecil, Eve cukup menghitung semua enkripsi $e_{k_e}(m)$ untuk setiap $m\in{\mathcal M}$, lalu membandingkannya dengan cipherteks $c$ yang berhasil dicegatnya.

Serangan terhadap ruang pesan ini dapat dicegah dengan memperbesar ruang tersebut secara artifisial. Biasanya, orang menambahkan data berikut.

Setelah Alice menambahkan salt pada pesannya, Eve harus menelusuri seluruh ruang pesan beserta salt, yang dapat jauh lebih besar daripada ${\mathcal M}$.

Sebagai manfaat tambahan, salt membuat cipherteks hampir selalu berbeda pada setiap pengiriman rahasia, sekalipun plainteksnya sama, apabila dipilih secara independen dari ruang yang cukup besar. Eve tentu mengetahui bahwa Alice dan Bob sedang berkomunikasi, tetapi dengan hanya membandingkan kesamaan cipherteks, analisisnya tidak lagi dapat mengenali pengiriman ulang pesan yang sama secara andal. Tanpa salt, Eve yang cermat mungkin dapat menghubungkan cipherteks pesan dengan tindakan di dunia nyata, sehingga pada dasarnya mengetahui hasil dekripsinya tanpa memecahkan kriptosistem. Jika salt dipilih secara independen dari ruang yang cukup besar, korelasi yang hanya mengandalkan kesamaan cipherteks menjadi sangat tidak andal, sebab peluang penggunaan ulang salt yang sama menjadi sangat kecil.

Karena kunci enkripsi Bob $k_e$ tersedia bagi publik, seluruh keamanan kriptosistem ini runtuh jika Eve dapat memulihkan kunci privat $k_d$ yang bersesuaian. Di sisi lain, Bob harus dapat membangkitkan pasangan $(k_e,k_d)$ secara layak pada tahap penyiapan. Asimetri antara komputasi maju yang mudah dan pemulihan rahasia yang sulit ini biasanya dibangun dari fungsi dengan sifat khusus berikut.

 

Perkalian dua bilangan, bahkan dua bilangan yang sangat besar, dapat dilakukan komputer dengan cukup cepat. Menentukan apakah bilangan yang sangat besar itu prima atau komposit juga ternyata sangat cepat (lihat (Agrawal dkk. 2004) untuk hasil mengagumkan dalam sejarah panjang uji keprimaan ini).

Namun, belum ditemukan cara klasik yang layak untuk memfaktorkan semiprima RSA yang cukup besar, yaitu hasil kali dua prima besar berukuran sebanding.⁵ Pembatasan bentuk ini penting: bilangan genap atau bilangan dengan faktor kecil dapat difaktorkan dengan mudah, berapa pun besarnya. Sebagai contoh, salah satu semiprima RSA terbesar yang pernah difaktorkan pada saat naskah sumber ditulis adalah soal tantangan terkenal RSA-768, sebuah bilangan komposit 232 digit (768 bit). Bilangan itu akhirnya difaktorkan pada 2009 setelah jaringan berisi ratusan komputer bekerja bersama selama sekitar dua tahun, meskipun tidak secara eksklusif mengerjakan soal tersebut. Semiprima RSA sejenis yang lebih besar mudah dibuat, tetapi pada umumnya jauh lebih sulit difaktorkan.

Karena itu, fungsi yang mengalikan dua bilangan prima besar berukuran sebanding untuk menghasilkan semiprima yang sangat besar merupakan calon fungsi satu arah kriptografis yang baik.

Pada 1978, Ron Rivest, Adi Shamir, dan Leonard Adleman menjelaskan ((Rivest dkk. 1978)) kriptosistem kunci publik berikut yang didasarkan pada fungsi satu arah tersebut.

Secara grafis:

  Pertama-tama, kita perlu memastikan bahwa sistem ini memenuhi syarat dasar agar berfungsi sebagai kriptosistem.

Selain memastikan fungsi dasarnya, kita perlu menilai seberapa praktis RSA. Mari kita telusuri dengan cermat algoritme yang diperlukan pada setiap langkah.

Kriptosistem kunci publik memungkinkan beberapa penggunaan yang tidak tersedia pada kriptosistem simetris. Salah satu penggunaan yang makin penting dalam ekonomi digital modern ialah pembuatan tanda tangan digital: bagian dari dokumen elektronik yang diharapkan memiliki salah satu sifat tanda tangan fisik, yakni sulit dipalsukan oleh penyamar. Dokumen bertanda tangan semacam itu mungkin diperlukan, misalnya, jika Bob dari bagian sebelumnya (yang memasang kunci publik RSA-nya di situs web) hendak mengirim kontrak yang mengikat secara hukum melalui surel. Barangkali Alice dan Bob ingin mengirim kepada calon pemilik rumah mereka, Larry, perjanjian sewa bertanda tangan untuk apartemen yang akan mereka tinggali bersama. Ketika menerima surel dari Bob yang berbunyi “Saya setuju terikat oleh ketentuan perjanjian sewa ini,” Larry perlu yakin bahwa surel tersebut benar-benar berasal dari Bob; tanda tangan digital dapat memberikan keyakinan itu.

Untuk skema dasar berikut, kita memerlukan sifat tambahan. Setiap pesan yang hendak ditandatangani harus berada dalam domain operasi privat $d_{k_d}$; untuk setiap pasangan $(k_e,k_d)$ yang dihasilkan $\mathsf{Gen}$ dan setiap $m\in{\mathcal M}$, harus berlaku $e_{k_e}(d_{k_d}(m))=m$, seperti pada RSA. Definisi umum kriptosistem asimetris sebelumnya hanya mensyaratkan urutan sebaliknya.

Bob lalu dapat melakukan hal berikut. Ia mengambil salinan perjanjian sewa, menambahkan bagian di akhir yang menyatakan persetujuannya atas ketentuan tersebut dan memuat informasi pengenal pribadi (mungkin pindaian surat izin mengemudinya). Sebut seluruh bongkah data ini $m$. Bob kemudian menerapkan algoritme dekripsi dengan kunci privat (dekripsi) $k_d$, sehingga diperoleh $s=d_{k_d}(m)$. Nilai $s$ ini disebut tanda tangan Bob atas pesan $m$. Ia lalu mengirimkan $m$ dan $s$ kepada Larry melalui surel.

Ketika menerima pesan bertanda tangan ini, Larry mula-mula memisahkan tanda tangan $s$, lalu menghitung enkripsinya, $e_{k_e}(s)$, menggunakan kunci publik yang ia unduh dari situs web Bob. Berdasarkan sifat tambahan di atas, hasilnya harus sama dengan $m$. Verifikasi $e_{k_e}(s)=m$ itu sendiri hanya menetapkan konsistensi aljabar pasangan $(m,s)$ terhadap kunci publik tersebut. Untuk menyimpulkan bahwa Bob menghasilkan tanda tangan dan bahwa pesan tidak berubah sejak ditandatangani, Larry juga harus mengandalkan skema tanda tangan yang tak dapat dipalsukan, kunci privat Bob yang tidak terkompromi, serta pengikatan tepercaya antara identitas Bob dan kunci publik tersebut. Bahkan dengan asumsi-asumsi itu, verifikasi tidak dengan sendirinya membuktikan identitas pengirim surel ataupun kebaruan pesan, sebab pasangan bertanda tangan yang lama dapat diteruskan atau diputar ulang oleh siapa pun.

Secara grafis:

  Salah satu masalah skema ini ialah ukuran pesan secara efektif menjadi dua kali lipat. Tanda tangan yang lebih kecil dan efisien dapat dibuat dengan mendekripsi bukan seluruh $m$, melainkan nilai suatu fungsi $h(m)$. Fungsi $h$ harus menerima pesan berukuran sebarang dan menghasilkan ringkasan data yang kecil, tetapi tetap bergantung pada setiap bagian masukan $m$. Bagaimanapun, jika $h(m)$ hanya bergantung pada 100 bit pertama $m$, misalnya, Eve yang berniat jahat dapat mengubah pesan selama pengiriman tanpa terdeteksi selama ia tidak mengubah 100 bit pertama pesan tersebut.

Kriptolog mempunyai nama untuk fungsi seperti $h$ ini.

Perhatikan bahwa karena fungsi hash menerima masukan berpanjang sebarang tetapi mempunyai ukuran keluaran tetap, pasti terdapat tak hingga banyak tumbukan.

Pembuatan fungsi hash kriptografis sedikit menyerupai seni gelap. Ternyata, jika suatu calon fungsi hash dibangun dengan struktur yang jelas (biasanya struktur matematis), terutama bila fungsi itu cepat dihitung, komunitas kriptologi biasanya menemukan cara untuk menembus salah satu syarat ketahanannya. Karena itu, algoritme yang digunakan secara luas cenderung berupa komputasi yang sangat ad hoc, tampak rumit, dan sejauh ini bertahan terhadap upaya membalikkan fungsi atau mematahkan sifat ketahanannya.

Secara grafis:

Dengan pemahaman ini, kita dapat mendeskripsikan tanda tangan digital secara lebih formal.

Kripto kunci publik dapat tampak sebagai manfaat tanpa cela bagi dunia berjejaring. Namun, pemeriksaan cermat atas dua bagian sebelumnya menunjukkan kesenjangan berbahaya antara gambaran sederhana mengenai sifat alat kriptografis itu dan kenyataannya. Perbedaan yang mula-mula luput dari perhatian ialah antara Bob sebagai orang dan bit-bit yang tiba melalui jaringan ke Alice atau Larry sambil mengaku berasal dari Bob. Perbedaan ini tidak banyak berpengaruh jika Eve hanya menjadi pengamat pasif komunikasi antara Alice dan Bob (dan kadang-kadang Larry), seperti yang selama ini umumnya kita asumsikan. Namun, jika Eve menguasai jaringan lebih jauh dan dapat mengganti semua komunikasi dengan versinya sendiri, serangan baru menjadi mungkin.

Misalkan Alice ingin mengirim pesan rahasia kepada Bob tanpa pernah bertemu dengannya untuk bertukar kunci kriptosistem simetris. Ia berharap Bob mempunyai kunci publik, lalu mengakses web dan mengunduh halaman utama Bob.

Pada titik inilah Eve bertindak. Ia mencegat respons Bob (tepatnya, server web Bob) terhadap permintaan tersebut. Eve menyimpan salinan kunci publik Bob $k_e^B$, tetapi mengganti kunci itu dalam data halaman web dengan kunci enkripsi RSA milik Eve, $k_e^E$; hanya Eve yang mengetahui kunci dekripsi pasangannya, $k_d^E$. Ia kemudian meneruskan halaman yang telah diubah kepada Alice.

Alice menyusun teks terang $m$ dan mengirim cipherteks yang bersesuaian, $c_A=e_{k_e^E}(m)$, kepada Bob—setidaknya demikian menurutnya. Eve justru mencegat cipherteks itu, mendekripsinya, lalu menyimpan $m=d_{k_d^E}(c_A)=d_{k_d^E}(e_{k_e^E}(m))$. Agar Alice dan Bob mengira semuanya berjalan normal (dan terus bercakap-cakap sambil membocorkan informasi), Eve meneruskan $c_E=e_{k_e^B}(m)$ kepada Bob.

Dari sudut pandang Bob, ia menerima surel yang tampak berasal dari Alice dan yang, setelah didekripsi dengan kunci privatnya, sepenuhnya masuk akal. Bahkan, jika ia berinteraksi dengan Alice di luar jaringan, Alice bertindak seolah-olah memang mengirim pesan itu. Alice memang mengirimnya, tetapi bukan dalam bentuk terenkripsi yang diterima Bob. Eve telah sepenuhnya melanggar kerahasiaan komunikasi Alice dan Bob. Ia juga dapat merusak integritas pesan kapan pun ia mau sambil tetap membuatnya tampak sah berasal dari Alice.

Skenario di atas disebut serangan man-in-the-middle (istilah konvensional ini memang tidak netral gender).

Berikut gambaran grafis serangan tersebut:

 

Jadi, kriptosistem simetris ternyata mempunyai satu keuntungan bawaan. Ketika para pihak bertemu pada saat ideal untuk bertukar kunci simetris, mereka semestinya dapat memastikan identitas lawan bicara. Jika tidak, mereka tentu tidak akan bertukar kunci sebelum memeriksa cukup banyak dokumen identitas yang terlihat resmi. Kriptosistem asimetris harus mengatasi kesulitan mendasar: membangun hubungan tepercaya antara identitas orang nyata dan kunci publik di Internet yang mengaku berasal dari orang tersebut.

Teknik dari bagian sebelumnya, §4.5, setidaknya dapat membantu memindahkan kepercayaan. Misalkan Alice ingin berkomunikasi secara rahasia dengan Bob, tetapi tidak tahu apakah kunci publik yang tampak berada di halaman web Bob dapat dipercaya. Jika kunci tersebut disertai tanda tangan digital yang diterbitkan oleh pihak ketiga tepercaya [TTP] dan Alice telah memperoleh kunci publik TTP sebagai jangkar kepercayaan melalui kanal yang diautentikasi secara independen—atau dapat memvalidasi jalur sertifikasi hingga jangkar semacam itu—ia dapat memverifikasi pengikatan kunci tersebut dengan identitas Bob, setidaknya sejauh yang telah diperiksa dan dinyatakan oleh TTP.

Berikut definisi formalnya.

Dalam praktik yang dibahas naskah sumber, CA sering kali hanya dapat menyertifikasi bahwa suatu kunci publik dikuasai oleh orang yang mempunyai akses ke alamat surel tertentu, kata sandi pengelola situs tertentu, atau token lain yang sepenuhnya berbasis Internet. Pemeriksaan itu biasanya mudah. Mengaitkannya dengan identitas nyata di luar jaringan mungkin memerlukan pemeriksaan dokumen identitas resmi dan jarang dilakukan. Naskah sumber juga mengusulkan kemungkinan peran pemerintah sebagai CA serta dokumen identitas ber-RFID yang dapat mengirimkan sertifikat bagi kunci publik pemiliknya (paspor Amerika Serikat yang lebih baru ketika itu telah memakai RFID).

Ada pendekatan lain untuk menentukan apakah suatu kunci publik dapat dipercaya, yang disukai orang-orang yang tidak memercayai otoritas terpusat tetapi bersedia memercayai orang tertentu yang mereka kenal langsung. Dalam pendekatan ini, orang-orang yang saling mengenal dan telah memverifikasi identitas serta kunci satu sama lain dapat menandatangani pengikatan identitas–kunci tersebut, menambahkan tanda tangan digital pada kumpulan yang sudah ada. Ketika hendak memakai kunci publik seseorang, Anda dapat menelusuri rantai tanda tangan digital, masing-masing mengesahkan pengikatan berikutnya, hingga mencapai orang yang Anda kenal langsung dan yang kuncinya telah Anda verifikasi.

Tanda tangan yang valid hanya menunjukkan bahwa suatu kunci menyertifikasi pengikatan identitas–kunci berikutnya; validitas itu sendiri belum membuat penyertifikasi tersebut layak dipercaya sebagai pengenal. Pengguna tetap harus menetapkan kebijakan kepercayaan lokal, termasuk seberapa jauh ia memercayai ketelitian setiap penyertifikasi dalam mengesahkan orang lain ( ownertrust), lalu menerima suatu pengikatan hanya jika sertifikasi yang ada memenuhi kebijakan tersebut.

Pendekatan ini dikenal sebagai jejaring kepercayaan (web of trust) . Pendekatan tersebut didukung kuat oleh GnuPG dan perangkat lain yang kompatibel dengan OpenPGP; lihat gnupg.org.

Agar berguna, jejaring kepercayaan memerlukan sertifikasi yang telah diverifikasi dan memenuhi kebijakan kepercayaan lokal serta penilaian ownertrust; sekadar menambah sebanyak mungkin tanda tangan tanpa verifikasi tidak memperkuat kepercayaan. Salah satu cara membangun sertifikasi tersebut ialah mengadakan pertemuan penandatanganan kunci. Pada pertemuan semacam itu, setiap penanda tangan harus memeriksa identitas pemilik kunci dan membandingkan sidik jari kunci lengkap secara langsung. Pernyataan pihak lain saja tidak cukup. Gunakan algoritme sidik jari yang diwajibkan format kunci yang berlaku, bukan md5, karena md5 tidak lagi aman terhadap tumbukan.