Rust RSA implementation weird behaviours

#1

Hi Rustaceans.
I’ve implemented a very basic Rust implementation of the RSA algorithm. All seems to work nice, but I’ve found a strange behavior with the encryption/decryption process on my testing. Because it works 3/4 times, which is really weird… I’ts been weeks searching for the error but still not finding it, so I’ve decided to look for help.

The library can be found here: https://github.com/CPerezz/rust-rsa

Here is the code:

math.rs (Each of the functions have been tested and passed)

//! Math functions to build keys with trusted primes
use std::str::FromStr;
use rand::Rng;
use num_bigint::{ToBigUint, BigUint, RandBigInt, BigInt, Sign};
use num::{Zero, One, Integer, FromPrimitive};
use crate::helpers::generics::*;


// Generates a big number of lenght = u32 param.
pub fn gen_big_num(bit_len: &u32) -> BigUint {
    // RNG depends on rng_core crate.
    let mut rng = rand::thread_rng();
    let mut a = rng.gen_biguint(bit_len.to_owned() as usize);
    a
}

// Given lenght, generates a prime number of that lenght approximately.
// That prime number is prime with probability = 4^-threshold 
pub fn gen_big_prime(size: &u32, threshold: u32) -> BigUint {
    let mut proposal =  gen_big_num(size);
    // Remove all even numbers to reduce the iterations a half.
    if proposal.is_even() {
        proposal = proposal + BigUint::one();
    }
    while !is_prime(&proposal, threshold) {
        // Steps of 2 to avoid the even numbers on the iterations.
        proposal =  proposal + 2.to_biguint().unwrap();
    }
    proposal
}

// Posible to remove and implement it on gen big prime
// Given a prime proposal, compute Rabin Miller's algorithm.
fn is_prime(proposal: &BigUint, threshold: u32) -> bool {
    if !rabin_miller(proposal, threshold) {return false}
    true
}

// Rabin-Miller is a probabilistic algorithm that checks if a number is prime based on Riemmann's conjecture.
// Implemented from psoudocode found on: https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Primality_Testing 
// The function recieves a prime proposal and the threshold probability of a false positive
// due to composite numbers reported as primes.
// The pobability of a false positive is 4^-threshold. With t=9 => P(false_positive) = 3/1_000_000 
fn rabin_miller(proposal: &BigUint, t: u32) -> bool {
    // Needed constants
    let (z, o, tw) = gen_basic_biguints();
    let (zero, one, two) = (&z, &o, &tw);
    // If proposal <= 1 Rabin-Miller has to fail.
    if proposal.clone() <= one.to_owned() {return false};
    // If proposal != 2 and modulus 2 = 0, Rabin-Miller fails.
    if proposal.clone() != two.to_owned() && proposal.clone() % two == zero.to_owned() {return false};
    // Getting exp to execute mulmod.
    let (s,d) = refactor(proposal);

    let mut counter = 0;
    while counter < t {
        // Gen rand biguint from a range (2, proposal-2)
        let mut rng = rand::thread_rng();
        let a = rng.gen_biguint_range(&two , &(proposal - two) );

        let mut x = mod_exp_pow(&a, &d, proposal);
        if x != one.to_owned() && x != proposal.to_owned() - one {
            let mut i = zero.clone();
            loop {
                x = mod_exp_pow(&x, &two, proposal);
                if x == proposal.to_owned() - one {break;}
                if x == one.to_owned() || i >= s.clone()- one{return false;};
                
                i = i.clone() + one;
            }
        }
        counter +=2;
    }  
    true
}

// Modular exponentiation implemented on binary exponentiation (squaring)
pub fn mod_exp_pow(base: &BigUint, exp: &BigUint, md: &BigUint) -> BigUint {
    let mut res = BigUint::one();
    let (zero, one, _) = gen_basic_biguints();
    let (mut base, mut exponent) = (base.clone(), exp.clone());

    while exponent > zero {
        if exponent.clone() & one.clone() > zero {
            res = (res * base.clone()) % md;
        }
        // Shifting 1 bit of the exponent as a binary number.
        exponent >>= 1;
        // Generating next base by squaring
        base = (base.clone() * base.clone()) % md;
    }
    res
}

// Given a number n, write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1
fn refactor(n: &BigUint) -> (BigUint, BigUint) {
  let (mut s, one, two) = gen_basic_biguints();
  let mut d = n.clone() - one.clone();

  while d.is_even() {
    d = d / two.clone();
    s = s + one.clone();
  }
  (s, d)
}

