rsa_rust/helpers/
math.rs

1//! Math
2use std::str::FromStr;
3use rand::Rng;
4use num_bigint::{ToBigUint, BigUint, RandBigInt, BigInt, Sign};
5use num::{Zero, One, Integer};
6use crate::helpers::generics::*;
7
8
9const DISCARTERS: [u8; 7] = [3, 5, 7, 11, 13, 17, 19];
10
11// Generates a big number of lenght = u32 param.
12pub fn gen_big_num(bit_len: &u32) -> BigUint {
13    // RNG depends on rng_core crate.
14    let mut rng = rand::thread_rng();
15    let a = rng.gen_biguint(bit_len.to_owned() as usize);
16    a
17}
18
19// Given lenght, generates a prime number of that lenght approximately.
20// That prime number is prime with probability = 4^-threshold 
21pub fn gen_big_prime(size: &u32, threshold: u32) -> BigUint {
22    let mut proposal =  gen_big_num(size);
23    // Remove all even numbers to reduce the iterations a half.
24    if proposal.is_even() {
25        proposal = proposal + BigUint::one();
26    }
27    while !is_prime(&proposal, threshold) {
28        // Steps of 2 to avoid the even numbers on the iterations.
29        proposal =  proposal + 2.to_biguint().unwrap();
30    }
31    proposal
32}
33
34// Posible to remove and implement it on gen big prime
35// Given a prime proposal, compute Rabin Miller's algorithm.
36pub fn is_prime(proposal: &BigUint, threshold: u32) -> bool {
37    if !rabin_miller(proposal, threshold) {return false}
38    true
39}
40
41// Rabin-Miller is a probabilistic algorithm that checks if a number is prime based on Riemmann's conjecture.
42// Implemented from psoudocode found on: https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Primality_Testing 
43// The function recieves a prime proposal and the threshold probability of a false positive
44// due to composite numbers reported as primes.
45// The pobability of a false positive is 4^-threshold. With t=9 => P(false_positive) = 3/1_000_000 
46fn rabin_miller(proposal: &BigUint, t: u32) -> bool {
47    // Needed constants
48    let (z, o, tw) = gen_basic_biguints();
49    let (zero, one, two) = (&z, &o, &tw);
50    // If proposal <= 1 Rabin-Miller has to fail.
51    if proposal.clone() <= one.to_owned() {return false};
52    // If proposal != 2 and modulus 2 = 0, Rabin-Miller fails.
53    if proposal.clone() != two.to_owned() && proposal.clone() % two == zero.to_owned() {return false};
54    // Discarting proposals divisibles by DISCARTERS improving performance of the algorythm
55    let discarts: Vec<bool> = DISCARTERS.into_iter().map(|x| (proposal % x.to_biguint().unwrap()).is_zero()).collect();
56    println!("{:?}", discarts);
57    for result in discarts {
58        if result == true {return false} 
59    } 
60    
61    // Getting exp to execute mulmod.
62    let (s,d) = refactor(proposal);
63
64    let mut counter = 0;
65    while counter < t {
66        // Gen rand biguint from a range (2, proposal-2)
67        let mut rng = rand::thread_rng();
68        let a = rng.gen_biguint_range(&two , &(proposal - two) );
69
70        let mut x = mod_exp_pow(&a, &d, proposal);
71        if x != one.to_owned() && x != proposal.to_owned() - one {
72            let mut i = zero.clone();
73            loop {
74                x = mod_exp_pow(&x, &two, proposal);
75                if x == proposal.to_owned() - one {break;}
76                if x == one.to_owned() || i >= s.clone()- one{return false;};
77                
78                i = i.clone() + one;
79            }
80        }
81        counter +=2;
82    }  
83    true
84}
85#[cfg(test)]
86#[test]
87fn rabin_miller_works() {
88    //Small primes
89    let res = rabin_miller(&179425357u32.to_biguint().unwrap(), 9);
90    assert_eq!(res, true);
91    let res2 = rabin_miller(&82589933u32.to_biguint().unwrap(), 64);
92    assert_eq!(res2, true);
93    
94    
95    // Big primes
96    let known_prime_str =
97    "118595363679537468261258276757550704318651155601593299292198496313960907653004730006758459999825003212944725610469590674020124506249770566394260832237809252494505683255861199449482385196474342481641301503121142740933186279111209376061535491003888763334916103110474472949854230628809878558752830476310536476569";
98    let known_prime: BigUint = FromStr::from_str(known_prime_str).unwrap();
99    assert!(rabin_miller(&known_prime, 64));
100
101    assert_eq!(rabin_miller(&19u32.to_biguint().unwrap(), 9), false);
102}
103
104// Modular exponentiation implemented on binary exponentiation (squaring)
105pub fn mod_exp_pow(base: &BigUint, exp: &BigUint, md: &BigUint) -> BigUint {
106    let mut res = BigUint::one();
107    let (zero, one, _) = gen_basic_biguints();
108    let (mut base, mut exponent) = (base.clone(), exp.clone());
109
110    while exponent > zero {
111        if exponent.clone() & one.clone() > zero {
112            res = (res * base.clone()) % md;
113        }
114        // Shifting 1 bit of the exponent as a binary number.
115        exponent >>= 1;
116        // Generating next base by squaring
117        base = (base.clone() * base.clone()) % md;
118    }
119    res
120}
121
122#[cfg(test)]
123#[test]
124fn mod_exp_works() {
125    let res = mod_exp_pow(&BigUint::from(4 as u32), &BigUint::from(13 as u32), &BigUint::from(497 as u32));
126    assert_eq!(res, BigUint::from(445 as u32));
127
128    let res2 = mod_exp_pow(&BigUint::from(5 as u32), &BigUint::from(3 as u32), &BigUint::from(13 as u32));
129    assert_eq!(res2, BigUint::from(8 as u32));
130}
131
132// Given a number n, write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1
133fn refactor(n: &BigUint) -> (BigUint, BigUint) {
134  let (mut s, one, two) = gen_basic_biguints();
135  let mut d = n.clone() - one.clone();
136
137  while d.is_even() {
138    d = d / two.clone();
139    s = s + one.clone();
140  }
141  (s, d)
142}
143
144// Extended Euclidean Algorithm
145// Returns gcd(a,b) and Bézout's identity coefficients
146// ax + by = gcd(a,b)
147pub fn egcd<'a>(a: &'a mut BigInt, b: &'a mut BigInt) -> (BigInt, BigInt, BigInt) {
148    // base case
149    if a.to_owned() == BigInt::from(0 as u32) {
150        (b.clone(), BigInt::from(0 as i32), BigInt::from(1 as i32))
151    } else {
152        let mut b_mod_a = b.clone() % a.clone();
153        let ref_b_mod_a = &mut b_mod_a;
154        let (g, x, y) = egcd(ref_b_mod_a, a);
155        let mut b_div_a = b.clone() / a.clone();
156        let ref_b_div_a = &mut b_div_a;
157        (g, (y - ref_b_div_a.clone() * x.clone()), x)
158    }
159}
160
161#[cfg(test)]
162
163#[test]
164fn egcd_test() {
165    use num_bigint::ToBigInt;
166    use std::str::FromStr;
167
168    // small primes
169    let a = &mut 179425357u32.to_bigint().unwrap();
170    let b = &mut 97u32.to_bigint().unwrap();
171    let (g, x, y) = egcd(a, b);
172    assert_eq!(a.clone()*x + b.clone()*y, g);
173
174    // small primes
175    let a = &mut 1024u32.to_bigint().unwrap();
176    let b = &mut 512u32.to_bigint().unwrap();
177    let (g, _x, _y) = egcd(a, b);
178    assert_eq!(512u32.to_bigint().unwrap(), g);
179
180    // big primes
181    let known_prime_str = "118595363679537468261258276757550704318651155601593299292198496313960907653004730006758459999825003212944725610469590674020124506249770566394260832237809252494505683255861199449482385196474342481641301503121142740933186279111209376061535491003888763334916103110474472949854230628809878558752830476310536476569";
182    let known_prime_str_2 = "357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199211223227229233239241251257263269271277281283293307311313317331337347349353359367373379383389397401409419421431433439443449457461463467479487491499503509521523541547557563569571577587593599601607613617619631641643647653659661673677683691701709719727733739743751757761769773787797809811821823827829839853857859863877881883887907911919929937941947953967971977983991997";
183    let mut a: BigInt = FromStr::from_str(known_prime_str).unwrap();
184    let mut b: BigInt = FromStr::from_str(known_prime_str_2).unwrap();
185    let a_r = &mut a;
186    let b_r = &mut b;
187    let (g, x, y) = egcd(a_r, b_r);
188    assert_eq!(a_r.clone()*x + b_r.clone()*y, g);
189}
190
191// Given a fi_n, find on the interval (fi_n/2, fi_n) a number 
192// that is co-prime with fi_n
193pub fn find_e(fi_n: &BigUint) -> Result<BigUint, bool> {
194    // Gen random number on interval
195    let mut rng = rand::thread_rng();
196    //Get fi_n as 
197    let sign = Sign::Plus;
198    let mut fi_n = BigInt::from_biguint(sign, fi_n.clone());
199    let (zero, one, two) = gen_basic_bigints();
200    let mut a = rng.gen_bigint_range(&(fi_n.clone()/two.clone()) , &((BigInt::from(3) * fi_n.clone())/BigInt::from(4) ));
201    //We want to avoid the even random numbers.
202    if a.is_even() {a = a + one.clone()};
203    let mut res = zero;
204    while res != one.clone() && a <= fi_n.clone() - one.clone() {
205        let (res2, _, _) = egcd(&mut fi_n, &mut a);
206        res = res2;
207        a = a.clone() + two.clone(); 
208    }
209
210    if res == one {
211        a = a.clone() - two.clone();
212        return Ok(biguint_from_bigint(&a).unwrap());
213    }
214    Err(false)
215}
rsa_rust/helpers/math.rs

rsa_rust/helpers/
math.rs
