Jika sistem kriptografi tradisional digunakan, siapa pun yang cukup memahami cara mengenkripsi pesan juga akan cukup memahami cara mendekripsi pesan yang disadap. Pada tahun 1976, W. Diffie dan M. Hellman mengusulkan kriptografi kunci publik, yang didasarkan pada pengamatan bahwa prosedur enkripsi dan dekripsi tidak harus menggunakan kunci yang sama. Hal ini menghilangkan keharusan untuk merahasiakan kunci enkripsi. Fungsi enkripsi
\(f\) harus relatif mudah dihitung, tetapi
\(f^{-1}\) harus sangat sulit dihitung tanpa informasi tambahan, sehingga orang yang hanya mengetahui kunci enkripsi tidak dapat menemukan kunci dekripsi tanpa komputasi yang terlampau berat. Menarik untuk dicatat bahwa hingga kini, belum ada sistem yang terbukti “satu arah;” artinya, untuk setiap sistem kriptografi kunci publik yang ada, belum pernah dibuktikan bahwa mendekripsi pesan hanya dengan mengetahui kunci enkripsinya memerlukan komputasi yang terlampau berat.
Subbagian 7.2.1 Sistem Kriptografi RSA
Sistem kriptografi
RSA yang diperkenalkan oleh R. Rivest, A. Shamir, dan L. Adleman pada tahun 1978 didasarkan pada sulitnya memfaktorkan bilangan besar. Walaupun mencari dua bilangan prima besar secara acak lalu mengalikannya bukan tugas yang sulit, dengan algoritma tercepat yang tersedia pada awal 1990-an, memfaktorkan bilangan 150 digit yang merupakan hasil kali dua bilangan prima besar akan memerlukan sekitar 50 juta tahun jika dikerjakan oleh 100 juta komputer yang masing-masing menjalankan 10 juta instruksi per detik. Meskipun algoritmanya telah berkembang, memfaktorkan bilangan yang merupakan hasil kali dua bilangan prima besar tetap memerlukan komputasi yang terlampau berat.
Sistem kriptografi
RSA bekerja sebagai berikut. Misalkan kita memilih dua bilangan prima acak berukuran 150 digit,
\(p\) dan
\(q\text{.}\) Selanjutnya, kita hitung hasil kali
\(n= pq\) dan juga
\(\phi(n) = m = (p - 1)(q-1)\text{,}\) dengan
\(\phi\) sebagai fungsi
\(\phi\) Euler. Kemudian kita memilih bilangan bulat acak
\(E\) sampai menemukan satu yang relatif prima terhadap
\(m\text{;}\) yaitu, kita pilih
\(E\) sedemikian sehingga
\(\gcd(E, m) = 1\text{.}\) Dengan algoritma Euklides, kita dapat menemukan bilangan
\(D\) sedemikian sehingga
\(DE \equiv 1 \pmod{m}\text{.}\) Bilangan
\(n\) dan
\(E\) kemudian diumumkan kepada publik.
Sekarang, misalkan orang B (Bob) ingin mengirimkan pesan kepada orang A (Alice) melalui saluran publik. Karena
\(E\) dan
\(n\) diketahui oleh semua orang, siapa pun dapat mengenkripsi pesan. Mula-mula Bob menyatakan pesan dengan angka menurut suatu skema, misalnya
\(\text{A} = 00, \text{B} = 02, \ldots, \text{Z}= 25\text{.}\) Jika perlu, ia memecah pesan menjadi bagian-bagian sehingga setiap bagian merupakan bilangan bulat positif yang lebih kecil daripada
\(n\text{.}\) Misalkan
\(x\) adalah salah satu bagian tersebut. Bob membentuk bilangan
\(y = x^E \mod n\) dan mengirimkan
\(y\) kepada Alice. Untuk memperoleh kembali
\(x\text{,}\) Alice cukup menghitung
\(x = y^D \bmod n\text{.}\) Hanya Alice yang mengetahui
\(D\text{.}\)
Contoh 7.2.1.
Sebelum menyelidiki teori di balik sistem kriptografi
RSA atau mencoba menggunakan bilangan bulat besar, kita akan menggunakan beberapa bilangan bulat kecil untuk melihat bahwa sistem tersebut memang bekerja. Misalkan kita ingin mengirim suatu pesan yang setelah dinyatakan dengan angka menjadi
\(25\text{.}\) Ambil
\(p = 23\) dan
\(q = 29\text{.}\) Maka
\begin{equation*}
n = pq = 667
\end{equation*}
dan
\begin{equation*}
\phi(n) = m = (p - 1)(q - 1) = 616\text{.}
\end{equation*}
Kita dapat mengambil \(E = 487\text{,}\) karena \(\gcd(616, 487) = 1\text{.}\) Pesan terenkripsi dihitung sebagai
\begin{equation*}
25^{487} \bmod 667 = 169\text{.}
\end{equation*}
Perhitungan ini dapat dilakukan secara wajar dengan metode kuadrat berulang seperti yang dijelaskan dalam
Bab 4. Dengan algoritma Euklides, kita memperoleh
\(191 E = 1 + 151 m\text{;}\) oleh karena itu, kunci dekripsinya adalah
\((n, D) = ( 667, 191)\text{.}\) Kita dapat memperoleh kembali pesan asli dengan menghitung
\begin{equation*}
169^{191} \bmod 667 = 25\text{.}
\end{equation*}
Sekarang mari kita periksa mengapa sistem kriptografi
RSA bekerja. Kita mengetahui bahwa
\(DE \equiv 1 \pmod{ m}\text{;}\) maka terdapat
\(k\) sedemikian sehingga
\begin{equation*}
DE = km + 1 = k \phi(n) + 1\text{.}
\end{equation*}
Ada dua kasus yang perlu dipertimbangkan. Pada kasus pertama, anggap bahwa
\(\gcd(x, n) = 1\text{.}\) Berdasarkan
Teorema 6.3.2,
\begin{equation*}
y^D = (x^E)^D = x^{DE} = x^{km + 1} = (x^{\phi(n)})^k x = (1)^k x = x \bmod n\text{.}
\end{equation*}
Jadi, kita melihat bahwa Alice memperoleh kembali pesan asli \(x\) ketika menghitung \(y^D \bmod n\text{.}\)
Untuk kasus lainnya, anggap bahwa
\(\gcd(x, n) \neq 1\text{.}\) Karena
\(n = pq\) dan
\(x \lt n\text{,}\) kita mengetahui bahwa
\(x\) merupakan kelipatan
\(p\) atau kelipatan
\(q\text{,}\) tetapi bukan keduanya. Kita hanya akan menjelaskan kemungkinan pertama, karena kemungkinan kedua sepenuhnya serupa. Maka terdapat bilangan bulat
\(r\) dengan
\(r \lt q\) dan
\(x = rp\text{.}\) Perhatikan bahwa
\(\gcd(x, q) = 1\) dan
\(m=\phi(n)=(p - 1)(q - 1)=\phi(p)\phi(q)\text{.}\) Kemudian, dengan menggunakan
Teorema 6.3.2, tetapi sekarang modulo
\(q\text{,}\)
\begin{equation*}
x^{km} = x^{k\phi(p)\phi(q)} = (x^{\phi(q)})^{k\phi(p)} = (1)^{k\phi(p)} = 1 \bmod q\text{.}
\end{equation*}
Jadi terdapat bilangan bulat \(t\) sedemikian sehingga \(x^{km}=1 + tq\text{.}\) Dengan demikian, Alice juga memperoleh kembali pesan pada kasus ini,
\begin{equation*}
y^D = x^{km + 1} = x^{km} x = (1 + tq) x = x + tq(rp) = x + trn = x \bmod n\text{.}
\end{equation*}
Sekarang kita dapat menanyakan bagaimana cara memecahkan sistem kriptografi
RSA. Untuk menemukan
\(D\) jika
\(n\) dan
\(E\) diketahui, kita hanya perlu memfaktorkan
\(n\) dan mencari
\(D\) dengan menggunakan algoritma Euklides. Jika kita mengetahui bahwa
\(667 = 23 \cdot 29\) dalam
Contoh 7.2.1, kita dapat memperoleh
\(D\text{.}\)
Subbagian 7.2.2 Verifikasi Pesan
Sistem kriptografi kunci publik menghadapi masalah verifikasi pesan. Karena kunci enkripsi diketahui publik, siapa pun dapat mengirimkan pesan terenkripsi. Jika Alice menerima pesan dari Bob, ia ingin dapat memverifikasi bahwa Bob benar-benar mengirim pesan tersebut. Misalkan kunci enkripsi Bob adalah \((n', E')\) dan kunci dekripsinya adalah \((n', D')\text{.}\) Misalkan pula kunci enkripsi Alice adalah \((n, E)\) dan kunci dekripsinya adalah \((n, D)\text{.}\) Karena kunci enkripsi merupakan informasi publik, mereka dapat bertukar pesan tersandi kapan pun diperlukan. Bob ingin meyakinkan Alice bahwa pesan yang dikirimnya autentik. Sebelum mengirimkan pesan \(x\) kepada Alice, Bob mendekripsi \(x\) dengan kuncinya sendiri:
\begin{equation*}
x' = x ^{D'} \bmod n'\text{.}
\end{equation*}
Siapa pun dapat mengubah \(x'\) kembali menjadi \(x\) hanya dengan enkripsi, tetapi hanya Bob yang dapat membentuk \(x'\text{.}\) Sekarang Bob mengenkripsi \(x'\) dengan kunci enkripsi Alice untuk membentuk
\begin{equation*}
y' = {x'}^E \bmod n\text{,}
\end{equation*}
yaitu pesan yang hanya dapat didekripsi oleh Alice. Alice mendekripsi pesan tersebut, kemudian mengenkripsi hasilnya dengan kunci Bob untuk membaca pesan asli, yaitu pesan yang hanya mungkin dikirim oleh Bob.
Subbagian 7.2.3 Catatan Sejarah
Enkripsi pesan rahasia telah dilakukan sejak zaman Yunani dan Romawi kuno. Seperti yang telah kita ketahui, Julius Caesar menggunakan sandi geser sederhana untuk mengirim dan menerima pesan. Namun, kajian formal mengenai enkripsi dan dekripsi pesan kemungkinan dimulai oleh bangsa Arab pada abad ke-15. Pada abad ke-15 dan ke-16, matematikawan seperti Alberti dan Viete menemukan bahwa sistem kriptografi monoalfabetik tidak memberikan keamanan yang nyata. Pada abad ke-19, F. W. Kasiski menyusun metode untuk memecahkan sandi yang memungkinkan satu huruf teks tersandi mewakili lebih dari satu huruf teks terang, apabila kunci yang sama digunakan beberapa kali. Penemuan ini mendorong penggunaan sistem kriptografi dengan kunci yang hanya dipakai satu kali. Pada awal abad ke-20, tokoh seperti W. Friedman dan L. Hill meletakkan kriptografi di atas landasan matematika yang kukuh.
Setelah Perang Dunia I, dikembangkan mesin-mesin khusus untuk mengenkripsi dan mendekripsi pesan, dan para matematikawan sangat aktif dalam kriptografi selama Perang Dunia II. Upaya menembus sistem kriptografi negara-negara Poros diselenggarakan di Inggris dan Amerika Serikat oleh matematikawan terkemuka seperti Alan Turing dan A. A. Albert. Pihak Sekutu memperoleh keuntungan besar dalam Perang Dunia II dengan memecahkan sandi yang dihasilkan oleh mesin Enigma Jerman dan sandi Purple Jepang.
Menjelang 1970-an, minat terhadap kriptografi komersial mulai berkembang. Kebutuhan untuk melindungi transaksi perbankan, data komputer, dan surat elektronik terus meningkat. Pada awal 1970-an,
IBM mengembangkan dan menerapkan
LUZIFER, pendahulu Data Encryption Standard (DES) milik National Bureau of Standards.
Konsep sistem kriptografi kunci publik yang dikemukakan oleh Diffie dan Hellman masih sangat baru (1976). Konsep ini dikembangkan lebih lanjut oleh Rivest, Shamir, dan Adleman melalui sistem kriptografi
RSA (1978). Belum diketahui seberapa aman sistem-sistem tersebut. Sistem kriptografi ransel berpintu jebak yang dikembangkan oleh Merkle dan Hellman telah berhasil dipecahkan. Apakah sistem
RSA dapat dipecahkan masih merupakan pertanyaan terbuka. Pada tahun 1991,
RSA Laboratories menerbitkan daftar bilangan semiprima (bilangan yang memiliki tepat dua faktor prima) dengan hadiah uang bagi siapa pun yang mampu memberikan faktorisasi (
http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-challenge-numbers.htm). Meskipun tantangan tersebut berakhir pada tahun 2007, banyak di antara bilangan-bilangan ini belum berhasil difaktorkan.
Penelitian kriptografi dan kriptografi itu sendiri telah menimbulkan banyak kontroversi. Pada tahun 1929, Henry Stimson, Menteri Luar Negeri di bawah Herbert Hoover, membubarkan Black Chamber (divisi kriptografi Departemen Luar Negeri) atas dasar etika bahwa “pria terhormat tidak membaca surat milik satu sama lain.” Selama dua dasawarsa terakhir abad ke-20, National Security Agency ingin merahasiakan informasi tentang kriptografi, sedangkan komunitas akademik memperjuangkan hak untuk menerbitkan penelitian dasar. Saat ini, penelitian dalam kriptografi matematika dan teori bilangan komputasional sangat aktif, dan para matematikawan bebas menerbitkan hasil mereka dalam bidang-bidang tersebut.
