krypteia-arcana 0.1.0

//! RSA core operations (RFC 8017 / PKCS#1 v2.2): key generation,
//! raw encrypt / decrypt with the Chinese Remainder Theorem (CRT).
//!
//! Supports key sizes from 1024 to 4096 bits (tested values
//! 1024 / 2048 / 3072 / 4096). Arbitrary widths are supported by
//! the [`super::bigint::BigInt`] arithmetic but keygen above ~4096
//! bits gets impractical with the current schoolbook multiplier.
//!
//! # Side-channel posture
//!
//! This module is the **highest-priority evaluation gap** on the
//! classical side as of 2026-04-21:
//!
//! | Threat                             | Status         | Roadmap item                                               |
//! |------------------------------------|----------------|------------------------------------------------------------|
//! | Bellcore single-fault on RSA-CRT   | **vulnerable** | `T1-C` — Aumüller 2002, formally verified Rauzy-Guilley    |
//! | SPA on modular exponentiation      | partial        | `T1-E` — bigint CT audit + `black_box` shielding           |
//! | DPA on Montgomery multiplication   | **vulnerable** | `T2-I` — message blinding (Coron 1999)                     |
//! | Timing on bigint operations        | partial        | `T1-E`                                                     |
//! | Padding-oracle (PKCS#1 v1.5)       | partial        | `T2-J` — RFC 8017 §7.2.2 CT padding-oracle handling        |
//!
//! The Bellcore attack (Boneh-DeMillo-Lipton 1997 → JoC 2001)
//! computes `gcd(N, S - S')` where `S'` is a CRT-faulted
//! signature: a single fault on either half-exponentiation
//! reveals `p` or `q`, which factors `N` and recovers the entire
//! secret key. Equipment cost: ~1 k€ for a Chipwhisperer voltage
//! glitcher, days of bench time for a skilled operator.
//! **Aumüller's countermeasure resists all single-fault attacks**
//! under the formal model of `rauzy2013_formal_crt_rsa`.
//!
//! See `arcana/doc/sca/countermeasures/rsa.rst` for the full
//! threat model, the implementation route for each item, and the
//! published references.
//!
//! # Zeroize-on-Drop
//!
//! [`RsaSecretKey`] currently does **not** implement `Drop` with
//! `silentops::ct_zeroize`. Callers handling a `RsaSecretKey`
//! must zeroize the underlying `BigInt` storage explicitly when
//! it leaves scope. Roadmap item `T2-E`.

use super::bigint::BigInt;

/// RSA public key.
#[derive(Clone, Debug)]
pub struct RsaPublicKey {
    /// Modulus n = p * q.
    pub n: BigInt,
    /// Public exponent (typically 65537).
    pub e: BigInt,
}

/// RSA secret key with CRT components.
#[derive(Clone, Debug)]
pub struct RsaSecretKey {
    /// Modulus n = p * q.
    pub n: BigInt,
    /// Private exponent d = e^{-1} mod lcm(p-1, q-1).
    pub d: BigInt,
    /// First prime factor.
    pub p: BigInt,
    /// Second prime factor.
    pub q: BigInt,
    /// d mod (p-1) for CRT.
    pub dp: BigInt,
    /// d mod (q-1) for CRT.
    pub dq: BigInt,
    /// q^{-1} mod p for CRT.
    pub qinv: BigInt,
}

impl RsaPublicKey {
    /// Byte length of the modulus.
    pub fn modulus_byte_len(&self) -> usize {
        self.n.byte_len()
    }
}

impl RsaSecretKey {
    /// Byte length of the modulus.
    pub fn modulus_byte_len(&self) -> usize {
        self.n.byte_len()
    }
}

/// Generate an RSA key pair of the given bit size.
///
/// `rng` is a callback that fills a buffer with random bytes.
/// Typical bit sizes: 1024 (testing only), 2048, 3072, 4096.
pub fn rsa_keygen(bits: usize, rng: &mut dyn FnMut(&mut [u8])) -> (RsaPublicKey, RsaSecretKey) {
    let half = bits / 2;
    let e = BigInt::from_u64(65537);

    loop {
        let p = BigInt::random_prime(half, rng);
        let q = BigInt::random_prime(half, rng);

        if p == q {
            continue;
        }

        let n = p.mul(&q);
        if n.bit_len() != bits {
            continue;
        }

        let one = BigInt::from_u64(1);
        let p1 = p.sub(&one);
        let q1 = q.sub(&one);

        // Compute lcm(p-1, q-1) = (p-1)*(q-1) / gcd(p-1, q-1)
        let phi = p1.mul(&q1);
        let g = gcd(&p1, &q1);
        let lambda = phi.div_rem(&g).0;

        // d = e^{-1} mod lambda
        let d = match e.mod_inv(&lambda) {
            Some(d) => d,
            None => continue,
        };

        // CRT components
        let dp = d.rem(&p1);
        let dq = d.rem(&q1);
        let qinv = match q.mod_inv(&p) {
            Some(qi) => qi,
            None => continue,
        };

        let pk = RsaPublicKey { n: n.clone(), e };
        let sk = RsaSecretKey {
            n,
            d,
            p,
            q,
            dp,
            dq,
            qinv,
        };
        return (pk, sk);
    }
}

