# Playing around with RSA key generation in Rust

## Recommended Posts

Posted (edited)

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

## Create an account

Register a new account