arcana/rsa/
rsa.rs

1//! RSA core operations (RFC 8017 / PKCS#1 v2.2): key generation,
2//! raw encrypt / decrypt with the Chinese Remainder Theorem (CRT).
3//!
4//! Supports key sizes from 1024 to 4096 bits (tested values
5//! 1024 / 2048 / 3072 / 4096). Arbitrary widths are supported by
6//! the [`super::bigint::BigInt`] arithmetic but keygen above ~4096
7//! bits gets impractical with the current schoolbook multiplier.
8//!
9//! # Side-channel posture
10//!
11//! This module is the **highest-priority evaluation gap** on the
12//! classical side as of 2026-04-21:
13//!
14//! | Threat                             | Status         | Roadmap item                                               |
15//! |------------------------------------|----------------|------------------------------------------------------------|
16//! | Bellcore single-fault on RSA-CRT   | **vulnerable** | `T1-C` — Aumüller 2002, formally verified Rauzy-Guilley    |
17//! | SPA on modular exponentiation      | partial        | `T1-E` — bigint CT audit + `black_box` shielding           |
18//! | DPA on Montgomery multiplication   | **vulnerable** | `T2-I` — message blinding (Coron 1999)                     |
19//! | Timing on bigint operations        | partial        | `T1-E`                                                     |
20//! | Padding-oracle (PKCS#1 v1.5)       | partial        | `T2-J` — RFC 8017 §7.2.2 CT padding-oracle handling        |
21//!
22//! The Bellcore attack (Boneh-DeMillo-Lipton 1997 → JoC 2001)
23//! computes `gcd(N, S - S')` where `S'` is a CRT-faulted
24//! signature: a single fault on either half-exponentiation
25//! reveals `p` or `q`, which factors `N` and recovers the entire
26//! secret key. Equipment cost: ~1 k€ for a Chipwhisperer voltage
27//! glitcher, days of bench time for a skilled operator.
28//! **Aumüller's countermeasure resists all single-fault attacks**
29//! under the formal model of `rauzy2013_formal_crt_rsa`.
30//!
31//! See `arcana/doc/sca/countermeasures/rsa.rst` for the full
32//! threat model, the implementation route for each item, and the
33//! published references.
34//!
35//! # Zeroize-on-Drop
36//!
37//! [`RsaSecretKey`] currently does **not** implement `Drop` with
38//! `silentops::ct_zeroize`. Callers handling a `RsaSecretKey`
39//! must zeroize the underlying `BigInt` storage explicitly when
40//! it leaves scope. Roadmap item `T2-E`.
41
42use super::bigint::BigInt;
43
44/// RSA public key.
45#[derive(Clone, Debug)]
46pub struct RsaPublicKey {
47    /// Modulus n = p * q.
48    pub n: BigInt,
49    /// Public exponent (typically 65537).
50    pub e: BigInt,
51}
52
53/// RSA secret key with CRT components.
54#[derive(Clone, Debug)]
55pub struct RsaSecretKey {
56    /// Modulus n = p * q.
57    pub n: BigInt,
58    /// Private exponent d = e^{-1} mod lcm(p-1, q-1).
59    pub d: BigInt,
60    /// First prime factor.
61    pub p: BigInt,
62    /// Second prime factor.
63    pub q: BigInt,
64    /// d mod (p-1) for CRT.
65    pub dp: BigInt,
66    /// d mod (q-1) for CRT.
67    pub dq: BigInt,
68    /// q^{-1} mod p for CRT.
69    pub qinv: BigInt,
70}
71
72impl RsaPublicKey {
73    /// Byte length of the modulus.
74    pub fn modulus_byte_len(&self) -> usize {
75        self.n.byte_len()
76    }
77}
78
79impl RsaSecretKey {
80    /// Byte length of the modulus.
81    pub fn modulus_byte_len(&self) -> usize {
82        self.n.byte_len()
83    }
84}
85
86/// Generate an RSA key pair of the given bit size.
87///
88/// `rng` is a callback that fills a buffer with random bytes.
89/// Typical bit sizes: 1024 (testing only), 2048, 3072, 4096.
90pub fn rsa_keygen(bits: usize, rng: &mut dyn FnMut(&mut [u8])) -> (RsaPublicKey, RsaSecretKey) {
91    let half = bits / 2;
92    let e = BigInt::from_u64(65537);
93
94    loop {
95        let p = BigInt::random_prime(half, rng);
96        let q = BigInt::random_prime(half, rng);
97
98        if p == q {
99            continue;
100        }
101
102        let n = p.mul(&q);
103        if n.bit_len() != bits {
104            continue;
105        }
106
107        let one = BigInt::from_u64(1);
108        let p1 = p.sub(&one);
109        let q1 = q.sub(&one);
110
111        // Compute lcm(p-1, q-1) = (p-1)*(q-1) / gcd(p-1, q-1)
112        let phi = p1.mul(&q1);
113        let g = gcd(&p1, &q1);
114        let lambda = phi.div_rem(&g).0;
115
116        // d = e^{-1} mod lambda
117        let d = match e.mod_inv(&lambda) {
118            Some(d) => d,
119            None => continue,
120        };
121
122        // CRT components
123        let dp = d.rem(&p1);
124        let dq = d.rem(&q1);
125        let qinv = match q.mod_inv(&p) {
126            Some(qi) => qi,
127            None => continue,
128        };
129
130        let pk = RsaPublicKey { n: n.clone(), e };
131        let sk = RsaSecretKey {
132            n,
133            d,
134            p,
135            q,
136            dp,
137            dq,
138            qinv,
139        };
140        return (pk, sk);
141    }
142}
143
144/// Raw RSA encryption: `m^e mod n`.
145///
146/// Operates on the public modulus and the public message; **no
147/// secret material flows through this function**, so SCA is not a
148/// concern here. The public exponent `e` (typically 65537) leaks
149/// trivially through control flow, which is fine.
150pub fn rsa_encrypt_raw(pk: &RsaPublicKey, m: &BigInt) -> BigInt {
151    m.mod_exp(&pk.e, &pk.n)
152}
153
154/// Raw RSA decryption with the Chinese Remainder Theorem:
155/// computes `c^d mod n` via the CRT half-exponentiations
156///
157/// ```text
158///   m_p = c^{dp} mod p,   m_q = c^{dq} mod q,
159///   m   = m_q + q * (qinv * (m_p - m_q) mod p)
160/// ```
161///
162/// # ⚠ Side-channel surface (evaluation-critical)
163///
164/// This is the function targeted by the **Bellcore attack**
165/// (Boneh-DeMillo-Lipton 1997): a single fault on either
166/// `m_p` or `m_q` produces a faulted signature `S'` such that
167/// `gcd(N, S - S')` reveals `p` or `q`, which factors `N` and
168/// breaks the key. **Aumüller's countermeasure
169/// (`aumuller2002rsa_crt`) is the standard fix and is NOT yet
170/// implemented in arcana** — roadmap item `T1-C` (see
171/// `arcana/doc/sca/countermeasures/rsa.rst`).
172///
173/// Additional gaps tracked in the same document:
174///
175/// - `T1-E`: bigint CT audit (`pow_mod`, Montgomery multiply,
176///   `cmp` early-exit).
177/// - `T2-I`: message blinding (`r^e * c`) against DPA on the
178///   per-iteration Montgomery multiplications inside `pow_mod`.
179///
180/// Until these countermeasures land, **this function should not
181/// be used in deployments where a level-2 (observational) or
182/// level-3 (active fault) attacker is in scope**.
183pub fn rsa_decrypt_raw(sk: &RsaSecretKey, c: &BigInt) -> BigInt {
184    // CRT decryption:
185    // m1 = c^dp mod p
186    // m2 = c^dq mod q
187    // h = qinv * (m1 - m2) mod p
188    // m = m2 + h * q
189    let cp = c.rem(&sk.p);
190    let cq = c.rem(&sk.q);
191    let m1 = cp.mod_exp(&sk.dp, &sk.p);
192    let m2 = cq.mod_exp(&sk.dq, &sk.q);
193
194    // Compute h = qinv * (m1 - m2) mod p
195    // m1 is in [0, p) and m2 is in [0, q). The difference can be negative,
196    // so we reduce m2 mod p first, then handle the sign.
197    let m2_mod_p = m2.rem(&sk.p);
198    let diff = if m1 >= m2_mod_p {
199        m1.sub(&m2_mod_p)
200    } else {
201        m1.add(&sk.p).sub(&m2_mod_p)
202    };
203    let h = sk.qinv.mul(&diff).rem(&sk.p);
204
205    // m = m2 + h * q
206    m2.add(&h.mul(&sk.q))
207}
208
209/// GCD of two BigInts using Euclidean algorithm.
210fn gcd(a: &BigInt, b: &BigInt) -> BigInt {
211    let mut a = a.clone();
212    let mut b = b.clone();
213    while !b.is_zero() {
214        let r = a.rem(&b);
215        a = b;
216        b = r;
217    }
218    a
219}
220
221#[cfg(test)]
222mod tests {
223    use super::*;
224
225    fn test_rng() -> impl FnMut(&mut [u8]) {
226        let mut state: u64 = 0xdeadbeefcafebabe;
227        move |buf: &mut [u8]| {
228            for b in buf.iter_mut() {
229                state = state
230                    .wrapping_mul(6364136223846793005)
231                    .wrapping_add(1442695040888963407);
232                *b = (state >> 33) as u8;
233            }
234        }
235    }
236
237    #[test]
238    fn test_raw_encrypt_decrypt_small() {
239        // Use known small primes for a quick test.
240        let p = BigInt::from_u64(61);
241        let q = BigInt::from_u64(53);
242        let n = p.mul(&q); // 3233
243        let e = BigInt::from_u64(17);
244        let one = BigInt::from_u64(1);
245        let p1 = p.sub(&one);
246        let q1 = q.sub(&one);
247        let lambda = p1.mul(&q1); // 60 * 52 = 3120
248        let d = e.mod_inv(&lambda).unwrap();
249        let dp = d.rem(&p1);
250        let dq = d.rem(&q1);
251        let qinv = q.mod_inv(&p).unwrap();
252
253        let pk = RsaPublicKey { n: n.clone(), e };
254        let sk = RsaSecretKey {
255            n,
256            d,
257            p,
258            q,
259            dp,
260            dq,
261            qinv,
262        };
263
264        let m = BigInt::from_u64(42);
265        let c = rsa_encrypt_raw(&pk, &m);
266        let m2 = rsa_decrypt_raw(&sk, &c);
267        assert_eq!(m, m2);
268    }
269
270    #[test]
271    fn test_keygen_roundtrip() {
272        let mut rng = test_rng();
273        let (pk, sk) = rsa_keygen(512, &mut rng);
274        let m = BigInt::from_u64(12345678);
275        let c = rsa_encrypt_raw(&pk, &m);
276        let m2 = rsa_decrypt_raw(&sk, &c);
277        assert_eq!(m, m2);
278    }
279}
arcana/rsa/rsa.rs

arcana/rsa/
rsa.rs
