MSTR Cat

Blockchain/Tahap I · Wang/1.2 Jalan cypherpunk/Pelajaran 1

Kriptografi kunci awam: Diffie-Hellman dan RSA

Rahsia yang dikongsi tanpa bertemu, dan tandatangan yang membuktikan pemilikan

BahanKalkulator atau hamparan yang boleh mengendalikan aritmetik modularKertas kerja Diffie-Hellman (1976)

Ingin tahu

  1. Bagaimanakah dua orang asing boleh bersetuju tentang satu kunci rahsia sedangkan semua orang lain turut mendengar?
  2. Mengapa pendaraban dua nombor perdana yang besar adalah perkara yang mudah, tetapi mencari nombor perdana tersebut daripada hasil darabnya hampir mustahil?
  3. Apa maksudnya memiliki sesuatu jika pemilikan ditakrifkan oleh keupayaan untuk menandatangani?

Teroka

  1. Sebelum tahun 1976, komunikasi yang selamat memerlukan kunci rahsia yang dikongsi dan ditukar melalui saluran yang boleh dipercayai. Jika pihak yang mengintip berjaya mendapatkan kunci tersebut, semua trafik seterusnya akan terancam keselamatannya. Whitfield Diffie dan Martin Hellman mencadangkan penyelesaian dalam “New Directions in Cryptography” (IEEE Transactions on Information Theory, November 1976). Dua pihak boleh memperoleh kunci rahsia bersama melalui saluran terbuka menggunakan pengeksponenan modular. Proses matematik ini bersifat sehala: mudah dikira ke hadapan, tetapi mustahil dari segi pengiraan untuk dibalikkan tanpa input peribadi.
  2. Ralph Merkle mencipta teka-teki serupa antara tahun 1974 dan 1975, dan menerbitkannya pada tahun 1978. Satu pihak menerbitkan banyak teka-teki kecil yang disulitkan; pihak yang lain menyelesaikan satu daripadanya secara rawak dan menggunakan kandungannya sebagai kunci. Kelebihannya hanya bersifat kuadratik: dengan n teka-teki, kedua-dua pihak melakukan kira-kira n unit kerja, manakala pengintip perlu melakukan kira-kira n². Jurang dalam Diffie-Hellman pula membesar seiring dengan saiz kunci, dan apabila pasangan kunci baharu digunakan bagi setiap sesi, kebocoran kunci jangka panjang pada kemudian hari tidak akan mendedahkan trafik lalu.
  3. Ron Rivest, Adi Shamir, dan Leonard Adleman di MIT telah membangunkan RSA pada tahun 1977. Martin Gardner menerangkan sistem ini dalam ruangannya di Scientific American pada bulan Ogos 1977, sebelum kertas kerja rasmi diterbitkan dalam Communications of the ACM (Februari 1978). RSA bergantung pada kesukaran untuk memfaktorkan hasil darab dua nombor perdana yang besar kepada komponennya. Ia membolehkan penggunaan tandatangan digital: kunci peribadi digunakan untuk menandatangani data, manakala kunci awam yang sepadan digunakan untuk mengesahkannya tanpa mendedahkan rahsia penandatangan.
  4. James Ellis di GCHQ mencipta konsep “penyulitan bukan rahsia” sekitar tahun 1969 dan menuliskannya pada tahun 1970; Clifford Cocks membangunkan sistem yang setara dengan RSA pada tahun 1973; Malcolm Williamson pula membangunkan konsep yang setara dengan Diffie-Hellman pada tahun 1974. Penemuan-penemuan ini kekal dirahsiakan sehingga tahun 1997. Perkembangan serentak ini menunjukkan bahawa asas matematiknya sudah matang menjelang awal tahun 1970-an, tetapi penggunaannya hanya berlaku setelah para penyelidik akademik menerbitkan hasil kajian mereka secara terbuka. Kerja rahsia tidak membina infrastruktur awam.
  5. Rivest, Shamir dan Adleman menerima Anugerah Turing pada tahun 2002; Diffie dan Hellman pula menerimanya pada tahun 2015. Hal ini penting bagi bitcoin: pemilikan kini tidak lagi terikat pada jagaan fizikal atau rekod bank, tetapi pada keupayaan untuk menghasilkan tandatangan yang sah menggunakan kunci peribadi. Bitcoin menggunakan kriptografi lengkung eliptik secp256k1, bukannya RSA, namun struktur terasnya tetap sama. Pengguna membuktikan kawalan mereka ke atas dana dengan menandatangani transaksi; rangkaian pula mengesahkannya melalui kunci awam tanpa pernah melihat kunci peribadi.
  6. Cuba kira Diffie-Hellman menggunakan nombor kecil. Persetujui secara terbuka nombor perdana p = 23 dan asas g = 5. Alice memilih nilai rahsia a = 6 dan menghantar 5^6 mod 23 = 8. Bob memilih b = 15 dan menghantar 5^15 mod 23 = 19. Alice mengira 19^6 mod 23 = 2; Bob pula mengira 8^15 mod 23 = 2. Kedua-duanya kini memegang rahsia 2, walaupun hanya 23, 5, 8 dan 19 yang melalui saluran terbuka. Sistem sebenar menggunakan nombor sepanjang ratusan digit, dan mendapatkan semula a atau b daripada nilai-nilai awam itu adalah mustahil.

Fakta utama

  • Diffie dan Hellman menerbitkan protokol pertukaran kunci mereka pada bulan November 1976.
  • RSA dibangunkan di MIT pada tahun 1977 dan diterbitkan dalam Communications of the ACM pada Februari 1978.
  • Di GCHQ, James Ellis, Clifford Cocks dan Malcolm Williamson telah membangunkan kaedah kunci awam antara sekitar tahun 1970 hingga 1974, secara bebas daripada kerja di Amerika yang muncul kemudian.
  • Kerja GCHQ dalam kriptografi kunci awam telah didedahkan pada tahun 1997.
  • Keselamatan RSA bergantung pada kesukaran untuk memfaktorkan hasil darab dua nombor perdana yang besar.
  • Pemilikan bitcoin ditentukan oleh keupayaan untuk menandatangani menggunakan kunci peribadi.

Latihan sembilan, enam, tiga, satu

9KumpulSenaraikan 9 primitif atau protokol kriptografi dari tahun 1970 hingga 2008. Catatkan penciptanya, tahunnya dan sifat matematik terasnya.
6KelompokkanKumpulkan 9 item tersebut kepada 6 kategori: pertukaran kunci, tandatangan digital, hashing, penyulitan simetri, pengesahan, atau lain-lain.
3SaringKurangkan 6 kumpulan tersebut kepada 3 sebab kriptografi asimetrik membolehkan wujudnya sistem terdesentralisasi.
1KristalkanTulis 1 ayat tentang apa yang dibuktikan oleh kunci peribadi dan mengapa hal itu mengubah konsep pemilikan.

Semakan fakta

Tarikh, angka dan dakwaan telah disemak berbanding dengan sumber yang diterbitkan yang disenaraikan di bawah.

Buka dalam akademi interaktif →

EN PT ES ZH JA KO RU DE FR