krypteia-quantica 0.1.0

//! Fisher-Yates shuffle for NTT butterfly index randomization
//! (**countermeasure: SPA / SEMA on secret-polynomial NTT**).
//!
//! ## Principle
//!
//! Butterflies at the same NTT level are mutually independent: permuting
//! their execution order does not change the output polynomial, only the
//! pattern of memory accesses and instantaneous power consumption. By
//! drawing a fresh permutation on every invocation from a CSPRNG seeded
//! with per-signature entropy, two successive NTTs on the same input
//! produce different power / EM traces, defeating trace-alignment-based
//! SPA and template attacks.
//!
//! The permutation is drawn with rejection sampling on a 16-bit RNG
//! output so the sampled indices are unbiased.
//!
//! ## References
//!
//! * J. Aycock et al., *Hardware NTT shuffling as a lightweight
//!   countermeasure for ML-KEM* (arXiv, 2024) — baseline hardware
//!   construction we re-implement in software.
//! * M.-J. O. Saarinen, *Practical side-channel evaluation of post-
//!   quantum primitives* (NIST, 2023) — independent evaluation of the
//!   shuffling benefit on ML-KEM / ML-DSA.
//!
//! ## Where to look next
//!
//! * Countermeasure description and threat analysis:
//!   `doc/sca/countermeasures/ml_kem.rst`, section
//!   *SPA / SEMA — NTT butterfly shuffling*.
//! * Call sites: `quantica/src/ml_kem/kem.rs`, functions
//!   `keygen_internal_sca` and `decaps_internal_sca`.
//! * Companion primitive reference: `doc/sca/primitives.rst`.

use super::MlKemError;
use super::rng::CryptoRng;

/// Generate a uniform random permutation of `0..n` using Fisher-Yates.
///
/// Iterates from the last index down to 1, swapping each element with a
/// uniformly chosen earlier (or equal) element. Uses rejection sampling
/// on 16-bit random values to avoid modular bias.
///
/// # Arguments
///
/// * `perm` - Output slice of length `n`, initialized to `[0, 1, ..., n-1]`
///   then shuffled in place.
/// * `rng` - A cryptographic RNG for generating swap indices.
///
/// # Errors
///
/// Returns [`MlKemError::RngFailure`] if the RNG fails.
pub fn generate_permutation(perm: &mut [u16], rng: &mut impl CryptoRng) -> Result<(), MlKemError> {
    let n = perm.len();
    for i in 0..n {
        perm[i] = i as u16;
    }
    // Fisher-Yates: for i from n-1 downto 1, swap perm[i] with perm[rand(0..=i)]
    let mut rand_buf = [0u8; 2];
    for i in (1..n).rev() {
        let bound = (i + 1) as u16;
        // Rejection sampling to avoid modular bias
        let limit = u16::MAX - (u16::MAX % bound);
        loop {
            rng.fill_bytes(&mut rand_buf)?;
            let r = u16::from_le_bytes(rand_buf);
            if r < limit {
                let j = (r % bound) as usize;
                perm.swap(i, j);
                break;
            }
        }
    }
    Ok(())
}

/// Forward NTT with randomized butterfly ordering (SPA countermeasure).
///
/// Functionally equivalent to [`super::ntt::ntt`] but randomizes the
/// execution order of butterfly operations at each NTT level. Both the
/// group order (which butterfly group runs first) and the intra-group
/// order (which pair within a group runs first) are independently
/// shuffled using fresh [`generate_permutation`] calls.
///
/// A new random permutation is generated for every level and every group,
/// so successive invocations produce different power traces even for
/// identical inputs.
///
/// # Arguments
///
/// * `f` - A mutable reference to a 256-coefficient polynomial. Modified in place.
/// * `rng` - A cryptographic RNG for generating shuffle permutations.
///
/// # Errors
///
/// Returns [`MlKemError::RngFailure`] if the RNG fails during permutation generation.
pub fn ntt_shuffled(f: &mut [i16; 256], rng: &mut impl CryptoRng) -> Result<(), MlKemError> {
    use super::ntt::Q;
    const ZETAS: [i16; 128] = [
        1, 1729, 2580, 3289, 2642, 630, 1897, 848, 1062, 1919, 193, 797, 2786, 3260, 569, 1746, 296, 2447, 1339, 1476,
        3046, 56, 2240, 1333, 1426, 2094, 535, 2882, 2393, 2879, 1974, 821, 289, 331, 3253, 1756, 1197, 2304, 2277,
        2055, 650, 1977, 2513, 632, 2865, 33, 1320, 1915, 2319, 1435, 807, 452, 1438, 2868, 1534, 2402, 2647, 2617,
        1481, 648, 2474, 3110, 1227, 910, 17, 2761, 583, 2649, 1637, 723, 2288, 1100, 1409, 2662, 3281, 233, 756, 2156,
        3015, 3050, 1703, 1651, 2789, 1789, 1847, 952, 1461, 2687, 939, 2308, 2437, 2388, 733, 2337, 268, 641, 1584,
        2298, 2037, 3220, 375, 2549, 2090, 1645, 1063, 319, 2773, 757, 2099, 561, 2466, 2594, 2804, 1092, 403, 1026,
        1143, 2150, 2775, 886, 1722, 1212, 1874, 1029, 2110, 2935, 885, 2154,
    ];

    fn mod_q(a: i32) -> i16 {
        let mut r = a % (Q as i32);
        r += (Q as i32) & (r >> 31);
        r as i16
    }
    fn mul_mod(a: i16, b: i16) -> i16 {
        mod_q(a as i32 * b as i32)
    }

    let mut k = 1usize;
    let mut len = 128;
    while len >= 2 {
        let num_groups = 256 / (2 * len);
        // Generate random permutation of group indices
        let mut perm = vec![0u16; num_groups];
        generate_permutation(&mut perm, rng)?;

        for &gi in perm.iter() {
            let start = gi as usize * 2 * len;
            let zeta = ZETAS[k + gi as usize];
            // Also shuffle butterfly indices within each group
            let mut inner_perm = vec![0u16; len];
            generate_permutation(&mut inner_perm, rng)?;
            for &ji in inner_perm.iter() {
                let j = start + ji as usize;
                let t = mul_mod(zeta, f[j + len]);
                f[j + len] = mod_q(f[j] as i32 - t as i32);
                f[j] = mod_q(f[j] as i32 + t as i32);
            }
        }
        k += num_groups;
        len >>= 1;
    }
    Ok(())
}