rsa/algorithms/
generate.rs

1//! Generate prime components for the RSA Private Key
2
3use alloc::vec::Vec;
4use num_bigint::{BigUint, RandPrime};
5#[allow(unused_imports)]
6use num_traits::Float;
7use num_traits::Zero;
8use rand_core::CryptoRngCore;
9
10use crate::{
11    algorithms::rsa::{compute_modulus, compute_private_exponent_euler_totient},
12    errors::{Error, Result},
13};
14
15pub struct RsaPrivateKeyComponents {
16    pub n: BigUint,
17    pub e: BigUint,
18    pub d: BigUint,
19    pub primes: Vec<BigUint>,
20}
21
22/// Generates a multi-prime RSA keypair of the given bit size, public exponent,
23/// and the given random source, as suggested in [1]. Although the public
24/// keys are compatible (actually, indistinguishable) from the 2-prime case,
25/// the private keys are not. Thus it may not be possible to export multi-prime
26/// private keys in certain formats or to subsequently import them into other
27/// code.
28///
29/// Table 1 in [2] suggests maximum numbers of primes for a given size.
30///
31/// [1]: https://patents.google.com/patent/US4405829A/en
32/// [2]: http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf
33pub(crate) fn generate_multi_prime_key_with_exp<R: CryptoRngCore + ?Sized>(
34    rng: &mut R,
35    nprimes: usize,
36    bit_size: usize,
37    exp: &BigUint,
38) -> Result<RsaPrivateKeyComponents> {
39    if nprimes < 2 {
40        return Err(Error::NprimesTooSmall);
41    }
42
43    if bit_size < 64 {
44        let prime_limit = (1u64 << (bit_size / nprimes) as u64) as f64;
45
46        // pi aproximates the number of primes less than prime_limit
47        let mut pi = prime_limit / (prime_limit.ln() - 1f64);
48        // Generated primes start with 0b11, so we can only use a quarter of them.
49        pi /= 4f64;
50        // Use a factor of two to ensure that key generation terminates in a
51        // reasonable amount of time.
52        pi /= 2f64;
53
54        if pi < nprimes as f64 {
55            return Err(Error::TooFewPrimes);
56        }
57    }
58
59    let mut primes = vec![BigUint::zero(); nprimes];
60    let n_final: BigUint;
61    let d_final: BigUint;
62
63    'next: loop {
64        let mut todo = bit_size;
65        // `gen_prime` should set the top two bits in each prime.
66        // Thus each prime has the form
67        //   p_i = 2^bitlen(p_i) × 0.11... (in base 2).
68        // And the product is:
69        //   P = 2^todo × α
70        // where α is the product of nprimes numbers of the form 0.11...
71        //
72        // If α < 1/2 (which can happen for nprimes > 2), we need to
73        // shift todo to compensate for lost bits: the mean value of 0.11...
74        // is 7/8, so todo + shift - nprimes * log2(7/8) ~= bits - 1/2
75        // will give good results.
76        if nprimes >= 7 {
77            todo += (nprimes - 2) / 5;
78        }
79
80        for (i, prime) in primes.iter_mut().enumerate() {
81            *prime = rng.gen_prime(todo / (nprimes - i));
82            todo -= prime.bits();
83        }
84
85        // Makes sure that primes is pairwise unequal.
86        for (i, prime1) in primes.iter().enumerate() {
87            for prime2 in primes.iter().take(i) {
88                if prime1 == prime2 {
89                    continue 'next;
90                }
91            }
92        }
93
94        let n = compute_modulus(&primes);
95
96        if n.bits() != bit_size {
97            // This should never happen for nprimes == 2 because
98            // gen_prime should set the top two bits in each prime.
99            // For nprimes > 2 we hope it does not happen often.
100            continue 'next;
101        }
102
103        if let Ok(d) = compute_private_exponent_euler_totient(&primes, exp) {
104            n_final = n;
105            d_final = d;
106            break;
107        }
108    }
109
110    Ok(RsaPrivateKeyComponents {
111        n: n_final,
112        e: exp.clone(),
113        d: d_final,
114        primes,
115    })
116}
117
118#[cfg(test)]
119mod tests {
120    use super::*;
121    use num_bigint::BigUint;
122    use num_traits::FromPrimitive;
123    use rand_chacha::{rand_core::SeedableRng, ChaCha8Rng};
124
125    const EXP: u64 = 65537;
126
127    #[test]
128    fn test_impossible_keys() {
129        let mut rng = ChaCha8Rng::from_seed([42; 32]);
130        let exp = BigUint::from_u64(EXP).expect("invalid static exponent");
131        for i in 0..32 {
132            let _ = generate_multi_prime_key_with_exp(&mut rng, 2, i, &exp);
133            let _ = generate_multi_prime_key_with_exp(&mut rng, 3, i, &exp);
134            let _ = generate_multi_prime_key_with_exp(&mut rng, 4, i, &exp);
135            let _ = generate_multi_prime_key_with_exp(&mut rng, 5, i, &exp);
136        }
137    }
138
139    macro_rules! key_generation {
140        ($name:ident, $multi:expr, $size:expr) => {
141            #[test]
142            fn $name() {
143                let mut rng = ChaCha8Rng::from_seed([42; 32]);
144                let exp = BigUint::from_u64(EXP).expect("invalid static exponent");
145
146                for _ in 0..10 {
147                    let components =
148                        generate_multi_prime_key_with_exp(&mut rng, $multi, $size, &exp).unwrap();
149                    assert_eq!(components.n.bits(), $size);
150                    assert_eq!(components.primes.len(), $multi);
151                }
152            }
153        };
154    }
155
156    key_generation!(key_generation_128, 2, 128);
157    key_generation!(key_generation_1024, 2, 1024);
158
159    key_generation!(key_generation_multi_3_256, 3, 256);
160
161    key_generation!(key_generation_multi_4_64, 4, 64);
162
163    key_generation!(key_generation_multi_5_64, 5, 64);
164    key_generation!(key_generation_multi_8_576, 8, 576);
165    key_generation!(key_generation_multi_16_1024, 16, 1024);
166}
rsa/algorithms/generate.rs

rsa/algorithms/
generate.rs
