classic-mceliece-rust 3.1.0

Pure rust implementation of the PQC scheme Classic McEliece
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

//! This file implements the Berlekamp-Massey algorithm
//! see <http://crypto.stanford.edu/~mironov/cs359/massey.pdf>

use crate::gf::{gf_frac, gf_mul, Gf};
use crate::params::SYS_T;

fn min(a: usize, b: usize) -> usize {
    let c = (a < b) as isize;
    let d = c << (isize::BITS - 1);
    let e = (d >> (isize::BITS - 1)) as usize;
    (a & e) | (b & !e)
}

/// The Berlekamp-Massey algorithm.
/// Uses `s` as input (sequence of field elements)
/// and `out` as output (minimal polynomial of `s`)
pub(crate) fn bm(out: &mut [Gf; SYS_T + 1], s: &mut [Gf; 2 * SYS_T]) {
    let mut l: u16 = 0;
    let mut mle: u16;
    let mut mne: u16;

    let mut t;
    let mut c = [0u16; SYS_T + 1];
    let mut b = [0u16; SYS_T + 1];

    let mut base: Gf = 1;

    b[1] = 1;
    c[0] = 1;

    for n in 0..(2 * SYS_T) {
        let mut d: Gf = 0;
        for i in 0..=min(n, SYS_T) {
            d ^= gf_mul(c[i], s[n - i]);
        }
        mne = d;
        mne = mne.wrapping_sub(1);
        mne >>= 15;
        mne = mne.wrapping_sub(1);

        mle = n as u16;
        mle = mle.wrapping_sub(l.wrapping_mul(2));
        mle >>= 15;
        mle = mle.wrapping_sub(1);
        mle &= mne;

        t = c;

        let f: Gf = gf_frac(base, d);

        for i in 0..=SYS_T {
            c[i] ^= gf_mul(f, b[i]) & mne;
        }

        l = (l & !mle) | ((n as u16 + 1 - l) & mle);

        for i in 0..=SYS_T {
            b[i] = (b[i] & !mle) | (t[i] & mle);
        }

        base = (base & !mle) | (d & mle);

        for i in (1..=SYS_T).rev() {
            b[i] = b[i - 1];
        }

        b[0] = 0;
    }

    for i in 0..=SYS_T {
        out[i] = c[SYS_T - i];
    }
}

#[cfg(test)]
#[cfg(feature = "mceliece8192128f")]
mod tests {
    use super::*;
    use crate::macros::sub;
    use crate::test_utils::TestData;

    #[test]
    fn test_simple_bm() {
        assert_eq!(SYS_T + 1, 129);

        let compare_array: [u16; 129] = [
            7438, 1794, 2310, 1794, 5390, 1794, 2310, 1794, 3333, 1794, 2310, 1794, 5390, 1794,
            2310, 1794, 7432, 1794, 2310, 1794, 5390, 1794, 2310, 1794, 3333, 1794, 2310, 1794,
            5390, 1794, 2310, 1794, 7433, 1794, 2310, 1794, 5390, 1794, 2310, 1794, 3333, 1794,
            2310, 1794, 5390, 1794, 2310, 1794, 7432, 1794, 2310, 1794, 5390, 1794, 2310, 1794,
            3333, 1794, 2310, 1794, 5390, 1794, 2310, 1794, 7435, 1794, 2310, 1794, 5390, 1794,
            2310, 1794, 3333, 1794, 2310, 1794, 5390, 1794, 2310, 1794, 7432, 1794, 2310, 1794,
            5390, 1794, 2310, 1794, 3333, 1794, 2310, 1794, 5390, 1794, 2310, 1794, 7433, 1794,
            2310, 1794, 5390, 1794, 2310, 1794, 3333, 1794, 2310, 1794, 5390, 1794, 2310, 1794,
            7432, 1794, 2310, 1794, 5390, 1794, 2310, 1794, 3333, 1794, 2310, 1794, 5390, 1794,
            2310, 1794, 1,
        ];

        let mut locator = [0u16; SYS_T + 1];
        let mut s = [0u16; SYS_T * 2];

        for i in 0..s.len() {
            s[i] = i as u16;
        }

        bm(&mut locator, &mut s);

        assert_eq!(locator, compare_array);
    }

    #[test]
    fn test_first_round_bm() {
        let compare_array = TestData::new().u16vec("mceliece8192128f_bm_first_round_compare_array");
        let compare_array_slice = sub!(compare_array.as_slice(), 0, SYS_T + 1, u16);
        let mut s_input = TestData::new().u16vec("mceliece8192128f_bm_first_round_s_input");
        let s_input_slice = sub!(mut s_input.as_mut_slice(), 0, 2 * SYS_T, u16);

        let mut locator = [0u16; SYS_T + 1];
        bm(&mut locator, s_input_slice);

        assert_eq!(&locator, compare_array_slice);
    }
}