logicaffeine_proof/
xl.rs

1//! XL — algebraic cryptanalysis of multivariate quadratic (MQ) systems by linearization.
2//!
3//! Multivariate signatures (Oil-and-Vinegar, Rainbow, HFE) hide a secret behind a system of
4//! quadratic equations over a finite field; forging a signature or recovering a key reduces
5//! to *solving* such a system. XL does it by **linearization**: multiply every equation by
6//! every monomial up to a chosen degree `D`, treat each distinct monomial (including the
7//! quadratics) as an independent unknown, and solve the resulting *linear* system. When the
8//! equations are dense enough — past the *degree of regularity* Prof. Ding formalized — the
9//! linear system pins the original variables and the secret falls out.
10//!
11//! The engine is field-generic over [`Field`]: [`Gf2`] (the multilinear ring where `x² = x`)
12//! and [`Gf256`] (the field multivariate signatures actually use, delegating to the
13//! pit-of-success-tested [`logicaffeine_base::gf256`]). The linear algebra is exact Gaussian
14//! elimination — no floating point.
15//!
16//! **Contract:** [`xl_solve`] returns `Some(x)` *only after verifying* `x` satisfies the
17//! original system. It can therefore never report a spurious break — at worst it misses (needs
18//! a higher degree) and returns `None`. A returned solution is a genuine preimage/forgery.
19
20use crate::macaulay::{self, one, Monomial};
21use std::collections::{BTreeMap, HashMap};
22
23/// A finite field small enough to enumerate — the arithmetic XL runs its linear algebra over.
24pub trait Field: Copy + Eq + std::fmt::Debug {
25    /// Whether the polynomial ring is multilinear (`x² = x`). True for GF(2), where we impose
26    /// the field equations; false for GF(256), where quadratics are genuine.
27    const MULTILINEAR: bool;
28    fn zero() -> Self;
29    fn one() -> Self;
30    fn add(self, o: Self) -> Self;
31    fn sub(self, o: Self) -> Self;
32    fn mul(self, o: Self) -> Self;
33    /// Multiplicative inverse; caller guarantees `self` is non-zero.
34    fn inv(self) -> Self;
35    fn is_zero(self) -> bool {
36        self == Self::zero()
37    }
38}
39
40/// GF(2) as the multilinear ring: elements `0`/`1`, addition is XOR, multiplication is AND.
41#[derive(Clone, Copy, PartialEq, Eq, Debug)]
42pub struct Gf2(pub u8);
43
44impl Field for Gf2 {
45    const MULTILINEAR: bool = true;
46    fn zero() -> Self {
47        Gf2(0)
48    }
49    fn one() -> Self {
50        Gf2(1)
51    }
52    fn add(self, o: Self) -> Self {
53        Gf2(self.0 ^ o.0)
54    }
55    fn sub(self, o: Self) -> Self {
56        Gf2(self.0 ^ o.0)
57    }
58    fn mul(self, o: Self) -> Self {
59        Gf2(self.0 & o.0)
60    }
61    fn inv(self) -> Self {
62        debug_assert_eq!(self.0, 1, "GF(2) inverse of 0");
63        Gf2(1)
64    }
65}
66
67/// GF(2^8) — the field of the multivariate-signature attack surface. All arithmetic delegates
68/// to [`logicaffeine_base::gf256`] (the exhaustively-verified shared field substrate).
69#[derive(Clone, Copy, PartialEq, Eq, Debug)]
70pub struct Gf256(pub u8);
71
72impl Field for Gf256 {
73    const MULTILINEAR: bool = false;
74    fn zero() -> Self {
75        Gf256(0)
76    }
77    fn one() -> Self {
78        Gf256(1)
79    }
80    fn add(self, o: Self) -> Self {
81        Gf256(logicaffeine_base::gf256::add(self.0, o.0))
82    }
83    fn sub(self, o: Self) -> Self {
84        Gf256(logicaffeine_base::gf256::sub(self.0, o.0))
85    }
86    fn mul(self, o: Self) -> Self {
87        Gf256(logicaffeine_base::gf256::mul(self.0, o.0))
88    }
89    fn inv(self) -> Self {
90        Gf256(logicaffeine_base::gf256::inv(self.0))
91    }
92}
93
94/// A polynomial: monomial → coefficient, only non-zero terms stored.
95pub type Poly<F> = BTreeMap<Monomial, F>;
96
97/// A multivariate quadratic system in `n` variables: solutions are the common zeros of `polys`.
98#[derive(Clone, Debug)]
99pub struct MQSystem<F: Field> {
100    pub n: usize,
101    pub polys: Vec<Poly<F>>,
102}
103
104/// Evaluate a polynomial at an assignment `x` (length ≥ every variable index used).
105pub fn eval<F: Field>(p: &Poly<F>, x: &[F]) -> F {
106    let mut acc = F::zero();
107    for (m, &c) in p {
108        let mut term = c;
109        for &v in m {
110            term = term.mul(x[v as usize]);
111        }
112        acc = acc.add(term);
113    }
114    acc
115}
116
117impl<F: Field> MQSystem<F> {
118    /// Does `x` satisfy every equation (i.e. is it a common zero)?
119    pub fn satisfied_by(&self, x: &[F]) -> bool {
120        self.polys.iter().all(|p| eval(p, x).is_zero())
121    }
122}
123
124/// Multiply a polynomial by a single monomial in the (possibly multilinear) ring.
125fn poly_mul_mono<F: Field>(p: &Poly<F>, t: &Monomial, multilinear: bool) -> Poly<F> {
126    let mut r: Poly<F> = BTreeMap::new();
127    for (m, &c) in p {
128        let mm = macaulay::mul(m, t, multilinear);
129        let s = r.get(&mm).copied().unwrap_or_else(F::zero).add(c);
130        if s.is_zero() {
131            r.remove(&mm);
132        } else {
133            r.insert(mm, s);
134        }
135    }
136    r
137}
138
139/// Reduce augmented `rows` to reduced row-echelon form, pivoting only in the first
140/// `pivot_limit` columns. Returns the pivot column of each pivot row, in row order.
141fn rref<F: Field>(rows: &mut [Vec<F>], pivot_limit: usize) -> Vec<usize> {
142    let mut pivots = Vec::new();
143    if rows.is_empty() {
144        return pivots;
145    }
146    let width = rows[0].len();
147    let mut r = 0usize;
148    for c in 0..pivot_limit {
149        let mut piv = None;
150        for i in r..rows.len() {
151            if !rows[i][c].is_zero() {
152                piv = Some(i);
153                break;
154            }
155        }
156        let Some(pi) = piv else { continue };
157        rows.swap(r, pi);
158        let invp = rows[r][c].inv();
159        for j in 0..width {
160            rows[r][j] = rows[r][j].mul(invp);
161        }
162        for i in 0..rows.len() {
163            if i != r && !rows[i][c].is_zero() {
164                let f = rows[i][c];
165                for j in 0..width {
166                    let t = f.mul(rows[r][j]);
167                    rows[i][j] = rows[i][j].sub(t);
168                }
169            }
170        }
171        pivots.push(c);
172        r += 1;
173        if r == rows.len() {
174            break;
175        }
176    }
177    pivots
178}
179
180/// A particular solution of `A x = b` over `F` (free variables set to zero), or `None` if the
181/// system is inconsistent.
182fn solve<F: Field>(a: &[Vec<F>], b: &[F]) -> Option<Vec<F>> {
183    if a.is_empty() {
184        return None;
185    }
186    let n = a[0].len();
187    let mut rows: Vec<Vec<F>> = a
188        .iter()
189        .zip(b.iter())
190        .map(|(row, &rhs)| {
191            let mut r = row.clone();
192            r.push(rhs);
193            r
194        })
195        .collect();
196    let pivots = rref(&mut rows, n);
197    for row in &rows {
198        if row[..n].iter().all(|c| c.is_zero()) && !row[n].is_zero() {
199            return None; // 0 = nonzero
200        }
201    }
202    let mut x = vec![F::zero(); n];
203    for (ri, &c) in pivots.iter().enumerate() {
204        x[c] = rows[ri][n];
205    }
206    Some(x)
207}
208
209/// Solve an MQ system by XL: linearize at increasing degrees `d` up to `max_degree`, and at
210/// each degree read the linear variables off the linear solution and verify them against the
211/// original system. Returns a verified common zero, or `None` if none was found by
212/// `max_degree`.
213pub fn xl_solve<F: Field>(sys: &MQSystem<F>, max_degree: usize) -> Option<Vec<F>> {
214    let ml = F::MULTILINEAR;
215    let n = sys.n as u32;
216    let sys_deg = sys
217        .polys
218        .iter()
219        .flat_map(|p| p.keys())
220        .map(|m| m.len())
221        .max()
222        .unwrap_or(0);
223    let start = sys_deg.max(1);
224    for d in start..=max_degree {
225        // Columns = every monomial up to degree d; the constant (index 0) is known = 1, so it
226        // becomes the right-hand side and the remaining monomials are the linearized unknowns.
227        let cols = macaulay::monomials_up_to_degree(n, d, ml);
228        let mut idx: HashMap<Monomial, usize> = HashMap::with_capacity(cols.len());
229        for (i, m) in cols.iter().enumerate() {
230            idx.insert(m.clone(), i);
231        }
232        let num_unknowns = cols.len() - 1; // minus the constant
233
234        let mut a_rows: Vec<Vec<F>> = Vec::new();
235        let mut b: Vec<F> = Vec::new();
236        for f in &sys.polys {
237            let fdeg = f.keys().map(|m| m.len()).max().unwrap_or(0);
238            if fdeg > d {
239                continue;
240            }
241            for t in macaulay::monomials_up_to_degree(n, d - fdeg, ml) {
242                let ext = poly_mul_mono(f, &t, ml);
243                let mut row = vec![F::zero(); num_unknowns];
244                let mut rhs = F::zero();
245                for (m, &c) in &ext {
246                    if m.is_empty() {
247                        rhs = rhs.sub(c); // move the constant term to the RHS: A u = −const
248                    } else {
249                        let j = idx[m] - 1; // shift past the constant column
250                        row[j] = row[j].add(c);
251                    }
252                }
253                a_rows.push(row);
254                b.push(rhs);
255            }
256        }
257
258        if let Some(u) = solve(&a_rows, &b) {
259            let mut x = vec![F::zero(); sys.n];
260            for i in 0..sys.n {
261                if let Some(&ci) = idx.get(&vec![i as u32]) {
262                    x[i] = u[ci - 1];
263                }
264            }
265            if sys.satisfied_by(&x) {
266                return Some(x);
267            }
268        }
269    }
270    None
271}
272
273#[cfg(test)]
274#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/xl/tests.rs"]
275mod tests;
logicaffeine_proof/xl.rs

logicaffeine_proof/
xl.rs
