simoom_tls/crypto/
rsa.rs

1//! RSA signatures: PKCS#1 v1.5 and RSASSA-PSS (RFC 8017) verify and sign.
2//!
3//! Private-key operations use a fixed square-and-multiply-always Montgomery
4//! exponentiation over the full exponent width, with base blinding (the input is
5//! multiplied by `r^e` and the result by `r^-1` for a random `r`, the pair being
6//! squared after every use) and the Chinese Remainder Theorem when the key carries its
7//! CRT parameters (PKCS#1 keys); every result is verified with the public exponent before
8//! it is released (fault attacks on CRT). Not hardened against cache or power analysis
9//! beyond that.
10
11use std::sync::{Arc, Mutex};
12
13use super::bigint::{adc, bit_len, from_be_bytes, lt, mac, mod_sub, reduce_be, sbb, to_be_bytes, MontCtx};
14use super::sha2::HashAlg;
15use super::rng;
16use crate::util::ct_eq;
17
18#[derive(Clone)]
19pub struct RsaPublicKey {
20    ctx: MontCtx,
21    e: Vec<u64>,
22    /// Modulus size in bytes.
23    k: usize,
24    mod_bits: usize,
25}
26
27#[derive(Clone)]
28pub struct RsaPrivateKey {
29    pub public: RsaPublicKey,
30    d: Vec<u64>,
31    /// The original PKCS#1 encoding (with CRT parameters), when parsed from one.
32    pub(crate) pkcs1: Option<Vec<u8>>,
33    crt: Option<Crt>,
34    blinding: Arc<Mutex<Option<Blinding>>>,
35}
36
37/// CRT parameters: Montgomery contexts for p and q, d mod (p-1), d mod (q-1), q^-1 mod p.
38#[derive(Clone)]
39struct Crt {
40    p: MontCtx,
41    q: MontCtx,
42    dp: Vec<u64>,
43    dq: Vec<u64>,
44    qinv: Vec<u64>,
45}
46
47/// Base blinding pair: `vi = r^e mod n`, `vf = r^-1 mod n`.
48struct Blinding {
49    vi: Vec<u64>,
50    vf: Vec<u64>,
51}
52
53/// a * b mod m (plain representations).
54fn mod_mul(ctx: &MontCtx, a: &[u64], b: &[u64]) -> Vec<u64> {
55    ctx.mul(&ctx.to_mont(a), b)
56}
57
58/// Full product a * b.
59fn mul_full(a: &[u64], b: &[u64]) -> Vec<u64> {
60    let mut r = vec![0u64; a.len() + b.len()];
61    for (i, &x) in a.iter().enumerate() {
62        let mut carry = 0;
63        for (j, &y) in b.iter().enumerate() {
64            let (lo, hi) = mac(r[i + j], x, y, carry);
65            r[i + j] = lo;
66            carry = hi;
67        }
68        r[i + b.len()] = carry;
69    }
70    r
71}
72
73fn add_assign(r: &mut [u64], b: &[u64]) {
74    let mut carry = 0;
75    for i in 0..r.len() {
76        let (v, c) = adc(r[i], *b.get(i).unwrap_or(&0), carry);
77        r[i] = v;
78        carry = c;
79    }
80}
81
82fn trim_to(mut v: Vec<u64>, n: usize) -> Option<Vec<u64>> {
83    if v[n.min(v.len())..].iter().any(|x| *x != 0) {
84        return None;
85    }
86    v.resize(n, 0);
87    Some(v)
88}
89
90impl std::fmt::Debug for RsaPublicKey {
91    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
92        write!(f, "RsaPublicKey({} bits)", self.mod_bits)
93    }
94}
95
96impl std::fmt::Debug for RsaPrivateKey {
97    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
98        write!(f, "RsaPrivateKey({} bits)", self.public.mod_bits)
99    }
100}
101
102fn digest_info_prefix(h: HashAlg) -> &'static [u8] {
103    match h {
104        HashAlg::Sha256 => &[
105            0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01, 0x05, 0x00, 0x04, 0x20,
106        ],
107        HashAlg::Sha384 => &[
108            0x30, 0x41, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x02, 0x05, 0x00, 0x04, 0x30,
109        ],
110        HashAlg::Sha512 => &[
111            0x30, 0x51, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03, 0x05, 0x00, 0x04, 0x40,
112        ],
113    }
114}
115
116fn mgf1(hash: HashAlg, seed: &[u8], len: usize) -> Vec<u8> {
117    let mut out = Vec::with_capacity(len + hash.output_len());
118    let mut counter = 0u32;
119    while out.len() < len {
120        let mut input = seed.to_vec();
121        input.extend_from_slice(&counter.to_be_bytes());
122        out.extend_from_slice(&hash.hash(&input));
123        counter += 1;
124    }
125    out.truncate(len);
126    out
127}
128
129impl RsaPublicKey {
130    /// Builds a key from big-endian modulus and exponent.
131    pub fn new(n: &[u8], e: &[u8]) -> Option<RsaPublicKey> {
132        let n = {
133            let mut i = 0;
134            while i < n.len() && n[i] == 0 {
135                i += 1;
136            }
137            &n[i..]
138        };
139        if n.len() < 64 || n.len() > 1024 || n[n.len() - 1] & 1 == 0 {
140            return None; // < 512 bits or > 8192 bits or even
141        }
142        let limbs = n.len().div_ceil(8);
143        let nl = from_be_bytes(n, limbs)?;
144        let el = from_be_bytes(e, limbs)?;
145        if el.iter().all(|x| *x == 0) || !lt(&el, &nl) {
146            return None;
147        }
148        let mod_bits = bit_len(&nl);
149        Some(RsaPublicKey { ctx: MontCtx::new(nl), e: el, k: mod_bits.div_ceil(8), mod_bits })
150    }
151
152    pub fn modulus_bits(&self) -> usize {
153        self.mod_bits
154    }
155
156    /// Big-endian (modulus, public exponent).
157    pub fn components(&self) -> (Vec<u8>, Vec<u8>) {
158        let n = to_be_bytes(&self.ctx.m, self.k);
159        let mut e = to_be_bytes(&self.e, self.k);
160        while e.len() > 1 && e[0] == 0 {
161            e.remove(0);
162        }
163        (n, e)
164    }
165
166    pub fn size(&self) -> usize {
167        self.k
168    }
169
170    fn encrypt_raw(&self, sig: &[u8]) -> Option<Vec<u8>> {
171        if sig.len() != self.k {
172            return None;
173        }
174        let s = from_be_bytes(sig, self.ctx.n())?;
175        if !lt(&s, &self.ctx.m) {
176            return None;
177        }
178        let m = self.ctx.pow(&s, &self.e, false);
179        Some(to_be_bytes(&m, self.k))
180    }
181
182    /// RSASSA-PKCS1-v1_5 verification over a digest.
183    pub fn verify_pkcs1(&self, hash: HashAlg, digest: &[u8], sig: &[u8]) -> bool {
184        let em = match self.encrypt_raw(sig) {
185            Some(e) => e,
186            None => return false,
187        };
188        match pkcs1_encode(hash, digest, self.k) {
189            Some(expect) => ct_eq(&em, &expect),
190            None => false,
191        }
192    }
193
194    /// RSASSA-PKCS1-v1_5 verification over a SHA-1 digest (legacy certificates, CRLs and OCSP
195    /// responses only; never accepted in a TLS handshake).
196    #[cfg(feature = "sha1")]
197    pub fn verify_pkcs1_sha1(&self, digest: &[u8; 20], sig: &[u8]) -> bool {
198        match (self.encrypt_raw(sig), pkcs1_encode_prefixed(SHA1_DIGEST_INFO, digest, self.k)) {
199            (Some(em), Some(expect)) => ct_eq(&em, &expect),
200            _ => false,
201        }
202    }
203
204    /// RSASSA-PSS verification over a digest with MGF1 using the same hash.
205    /// `salt_len` = None accepts any salt length.
206    pub fn verify_pss(&self, hash: HashAlg, digest: &[u8], sig: &[u8], salt_len: Option<usize>) -> bool {
207        let em_full = match self.encrypt_raw(sig) {
208            Some(e) => e,
209            None => return false,
210        };
211        let em_bits = self.mod_bits - 1;
212        let em_len = em_bits.div_ceil(8);
213        let em = if em_len < self.k {
214            if em_full[0] != 0 {
215                return false;
216            }
217            &em_full[1..]
218        } else {
219            &em_full[..]
220        };
221        let hlen = hash.output_len();
222        if digest.len() != hlen || em_len < hlen + 2 || em[em_len - 1] != 0xbc {
223            return false;
224        }
225        let masked_db = &em[..em_len - hlen - 1];
226        let h = &em[em_len - hlen - 1..em_len - 1];
227        let top_bits = 8 * em_len - em_bits;
228        let top_mask: u8 = if top_bits == 0 { 0 } else { 0xffu8 << (8 - top_bits) };
229        if masked_db[0] & top_mask != 0 {
230            return false;
231        }
232        let db_mask = mgf1(hash, h, masked_db.len());
233        let mut db: Vec<u8> = masked_db.iter().zip(db_mask.iter()).map(|(a, b)| a ^ b).collect();
234        db[0] &= !top_mask;
235        let pos = match db.iter().position(|b| *b != 0) {
236            Some(p) => p,
237            None => return false,
238        };
239        if db[pos] != 1 {
240            return false;
241        }
242        let salt = &db[pos + 1..];
243        if let Some(sl) = salt_len {
244            if salt.len() != sl {
245                return false;
246            }
247        }
248        let mut mp = vec![0u8; 8];
249        mp.extend_from_slice(digest);
250        mp.extend_from_slice(salt);
251        ct_eq(&hash.hash(&mp), h)
252    }
253}
254
255fn pkcs1_encode(hash: HashAlg, digest: &[u8], k: usize) -> Option<Vec<u8>> {
256    if digest.len() != hash.output_len() {
257        return None;
258    }
259    pkcs1_encode_prefixed(digest_info_prefix(hash), digest, k)
260}
261
262/// The DigestInfo prefix of SHA-1 (RFC 8017 section 9.2 note 1).
263#[cfg(feature = "sha1")]
264const SHA1_DIGEST_INFO: &[u8] = &[0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b, 0x0e, 0x03, 0x02, 0x1a, 0x05, 0x00, 0x04, 0x14];
265
266fn pkcs1_encode_prefixed(prefix: &[u8], digest: &[u8], k: usize) -> Option<Vec<u8>> {
267    let t_len = prefix.len() + digest.len();
268    if k < t_len + 11 {
269        return None;
270    }
271    let mut em = vec![0x00, 0x01];
272    em.resize(k - t_len - 1, 0xff);
273    em.push(0);
274    em.extend_from_slice(prefix);
275    em.extend_from_slice(digest);
276    Some(em)
277}
278
279impl RsaPrivateKey {
280    /// Builds a private key from big-endian n, e, d.
281    pub fn new(n: &[u8], e: &[u8], d: &[u8]) -> Option<RsaPrivateKey> {
282        let public = RsaPublicKey::new(n, e)?;
283        let d = from_be_bytes(d, public.ctx.n())?;
284        if !lt(&d, &public.ctx.m) {
285            return None;
286        }
287        Some(RsaPrivateKey { public, d, pkcs1: None, crt: None, blinding: Arc::new(Mutex::new(None)) })
288    }
289
290    /// Adds the CRT parameters (big-endian p, q, d mod (p-1), d mod (q-1), q^-1 mod p);
291    /// returns false (and keeps the plain exponentiation) when they do not match the key.
292    pub fn set_crt(&mut self, p: &[u8], q: &[u8], dp: &[u8], dq: &[u8], qinv: &[u8]) -> bool {
293        let strip = |b: &[u8]| -> Vec<u8> { b.iter().copied().skip_while(|x| *x == 0).collect() };
294        let (p, q) = (strip(p), strip(q));
295        if p.is_empty() || q.is_empty() || p.last().unwrap() & 1 == 0 || q.last().unwrap() & 1 == 0 {
296            return false;
297        }
298        let limbs = |b: &[u8]| b.len().div_ceil(8).max(1);
299        let (Some(pl), Some(ql)) = (from_be_bytes(&p, limbs(&p)), from_be_bytes(&q, limbs(&q))) else { return false };
300        // p * q must be n
301        match trim_to(mul_full(&pl, &ql), self.public.ctx.n()) {
302            Some(n) if n == self.public.ctx.m => {}
303            _ => return false,
304        }
305        let (Some(dp), Some(dq), Some(qinv)) = (from_be_bytes(&strip(dp), pl.len()), from_be_bytes(&strip(dq), ql.len()), from_be_bytes(&strip(qinv), pl.len())) else { return false };
306        self.crt = Some(Crt { p: MontCtx::new(pl), q: MontCtx::new(ql), dp, dq, qinv });
307        true
308    }
309
310    /// Whether private operations use the CRT.
311    pub fn has_crt(&self) -> bool {
312        self.crt.is_some()
313    }
314
315    /// c^d mod n with the CRT.
316    fn crt_pow(&self, crt: &Crt, c: &[u64]) -> Option<Vec<u64>> {
317        let m1 = crt.p.pow(&crt.p.reduce(c), &crt.dp, true);
318        let m2 = crt.q.pow(&crt.q.reduce(c), &crt.dq, true);
319        let m2p = crt.p.reduce(&m2);
320        let mut diff = vec![0u64; crt.p.n()];
321        mod_sub(&mut diff, &m1, &m2p, &crt.p.m);
322        let h = mod_mul(&crt.p, &crt.qinv, &diff);
323        let mut s = mul_full(&h, &crt.q.m);
324        add_assign(&mut s, &m2);
325        trim_to(s, self.public.ctx.n())
326    }
327
328    /// The blinding pair for this operation (created on first use, then squared).
329    fn next_blinding(&self) -> Option<(Vec<u64>, Vec<u64>)> {
330        let ctx = &self.public.ctx;
331        let mut g = self.blinding.lock().unwrap();
332        if g.is_none() {
333            // r^-1 = r^(e*d - 2) mod n, as r^(e*d - 1) = 1 for r coprime to n
334            if self.public.e.iter().skip(1).any(|x| *x != 0) {
335                return None;
336            }
337            let e = self.public.e[0];
338            let mut ed = vec![0u64; self.d.len() + 1];
339            let mut carry = 0;
340            for (i, &x) in self.d.iter().enumerate() {
341                let (lo, hi) = mac(0, x, e, carry);
342                ed[i] = lo;
343                carry = hi;
344            }
345            ed[self.d.len()] = carry;
346            let mut borrow = 0;
347            for (i, limb) in ed.iter_mut().enumerate() {
348                let (v, b) = sbb(*limb, if i == 0 { 2 } else { 0 }, borrow);
349                *limb = v;
350                borrow = b;
351            }
352            let r = loop {
353                let r = reduce_be(&rng::bytes(self.public.k + 8), &ctx.m);
354                if bit_len(&r) > 64 {
355                    break r;
356                }
357            };
358            let vi = ctx.pow(&r, &self.public.e, false);
359            let vf = ctx.pow(&r, &ed, true);
360            if mod_mul(ctx, &vi, &ctx.pow(&vf, &self.public.e, false)).iter().enumerate().any(|(i, x)| *x != (i == 0) as u64) {
361                return None; // r not coprime to n (practically impossible)
362            }
363            *g = Some(Blinding { vi, vf });
364        }
365        let b = g.as_mut().unwrap();
366        let out = (b.vi.clone(), b.vf.clone());
367        b.vi = mod_mul(ctx, &b.vi, &b.vi);
368        b.vf = mod_mul(ctx, &b.vf, &b.vf);
369        Some(out)
370    }
371
372    /// The PKCS#1 `RSAPrivateKey` encoding this key was parsed from (keys built with
373    /// [`RsaPrivateKey::new`] lack the CRT parameters and have none).
374    pub fn pkcs1_der(&self) -> Option<&[u8]> {
375        self.pkcs1.as_deref()
376    }
377
378    fn decrypt_raw(&self, em: &[u8]) -> Option<Vec<u8>> {
379        let m = from_be_bytes(em, self.public.ctx.n())?;
380        if !lt(&m, &self.public.ctx.m) {
381            return None;
382        }
383        let ctx = &self.public.ctx;
384        let blinding = self.next_blinding();
385        let mb = match &blinding {
386            Some((vi, _)) => mod_mul(ctx, &m, vi),
387            None => m.clone(),
388        };
389        let sb = match &self.crt {
390            Some(crt) => self.crt_pow(crt, &mb)?,
391            None => ctx.pow(&mb, &self.d, true),
392        };
393        let s = match &blinding {
394            Some((_, vf)) => mod_mul(ctx, &sb, vf),
395            None => sb,
396        };
397        let sig = to_be_bytes(&s, self.public.k);
398        // guard against faults: verify before releasing
399        if self.public.encrypt_raw(&sig)? != to_be_bytes(&m, self.public.k) {
400            return None;
401        }
402        Some(sig)
403    }
404
405    pub fn sign_pkcs1(&self, hash: HashAlg, digest: &[u8]) -> Option<Vec<u8>> {
406        let em = pkcs1_encode(hash, digest, self.public.k)?;
407        self.decrypt_raw(&em)
408    }
409
410    /// RSASSA-PKCS1-v1_5 signature over a SHA-1 digest (only for test fixtures of legacy
411    /// formats).
412    #[cfg(feature = "sha1")]
413    pub fn sign_pkcs1_sha1(&self, digest: &[u8; 20]) -> Option<Vec<u8>> {
414        let em = pkcs1_encode_prefixed(SHA1_DIGEST_INFO, digest, self.public.k)?;
415        self.decrypt_raw(&em)
416    }
417
418    /// RSASSA-PSS signature with salt length = hash length (as TLS 1.3 requires).
419    pub fn sign_pss(&self, hash: HashAlg, digest: &[u8]) -> Option<Vec<u8>> {
420        let salt = rng::bytes(hash.output_len());
421        self.sign_pss_with_salt(hash, digest, &salt)
422    }
423
424    pub fn sign_pss_with_salt(&self, hash: HashAlg, digest: &[u8], salt: &[u8]) -> Option<Vec<u8>> {
425        let hlen = hash.output_len();
426        let em_bits = self.public.mod_bits - 1;
427        let em_len = em_bits.div_ceil(8);
428        if digest.len() != hlen || em_len < hlen + salt.len() + 2 {
429            return None;
430        }
431        let mut mp = vec![0u8; 8];
432        mp.extend_from_slice(digest);
433        mp.extend_from_slice(salt);
434        let h = hash.hash(&mp).to_vec();
435        let db_len = em_len - hlen - 1;
436        let mut db = vec![0u8; db_len - salt.len() - 1];
437        db.push(1);
438        db.extend_from_slice(salt);
439        let mask = mgf1(hash, &h, db_len);
440        let mut em: Vec<u8> = db.iter().zip(mask.iter()).map(|(a, b)| a ^ b).collect();
441        let top_bits = 8 * em_len - em_bits;
442        if top_bits > 0 {
443            em[0] &= 0xff >> top_bits;
444        }
445        em.extend_from_slice(&h);
446        em.push(0xbc);
447        let mut full = vec![0u8; self.public.k - em_len];
448        full.extend(em);
449        self.decrypt_raw(&full)
450    }
451}
452
453#[cfg(test)]
454mod tests {
455    use super::*;
456    use crate::util::unhex;
457
458    // Arbitrary 1024-bit odd value (structure checks only; signature vectors
459    // against OpenSSL live in keys.rs tests).
460    const N: &str = "c7f6a2d7ec1d1a1ac3cd29b2a6a04e5e3e4b2aca69f2c3c4e94f3dbfc40b2c7c\
4612b0b0f13c69c43c4a18c0bfa6e7bc5ff10a36eb4b55cb43e3098ce3a85c3e1d1\
4626f4f80bd2a9c1d13ba88da2bc4bf1ad3b6d15d5d71d6f9c6c55c0a1f33f01a1e\
463ab38f19c0e7c70e9c6c2fb7e43cd7d5e2c91b88dbdc7aa2a4b9cb7df5dc33d81";
464
465    #[test]
466    fn rejects_bad_keys() {
467        assert!(RsaPublicKey::new(&unhex("0f"), &[3]).is_none());
468        let mut even = unhex(N);
469        let last = even.len() - 1;
470        even[last] &= 0xfe;
471        assert!(RsaPublicKey::new(&even, &[1, 0, 1]).is_none());
472    }
473}
474
475#[cfg(test)]
476mod micro {
477    use super::super::bigint::{mont_mul, MontCtx};
478    #[test]
479    #[ignore]
480    fn rsa_breakdown() {
481        let key = match crate::keys::PrivateKey::from_pem(include_bytes!("../../testdata/rsa2048.pkcs1.pem")).unwrap() {
482            crate::keys::PrivateKey::Rsa(k) => k,
483            _ => unreachable!(),
484        };
485        let crt = key.crt.as_ref().unwrap();
486        let ctx: &MontCtx = &crt.p;
487        let a = ctx.to_mont(&vec![3u64; 16]);
488        let mut r = a.clone();
489        let mut t = vec![0u64; 18];
490        let n = 200_000;
491        let s = std::time::Instant::now();
492        for _ in 0..n {
493            let x = r.clone();
494            mont_mul(&mut r, &x, &a, &ctx.m, ctx.m0inv, &mut t);
495        }
496        println!("mont_mul 16 limbs: {:.0} ns", s.elapsed().as_nanos() as f64 / n as f64);
497        let s = std::time::Instant::now();
498        for _ in 0..200 {
499            std::hint::black_box(ctx.pow(&a, &crt.dp, true));
500        }
501        println!("pow 1024: {:.1} us", s.elapsed().as_nanos() as f64 / 200.0 / 1e3);
502        let dg = [1u8; 32];
503        let s = std::time::Instant::now();
504        for _ in 0..200 {
505            std::hint::black_box(key.sign_pss(crate::crypto::sha2::HashAlg::Sha256, &dg));
506        }
507        println!("sign: {:.1} us", s.elapsed().as_nanos() as f64 / 200.0 / 1e3);
508    }
509}
simoom_tls/crypto/rsa.rs

simoom_tls/crypto/
rsa.rs
