McEliece e Rust: avvicinandosi lentamente a uno standard NIST per PQC
Viviamo in un mondo dominato da grandi (e senza volto) corporazioni, ma spesso sono gli individui che hanno costruito il nostro mondo dell'informazione. Uno di questi era Robert J. McEliece, scomparso nel maggio 2019 all'età di 76 anni. Mentre lavorava a una serie di progetti legati allo spazio, ha contribuito in molte aree, tra cui la trasmissione e l'archiviazione delle informazioni. Alla fine Robert ha ricevuto il Claude E. Shannon Award per il suo lavoro e ha tenuto molti discorsi memorabili:
E:
Il suo lavoro più noto riguarda i codici di correzione degli errori, inclusi i codici di convoluzione, e ora il suo lavoro sta suscitando grande attenzione nella creazione di un sistema di crittografia che sarebbe robusto contro un computer quantistico.
Il suo lavoro
Molti dei nostri metodi a chiave pubblica si basano su logaritmi discreti e si basano sulle teorie create da John Napier. Bitcoin, Tor, smart card, Wif-fi e molte altre applicazioni utilizzano logaritmi discreti. Ma questi metodi, e altri metodi a chiave pubblica, sono a rischio dai computer quantistici. Un contendente è il metodo McEliece Cryptography.
In una lezione per qualsiasi ricercatore moderno, in sole due pagine, Robert McEliece, nel 1978, ha delineato un metodo di crittografia a chiave pubblica basato sulla codifica algebrica, ora noto come metodo McEliece Cryptography [ paper ][1]. È un metodo di crittografia asimmetrico (con una chiave pubblica e una chiave privata) e, all'epoca, sembrava essere un serio contendente per un metodo botola. Sfortunatamente, RSA è diventato il re della collina e il metodo McEliece è stato spinto in fondo alla coda per i designer.
È sostanzialmente andato alla deriva per quasi 40 anni. Ma, mentre sta nascendo un'era di computer quantistici, ora viene riconsiderata, poiché si è visto che è immune agli attacchi che utilizzano l'algoritmo di Shor [ qui ].
Il NIST ha ora iniziato a passare a metodi robusti quantistici con un documento che delinea i requisiti per nuovi metodi di crittografia, poiché un computer quantistico su larga scala romperà la maggior parte dei sistemi a chiave pubblica attualmente disponibili, inclusi RSA e metodi logaritmici discreti. La crittografia a chiave pubblica complessiva viene spesso utilizzata per proteggere le chiavi segrete utilizzate nella crittografia simmetrica e per provare l'identità. Una violazione su larga scala di una chiave pubblica porterebbe a una completa mancanza di fiducia su Internet per l'entità compromessa.
I principali contendenti per i metodi robusti quantistici sono:
- Crittografia basata su reticolo : questa classificazione mostra un grande potenziale e sta portando a una nuova crittografia, ad esempio per la crittografia completamente omomorfica [ qui ] e l'offuscamento del codice. Un esempio è fornito nella sezione seguente.
- Crittografia basata su codice : questo metodo è stato creato nel 1978 con il sistema crittografico McEliece, ma è stato utilizzato a malapena in applicazioni reali. Il metodo McEliece utilizza codici lineari utilizzati nei codici di correzione degli errori e prevede la moltiplicazione matrice-vettore. Un esempio di codice lineare è il codice di Hamming [ qui ]
- Crittografia polinomiale multivariata : si concentra sulla difficoltà di risolvere sistemi di polinomi multivariati su campi finiti. Sfortunatamente, molti dei metodi che sono stati proposti sono già falliti.
- Firme basate su hash : ciò comporterebbe la creazione di firme digitali utilizzando metodi di hashing. Lo svantaggio è che un firmatario deve tenere traccia di tutti i messaggi che sono stati firmati e che esiste un limite al numero di firme che possono essere prodotte.
Il metodo McEliece utilizza la crittografia basata su codice. La sua base si basa sulla difficoltà di decodificare un codice lineare generale ed è generalmente più veloce di RSA per la crittografia e la decrittografia. Al suo interno, abbiamo un metodo probabilistico di generazione della chiave, che viene poi utilizzato per produrre la chiave pubblica e quella privata. Le chiavi sono generate con i parametri di n, k e T.
Le chiavi sono generate con i parametri di n, k e t. Con questo, creiamo una matrice [n,k] di codici, e che è in grado di correggere t errori. Nel suo articolo, McEliece definisce n=1024, k=524, t=50 e che fornisce una dimensione della chiave pubblica di 524x(1024–524) = 262.000 bit. Nell'esempio sopra usiamo k=1608, N=2048 e T=40, che fornisce una dimensione della chiave pubblica di 1608x(2048–40) — 3.228.864 bit. Per la robustezza quantistica si raccomanda che N sia 6960, k sia 5.412 e t sia 119 (dando una chiave di grandi dimensioni di 8.373.911 bit.
Quanto segue è la dimensione della chiave derivata e il testo cifrato (in byte) di ciascuno dei metodi principali [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
Per prima cosa, creiamo il progetto con:
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
La performance di McEliece
Scoprirai che il codice è piuttosto lento e può richiedere alcuni secondi per creare la chiave condivisa. Questo perché McEliece è molto più lento di Kyber per la generazione delle chiavi [ qui ]:
Come si vede, McEliece è 11.490 volte più lento per la generazione di chiavi rispetto a Kyber. Ma i processi di incapsulamento e decapsulamento hanno prestazioni migliori, con prestazioni 1,9 volte più lente per l'incapsulamento e 9,7 volte più lente per il decapsulamento.
Conclusioni
Kyber è stato definito come il primo metodo ad essere definito come metodo PQC Key Exchange e Public Key Encryption. Nel complesso, si basa su metodi reticolari. Questi sono relativamente veloci per la generazione, la crittografia e la decrittografia delle chiavi e con dimensioni delle chiavi relativamente piccole. Il NIST, tuttavia, teme che diventeremo troppo dipendenti dai metodi del reticolo, e quindi sta cercando altri metodi. Questi includono McEliece, BIKE e HQC.
Puoi saperne di più qui:
https://asecuritysite.com/pqc/kem
E qualche crepa:
Scambio di chiavi McEliece: il guscio di tartaruga è un po' rotto, ma è ancora sicuroRiferimenti
[1] McEliece, RJ (1978). Un sistema crittografico a chiave pubblica basato sull'algebrico. Codifica Thv , 4244 , 114–116.
![Che cos'è un elenco collegato, comunque? [Parte 1]](https://post.nghiatu.com/assets/images/m/max/724/1*Xokk6XOjWyIGCBujkJsCzQ.jpeg)