// Extended Euclidean Algorithm
// Returns gcd(a,b) and Bézout's identity coefficients
// ax + by = gcd(a,b)
pub fn egcd<'a>(a: &'a mut BigInt, b: &'a mut BigInt) -> (BigInt, BigInt, BigInt) {
    // base case
    if a.to_owned() == BigInt::from(0 as u32) {
        (b.clone(), BigInt::from(0 as i32), BigInt::from(1 as i32))
    } else {
        let mut b_mod_a = b.clone() % a.clone();
        let ref_b_mod_a = &mut b_mod_a;
        let (g, x, y) = egcd(ref_b_mod_a, a);
        let mut b_div_a = b.clone() / a.clone();
        let ref_b_div_a = &mut b_div_a;
        (g, (y - ref_b_div_a.clone() * x.clone()), x)
    }
}

// Given a fi_n, find on the interval (fi_n/2, fi_n) a number 
// that is co-prime with fi_n
pub fn found_e(fi_n: &BigUint) -> Result<BigUint, bool> {
    // Gen random number on interval
    let mut rng = rand::thread_rng();
    //Get fi_n as 
    let sign = Sign::Plus;
    let mut fi_n = BigInt::from_biguint(sign, fi_n.clone());
    let (zero, one, two) = gen_basic_bigints();
    let mut a = rng.gen_bigint_range(&(fi_n.clone()/two.clone()) , &((BigInt::from(3) * fi_n.clone())/BigInt::from(4) ));
    //We want to avoid the even random numbers.
    if a.is_even() {a = a + one.clone()};
    let mut res = zero;
    while res != one.clone() && a <= fi_n.clone() - one.clone() {
        let (res2, _, _) = egcd(&mut fi_n, &mut a);
        res = res2;
        a = a.clone() + two.clone(); 
    }

    if res == one {
        a = a.clone() - two.clone();
        return Ok(biguint_from_bigint(&a));
    }
    Err(false)
}


#[test]
fn generates_random_biguint() {
    let a = gen_big_num(&1024);
    assert_ne!(a, BigUint::zero());
}

#[test]
fn mod_exp_works() {
    let res = mod_exp_pow(&BigUint::from(4 as u32), &BigUint::from(13 as u32), &BigUint::from(497 as u32));
    assert_eq!(res, BigUint::from(445 as u32));

    let res2 = mod_exp_pow(&BigUint::from(5 as u32), &BigUint::from(3 as u32), &BigUint::from(13 as u32));
    assert_eq!(res2, BigUint::from(8 as u32));
}


#[test]
fn rabin_miller_works() {
    //Small primes
    let res = rabin_miller(&179425357u32.to_biguint().unwrap(), 9);
    assert_eq!(res, true);
    let res2 = rabin_miller(&82589933u32.to_biguint().unwrap(), 64);
    assert_eq!(res2, true);
    
    
    // Big primes
    let known_prime_str =
    "118595363679537468261258276757550704318651155601593299292198496313960907653004730006758459999825003212944725610469590674020124506249770566394260832237809252494505683255861199449482385196474342481641301503121142740933186279111209376061535491003888763334916103110474472949854230628809878558752830476310536476569";
    let known_prime: BigUint = FromStr::from_str(known_prime_str).unwrap();
    assert!(rabin_miller(&known_prime, 64));
}


#[test]
fn gen_big_prime_works() {
    let res = gen_big_prime(&2056u32, 9);
    println!("The generated prime of 1024 bits is: {}", res);
}

#[test]
fn egcd_test() {
    use num_bigint::ToBigInt;
    use std::str::FromStr;

    // small primes
    let a = &mut 179425357u32.to_bigint().unwrap();
    let b = &mut 97u32.to_bigint().unwrap();
    let (g, x, y) = egcd(a, b);
    assert_eq!(a.clone()*x + b.clone()*y, g);

    // small primes
    let a = &mut 1024u32.to_bigint().unwrap();
    let b = &mut 512u32.to_bigint().unwrap();
    let (g, x, y) = egcd(a, b);
    assert_eq!(512u32.to_bigint().unwrap(), g);

    // big primes
    let known_prime_str = "118595363679537468261258276757550704318651155601593299292198496313960907653004730006758459999825003212944725610469590674020124506249770566394260832237809252494505683255861199449482385196474342481641301503121142740933186279111209376061535491003888763334916103110474472949854230628809878558752830476310536476569";
    let known_prime_str_2 = "357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199211223227229233239241251257263269271277281283293307311313317331337347349353359367373379383389397401409419421431433439443449457461463467479487491499503509521523541547557563569571577587593599601607613617619631641643647653659661673677683691701709719727733739743751757761769773787797809811821823827829839853857859863877881883887907911919929937941947953967971977983991997";
    let mut a: BigInt = FromStr::from_str(known_prime_str).unwrap();
    let mut b: BigInt = FromStr::from_str(known_prime_str_2).unwrap();
    let a_r = &mut a;
    let b_r = &mut b;
    let (g, x, y) = egcd(a_r, b_r);
    assert_eq!(a_r.clone()*x + b_r.clone()*y, g);
}

