RSA Key Basics

Recently, there’s been a lot of media chatter about quantum computing and how it will impact various industries in inconceivable ways. A recurring theme across these articles was the threat to current mainstream cybersecurity measures, specifically RSA, so I decided to learn more about RSA and bring some of that information together in this blog. Follow along to get a basic understanding into how RSA works and I’ll show you how to easily send encrypted files to your friends, safe from peering eyes.

Described publicly in 1978, RSA stands for its founders Ron Rivest, Adi Shamir, and Leonard Adlema. RSA is an asymmetric cryptographic algorithm because it entails two keys, one public and one private to securely transfer information. The private one, as you might assume, is never shared and its actually recommended to keep a physical copy in a safety deposit box (if used for highly sensitive information). The public one can then be shared freely for anyone to use to encrypt a message, but only the private key can decrypt it.

Now let’s go over RSA. It’s based on the difficulty computers have with prime factorization of VERY large numbers, hundreds of digits long. Computers can really easily multiple large prime numbers, but its time consuming to do take the product of two large primes and find its prime factors . Referring to the figure below, for the number entered into the Factor input (2.0747222467734853e+999), it would take in the range of 47 BILLION years versus multiplying the same input by itself .

Taken from Khan Academy (see more here)

Disclaimer: this might vary depending on method calculation…but you get the point.

As I said before, the first step is to choose two large random prime numbers p and q and multiply them together. Usually these numbers are in the order of 100 digits, but I’ll use a simple example for ease of demonstration.

n = p*q, let p = 11, q = 5

n = 55

Calculate the totient: φ(n) = (p -1)(q-1) = 10*4 = 40

Choose an integer e that is less than and relatively prime to the totient φ(n), which means they should share no factors other than 1 (i.e. GCD(e, n) = 1). Thus, we can use e = 7. To find relatively prime numbers of φ(n), you’ll need to guess and check to find all numbers x that satisfy φ(n) % x = 1, where x can’t be 1 or a factor of φ(n).

Next, choose d to satisfy the congruence relation, de ≅ 1 mod φ(n). If you’re not familiar with modular arithmetic don’t worry, just know the given equation is the same as saying de % φ(n) = 1. We can use the extended Euclidean algorithm to solve this.

Step 1)

φ(n)x + ey = 1

40x + 7y = 1 Now find how many times 7 goes into 40*, as well as the remainder**, and set up the following equation:

40 = 5*(7) + 5** Then take the bolded values and perform the previous step until the remainder is 1 (i.e. how many times does 5 go into 7).

7 = 1(5) + 2

5 = 2(2) + 1

Step 2) Rearrange the relation so everything is set equal to one, then substitute 2 with the relation that came just before it (20 = 6*3 + 2).

1 = 5–2(2)

1 = 5–2(7–1(5)), combine like terms without losing 7

1 = 3(40–5(7))-2(7)

1 = 3(4)-17(7), we care about the number in front of 7(our e value), which is positive so, because this isn’t positive: d = (num in front of e) mod φ(n) = -17 mod 40 = 23. If it were positive, the number in front of e would be our d.

Now that we’ve established our public key (n and e), we can share it freely so someone can encrypt a message for us to unlock with a private key (n and d). If we are sending some sort of message, we’ll need to convert it into a number m using some reversible protocol. Let’s say our message is simply a letter say ‘Y’ for responding ‘yes’ to some question. Let Y = 25, since that is its position in the alphabet.

c = m^e mod n

c = 25⁷ mod 55= 20

You could repeat this process for however many letters to create a longer message. Now, to decrypt:

m = c^d mod n

m = 20²³ mod 55= 25 → Y

The difference between the contrived example above and using RSA in practical applications is that, not only are the numbers much larger, but they’re also protected by additional layers of encryption, called a padding scheme. To get a little bit closer to an actual implementation of RSA, I generated RSA keys from the command line using OpenSSL.

Create private RSA key:

openssl genrsa -des3 -out private.pem 2048

Create public RSA key:

openssl rsa -in private.pem -outform PEM -pubout -out public.pem

NOTE: the -pubout flag ensures that only the public key is exported outside of its encrypted wrapper.

To view keys run: less public.pem . It’s not recommended to view your private key in this manner if you’re using it for anything of importance, but if you want to anyway, just run less private.pem.

Your keys will look something like this:

Private Key

Public Key

Now that you have your keys, create a plaintext file with the message you’d like to encrypt.

[DOUBLE CHECK IMPLEMENTATION]

echo "Hello World" > plain.txt

Then to encrypt the plaintext, use the following commands:

cat plain.txt \
 | openssl rsautl \
     -encrypt \
     -pubin -inkey public.pem \
 > cipher.txt

You’ll then see a copy of your encrypted message:

Encrypted message

Now you’re free to send this message by any means, email or otherwise. Then to decrypt it with the private key, use the following commands.

cat cipher.txt \
  | openssl rsautl \
      -decrypt \
      -inkey private.pem

And out pops the original message!

Decrypted message

RSA works because determining the prime factors, p and q from their quotient, requires some degree of trial an error. Thus, with large enough numbers, it can take 10’s or hundreds of years to crack RSA encryption.

You might be wondering why I opened with quantum computers. Well, the wait is up. According to Dario Gil, the Vice President of Science and Solutions at IBM Research, high-end implementations of RSA would take roughly 28,000,000,000,000,000,000,000 for a conventional computer to break, but for a quantum computer of roughly 50-quibits, the same operation would take 100 seconds (Dario Gil’s talk can be seen here). This estimate exemplifies the paradigm shift from conventional to quantum computation and the incredible risk it poses to traditional cybersecurity measures.

Dario Gil also claims that quantum computing in this capacity will be realized in the next 10 years. That is not a lot of time to adapt new global security protocols, so it’s important to educate ourselves sooner than later. I hope to follow this up with a post that explores quantum computing in more depth and reveals how software developers today will stay relevant in the age of quantum computing. Stay tuned for more!

Encryption example taken from Daniel Rees.