1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
use num_bigint::traits::ModInverse;
use num_bigint::{BigUint, RandPrime};
use num_traits::{FromPrimitive, One, Zero};
use rand::Rng;
use crate::errors::{Error, Result};
use crate::key::RSAPrivateKey;
const EXP: u64 = 65537;
pub fn generate_multi_prime_key<R: Rng>(
rng: &mut R,
nprimes: usize,
bit_size: usize,
) -> Result<RSAPrivateKey> {
if nprimes < 2 {
return Err(Error::NprimesTooSmall);
}
if bit_size < 64 {
let prime_limit = (1u64 << (bit_size / nprimes) as u64) as f64;
let mut pi = prime_limit / (prime_limit.ln() - 1f64);
pi /= 4f64;
pi /= 2f64;
if pi < nprimes as f64 {
return Err(Error::TooFewPrimes);
}
}
let mut primes = vec![BigUint::zero(); nprimes];
let n_final: BigUint;
let d_final: BigUint;
'next: loop {
let mut todo = bit_size;
if nprimes >= 7 {
todo += (nprimes - 2) / 5;
}
for (i, prime) in primes.iter_mut().enumerate() {
*prime = rng.gen_prime(todo / (nprimes - i));
todo -= prime.bits();
}
for (i, prime1) in primes.iter().enumerate() {
for prime2 in primes.iter().take(i) {
if prime1 == prime2 {
continue 'next;
}
}
}
let mut n = BigUint::one();
let mut totient = BigUint::one();
for prime in &primes {
n *= prime;
totient *= prime - BigUint::one();
}
if n.bits() != bit_size {
continue 'next;
}
let exp = BigUint::from_u64(EXP).expect("invalid static exponent");
if let Some(d) = exp.mod_inverse(totient) {
n_final = n;
d_final = d.to_biguint().unwrap();
break;
}
}
Ok(RSAPrivateKey::from_components(
n_final,
BigUint::from_u64(EXP).expect("invalid static exponent"),
d_final,
primes,
))
}