And here the types where encryption and decription is made:

use num_bigint::{BigUint, BigInt, ToBigInt, Sign};
use crate::helpers::math::*;
use crate::helpers::generics::*;
use num::{Signed, One};
use std::fmt;
use std::ops::Neg;
use std::str::{FromStr, from_utf8};

#[derive(Clone, PartialEq)]
pub struct KeyPair {
    pub pk: PublicKey,
    pub sk: SecretKey,
    pub size: u32,
    pub threshold: u32
}

#[derive(Clone, PartialEq)]
pub struct PublicKey {
    n: BigUint,
    e: BigUint
}

#[derive(Clone, PartialEq)]
pub struct SecretKey {
    n: BigUint,
    d: BigUint
}

#[derive(Clone, Copy, PartialEq)]
pub struct Threshold {
    value: u32
}

impl Threshold {
    // Creates a Threshold with a default error probability of generating a prime of 4^-64
    pub fn default() -> Self {
        let threshold = Threshold {
            value: 9 as u32
        };
        threshold
    }

    // Creates a Threshold with a selected value as thresholf of P(err). P(err prime) = 4^-threshold. 
    pub fn new(th: &u32) -> Self {
        let th = Threshold {
            value: *th
        };
        th
    }

    // Gets the value of a Threshold and returns it as u32.
    pub fn value(th: Self) -> u32 {
        th.value
    }
}


// Implementation of Display for KeyPair Struct.
impl fmt::Display for KeyPair {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "\nPublic Key: \n{}\nSecret Key: \n{}\nSize: {}\nThreshold: {} which gives a P(err_primes_gen) = 4^(-{})", self.pk, self.sk, self.size, self.threshold, self.threshold)
    }
}

impl KeyPair {
    // Generate a new KeyPair Struct from scratch by giving the size of the key desired (in bits) and the threshold of P(err) while assuming that
    // a number is prime. Statistic methods are used to found that numbers. P(err) = 4^-threshold (As is demonstraded on the Rabin-Miller algorithm)
    pub fn new(size: &u32, threshold: &Threshold) -> Result<Self, &'static str> {
        // Gen basic needed variables
        let (_, one, _) = gen_basic_biguints();
        // Gen p q primal base
        let p = gen_big_prime(size, threshold.value);
        let q = gen_big_prime(size, threshold.value);
        // Gen n and fi_n
        let n = &p * &q;
        let fi_n = (&p - &one) * (&q - &one);
        // Find a positive integer minor than fi_n , co-prime with fi_n 
        let e = found_e(&fi_n).unwrap();

        // Building Pk Struct
        let pk = PublicKey::new(&n, &e).unwrap();
        // Finding d and building Secret Key Struct
        let (_, _,mut d) = egcd(&mut fi_n.to_bigint().unwrap(), &mut e.to_bigint().unwrap());
        if d.is_negative() {
            d = d.neg();
        }
        let sk = SecretKey::new(&n, &biguint_from_bigint(&d)).unwrap();
        //Building KeyPair struct
        let kp = KeyPair {
            pk: pk,
            sk: sk,
            size: size.to_owned(),
            threshold: threshold.value.to_owned()
        };
        // Return the KeyPair struct
        Ok(kp)
    }
}



// Implementation of Display for KeyPair Struct.
impl fmt::Display for PublicKey {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "n: {}\ne: {}", self.n, self.e)
    }
}

