Jump to content

Playing around with RSA key generation in Rust


WarFox
 Share

Recommended Posts

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 by WarFox
Fix bug in code
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...