There Is Beauty in Cybersecurity: Bare Bones RSA in Rust

There Is Beauty in Cybersecurity: Bare Bones RSA in Rust

I really love creating code in Rust, but while there are lots of libraries around to integrate, there’s a real lack of practical examples of code. Personally, I have never been a believer in learning from generic code, such as ordering an online pizza, and much prefer to use real-life (and interesting) code. So, let’s dive in, and implement one of the most beautiful (and important) things in Cybersecurity: the RSA method.

The method

The RSA method is a thing of beauty. It has a public key and a private key, and where we can encrypt with one of these keys, and decrypt with the other one. In practice, we use often use it to prove identity, create digital signatures, and in encrypting data.

Last year, we were so lucky when Len Adleman - the ‘A’ in RSA method — outlined some of the history around its creation:

With RSA, we first generate two random prime numbers (p and q) and then produce a modulus of:

n=pq

It is the difficulty in factorizing this modulus back to its prime number factors that provide the core strength in the method. To encrypt a message value of M we generate ciphertext (C) of:

C=M^e (mod n)

and where e is the encryption value. Normally we use a value of e=65,537. To decrypt we determine a value of d and which is the inverse mod of e (modφ(n)):

d=e^{−1} (mod φ(n))

and where:

φ(n)=(p−1)(q−1)

To decrypt, we take:

D=C^d (mod n)

The public key is then (e,n) and the private key is (d,n). In this case, we will take a bare-bones approach to the implementation of RSA, and use 64-bit unsigned integers. In real-life we would use Big Integers for this [Big Int RSA], and where we would use integers with at least 1,024 bits.

Bare Bones RSA in Rust

First, we create the Rust project with:

cargo new rsa01

We then go into the rsa01 folder and then into the src folder, and edit the main.rs file with [here]:

use std::env;

// https://rosettacode.org/wiki/Modular_inverse#Rust
fn mod_inv(a: isize, module: isize) -> isize {
    let mut mn = (module, a);
    let mut xy = (0, 1);
   
    while mn.1 != 0 {
      xy = (xy.1, xy.0 - (mn.0 / mn.1) * xy.1);
      mn = (mn.1, mn.0 % mn.1);
    }
   
    while xy.0 < 0 {
      xy.0 += module;
    }
    xy.0
  }

// Ref: https://rob.co.bb/posts/2019-02-10-modular-exponentiation-in-rust/
fn mod_pow(mut base: u128, mut exp: u128, modulus: u128) -> u128 {
    if modulus == 1 { return 0 }
    let mut result = 1;
    base = base % modulus;
    while exp > 0 {
        if exp % 2 == 1 {
            result = result * base % modulus;
        }
        exp = exp >> 1;
        base = base * base % modulus
    }
    result
}

fn main(){

    let mut p:u128=97;
    let mut q:u128=101;
    let mut M:u128=999;

    let args: Vec   = env::args().collect();

  
    if args.len()> 1 { M= args[1].clone().parse::().unwrap();}
    if args.len()> 2 { p = args[2].clone().parse::().unwrap(); }
    if args.len()> 3 { q = args[3].clone().parse::().unwrap(); }

    println!("-- RSA Program --");
    let  n = p*q;

    let e = 65537;

    let C = mod_pow(M,e, n);

    println!("Input={}",M);
    println!("\np={:?}\nq={:?}\nn={:?}", p,q,n);

    let PHI = (p-1)*(q-1);
    println!("\ne={}, PHI={}",e,PHI);

    let d = mod_inv(e as isize, PHI as isize);

    println!("\nd={}",d);

    println!("\nEncrypted={}",C);

    let D = mod_pow(C,d as u128, n);
    println!("\nDecrypted={}",D);

}

Finally, we simply build with:

cargo build

For a run with M=99, p=97 and q=101 [here]:

cargo run 99 97 1010

we get:

-- RSA Program --
Input=99

p=97
q=101
n=9797

e=65537, PHI=9600

d=9473

Encrypted=1965

Decrypted=99

In this case, rather than integrating external code, we have integrated two functions: modinv() and mod_pow(). The modinv(e,PHI) function produces the inverse of e mod PHI, and the mod_pow(M,e,n) function does M to the power of e, mod n. The mod_pow() function makes the exponential efficient, as it takes into account the mod n part in the computation. This stops an overflow of the arithmetic operations, and also makes it much faster in its operation.

