A while back I did a variant of the Ceaser Cypher called the ROT13 cipher. It was a simple cipher to implement but it’s not very secure. In fact, it’s actually pretty trivial to crack so is not recommended for use other than for lolz. But encryption is a fascinating topic so I wanted to see if I could do more secure encryption. With that in mind today I’ll be going into a simple implementation of RSA Encryption.

Introduction

RSA which stands for Rivest–Shamir–Adleman is a public-key cryptosystem that is widely used for secure data transmission. That’s right, it’s secure enough that it’s currently in use.

The basic idea of RSA encryption is that you generate two keys, a public key, and a private key. You distribute the public key to anyone and everyone who would want to send you an encrypted message. They then use that public key to encrypt the message which can only be decrypted using the private key.

That’s not strictly true, encrypted messages can be decrypted without the private key but it’s infeasible or will take too long to do.

RSA depends on the practical difficulty of factoring the product of two large prime numbers i.e. the “factoring problem”. So until an algorithm is developed to solve that problem in a reasonable time it should remain relatively secure.

RSA Encryption Process

The process to use RSA is pretty simple. We will be using the same process found on Wikipedia for this post.

First, you need two distinct prime numbers. They should be similar in size and here we get to use our first function, the primality check.

For our example, we chose 61 and 53 as our primes. We will name them p and q.

Next, we compute the value we will use for our modulus operations.

We will call this n. The number also determines how large our message can be.

The next step is to calculate the Carmichael function of n. That sounds complicated but it’s actually just the lowest common multiple of (p -1, q-1).

Then we need to select an integer e that will be used as part of the public key to encrypt messages. This number has to be greater than 1 and less than the lambda_n that we calculated above.

We also need a value that will be used to decrypt our message. This value will be called d and we get this by calculating the modular multiplicative inverse of e on mod n.

Everything is now in place. The public key will be (n, e) while the private key will be (n, d).

Encrypting and Decrypting

To encrypt a message(m) you would use the function:

And to decrypt an encrypted message(c) you would use:

If you’ve been following along then at this point you might have run into an overflow error while trying to encrypt or decrypt. This is because we are trying to calculate the exponent of large numbers with even larger exponents. What can we do? If only we had some method to calculate modular exponents… oh wait, we do.

The whole thing looks like this:

mod inverse;
mod mod_exp;
mod numbers;
mod primality;

use crate::inverse::inverse;
use crate::mod_exp::mod_exp;
use crate::numbers::lcm;
use crate::primality::is_prime;

fn main() {
    println!("Simple RSA");

    // Initial Primes
    let p: i64 = 61;
    let q: i64 = 53;
    assert!(is_prime(p));
    assert!(is_prime(q));

    let n = p * q;
    println!("n: {}", n);

    // Carmichael function λ(n) of modulus
    let lambda_n: i64 = lcm(p - 1, q - 1);
    println!("Lambda_n: {}", lambda_n);

    let e: i64 = 17;
    let d: i64 = inverse(e, lambda_n);

    println!("Public Key: (n={}, e={})", n, e);
    println!("Private Key: (c={}, d={})", n, d);

    let message: i64 = 65;
    let encrypted_message: i64 = mod_exp(message, e, n);
    println!("Encrypted message: {}", encrypted_message);

    let decrypted_message = mod_exp(encrypted_message, d, n);
    println!("Decrypted: {}", decrypted_message);
}

Code language: Rust (rust)

And there you have it, folks. We have a simple RSA encryption implementation. Encryption is a complicated topic and this just gave me a greater appreciation of what goes into it. If you want to roll out your own home brew RSA encryption, don’t. Unless you want to spend a lifetime studying you’re better off using an existing library.

You can find the code for everything we did over the last few days on Github. Feel free to fork the repo and play around with it and if you make some interesting changes feel free to open a pull request and let me know about it on Twitter, @phoexer. This has been hella fun, happy coding.