scicrypt_numbertheory/
lib.rs

1#![warn(missing_docs, unused_imports)]
2
3//! _This is a part of **scicrypt**. For more information, head to the
4//! [scicrypt](https://crates.io/crates/scicrypt) crate homepage._
5//!
6//! Number theoretic functions, particularly suited for cryptography. Functions include extremely
7//! fast (safe) prime generation.
8
9mod primes;
10
11use crate::primes::FIRST_PRIMES;
12use scicrypt_bigint::UnsignedInteger;
13use scicrypt_traits::randomness::GeneralRng;
14use scicrypt_traits::randomness::SecureRng;
15
16/// Generates a uniformly random prime number of a given bit length. So, the number contains
17/// `bit_length` bits, of which the first and the last bit are always 1.
18pub fn gen_prime<R: SecureRng>(bit_length: u32, rng: &mut GeneralRng<R>) -> UnsignedInteger {
19    'outer: loop {
20        let mut candidate = UnsignedInteger::random(bit_length, rng);
21        candidate.set_bit_leaky(bit_length - 1);
22        candidate.set_bit_leaky(0);
23
24        // A heuristic that closely follows OpenSSL (https://github.com/openssl/openssl/blob/4cedf30e995f9789cf6bb103e248d33285a84067/crypto/bn/bn_prime.c)
25        let prime_count: usize = bit_length as usize / 3;
26        let mods: Vec<u64> = FIRST_PRIMES[..prime_count]
27            .iter()
28            .map(|p| candidate.mod_u_leaky(*p))
29            .collect();
30
31        let mut delta = 0;
32        let max_delta = u64::MAX - FIRST_PRIMES.last().unwrap();
33        candidate += &'sieve: loop {
34            for i in 1..prime_count {
35                if (mods[i] + delta) % FIRST_PRIMES[i] == 0 {
36                    // For candidate x and prime p, if x % p = 0 then x is not prime
37                    // So, we go to the next odd number and try again
38                    delta += 2;
39
40                    if delta > max_delta {
41                        continue 'outer;
42                    }
43
44                    continue 'sieve;
45                }
46            }
47
48            // If we have passed all prime_count first primes, then we are fairly certain this is a prime!
49            break UnsignedInteger::from(delta);
50        };
51
52        // Ensure that we have a prime with a stronger primality test
53        if candidate.is_probably_prime_leaky() {
54            return candidate;
55        }
56    }
57}
58
59/// Generates a uniformly random *safe* prime number of a given bit length. This is a prime $p$ of
60/// the form $p = 2q + 1$, where $q$ is a smaller prime.
61pub fn gen_safe_prime<R: SecureRng>(bit_length: u32, rng: &mut GeneralRng<R>) -> UnsignedInteger {
62    'outer: loop {
63        let mut candidate = UnsignedInteger::random(bit_length, rng);
64        candidate.set_bit_leaky(bit_length - 1);
65        candidate.set_bit_leaky(0);
66
67        // A heuristic that closely follows OpenSSL (https://github.com/openssl/openssl/blob/4cedf30e995f9789cf6bb103e248d33285a84067/crypto/bn/bn_prime.c)
68        let prime_count: usize = bit_length as usize / 3;
69        let mods: Vec<u64> = FIRST_PRIMES[..prime_count]
70            .iter()
71            .map(|p| candidate.mod_u_leaky(*p))
72            .collect();
73
74        let mut delta = 0;
75        let max_delta = u64::MAX - FIRST_PRIMES[prime_count - 1];
76        candidate += &'sieve: loop {
77            for i in 1..prime_count {
78                if (mods[i] + delta) % FIRST_PRIMES[i] <= 1 {
79                    // For candidate x and prime p, if x % p = 0 then x is not prime
80                    // So, we go to the next odd number and try again
81                    delta += 4;
82
83                    if delta > max_delta {
84                        continue 'outer;
85                    }
86
87                    continue 'sieve;
88                }
89            }
90
91            // If we have passed all prime_count first primes, then we are fairly certain this is a prime!
92            break UnsignedInteger::from(delta);
93        };
94
95        // Ensure that we have a prime with a stronger primality test
96        if candidate.is_probably_prime_leaky() {
97            // Ensure that p for 2p = 1 is also a prime with the stronger primality test
98            let candidate_reduced = &candidate >> 1;
99            if candidate_reduced.is_probably_prime_leaky() {
100                return candidate;
101            }
102        }
103    }
104}
105
106/// Generates a uniformly random RSA modulus, which is the product of two safe primes $p$ and $q$.
107/// This method returns both the modulus and $\lambda$, which is the least common multiple of
108/// $p - 1$ and $q - 1$.
109pub fn gen_rsa_modulus<R: SecureRng>(
110    bit_length: u32,
111    rng: &mut GeneralRng<R>,
112) -> (UnsignedInteger, UnsignedInteger) {
113    let mut p = gen_safe_prime(bit_length / 2, rng);
114    let mut q = gen_safe_prime(bit_length / 2, rng);
115
116    let n = &p * &q;
117
118    p.clear_bit_leaky(0);
119    q.clear_bit_leaky(0);
120
121    let lambda = p.lcm_leaky(&q);
122
123    (n, lambda)
124}
125
126#[cfg(test)]
127mod tests {
128    use crate::{gen_prime, gen_safe_prime};
129    use rand_core::OsRng;
130    use scicrypt_bigint::UnsignedInteger;
131    use scicrypt_traits::randomness::GeneralRng;
132
133    fn assert_primality_100_000_factors(integer: &UnsignedInteger) {
134        let (_, hi) = primal::estimate_nth_prime(100_000);
135        for prime in primal::Sieve::new(hi as usize).primes_from(0) {
136            assert!(
137                integer.mod_u_leaky(prime as u64) != 0,
138                "{} is divisible by {}",
139                integer,
140                prime
141            );
142        }
143    }
144
145    #[test]
146    fn test_gen_prime_for_factors() {
147        let mut rng = GeneralRng::new(OsRng);
148        let generated_prime = gen_prime(256, &mut rng);
149
150        assert_primality_100_000_factors(&generated_prime);
151    }
152
153    #[test]
154    fn test_gen_safe_prime_for_factors() {
155        let mut rng = GeneralRng::new(OsRng);
156        let generated_prime = gen_safe_prime(256, &mut rng);
157
158        assert_primality_100_000_factors(&generated_prime);
159
160        let sophie_germain_prime = &generated_prime >> 1;
161
162        assert_primality_100_000_factors(&sophie_germain_prime);
163    }
164}
scicrypt_numbertheory/lib.rs

scicrypt_numbertheory/
lib.rs