Here is the running code:

https://asecuritysite.com/rust/rsa02

RSA with Big Integers

In real life, we now use prime numbers which are at least 1,024 bits long, and which produces a 2,048-bit modulus. This is because a 1,204-bit modulus is under threat of being cracked by GPUs. In the previous program, we used 128-bit unsigned integers, so we now need to support much larger integers for our calculations. For this we can use Big Integers, and which store their values in a string format, and where we can still perform the mathematical operations on virtually any size of number.

First, we create the Rust project with:

cargo new rsa01

We then go into the rsa01 folder and add the following to the cargo.toml file:

[package]
name = "rsa01"
version = "0.1.0"
edition = "2021"

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

[dependencies]
glass_pumpkin = "1.0"
num-traits="0.2.14"
num-bigint="0.4.3"

Next, we go into the src folder, and edit the main.rs file with [here]:

extern crate glass_pumpkin;

extern crate num_traits;

use num_traits::*;

use glass_pumpkin::prime;

use num_bigint::{BigInt,Sign};

use std::env;

fn modinv(a0: BigInt, m0: BigInt) -> BigInt {
    if m0 == one() {return one()}
    let (mut a, mut m, mut x0, mut inv) = (a0, m0.clone(), zero(), one());
    while a > one() {
    inv -= (&a / &m) * &x0;
    a = (&a % &m);
    std::mem::swap(&mut a, &mut m);
    std::mem::swap(&mut x0, &mut inv)
    }
    if inv < zero() { inv += m0 }
    inv
    }

fn main(){

    let mut no_bits=512;
    let mut val="999";

  let args: Vec   = env::args().collect();

  if args.len()> 1 { val= args[1].as_str();}
  if args.len()> 2 { no_bits = args[2].clone().parse::().unwrap(); }

   let  p = BigInt::from_biguint(Sign::Plus,prime::new(no_bits).unwrap());
   let  q = BigInt::from_biguint(Sign::Plus,prime::new(no_bits).unwrap());

    let  n = p.clone()* q.clone();

    let e = BigInt::parse_bytes(b"65537", 10).unwrap();
    let M = BigInt::parse_bytes(val.as_bytes(), 10).unwrap();
    let Enc = M.modpow(&e, &n);

    println!("Input={}",val);
    println!("No of bits={}",no_bits);
    println!("p={:?}\nq={:?}\nn={:?}", p,q,n);

    let totient = (p - BigInt::one())*(q-BigInt::one());
    let d=modinv(e.clone(),totient.clone());
  
    println!("\nd={}",d);

    println!("\nEncrypted={}",Enc);

    let Dec = Enc.modpow(&d,&n);
    println!("\nDecrypted={}",Dec);

}

Finally, we simply build with:

cargo build

For 512-bit random prime numbers and a message of 999, we run with:

cargo run 999 512

The following is a sample run [here]:

Input=999
No of bits=512
p=10946126281476327264486450417725523699764222783727827357259857855877150488613979040834484700702575792264807423792134820751009083529387921014898845153210793
q=6865870094569483420970378796990546359694638375714827799024962165837778731708739496029075535654852923769370621245806006938606296317270216391330765677871563
n=75154681087369378975343258543620070092534691731512880614291553499141982411953741519979773065955356052992863682289211988887512785216819807853949880310744799520520611593554972065724166859497455704090536668795737729523433197385418991281753110337778861653295063309447244259025136646157311753836281848619719379459

d=69569999199344463651023840976330909139933200226981581827474948138188300456017175592300729245957452823091048736033685150828367763870009418848521863814516283502617449654012277579105391789146739216157752539455126943647433730658562409413379313109436976117193889868544145302746303904911370294044031420089601695537

Encrypted=48356899627010492816400972945818575762365424596512840055060583504553837827865691253744976286395582614972383925431238011662055328730326053652224301128397286215476623071658373502166255720722084694061330238966504900700621187872042891900322695556868537215947841861077156904978126345158606210602934915901836791088

Decrypted=999

Here is the running code:

https://asecuritysite.com/rust/rsa01

Conclusions

Is RSA beautiful? Simple, but has been at the core of cybersecurity for over four decades. If you are interested in learning more about Rust and cryptography, try here:

https://asecuritysite.com/rust/