/// Raw RSA encryption: `m^e mod n`.
///
/// Operates on the public modulus and the public message; **no
/// secret material flows through this function**, so SCA is not a
/// concern here. The public exponent `e` (typically 65537) leaks
/// trivially through control flow, which is fine.
pub fn rsa_encrypt_raw(pk: &RsaPublicKey, m: &BigInt) -> BigInt {
    m.mod_exp(&pk.e, &pk.n)
}

/// Raw RSA decryption with the Chinese Remainder Theorem:
/// computes `c^d mod n` via the CRT half-exponentiations
///
/// ```text
///   m_p = c^{dp} mod p,   m_q = c^{dq} mod q,
///   m   = m_q + q * (qinv * (m_p - m_q) mod p)
/// ```
///
/// # ⚠ Side-channel surface (evaluation-critical)
///
/// This is the function targeted by the **Bellcore attack**
/// (Boneh-DeMillo-Lipton 1997): a single fault on either
/// `m_p` or `m_q` produces a faulted signature `S'` such that
/// `gcd(N, S - S')` reveals `p` or `q`, which factors `N` and
/// breaks the key. **Aumüller's countermeasure
/// (`aumuller2002rsa_crt`) is the standard fix and is NOT yet
/// implemented in arcana** — roadmap item `T1-C` (see
/// `arcana/doc/sca/countermeasures/rsa.rst`).
///
/// Additional gaps tracked in the same document:
///
/// - `T1-E`: bigint CT audit (`pow_mod`, Montgomery multiply,
///   `cmp` early-exit).
/// - `T2-I`: message blinding (`r^e * c`) against DPA on the
///   per-iteration Montgomery multiplications inside `pow_mod`.
///
/// Until these countermeasures land, **this function should not
/// be used in deployments where a level-2 (observational) or
/// level-3 (active fault) attacker is in scope**.
pub fn rsa_decrypt_raw(sk: &RsaSecretKey, c: &BigInt) -> BigInt {
    // CRT decryption:
    // m1 = c^dp mod p
    // m2 = c^dq mod q
    // h = qinv * (m1 - m2) mod p
    // m = m2 + h * q
    let cp = c.rem(&sk.p);
    let cq = c.rem(&sk.q);
    let m1 = cp.mod_exp(&sk.dp, &sk.p);
    let m2 = cq.mod_exp(&sk.dq, &sk.q);

    // Compute h = qinv * (m1 - m2) mod p
    // m1 is in [0, p) and m2 is in [0, q). The difference can be negative,
    // so we reduce m2 mod p first, then handle the sign.
    let m2_mod_p = m2.rem(&sk.p);
    let diff = if m1 >= m2_mod_p {
        m1.sub(&m2_mod_p)
    } else {
        m1.add(&sk.p).sub(&m2_mod_p)
    };
    let h = sk.qinv.mul(&diff).rem(&sk.p);

    // m = m2 + h * q
    m2.add(&h.mul(&sk.q))
}

/// GCD of two BigInts using Euclidean algorithm.
fn gcd(a: &BigInt, b: &BigInt) -> BigInt {
    let mut a = a.clone();
    let mut b = b.clone();
    while !b.is_zero() {
        let r = a.rem(&b);
        a = b;
        b = r;
    }
    a
}

#[cfg(test)]
mod tests {
    use super::*;

    fn test_rng() -> impl FnMut(&mut [u8]) {
        let mut state: u64 = 0xdeadbeefcafebabe;
        move |buf: &mut [u8]| {
            for b in buf.iter_mut() {
                state = state
                    .wrapping_mul(6364136223846793005)
                    .wrapping_add(1442695040888963407);
                *b = (state >> 33) as u8;
            }
        }
    }

    #[test]
    fn test_raw_encrypt_decrypt_small() {
        // Use known small primes for a quick test.
        let p = BigInt::from_u64(61);
        let q = BigInt::from_u64(53);
        let n = p.mul(&q); // 3233
        let e = BigInt::from_u64(17);
        let one = BigInt::from_u64(1);
        let p1 = p.sub(&one);
        let q1 = q.sub(&one);
        let lambda = p1.mul(&q1); // 60 * 52 = 3120
        let d = e.mod_inv(&lambda).unwrap();
        let dp = d.rem(&p1);
        let dq = d.rem(&q1);
        let qinv = q.mod_inv(&p).unwrap();

        let pk = RsaPublicKey { n: n.clone(), e };
        let sk = RsaSecretKey {
            n,
            d,
            p,
            q,
            dp,
            dq,
            qinv,
        };

        let m = BigInt::from_u64(42);
        let c = rsa_encrypt_raw(&pk, &m);
        let m2 = rsa_decrypt_raw(&sk, &c);
        assert_eq!(m, m2);
    }

    #[test]
    fn test_keygen_roundtrip() {
        let mut rng = test_rng();
        let (pk, sk) = rsa_keygen(512, &mut rng);
        let m = BigInt::from_u64(12345678);
        let c = rsa_encrypt_raw(&pk, &m);
        let m2 = rsa_decrypt_raw(&sk, &c);
        assert_eq!(m, m2);
    }
}