Hari Kriptografi Berubah Selama-lamanya

Pada 1 Ogos 1977, Scientific American menerbitkan artikel Martin Gardner yang memperkenalkan RSA, satu bentuk kriptografi baharu yang bakal mengubah dunia selama-lamanya. Artikel ini mengisahkan perjalanan daripada sifir strim kepada kriptografi kunci awam, satu inovasi yang menjadi asas keselamatan internet moden.

Artikel ini oleh Steven Ellis telah diterbitkan dalam blog Medium beliau.

Sumbang.

Pada 1 Ogos 1977, Scientific American, sebuah majalah sains popular, mengeluarkan terbitan bulanannya, seperti yang telah dilakukannya sejak 1921. Ia mengandungi campuran menarik matematik, sains, kejuruteraan, biologi, mekanik, geografi dan kandungan lain yang seumpamanya.

Muncul hampir di penghujung terbitan pada muka surat 120, terdapat sebuah artikel pendek oleh ahli matematik popular Martin Gardner bertajuk *'Mathematical Games'*.

Di dalamnya, beliau menggambarkan 'sejenis sifir baharu yang memerlukan berjuta-juta tahun untuk dipecahkan'.

Bentuk kriptografi baharu ini, dinamakan *RSA* sempena penciptanya Ron Rivest, Adi Shamir dan Leonard Adleman, menurut penulis, bakal mengumandangkan era baharu dalam kriptografi.

Seperti yang terbukti, ramalannya tepat sekali.

Edisi Ogos 1977 Scientific American.

Apa yang dunia perlukan ialah … penyulitan tanpa kepercayaan

Sebelum 1977, kriptografi telah didominasi oleh sifir strim (stream ciphers), dan khususnya pad sekali guna (one-time pad). Pad sekali guna ialah jujukan rawak nombor, huruf atau bit, yang apabila digabungkan dengan mesej asal, menghasilkan jujukan pseudo-rawak. Tanpa mengetahui pad sekali guna, adalah mustahil untuk menyahsulit mesej yang telah disulitkan. Tetapi jika anda mengetahui kuncinya, adalah mudah untuk mengekstrak mesej asal daripada penyulitan tersebut.

Teori matematik menunjukkan bahawa sifir strim dan pad sekali guna adalah bentuk kriptografi yang paling selamat dan terjamin. Walau bagaimanapun, penggunaan bentuk penyulitan sedemikian datang dengan keperluan pelaksanaan yang agak membebankan dan sukar diurus.

Artikel yang kini terkenal oleh Martin Gardner tentang penyulitan kunci awam RSA, dalam edisi Ogos 1977 Scientific American.

Pertama, kunci hanya boleh digunakan sekali (kerana menggunakan kunci yang sama pada dua mesej berbeza serta-merta memecahkan sifir tersebut), dan kedua, kunci *mesti sentiasa sama panjang dengan mesej asal*.

Ini membayangkan bahawa dua pihak yang ingin berkomunikasi secara selamat melalui penggunaan pad sekali guna, *perlu mencari cara untuk berkongsi kunci antara satu sama lain sebelum berkomunikasi dengannya*.

Jika pihak-pihak tersebut tidak mengenali satu sama lain terlebih dahulu, atau dipisahkan oleh jarak atau masa yang jauh, ini menimbulkan masalah logistik: mereka perlu berkongsi kunci antara satu sama lain sebelum komunikasi tersulit dapat berlaku. Lebih-lebih lagi, jika pihak-pihak ini entah bagaimana mencari cara untuk saling menghantar kunci ini secara selamat (melalui kurier peribadi, pos berdaftar, kapal selam nuklear, dll.), timbul persoalan: mengapa tidak gunakan sahaja saluran itu untuk berkomunikasi dan bersusah payah dengan penyulitan sama sekali?

Ribut digital sedang berkembang…

Dengan latar belakang ini, jika anda merenung landskap digital pada tahun 1977, anda akan melihat gelombang pasang gergasi mula terbentuk di ufuk yang jauh. Gelombang pasang ini ialah penghimpunan perkakasan komputer dan rangkaian, perisian dan protokol, yang lama-kelamaan akan membentuk Revolusi Digital yang kita alami hari ini.

Banyak komponen utama pengkomputeran dan rangkaian moden telah pun ditemui atau dicipta, dan sedang menunggu keadaan yang sesuai untuk mencapai penggunaan meluas.