impl PublicKey {
    // Generate a PublicKey struct from n and d co-prime factors.
    fn new(_n: &BigUint, _e: &BigUint) -> Result<Self, &'static str> {
        Ok(PublicKey {
            n: _n.to_owned(),
            e: _e.to_owned()
        })
    }
    // Generate a PublicKey struct from n, fi_n and d params with the co-prime property checking.
    fn new_from_fi_n_e(_n: &BigUint, _fi_n: &BigUint, _e: &BigUint) -> Result<Self, &'static str> {
        let (_, _one, _) = gen_basic_bigints();

        match egcd(&mut BigInt::from_biguint(Sign::Plus, _fi_n.to_owned()), &mut BigInt::from_biguint(Sign::Plus, _e.to_owned())) {
            (possible_one, _, _) => {
                if possible_one.is_one() {
                    return  Ok(PublicKey {
                                n: _n.to_owned(),
                                e: _e.to_owned()
                            }
                        )
                }else {
                    return Err("Params passed to Sk builder haven't the properties to be a Public Key")
            
                }            
            }
        }
    }
    // Encrypts the data passed on the params.
    fn encrypt(&self, msg: &str) -> Result<&str, &'static str> {
        if !msg.is_ascii(){
            return Err("Message isn't ASCII like. Please remove non-ASCII characters.")
        }else{
            println!("Message as bytes: {:?}", msg.as_bytes());
            let res = BigUint::from_bytes_be(msg.as_bytes());
            println!("COPRIMES IF ONE ---->>  {:?}", egcd(&mut BigInt::from_biguint(Sign::Plus, res.clone()), &mut BigInt::from_biguint(Sign::Plus, self.n.clone())).0);
            Ok(string_to_static_str(format!("{}", mod_exp_pow(&res, &self.e, &self.n))))
        }
    }
}


// Implementation of Display for KeyPair Struct.
impl fmt::Display for SecretKey {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "n: {}\nd: {}", self.n, self.d)
    }
}

impl SecretKey {
    // Generate a SecretKey struct from n and d co-prime factors.
    fn new(_n: &BigUint, _e: &BigUint) -> Result<Self, &'static str> {
        Ok(SecretKey {
            n: _n.to_owned(),
            d: _e.to_owned()
        })
    }

    // Generate a SecretKey struct from n, fi_n and d params with the co-prime property checking.
    pub fn new_from_fi_n_e(_n: &BigUint, _fi_n: &BigUint, _d: &BigUint) -> Result<Self, &'static str> {
        let (_, _one, _) = gen_basic_bigints();

        match egcd(&mut BigInt::from_biguint(Sign::Plus, _fi_n.to_owned()), &mut BigInt::from_biguint(Sign::Plus, _d.to_owned())) {
            (possible_one, _, _) => {
                if possible_one.is_one() {
                    return  Ok(SecretKey {
                                n: _n.to_owned(),
                                d: _d.to_owned()
                            }
                    )
                }else {
                    return Err("Params passed to Sk builder haven't the properties to be a Public Key")
            
                }            
            }
        }
    }
    
    // Decrypts the cyphertext giving back an &str
    fn decrypt(&self, text: &str) -> Result<&str, &'static str> {
        let c = BigUint::from_str(text).unwrap();
        let result_as_bytes = mod_exp_pow(&c, &self.d, &self.n).to_bytes_be();
        println!("C as bytes: {:?}", result_as_bytes);
        let res_decrypt = std::str::from_utf8(&result_as_bytes).unwrap();
        Ok(string_to_static_str(format!("{}", res_decrypt)))
    }
}

The thing is that when I run the test:

#[test]
fn encrypts_decrypts_info(){
    let kp = KeyPair::new(&512u32, &Threshold::new(&10)).unwrap();
    let msg = "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Praesent non nunc et ipsum tempus fermentum";
    let cyphertext = kp.pk.encrypt(msg).unwrap();
    

    let res_decrypt = kp.sk.decrypt(&cyphertext).unwrap();
    println!("Result of decryption is: {}", res_decrypt);
    assert_eq!(res_decrypt, "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Praesent non nunc et ipsum tempus fermentum")
}

When the test gives an error I get this:

