WarFox Posted April 24, 2022 Share Posted April 24, 2022 (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 April 24, 2022 by WarFox Fix bug in code 1 Link to comment Share on other sites More sharing options...

Freak Posted May 19, 2022 Share Posted May 19, 2022 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. Link to comment Share on other sites More sharing options...

WarFox Posted July 10, 2022 Author Share Posted July 10, 2022 (edited) 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 Link to comment Share on other sites More sharing options...

## Recommended Posts

## 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