ARPANET (rangkaian suis paket teragih dan pelopor kepada internet moden) sudah wujud dan digunakan di pelbagai lokasi korporat dan akademik. TCP (protokol kawalan penghantaran, protokol berorientasikan sambungan yang digunakan oleh internet) dan FTP (protokol pemindahan fail, digunakan untuk pemindahan fail komputer antara klien dan pelayan pada rangkaian) juga telah pun digunakan. Pelbagai bentuk pemesejan elektronik satu-dengan-satu seperti FTPmail dan Mail Protocol (yang akan berkembang menjadi e-mel menggunakan SMTP pada tahun 80-an) telah dicipta, dan digunakan untuk menghantar mesej mel merentasi ARPANET. Pada tahun 1965, Gordon Moore, ketika itu CEO Intel, meramalkan penggandaan setiap tahun dalam bilangan komponen setiap litar bersepadu (yang disemaknya pada tahun 1975 kepada penggandaan setiap dua tahun). Ramalannya dikenali sebagai Hukum Moore, dan menjanjikan kemajuan berterusan dan mampan dalam elektronik digital dan perkakasan.

Syarikat komputer seperti Intel, IBM, SAP, dan Honeywell telah pun mantap. Dua tahun lebih awal, dua usahawan muda telah menubuhkan sebuah syarikat di Albuquerque, New Mexico, untuk membangunkan dan menjual pentafsir BASIC untuk Altair 8800. Dan setahun sebelumnya, seorang lagi usahawan muda menubuhkan syarikat di rumah zaman kanak-kanaknya di Crist Drive di Los Altos, California. Syarikat-syarikat tersebut ialah Microsoft dan Apple masing-masing.

Pendek kata, perisian dan perkakasan sudah bersedia untuk penggunaan secara besar-besaran dan menyeluruh. Tetapi dari segi rangkaian, ia kekurangan satu komponen penting: penyulitan tanpa kepercayaan (trustless encryption), yang membolehkan komunikasi antara dua pihak yang tidak mempunyai kenalan terlebih dahulu. Untuk rangkaian berbilang nod dan terdesentralisasi sebenar seperti internet untuk berkembang maju, ia memerlukan cara bagi ahli yang tidak dikenali dalam rangkaian tersebut tanpa hubungan terdahulu, untuk berkomunikasi secara selamat. Kaedah kontemporari menggunakan sifir strim meletakkan keperluan yang terlalu membebankan ke atas ahli rangkaian untuk bersetuju dan berkongsi kunci penyulitan terlebih dahulu.

Teka-teki Merkle — percubaan pertama terhadap masalah ini

Usaha pertama yang diiktiraf untuk menyelesaikan masalah pengedaran kunci adalah pada tahun 1974, apabila saintis komputer Ralph Merkle menghasilkan penyelesaian untuk membolehkan dua pihak bersetuju tentang kunci rahsia dengan bertukar-tukar mesej, walaupun mereka tidak mempunyai rahsia bersama terlebih dahulu.

Protokol ini berfungsi seperti berikut:

• Andaikan Alice dan Bob ingin berkomunikasi secara selamat. • Alice mencipta sejumlah besar teka-teki (masalah matematik yang sukar, tetapi tidak mustahil, untuk diselesaikan). • Bob secara rawak memilih salah satu teka-teki yang dihantar kepadanya, dan menyelesaikan teka-teki tersebut. • Penyelesaian yang dinyahsulit mengandungi pengecam dan kunci sesi (yang akan berfungsi sebagai kunci untuk komunikasi mereka). Bob menghantar pengecam itu kembali kepada Alice, dengan itu menunjukkan kepadanya teka-teki yang telah diselesaikannya. • Kedua-dua pihak kini mempunyai kunci yang sama; Bob, kerana dia menyelesaikan teka-teki, dan Alice, kerana dia menghantar teka-teki tersebut. • Mana-mana pengintip (contohnya Eve) mempunyai tugas yang lebih sukar kerana dia tidak tahu teka-teki mana yang telah diselesaikan oleh Bob. Strategi terbaiknya ialah menyelesaikan semua teka-teki, tetapi oleh kerana jumlahnya terlalu banyak, ini lebih mahal dari segi pengiraan untuk Eve berbanding untuk Bob.

