Playing around with RSA key generation in Rust

[WarFox]

Basic algorithm for RSA key generation

1. Choose 2 large primes and make those p and q

2. Let N = p * q

3. Let T = (p-1)(q-1) resulting in the Euler Totient

4. Choose 2 numbers, e and d, where (e*d) mod T = 1

5. Let the public key be (e, N)

6. Let the private key be (d, N)

A few details about my implementation

Primes are generated by a crate called 'num_primes".

Values e, d are selected by letting e = 0 and d = T, looping until the condition (e*d) mod T = 1. If the condition is not true, add one to e and subtract one to d.

Code

Cargo.toml

[package]
name = "rust-rsa-fun"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
num-primes = "0.3.0"

main.rs

use num_primes::{Generator, BigUint};

struct PublicKey {
    n: BigUint,
    e: u64,
}

struct PrivateKey {
    n: BigUint,
    d: u64,
}

impl PublicKey {
    pub fn new(n: BigUint, e: u64) -> Self {
        PublicKey {
            n: n,
            e: e,
        }
    }

    pub fn print(&self) {
        println!("Public Key");
        println!("\tN: {}", self.n);
        println!("\te: {}", self.e);
    }
}

impl PrivateKey {
    pub fn new(n: BigUint, d: u64) -> Self {
        PrivateKey {
            n: n,
            d: d
        }
    }

    pub fn print(&self) {
        println!("Private Key");
        println!("\tN: {}", self.n);
        println!("\td: {}", self.d);
    }
}

fn calc_e_d(e: u64, d: u64, t: &BigUint) -> u64 {
    let T: u64 = t.bits().try_into().unwrap();
    (e * d) % T
}

fn find_d_e(t: &BigUint) -> Option<(u64, u64)> {
    let mut d: u64 = t.bits().try_into().unwrap();
    let mut e: u64 = 2;

    let one: u64 = 1;

    while calc_e_d(e, d, &t) != one {
        if d == 2 {
            return None;
        }
        e = e + one;
        d = d - one;
    }
    
    Some((e, d))
}

fn main() {
    let p = Generator::new_prime(64);
    let q = Generator::new_prime(64);

    println!("Let p = {p}");
    println!("Let q = {q}");

    let N = &p * &q;
    println!("Let N = {N}");

    let one: u64 = 1;

    let T = (p - one) * (q - one);

    println!("Let T = {T}");

    let keys = if let Some(k) = find_d_e(&T) {
        k
    } else {
        println!("Could not find numbers e and d");
        return;
    };

    let public_key = PublicKey::new(N.clone(), keys.0);

    let private_key = PrivateKey::new(N.clone(), keys.1);

    public_key.print();
    private_key.print();


}

 

Edited April 24, 2022 by WarFox
Fix bug in code

[Freak]

This is cool. I used to be very interested in RSA and I wrote my thesis about it so this is a cool refresher. 

Your implementation of e and d is interesting. I'm wondering if it introduces any kind of vulnerability though. You said that every time e and d are not multiplicative inverses you add 1 to e and subtract 1 from d. Since e is public, that means that a third party knows that T is e more than d (if they know you implemented it this way). Since they don't know what T or d are, that's probably not enough to make much progress at cracking it, but it's usually a bad idea for people to have a means to infer anything about the private key. Here are some other ways to calculate modulo multiplicative inverses if you're interested.

In one of my cryptography classes we learned about the ElGamal Cipher at about the same time as RSA since they're very similar in a weird way. Maybe I'll write a program to generate keys for that and do a comparison of ElGamal and RSA. 

[WarFox]

For sure its not a great implementation. When I decided to try to implement, it wasn't for anything serious and for some reason thought, I'll do it in Rust which isn't my strongest to program in. So I think I definitely did something in not the best fashion to have something working in theory while also not fighting Rust's static analysis the whole time over safety.

 

Will check out those links!

Edited July 10, 2022 by WarFox