McEliece dan Rust: Merayap Perlahan Menuju Standar NIST untuk PQC
Kita hidup di dunia yang didominasi oleh perusahaan besar (dan tak berwajah), tetapi individulah yang sering membangun dunia informasi kita. Salah satunya adalah Robert J. McEliece, dan meninggal dunia pada Mei 2019 pada usia 76 tahun. Saat mengerjakan berbagai proyek terkait luar angkasa, dia berkontribusi di banyak bidang termasuk transmisi dan penyimpanan informasi. Robert akhirnya dianugerahi Penghargaan Claude E. Shannon untuk karyanya, dan memberikan banyak ceramah yang mengesankan:
Dan:
Pekerjaannya yang paling terkenal adalah seputar kode koreksi kesalahan, termasuk di dalam kode konvolusi, dan sekarang karyanya menimbulkan perhatian besar dalam menciptakan sistem enkripsi yang kuat terhadap komputer kuantum.
Dia bekerja
Banyak metode kunci publik kami didasarkan pada logaritma diskrit dan dibangun di atas teori yang dibuat oleh John Napier. Bitcoin, Tor, smart card, Wif-fi, dan banyak aplikasi lainnya menggunakan logaritma diskrit. Tetapi metode ini, dan metode kunci publik lainnya, berisiko dari komputer kuantum. Salah satu pesaingnya adalah metode Kriptografi McEliece.
Dalam sebuah pelajaran untuk peneliti modern mana pun, hanya dalam dua halaman, Robert McEliece, pada tahun 1978, menguraikan metode enkripsi kunci publik berdasarkan Pengodean Aljabar — sekarang dikenal sebagai metode Kriptografi McEliece [ paper ][1 ] . Ini adalah metode enkripsi asimetris (dengan kunci publik dan kunci pribadi), dan, pada saat itu, tampaknya menjadi pesaing serius untuk metode pintu jebakan. Sayangnya, RSA menjadi King of the Hill, dan metode McEliece didorong ke ujung antrean untuk para desainer.
Itu pada dasarnya telah melayang selama hampir 40 tahun. Namun, seiring dimulainya era komputer kuantum, hal itu sekarang sedang dipertimbangkan kembali, karena dianggap kebal terhadap serangan menggunakan algoritme Shor [ di sini ].
NIST sekarang telah mulai beralih ke metode kuat kuantum dengan makalah yang menguraikan persyaratan untuk metode kriptografi baru, karena komputer kuantum skala besar akan merusak sebagian besar sistem kunci publik yang tersedia saat ini, termasuk RSA dan metode logaritma diskrit. Enkripsi kunci publik secara keseluruhan paling sering digunakan untuk melindungi kunci rahasia yang digunakan dalam enkripsi simetris dan untuk membuktikan identitas. Pelanggaran kunci publik skala besar akan menyebabkan kurangnya kepercayaan di Internet untuk entitas yang diretas.
Pesaing utama untuk metode kuat kuantum adalah:
- Kriptografi berbasis kisi — Klasifikasi ini menunjukkan potensi besar dan mengarah ke kriptografi baru, seperti untuk enkripsi homomorfik penuh [ di sini ] dan penyamaran kode. Sebuah contoh diberikan pada bagian berikut.
- Kriptografi berbasis kode — Metode ini dibuat pada tahun 1978 dengan sistem kriptografi McEliece tetapi hampir tidak pernah digunakan dalam aplikasi nyata. Metode McEliece menggunakan kode linier yang digunakan dalam kode koreksi kesalahan, dan melibatkan perkalian matriks-vektor. Contoh kode linear adalah kode Hamming [ disini ]
- Kriptografi polinomial multivariat — Ini berfokus pada kesulitan penyelesaian sistem polinomial multivariat pada bidang terbatas. Sayangnya, banyak metode yang telah diusulkan telah rusak.
- Tanda tangan berbasis hash — Ini melibatkan pembuatan tanda tangan digital menggunakan metode hashing. Kelemahannya adalah bahwa penanda tangan perlu melacak semua pesan yang telah ditandatangani dan ada batasan jumlah tanda tangan yang dapat dihasilkan.
Metode McEliece menggunakan kriptografi berbasis kode. Landasannya didasarkan pada kesulitan dalam mendekode kode linier umum dan umumnya lebih cepat daripada RSA untuk enkripsi dan dekripsi. Di dalamnya, kami memiliki metode pembangkitan kunci probabilistik, yang kemudian digunakan untuk menghasilkan kunci publik dan privat. Kunci dihasilkan dengan parameter n, k dan T.
Kunci dihasilkan dengan parameter n, k dan t. Dengan ini, kami membuat matriks kode [n,k], dan yang dapat memperbaiki kesalahan t. Dalam makalahnya, McEliece mendefinisikan n=1024, k=524, t=50, dan yang memberikan ukuran kunci publik 524x(1024–524) = 262.000 bit. Dalam contoh di atas, kami menggunakan k=1608, N=2048 dan T=40, yang memberikan ukuran kunci publik 1608x(2048–40) — 3.228.864 bit. Untuk ketangguhan kuantum, disarankan bahwa N adalah 6960, k adalah 5.412, dan t adalah 119 (memberikan ukuran kunci besar 8.373.911 bit.
Berikut ini adalah ukuran kunci turunan dan ciphertext (dalam byte) dari masing-masing metode inti [1]:
m n t level | public key secret key ciphertext
--------------------------------------------------------------------------
mceliece348864 12 3,488 64 1 | 261,120 6,492 128
mceliece460896 13 4,608 94 3 | 524,160 13,608 188
mceliece6688128 13 6,688 128 5 | 1,044,992 13,932 240
mceliece6960119 13 6,960 119 5 | 1,047,319 13,948 226
mceliece8192128 13 8,192 128 5 | 1,357,824 14,120 240
Type Public key size (B) Secret key size (B) Ciphertext size (B)
------------------------------------------------------------------------
Kyber512 800 1,632 768 Learning with errors (Lattice)
Kyber738 1,184 2,400 1,088 Learning with errors (Lattice)
Kyber1024 1,568 3,168 1,568 Learning with errors (Lattice)
LightSABER 672 1,568 736 Learning with rounding (Lattice)
SABER 992 2,304 1,088 Learning with rounding (Lattice)
FireSABER 1,312 3,040 1,472 Learning with rounding (Lattice)
McEliece348864 261,120 6,452 128 Code based
McEliece460896 524,160 13,568 188 Code based
McEliece6688128 1,044,992 13,892 240 Code based
McEliece6960119 1,047,319 13,948 226 Code based
McEliece8192128 1,357,824 14,120 240 Code based
NTRUhps2048509 699 935 699 Lattice
NTRUhps2048677 930 1,234 930 Lattice
NTRUhps4096821 1,230 1,590 1,230 Lattice
SIKEp434 330 44 346 Isogeny
SIKEp503 378 56 402 Isogeny
SIKEp751 564 80 596 Isogeny
SIDH 564 48 596 Isogeny
Pertama, kami membuat proyek dengan:
cargo new mce
[package]
name = "mce"
version = "0.1.0"
edition = "2021"
[dependencies]
classic-mceliece-rust = "3.0"
rand = "^0.8.5"
hex="^0.4"
use classic_mceliece_rust::{keypair, encapsulate, decapsulate};
use classic_mceliece_rust::{CRYPTO_BYTES, CRYPTO_PUBLICKEYBYTES, CRYPTO_SECRETKEYBYTES};
use hex;
fn main() {
let mut rng = rand::thread_rng();
let mut public_key_buf = [0u8; CRYPTO_PUBLICKEYBYTES];
let mut secret_key_buf = [0u8; CRYPTO_SECRETKEYBYTES];
let (public_key, secret_key) = keypair(&mut public_key_buf, &mut secret_key_buf, &mut rng);
println!("\nBob public key (showing first 32 out of {} bytes): {:.32}", CRYPTO_PUBLICKEYBYTES,hex::encode(public_key.as_array()));
println!("\nBob secret key (showing first 32 out of {} bytes): {:.32}",CRYPTO_SECRETKEYBYTES,hex::encode(secret_key.as_array()));
let mut shared_secret_bob_buf = [0u8; CRYPTO_BYTES];
let (ciphertext, shared_secret_bob) = encapsulate(&public_key, &mut shared_secret_bob_buf, &mut rng);
let mut shared_secret_alice_buf = [0u8; CRYPTO_BYTES];
let shared_secret_alice = decapsulate(&ciphertext, &secret_key, &mut shared_secret_alice_buf);
println!("\nCiphertext (Bob to Alice) (showing {} bytes): {}",ciphertext.as_array().len(),hex::encode(ciphertext.as_array()));
println!("\nBob key: (showing {} bytes) {}",shared_secret_bob.as_array().len(),hex::encode(shared_secret_bob.as_array()));
println!("\nAlice key: (showing {} bytes) {}",shared_secret_alice.as_array().len(),hex::encode(shared_secret_alice.as_array()));
}
cargo build
Bob public key (showing first 32 out of 261120 bytes): 4b44ae97d30a04f2ade8334a4817b5cc
Bob secret key (showing first 32 out of 6492 bytes): 76ac75d052f030692d334d843bc29ee7
Ciphertext (Bob to Alice) (showing 96 bytes): f40bff3d7928cd70cd1cf8a04daaacbf67168585a79fc57a28fef71203771a2d572229f29079bf6fe1713e7b3444c9badaebd7a7277ef6c88db9f02a27b3ba98b6f82743b2ba4b47d781b5fc5b7657ee10ef5d30971c2f2d2a8395898e8c2fe0
Bob key: (showing 32 bytes) bb2853e129206f1d9e2802a5e6bd93265545b0369eb91750d799b876d870ff30
Alice key: (showing 32 bytes) bb2853e129206f1d9e2802a5e6bd93265545b0369eb91750d799b876d870ff30
kinerja McEliece
Anda akan menemukan kodenya cukup lambat, dan dapat memakan waktu beberapa detik untuk membuat kunci bersama. Ini karena McEliece jauh lebih lambat daripada Kyber untuk pembuatan kunci [ di sini ]:
Seperti yang kita lihat, McEliece 11.490 kali lebih lambat untuk pembuatan kunci dibandingkan dengan Kyber. Namun proses enkapsulasi dan dekapsulasi bekerja lebih baik, dengan kinerja 1,9 kali lebih lambat untuk enkapsulasi, dan 9,7 kali lebih lambat untuk dekapsulasi.
Kesimpulan
Kyber telah didefinisikan sebagai metode pertama yang didefinisikan sebagai metode PQC Key Exchange dan Public Key Encryption. Secara keseluruhan, ini didasarkan pada metode kisi. Ini relatif cepat untuk pembuatan kunci, enkripsi dan dekripsi, dan dengan ukuran kunci yang relatif kecil. NIST, bagaimanapun, memiliki kekhawatiran bahwa kita akan menjadi terlalu tergantung pada metode kisi, dan mencari metode lain. Ini termasuk McEliece, SEPEDA, dan HQC.
Anda dapat mengetahui lebih lanjut di sini:
https://asecuritysite.com/pqc/kem
Dan beberapa retak:
Pertukaran Kunci McEliece: Cangkang Kura-kura Sedikit Pecah, Tapi Masih AmanReferensi
[1] McEliece, RJ (1978). Kriptosistem kunci publik berdasarkan aljabar. Pengodean Thv , 4244 , 114–116.
![Apa itu Linked List? [Bagian 1]](https://post.nghiatu.com/assets/images/m/max/724/1*Xokk6XOjWyIGCBujkJsCzQ.jpeg)