running 1 test
Message as bytes: [76, 111, 114, 101, 109, 32, 105, 112, 115, 117, 109, 32, 100, 111, 108, 111, 114, 32, 115, 105, 116, 32, 97, 109, 101, 116, 44, 32, 99, 111, 110, 115, 101, 99, 116, 101, 116, 117, 114, 32, 97, 100, 105, 112, 105, 115, 99, 105, 110, 103, 32, 101, 108, 105, 116, 46, 32, 80, 114, 97, 101, 115, 101, 110, 116, 32, 110, 111, 110, 32, 110, 117, 110, 99, 32, 101, 116, 32, 105, 112, 115, 117, 109, 32, 116, 101, 109, 112, 117, 115, 32, 102, 101, 114, 109, 101, 110, 116, 117, 109]
COPRIMES IF ONE ---->>  BigInt { sign: Plus, data: BigUint { data: [1] } }
C as bytes: [61, 207, 34, 84, 216, 183, 90, 189, 50, 169, 219, 109, 65, 100, 222, 105, 115, 8, 229, 173, 114, 40, 162, 83, 121, 184, 99, 167, 157, 98, 165, 91, 226, 140, 203, 84, 185, 161, 137, 201, 231, 132, 35, 112, 96, 89, 32, 253, 249, 175, 57, 133, 235, 65, 230, 250, 50, 142, 54, 70, 123, 203, 51, 145, 82, 129, 249, 79, 236, 30, 107, 210, 49, 139, 232, 69, 248, 48, 108, 215, 234, 223, 51, 88, 64, 223, 218, 54, 117, 137, 136, 226, 166, 144, 96, 111, 203, 239, 121, 129, 158, 21, 191, 227, 119, 79, 109, 124, 103, 204, 243, 143, 86, 60, 19, 162, 247, 253, 96, 150, 49, 134, 41, 94, 58, 122, 89, 44]
thread 'types::encrypts_decrypts_info' panicked at 'called `Result::unwrap()` on an `Err` value: Utf8Error { valid_up_to: 1, error_len: Some(1) }', src/libcore/result.rs:1009:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
   1: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:71
   2: std::panicking::default_hook::{{closure}}
             at src/libstd/sys_common/backtrace.rs:59
             at src/libstd/panicking.rs:211
   3: std::panicking::default_hook
             at src/libstd/panicking.rs:227
   4: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:491
   5: std::panicking::continue_panic_fmt
             at src/libstd/panicking.rs:398
   6: rust_begin_unwind
             at src/libstd/panicking.rs:325
   7: core::panicking::panic_fmt
             at src/libcore/panicking.rs:95
   8: core::result::unwrap_failed
             at /rustc/9fda7c2237db910e41d6a712e9a2139b352e558b/src/libcore/macros.rs:26
   9: <core::result::Result<T, E>>::unwrap
             at /rustc/9fda7c2237db910e41d6a712e9a2139b352e558b/src/libcore/result.rs:808
  10: rsa_rust::types::SecretKey::decrypt
             at src/types.rs:191
  11: rsa_rust::types::encrypts_decrypts_info
             at src/types.rs:217
  12: rsa_rust::types::encrypts_decrypts_info::{{closure}}
             at src/types.rs:211
  13: core::ops::function::FnOnce::call_once
             at /rustc/9fda7c2237db910e41d6a712e9a2139b352e558b/src/libcore/ops/function.rs:238
  14: <F as alloc::boxed::FnBox<A>>::call_box
             at src/libtest/lib.rs:1471
             at /rustc/9fda7c2237db910e41d6a712e9a2139b352e558b/src/libcore/ops/function.rs:238
             at /rustc/9fda7c2237db910e41d6a712e9a2139b352e558b/src/liballoc/boxed.rs:673
  15: __rust_maybe_catch_panic
             at src/libpanic_unwind/lib.rs:102
test types::encrypts_decrypts_info ... FAILED

So at this point, idk if the error is coming from a bad key generation or a bad bytes encoding/decoding process.

Thanks for your time.

#2

First, I’d try to come up with a reliable test case. By logging the random keypair, you can find out which keypairs cause the test to fail, so you can write a test that fails every time instead of randomly. For example:

#[test]
fn encrypts_decrypts_info(){
    let kp = KeyPair {
        pk: PublicKey {
            n: BigUint::from_str("32688159406246185151878257509765804894743072383226844222832478271779972994800330582256479863083183450221620794002426498047748400982157084184482850274668074561080545257326819302825029244758804813092066031262671539824372699720947167840049861042306683374696058577708384553079477183066740271255068165448577764411").unwrap(),
            e: BigUint::from_str("21105340062372147985823096474298996892363242709626579553973096317003207001542314439932461224449251895745203248168585066827073689044985568322364937151097533695097695187017012096228413264330966916090064732180311458541665327731363311950286493070515793640429498045430020521663128514020636716622764066051548212169").unwrap(),
        },
        sk: SecretKey {
            n: BigUint::from_str("32688159406246185151878257509765804894743072383226844222832478271779972994800330582256479863083183450221620794002426498047748400982157084184482850274668074561080545257326819302825029244758804813092066031262671539824372699720947167840049861042306683374696058577708384553079477183066740271255068165448577764411").unwrap(),
            d: BigUint::from_str("15023962996167803603176745881247049776296900555032680992901596568355329390301323104247741758749480115711333971283566245001879229246435896163863514820400088525267568937175232770623987119873042711394755394814164033133951795598384827548099596243745723513855966224588188803871502837990870771564744860169333455559").unwrap(),
        },
        size: 512,
        threshold: 10,
    };
    let msg = "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Praesent non nunc et ipsum tempus fermentum";
    let cyphertext = kp.pk.encrypt(msg).unwrap();
    

    let res_decrypt = kp.sk.decrypt(&cyphertext).unwrap();
    println!("Result of decryption is: {}", res_decrypt);
    assert_eq!(res_decrypt, "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Praesent non nunc et ipsum tempus fermentum")
}
1 Like
#3

