Cryptography in Programming pt 2 — Diving into Encryption

In one of my recent blog posts, we explored the world of cryptography and more specifically, took a look at secret key cryptography and its applications.

We took a closer look at the Caesar Cipher, which albeit simple, is one of the oldest methods of encryption in the history of cryptography. Also, I feel that the Caesar Cipher is a good entry point into understanding cryptography.

In this blog I want to discuss the types of encryption methods and then take a look at a specific form of encryption known as RSA encryption.

Encryption

As per my other blog on cryptography, we discussed what encryption actually is.

The basic idea behind encryption is that we want to encrypt or transform some plaintext or information into ciphertext so that only the recipient can decrypt the the ciphertext back into plaintext.

There are two main types of encryption that we will discuss. The first is symmetric encryption and the second is asymmetric encryption.

Symmetric Encryption

symmetric encryption uses the same secret key for both encryption and decryption

Symmetric encryption is the conventional method of encryption and is typically the more simple method of the two. In these cases, there is only one key that is used by both parties to both encrypt and decrypt information.

So, the sender uses this key before sending this message and the recipient uses the same key before reading the message. Any party that somehow obtains the ciphertext won’t be able to decrypt the message without this key. The Caesar Cipher is actually an example of symmetric encryption since the same key used to encrypt a message can be used to decrypt a message.

This form of encryption is generally used when sending large amounts of data since it does not take much time.

Asymmetric Encryption

this method uses a public key/private key combo

Asymmetric encryption is a relatively new and more complex method over symmetric. The reason for its complexity is mainly due to the fact that we need two different keys for implementation. The first key is the public key which as the name suggests, is a key available for all to see. The private key however, is kept secret by the owner of the public key.

If we were sending some information using asymmetric encryption, the first thing we have to do is use an encryption algorithm, along with the public key to get obtain our ciphertext. Now, the algorithm we utilize allows for decryption not with the public key, but the private key. What is interesting here is that you cannot decrypt the information with the same key used to encrypt it, which was the case for the Caesar Cipher.

Can you imagine what these algorithms are like? Well, you won’t have to imagine for long as we move into…

RSA Encryption

RSA stands for Rivest Shamir and Adleman

RSA encryption is an asymmetric cryptosystem. It was created by these three geniuses, Ron Rivest, Adi Shamir and Len Adleman.

Ron Rivest — a cryptographer and professor at MIT, he helped come up with the RSA encryption algorithm. He also invented several symmetric key encryption algorithms such as RC2, RC4, RC5.

Adi Shamir — also had several contributions to computer science and cryptography such as Shamir secret sharing scheme, the breaking of Merkle-Hellman knapsack cryptosystem, and TWIRL. Along with the help of colleague, Eli Biham, he discovered differential cryptanalysis. It turned out that IBM and the NSA had already discovered this and kept it a secret.

Len Adleman — computer science professor at the University of Southern California. Aside from RSA encryption, he was known for the experimental use of DNA as a computational system.

The system or algorithm itself works with very, very large prime numbers.

A prime number is a whole number greater than 1, whose only two whole-number factors are 1 and itself.

How do they find these large primes?

Without popping a blood vessel on how this works, there are many ancient math algorithms out there that do things like find prime numbers. One such example is the Sieve of Eratosthenes.

Sieve of Eratosthenes

The algorithm is intended to find all prime numbers until any given limit, which in this case is 120.

The way this works is by iteratively marking as composite the multiples of each prime starting with 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime and the difference between them is equal to that prime.

Ok, back to RSA encryption.

Before moving on however, I must apologize if some of this seems arcane. That actually is partially the point. As programmers, we must be very cautious when taking encryption into our own hands.

The following slides were taken from a presentation I did on Cryptography.

We’ll go over how the encryption/decryption keys work and then how these keys are formulated.

Suppose we have an encryption key = (5, 14) and some plaintext which is the letter “B”. Oh man, what a big secret we must encrypt!

Since we need to deal with numbers and not letters, let’s change the letter “B” into a character code of 2. In order to transform this into ciphertext, we will use the following formula.

(p^e_a ) mod e_b

(p^e_a ) mod e_b, where p is plaintext(“B”), e_a is encryption key A(5) and e_b is encryption key B(14). You may or may not be familiar with the mod or modulo operator.

In computing, the modulo operation finds the remainder after division of one number by another

Great, so now we have the number 4 which is equivalent to the letter “D”. The letter “D” is our ciphertext. So, in order for us to decipher this text. We will use the private key or decryption key = (11, 14).

We can use the same formula above and as you can see from the slide above, we end up getting a character code 2, which is equivalent to our plaintext “B”. Eureka! It works!

What’s really interesting is how you can obtain these keys.

As I had mentioned before, the RSA encryption algorithm works with very large prime numbers, typically hundreds of digits long. For demonstration purposes we will work with small primes just so that we can conceptualize how we got those encryption and decryption key pairs.

NOTE: Remember that our encryption key was (5, 14) and our decryption key was (11, 14)

Let’s go over each step.

Step 1 — We need to find two numbers p and q. These two numbers must be prime, so let’s choose 2 and 7.

Step 2 — Next we need to come up with N. To find N we can use the formula p * q = N. Now we have N, which will be the encryption_b and decryption_b, which you can see is the same number, 14.

Step 3 — That funny symbol in this step is the greek letter phi which represents Euler’s ‘totient’ function. We need to use this(don’t worry about Euler or the specifics on totient too much now) function on N, which just finds the number of coprimes for N. That number turns out to be 6.

In number theory, two integers a and b are said to be relatively prime, mutually prime, or coprime (also spelled co-prime) if the only positive integer that divides both of them is 1. That is, the only common positive factor of the two numbers is 1. This is equivalent to their greatest common divisor being 1.

Step 4 — We need to find e or encryption_a. In order to do that we need to choose a number so that it is greater than 1, but less than the totient of N, which we found in Step 3, to be 6. So we choose 5 since it satisfies those conditions. Ok, so we can set encryption_a = 5.

Step 5 — Now we need to find d or decryption_a. The formula to figure this out is the following.

d * e(mod (φN)) = 1, we can plug the values in here and get

d * 5(mod 6) = 1

d = 11

NOTE: d can actually be one of several numbers, but we can choose the number 11 since it satisfies all conditions. Now we have both encryption and decryption key pairs(5, 14) and (11, 14).

And that, ladies and gentlemen, is a high-level view on how the RSA cryptosystem works!