Analisis matematik protokol ini mendedahkan bahawa terdapat jurang kuadratik antara masa dan usaha untuk penyerang (Eve) menyelesaikan semua teka-teki berbanding dengan Alice dan Bob.

Pada masa kini, kerumitan kuadratik biasanya tidak dianggap cukup selamat terhadap penyerang untuk aplikasi kriptografi praktikal dunia sebenar. Di samping itu, protokol Teka-teki Merkle memerlukan Alice menghasilkan sejumlah besar teka-teki, dan menghantar kesemuanya kepada Bob. Ini jelas merupakan banyak kerja untuk Alice, dan juga banyak trafik rangkaian antara Alice dan Bob. Memandangkan keperluan ini, protokol ini dianggap terlalu tidak cekap untuk digunakan dalam amalan. Walau bagaimanapun, kepentingan sumbangan Merkle tidak boleh dipandang ringan. Ini adalah pelaksanaan pertama skim di mana dua peserta boleh menghasilkan kunci 'secara spontan', dan di mana terdapat jurang yang ketara antara jumlah kerja yang diperlukan untuk peserta menghasilkan kunci, dan jumlah kerja yang diperlukan untuk penyerang memecahkan kunci. Ia juga akan memberikan inspirasi untuk protokol pengedaran kunci baharu yang dicipta dua tahun kemudian…

Satu kejayaan teori besar telah dicapai

Diilhamkan oleh kerja Merkle, pada 6 November 1976 dua profesor Harvard, Whitfield Diffie dan Martin Hellman menerbitkan kertas teori yang menangani banyak masalah lama sekitar penyulitan tanpa kepercayaan dan pengedaran kunci.

'New Directions in Cryptography' — sebuah kertas kerja oleh Whitfield Diffie dan Martin Hellman pada tahun 1976.

Kedua-dua Diffie dan Hellman memahami sepenuhnya bagaimana kekurangan kriptografi pada ketika itu menghalang komunikasi yang selamat dan mudah antara dua orang yang tidak mempunyai kenalan terlebih dahulu.

Mereka juga menyedari bahawa satu-satunya cara untuk menyelesaikan masalah pertukaran kunci adalah dengan penggunaan matematik yang kompleks. Dalam erti kata lain, seperti yang mereka katakan, '*mengubah seni kuno ini menjadi sains*'.

Penyelesaian cemerlang dan terobos mereka terhadap masalah ini ialah kriptografi kunci awam (public key cryptography).

Dalam protokol ini, terdapat dua set kunci untuk *penyulitan* dan *penyahsulitan* (kita akan panggil kunci ini E dan D). Protokol ini menggunakan sifat matematik untuk memastikan bahawa: • E ialah *songsangan* bagi D • memperoleh kedua-dua E dan D adalah mudah dari segi pengiraan • mengira D daripada E adalah tidak dapat dilaksanakan dari segi pengiraan (iaitu *sangat* sukar) • E boleh didedahkan secara awam tanpa menjejaskan integriti D (berdasarkan syarat di atas).

Sifat-sifat protokol sedemikian membolehkan perbualan peribadi antara dua orang yang tidak pernah berkomunikasi sebelum ini.

Bagaimana? • Seorang pengguna (Bob) menjana sepasang transformasi songsang E dan D. • Transformasi penyahsulitan D mesti dirahsiakan, dan tidak perlu dikomunikasikan kepada sesiapa pun. • Kunci penyulitan E boleh diumumkan dengan meletakkannya dalam direktori awam bersama nama dan alamat Bob. • Sesiapa sahaja (contohnya Alice) boleh mencari kunci awam Bob E dalam direktori, menyulitkan mesej menggunakan E dan menghantarnya kepada Bob, tetapi tiada orang lain boleh menyahsulit mesej yang ditujukan untuk Bob, kecuali Bob sendiri (yang menggunakan D untuk melakukannya).

Konsep fungsi sehala (one-way function) menawarkan penyelesaian yang cekap untuk pertukaran kunci. Walau bagaimanapun, kedua-dua penulis mengakui bahawa pelaksanaan praktikal protokol tersebut masih 'masalah terbuka', dan menjemput pembaca untuk menumpukan fikiran mereka untuk mencarinya. Kejayaan itu akan datang kurang dari setahun kemudian.

Satu fungsi sehala praktikal telah direka