I have looked for some time and I have not found any error, but there are many places to check.

I would say poorly tested.

  • generates_random_biguint: Just comparing one number with zero? Well, one could argue that it is a trivial function.
  • mod_exp_works: You only tested two cases.
  • rabin_miller_works: You have only considered true cases. Could it be returning true for composite numbers? I think you should test many/all small numbers up to a few millions. Perhaps by comparing against some easy to verify primality algorithm.
  • gen_big_prime_works: This is not a test, is it?
  • egcd_test: You should generate many more cases. For the standard gcd part you may check that g actually divides a and b. You may also try to generate a=random()*k and b=random()*k and check that g is multiple of k. I cannot think just now some algorithmic way for the extended part. Ok, just a=random(), b=random() and verify the equation ax+by=g. And you can add other tests substituting random for many small values.

I would wait to have all mathematical functions very tested before entering into the encoding algorithms.

EDIT: I have found a bug on egcd. Look at this: No, I did not, I though g was the last element, sorry.

EDIT: A pair of things on rabin_miller. The range of gen_biguint_range is exclusive on the upper part, so it is not including proposal-two as candidate. And in the algorithm in the wikipedia the squaring is made s-1 times and you are executing x = mod_exp_pow(&x, &two, proposal); up to s times. Could this be creating false positives?

1 Like
#4

Like @mbrubeck mentions should be getting a reliable test, but be sure too your input keypair is valid. (It’s a pain in the neck trying to debug a function but overlooking that the input is not what you expect.)

Stab in dark since too unfamiliar with algorithms and not spending time looking it up; but wonder if this should not be d+n
if d.is_negative() { d = d.neg(); }

#5
#6

Yes, you’re right.
I’ll try to go deeper by reviewing this kind of tests.

#7

You’re right, the test could be so much better. I’m sorry for asking before having good mathematical tests, it’s just that it worked every 3/4 of the times and I thought it was a little detail…

Yes, it could, but it’s fearly unlikely since it reduces /4 the chances of a false positive.
I fixed it, I didn’t realize that was non-inclusive.

It definetely has to be something related to the KeyPair creation counting that it encrypts/decrypts well 3/4 times. So as you said, I’ll have to test more exhaustively.

Thank you a lot for reviewing it! I really appreciate it.

#8

Hi @jonh

No, at this point if n is negative I need it’s opposite value.

You’re right on the testing with valid keypairs part!

#9

Since d is defined as d = inv(e, mod N) (with N = lcm(p-1, q-1) if I remember correctly), i.e., d * e = 1 mod N must hold, then there is no way that using -d will keep that property intact (unless N = 2, which it is not). If Bezout yields a d < 0, and you need a positive value, you need to add N until it becomes positive. So @jonh was right about that. I don’t know if it will solve all the problems, but there was definitely a bug when Bezout yielded a negative inverse.

As an (important Rust-wise) aside (that is, it won’t fix the error detected by the tests), you seem unaware that you can use a &String where a &str is expected; (instead of doing String -> Box<str> -leak-> &'static str). The best rule to avoid lifetime issues when returning a value (e.g., your encrypt function) is to try and return an owned value (such as a String). In the encrypt example for instance, the return value could be -> Result<String, &'static str>.

#10

@john was right and you @Yandros too. I didn’t see that first but I checked it out and as you said you were right, and it’s FULLY WORKING!! You’ve made my week guys seriously. 20/20 encryption/decryption process tests passing.

I wasn’t aware of this!!! Definitely, it’s a more efficient way of proceeding. I’ll refactor all of that!!

Thank you very much to all of you who helped guys!!

1 Like