A safe pure-rust implementation of the Classic McEliece post-quantum scheme.
- Classic McEliece is a lattice-based key encapsulation mechanism (KEM)
- The implementation is based on the Classic McEliece reference implementation of NIST round 3
- The implementation does not utilize any concurrency techniques (SIMD/threading/…, except maybe auto-vectorization on your CPU)
- It depends on
sha3
as SHA-3 implementation andaes
as AES block cipher (used as RNG) implementation - It passes the 100 testcases of the C reference implementation
- It implements all 10 variants of the Classic McEliece KEM
- The implementation takes between 100 milliseconds (
mceliece348864
) and 500 milliseconds (mceliece8192128f
) to run on a modern computer - The implementation is constant-time on software instruction level
- The random number generator is based on AES256 in counter mode
- First described in 1978, the cryptographic scheme has a rich history in security analysis. Its large public key size, however, often limits adoption.
The 10 variants have the following designated identifiers:
mceliece348864
mceliece348864f
mceliece460896
mceliece460896f
mceliece6688128
mceliece6688128f
mceliece6960119
mceliece6960119f
mceliece8192128
mceliece8192128f
Anyone, how wants to use Classic McEliece to negotiate a key between two parties.
Add this to your Cargo.toml
:
[dependencies]
classic-mceliece-rust = "1.0"
To use a specific Classic McEliece variant, you need to import it with the corresponding feature flag:
[dependencies]
classic-mceliece-rust = { version = "1.0", features = ["mceliece6960119"] }
The simple
example illustrates the API:
use classic_mceliece_rust::AesState;
use classic_mceliece_rust::{crypto_kem_dec, crypto_kem_enc, crypto_kem_keypair};
use classic_mceliece_rust::{CRYPTO_BYTES, CRYPTO_CIPHERTEXTBYTES, CRYPTO_PUBLICKEYBYTES, CRYPTO_SECRETKEYBYTES};
fn main() -> Result<(), Box<dyn error::Error>> {
let mut rng = AesState::new();
let mut pk = [0u8; CRYPTO_PUBLICKEYBYTES];
let mut sk = [0u8; CRYPTO_SECRETKEYBYTES];
let mut ct = [0u8; CRYPTO_CIPHERTEXTBYTES];
let mut ss_alice = [0u8; CRYPTO_BYTES];
let mut ss_bob = [0u8; CRYPTO_BYTES];
crypto_kem_keypair(&mut pk, &mut sk, &mut rng)?;
crypto_kem_enc(&mut ct, &mut ss_bob, &pk, &mut rng)?;
crypto_kem_dec(&mut ss_alice, &ct, &sk)?;
assert_eq!(ss_bob, ss_alice);
}
This library comes with two examples:
$ cargo run --example basic
The output annotates messages with Alice/Bob to illustrate which data is processed by which party.
The katkem
example implements the classic request/response file structure which is part of the NIST PQC framework.
$ cargo run --example katkem PQCkemKAT_935.req PQCkemKAT_935.rsp
$ cargo run --example katkem PQCkemKAT_935.rsp
The different variants can be enabled through feature flags:
$ cargo run --example katkem --features mceliece6960119 -- PQCkemKAT_1450.req PQCkemKAT_1450.rsp
mceliece348864
is the default variant. You cannot enable two variants simultaneously.
All data uses clock cycles as unit (the smaller the better). The rust implementation yielded the following runtime results:
complete KEM | keypair | enc | dec | |
mceliece348864 | 439,132,283 | 418,968,068 | 268,722 | 43,444,716 |
mceliece348864f | 265,775,807 | 222,549,540 | 269,555 | 43,245,009 |
mceliece460896 | 1,231,610,738 | 1,211,071,786 | 461,924 | 107,828,642 |
mceliece460896f | 723,224,611 | 650,813,812 | 435,803 | 104,153,026 |
mceliece6688128 | 2,559,092,096 | 2,231,201,954 | 947,605 | 198,260,095 |
mceliece6688128f | 1,166,028,776 | 1,210,393,799 | 1,210,453 | 200,919,923 |
mceliece6960119 | 2,684,515,149 | 2,194,168,253 | 3,135,087 | 194,131,917 |
mceliece6960119f | 1,146,146,983 | 1,038,560,469 | 3,101,435 | 194,415,995 |
mceliece8192128 | 3,044,572,096 | 2,873,255,542 | 1,068,166 | 249,912,972 |
mceliece8192128f | 1,362,327,626 | 2,009,006,653 | 1,790,924 | 272,566,816 |
The C reference implementation yielded the following runtime results:
complete KEM | keypair | enc | dec | |
mceliece348864 | 434,103,000 | 437,187,000 | 187,557 | 73,801,300 |
mceliece348864f | 252,423,000 | 180,235,000 | 189,522 | 73,668,000 |
mceliece460896 | 760,993,000 | 894,497,000 | 298,041 | 154,507,000 |
mceliece460896f | 606,225,000 | 44,906,000 | 297,743 | 154,013,000 |
mceliece6688128 | 1,568,900,000 | 1,780,660,000 | 425,504 | 29,575,000 |
mceliece6688128f | 109,471,000 | 760,298,000 | 414,358 | 298,173,000 |
mceliece6960119 | 3,405,730,000 | 1,694,410,000 | 840,598 | 287,154,000 |
mceliece6960119f | 1,311,130,000 | 942,987,000 | 984,660 | 303,543,000 |
mceliece8192128 | 1,635,550,000 | 760,619,000 | 428,112 | 361,999,000 |
mceliece8192128f | 1,772,530,000 | 1,222,720,000 | 534,503 | 392,729,000 |
The tests were done on a Lenovo Thinkpad x260 (Intel Core i5-6200U CPU @ 2.30GHz). In the case of rust, criterion 0.3.5 has been used as given in benches/
and in case of C, Google's benchmark with PFM support and disabled CPU frequency scaling. You can run the benchmark suite yourself with the bench
subcommand and optionally some variant feature flag:
$ cargo bench --features mceliece348864
Yes, besides passing unittests (derived from the C implementation), the generated KAT KEM test files have equivalent MD5 hashes. Namely …
variant | expected MD5 hash |
mceliece348864 | d2def196fde89e938d3d45b2c6f806aa |
mceliece348864f | 84b5357d8dd656bed9297e28beb15057 |
mceliece460896 | 8aac2122916b901172e49e009efeede6 |
mceliece460896f | d84d3b179e303b9f3fc32ccb6befb886 |
mceliece6688128 | b86987d56c45da2e326556864e66bda7 |
mceliece6688128f | ae1e42cac2a885a87a2c241e05391481 |
mceliece6960119 | 9d9b3c9e8d7595503248131c584394be |
mceliece6960119f | c79b1bd28fd307f8d157bd566374bfb3 |
mceliece8192128 | b233e2585359a1133a1135c66fa48282 |
mceliece8192128f | d21bcb80dde24826e2c14254da917df3 |
On github.
- 2022-04-01 version 1.0.0: public release (no April fools though)
On github.