'On Digital Signatures and Public-Key Cryptosystems' — kertas kerja oleh Ronald Rivest, Adi Shamir dan Len Adleman, diterbitkan pada 1977.

Ronald Rivest dan Adi Shamir adalah kedua-dua saintis komputer di MIT manakala Len Adleman ialah seorang ahli matematik.

Kertas Diffie–Hellman telah menangkap imaginasi mereka, dan mereka mula berusaha untuk mencari pelaksanaan yang memenuhi spesifikasinya. Apabila Rivest atau Shamir menghasilkan skim teori baharu, Adleman biasanya menolaknya selepas hanya beberapa minit analisis.

Sekitar tengah malam pada malam Seder Paskah (Passover Seder) pada tahun 1977, Rivest menghubungi Adleman dengan idea menggunakan *pemfaktoran nombor perdana* sebagai fungsi perangkap (trapdoor function). Adleman gagal mencari sebarang kelemahan dalam idea ini. (Malah, lebih 40 tahun kemudian, masih tiada sesiapa yang berjaya melakukannya).

Keberkesanan fungsi sehala RSA bergantung pada fakta bahawa mendarab dua nombor perdana besar bersama adalah mudah, tetapi memfaktorkan hasil darab ini kepada dua nombor perdana yang membentuknya, adalah sangat sukar.

Nombor perdana — nombor yang lebih besar daripada satu yang hanya boleh dibahagi dengan satu dan dirinya sendiri — mempunyai sifat matematik khas yang telah menarik minat ahli matematik selama berabad-abad. Pandangan cemerlang Rivest, Shamir dan Adleman adalah menggunakan sifat nombor perdana ini untuk membina fungsi perangkap yang praktikal dan cekap.

Saya menggalakkan pembaca membaca kertas asal untuk mendapatkan gambaran terperinci tentang pelaksanaan aritmetik protokol tersebut.

Secara ringkas, untuk menggunakan RSA: • Cari dua nombor perdana P & Q (biasanya setiapnya ratusan digit panjang), dan darabkannya bersama untuk mencipta hasil darabnya, dipanggil N. • Jana nombor, dipanggil jumlah Euler (Euler totient) dan dilambangkan dengan φ(N), dan dikira sebagai (P-1) × (Q-1). Ini mewakili bilangan integer yang relatif perdana (relatively prime) kepada N (tidak termasuk nombor 1, yang relatif perdana kepada setiap integer bukan sifar). • Cari nombor E (*kunci penyulitan*) yang relatif perdana kepada kedua-dua N dan φ(N). • Tentukan nombor D (*kunci penyahsulitan*) yang merupakan songsangan darab modulo (modular multiplicative inverse) bagi E. Ini dikira menggunakan persamaan E × D = 1 (mod φ(N)). • Kunci awam ialah nombor N dan nombor E. • Kunci peribadi ialah nombor N dan nombor D. Sifir kemudiannya dicapai dengan menaikkan mesej kepada E mod N. Penyahsulitan dicapai dengan menaikkan sifir kepada D mod N. C ≡ Mᴱ mod N M ≡ Cᴰ mod N (operasi 'mod' seperti yang digunakan di atas diterangkan di sini)

Contoh RSA 1

• Cari dua nombor perdana P & Q: P = 2, Q = 7 • Kira N: N = P × Q = 2 × 7 = 14 • Kira φ(N): φ(N) = (P − 1)(Q − 1) = 1 × 6 = 6 • Pilih kunci penyulitan E: E mestilah antara 1 dan ϕ iaitu 1 < E < 6. E mestilah relatif perdana kepada N dan φ(N). Berdasarkan keperluan ini, E dikira sebagai 5. • Kira kunci penyahsulitan D: D ialah songsangan E mod φ(N). Dengan kata lain, D × E (mod φ(N)) = 1. Iaitu dalam contoh kita, 5 × D (mod 6) = 1. Berdasarkan ini, kita boleh pilih D = 11 (kerana 5 × 11 mod 6 = 1). *E = 5, D = 11, N = 14, C ≡ Mᴱ mod N, M ≡ Cᴰ mod N* Jika mesej M kita katakan 9: *C = 9⁵ mod 14 = 11, M = 11¹¹ mod 14 = 9*

Contoh RSA 2

