McEliece i Rust: powolne zbliżanie się do standardu NIST dla PQC
Żyjemy w świecie zdominowanym przez wielkie (i anonimowe) korporacje, ale to jednostki często budowały nasz świat informacji. Jednym z nich był Robert J. McEliece, który zmarł w maju 2019 roku w wieku 76 lat. Pracując nad szeregiem projektów związanych z kosmosem, wniósł wkład w wiele dziedzin, w tym transmisję i przechowywanie informacji. Robert ostatecznie otrzymał nagrodę Claude'a E. Shannona za swoją pracę i wygłosił wiele pamiętnych przemówień:
I:
Jego najlepiej znana praca dotyczy kodów korygujących błędy, w tym kodów splotowych, a teraz jego praca przyciąga wielką uwagę w tworzeniu systemu szyfrowania, który byłby odporny na komputer kwantowy.
Jego praca
Wiele naszych metod klucza publicznego opiera się na logarytmach dyskretnych i opiera się na teoriach stworzonych przez Johna Napiera. Bitcoin, Tor, karty inteligentne, Wif-fi i wiele innych aplikacji używa logarytmów dyskretnych. Ale te metody i inne metody z kluczem publicznym są zagrożone przez komputery kwantowe. Jednym z pretendentów jest metoda kryptograficzna McEliece.
W lekcji dla każdego współczesnego badacza, na zaledwie dwóch stronach, Robert McEliece w 1978 roku nakreślił metodę szyfrowania kluczem publicznym opartą na kodowaniu algebraicznym — obecnie znaną jako metoda kryptograficzna McEliece [artykuł][1 ] . Jest to metoda szyfrowania asymetrycznego (z kluczem publicznym i kluczem prywatnym) iw tamtym czasie wydawała się poważnym pretendentem do metody zapadni. Niestety RSA został Królem Wzgórza, a metoda McEliece została zepchnięta na koniec kolejki projektantów.
W zasadzie dryfuje od prawie 40 lat. Jednak wraz z nadejściem ery komputerów kwantowych jest ona ponownie rozważana, ponieważ uważa się, że jest ona odporna na ataki przy użyciu algorytmu Shora [ tutaj ].
NIST zaczął teraz przechodzić do metod odpornych na kwantowe z artykułem przedstawiającym wymagania dla nowych metod kryptograficznych, ponieważ wielkoskalowy komputer kwantowy złamie większość obecnie dostępnych systemów klucza publicznego, w tym metody RSA i logarytmów dyskretnych. Ogólne szyfrowanie kluczem publicznym jest najczęściej używane do ochrony tajnych kluczy używanych w szyfrowaniu symetrycznym i do potwierdzania tożsamości. Złamanie klucza publicznego na dużą skalę doprowadziłoby do całkowitego braku zaufania w Internecie do zaatakowanego podmiotu.
Głównymi pretendentami do metod odporności kwantowej są:
- Kryptografia oparta na kratach — Ta klasyfikacja wykazuje ogromny potencjał i prowadzi do nowej kryptografii, takiej jak w pełni homomorficzne szyfrowanie [ tutaj ] i zaciemnianie kodu. Przykład podano w poniższej sekcji.
- Kryptografia oparta na kodzie — ta metoda została stworzona w 1978 roku wraz z kryptosystemem McEliece, ale była rzadko używana w rzeczywistych aplikacjach. Metoda McEliece wykorzystuje kody liniowe, które są używane w kodach korekcji błędów i obejmuje mnożenie macierzy przez wektory. Przykładem kodu liniowego jest kod Hamminga [ tutaj ]
- Kryptografia wielomianów wielowymiarowych — skupia się na trudności w rozwiązywaniu układów wielomianów wielomianowych na polach skończonych. Niestety, wiele z proponowanych metod zostało już złamanych.
- Podpisy oparte na mieszaniu — wymagałoby to tworzenia podpisów cyfrowych przy użyciu metod mieszania. Wadą jest to, że osoba podpisująca musi śledzić wszystkie podpisane wiadomości oraz że istnieje ograniczenie liczby podpisów, które można złożyć.
Metoda McEliece wykorzystuje kryptografię opartą na kodzie. Jego podstawa opiera się na trudności w dekodowaniu ogólnego kodu liniowego i generalnie jest szybsza niż RSA do szyfrowania i deszyfrowania. W jej ramach mamy probabilistyczną metodę generowania klucza, która jest następnie wykorzystywana do tworzenia klucza publicznego i prywatnego. Klucze są generowane z parametrami n, k i T.
Klucze są generowane z parametrami n, k i t. W ten sposób tworzymy macierz kodów [n,k], która jest w stanie poprawić t błędów. W swoim artykule McEliece definiuje n=1024, k=524, t=50, co daje rozmiar klucza publicznego 524x(1024-524) = 262 000 bitów. W powyższym przykładzie używamy k=1608, N=2048 i T=40, co daje rozmiar klucza publicznego 1608x(2048–40) — 3 228 864 bitów. W przypadku odporności kwantowej zaleca się, aby N wynosiło 6960, k wynosiło 5412, a t wynosiło 119 (co daje duży rozmiar klucza wynoszący 8 373 911 bitów.
Poniżej przedstawiono pochodny rozmiar klucza i tekst zaszyfrowany (w bajtach) każdej z podstawowych metod [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
Najpierw tworzymy projekt z:
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
Występ McEliece'a
Przekonasz się, że kod jest dość powolny, a utworzenie klucza współdzielonego może zająć kilka sekund. Dzieje się tak, ponieważ McEliece jest znacznie wolniejszy niż Kyber do generowania kluczy [ tutaj ]:
Jak widzimy, McEliece jest 11 490 razy wolniejszy w generowaniu kluczy w porównaniu z Kyber. Ale procesy enkapsulacji i dekapsulacji działają lepiej, z 1,9 razy wolniejszą wydajnością w przypadku enkapsulacji i 9,7 razy wolniejszą w przypadku dekapsulacji.
Wnioski
Kyber został zdefiniowany jako pierwsza metoda, która została zdefiniowana jako metoda PQC Key Exchange i Public Key Encryption. Ogólnie rzecz biorąc, opiera się na metodach kratowych. Są one stosunkowo szybkie w generowaniu kluczy, szyfrowaniu i deszyfrowaniu oraz mają stosunkowo małe rozmiary kluczy. NIST obawia się jednak, że staniemy się zbyt zależni od metod sieciowych, dlatego poszukuje innych metod. Należą do nich McEliece, BIKE i HQC.
Tutaj dowiesz sie więcej:
https://asecuritysite.com/pqc/kem
I trochę krakingu:
Wymiana kluczy McEliece: Skorupa żółwia jest trochę zepsuta, ale nadal jest bezpiecznaBibliografia
[1] McEliece, RJ (1978). Kryptosystem klucza publicznego oparty na algorytmach algebraicznych. Kodowanie Thv , 4244 , 114-116.
![Czym w ogóle jest lista połączona? [Część 1]](https://post.nghiatu.com/assets/images/m/max/724/1*Xokk6XOjWyIGCBujkJsCzQ.jpeg)