• Cari dua nombor perdana P & Q: P = 61, Q = 53 • Kira N: N = P × Q = 61 × 53 = 3233 • Kira φ(N): φ(N) = (P − 1)(Q − 1) = 60 × 52 = 3120 • Pilih kunci penyulitan E: E mestilah antara 1 dan φ(N) iaitu 1 < E < 3120. E mestilah relatif perdana kepada N dan φ(N). Berdasarkan keperluan ini, E dikira sebagai 17. • Kira kunci penyahsulitan D: D ialah songsangan E mod φ(N). Dengan kata lain, D × E (mod φ(N)) = 1. Iaitu dalam contoh kita, 17 × D (mod 3120) = 1. Menggunakan Algoritma Euclid Lanjutan, kita kira D = 2753 (kerana 17 × 2753 mod 3120 = 1). *E = 17, D = 2753, N = 3233, C ≡ Mᴱ mod N, M ≡ Cᴰ mod N* Jika mesej M kita katakan 42: *C = 42¹⁷ mod 3233 = 2557, M = 2557²⁷⁵³ mod 3233 = 42*

Contoh RSA 3

• Cari dua nombor perdana P & Q: P = 5, Q = 11 • Kira N: N = P × Q = 5 × 11 = 55 • Kira φ(N): φ(N) = (P − 1)(Q − 1) = 4 × 10 = 40 • Pilih kunci penyulitan E: E mestilah antara 1 dan φ(N) iaitu 1 < E < 40. E mestilah relatif perdana kepada N dan φ(N). Berdasarkan keperluan ini, E dikira sebagai 7. • Kira kunci penyahsulitan D: D ialah songsangan E mod φ(N). Dengan kata lain, D × E (mod φ(N)) = 1. Iaitu dalam contoh kita, 7 × D (mod 40) = 1. Menggunakan Algoritma Euclid Lanjutan, kita kira D = 23 (kerana 7 × 23 mod 40 = 1). *E = 7, D = 23, N = 55, C ≡ Mᴱ mod N, M ≡ Cᴰ mod N* Jika mesej M kita katakan 15: *C = 15⁷ mod 55 = 5, M = 5²³ mod 55 = 15*

Ucapan akhir

Walaupun Rivest, Shamir dan Adleman menerbitkan kertas mereka pada April 1977, penerbitan dalam Scientific American 4 bulan kemudian yang memberitahu dunia tentang penemuan mereka, dan mengumandangkan era baharu dalam kriptografi.

Kesan sistem kriptografi kunci awam Diffie-Hellman, dan pelaksanaan RSA daripadanya, sukar untuk dilebih-lebihkan. Penyulitan kunci awam kini membentuk asas bagi kebanyakan protokol keselamatan yang kerap digunakan di internet hari ini, dan amat penting kepada privasi, integriti dan pengesahan dalam sistem komunikasi moden.

Di samping itu, teknologi penyulitan sejak 1976 telah menjadi domain awam, tidak dikawal oleh mana-mana entiti tunggal. Seperti yang dikatakan oleh Diffie kemudian, selepas mereka menerbitkan kertas mereka, monopoli kripto Agensi Keselamatan Negara (NSA) telah ditamatkan dengan berkesan. "Setiap syarikat, setiap rakyat kini mempunyai akses rutin kepada jenis teknologi kriptografi yang tidak beberapa tahun lalu setanding dengan bom atom sebagai sumber kuasa."

Menariknya, tiada siapa yang dapat membuktikan bahawa pemfaktoran nombor perdana adalah sukar dari segi pengiraan (dengan kata lain, kita tidak mempunyai jaminan bahawa pada masa hadapan seseorang tidak akan menemui teknik untuk memfaktorkan nombor perdana besar dengan cekap). Namun begitu, selama lebih 40 tahun, walaupun kelemahan tertentu dalam pelaksanaan algoritma telah ditemui, tiada siapa yang membuat sebarang kemajuan sebenar dalam menyerang teras algoritma tersebut.

Oleh itu, kita boleh menganggap dengan selamat bahawa protokol dan piawaian ini akan bertahan lama pada masa hadapan.

Temui wira kriptografi moden. Dari kiri ke kanan: Adi Shamir, Ron Rivest, Len Adleman, Ralph Merkle, Martin Hellman, dan Whitfield Diffie. (Gambar ihsan Eli Biham, diambil semasa pembentangan pada 21 Ogos di Crypto 2000, persidangan IACR).