Ozgur's Blog

Random ramblings of personal nature

RSA Encryption - A Non-Mathematician's Primer


Introduction

Rivest-Shamir-Adleman algorithm (which are the surnames of the people who discovered it) is probably the most common asymmetric encryption scheme used worldwide. It was discovered in 1970s and patented in the USA (but not in the rest of the world) until 2000.

Let's try to explain what is a symmetric encryption scheme. In this method both the sender and the receiver use the same key to encrypt and decrypt the message. The problem here is it is often impossible to share this key wtihout meeting physically - or rather sending the key alone from various channels in our modern times. Also it is not that efficient. To provide secure communications a bank, for example, needs to provide each and every client a lock and a key.

Instead, as James Ellis have discovered, locking and unlocking are inverse operations. If we follow our previous example a bank can buy a lock, keep the key and distribute the open locks to its customers. Bank only needs to keep track of a single key but locks are publicly available. This creates the backbone of asymmetric encryption scheme. The person who wants to encrypt his message to me doesn't need to have my key, only my lock is enough to encrypt his message.

In other words we have two keys, one is used for encryption (lock - public key) and the other is for decryption (key - private key). RSA enters into the picture in this conjuncture.

RSA is rather slow so it is often used to encrypt the key to facilitate symmetric encryption between parties.

How to Use RSA - A Basic Example

rci-summary

I am not a mathematics expert so I would be lying if I told you I understood all the nitty gritty details of RSA encryption scheme. What it basically does is to use the complexity of prime factorization as a basis for creating the key. Although multiplication is a fast operation, it is not easy to find which multiplicatives used to generate this result. It may even take years to calculate all the constituents if numbers with 23 digits or more has been chosen.

Generating Public and Private Key Pairs

As I have stated we have two keys in RSA. One is public and the other is private. Alice shares her public key with me (7, 143). Canonically 143 is called as n and is calculated via multiplication of two primes - I don't know which and don't need to know as well - in our case it is 11 and 13; and 7 is called as e which is something we choose limiting our choice by seeing the Greatest common denominator between my n and it should be 1.

To generate my encryption I first convert my message to a number or a series of numbers and apply this function:

def encrypt_rsa(clear_number, e, n):
    return clear_number ** e % n

In here I plug my number get its power by the e and return the remainder by modulus of n. This encrypts my message. I send this to Alice and she takes this and decrypts it by using her private key which is something only she knows. In our case this is (103, 143) She calculates this number, 103 and canonically called as d, by using Extended Euclidean algorithm and finding its inverse:

def findInverse(e, phimod):
    e = e % mod
    for i in range(1, phimod):
        if ((e * i) % phimod == 1):
            return i
    return 1

print(findInverse(7,120)) #103

Then she uses this number to decrypt my message. d and e are inverse numbers of each other and they are connected via n. You can think this through with an analogy. I and Alice are transferring colors. Alice uses red as her private key color. She then finds its inverse - when this inverse color is added red becomes white. This color is cyan and she shares this color with me. I mix my color with cyan and send it to her. When she adds her red, my original color appears - because red and cyan neutralize themselves.

To decrypt my message she uses this algorithm:

def decrypt(encrypted_number, d, n):
    return encrypted_number ** d % n

In here I take the power of the encrypted number to the d and get its remainder by modulus of n. Which gives me my original number.

As you can see I can encrypt my message without knowing d and those who intercept my messages won't be able to decrypt my message with knowing n and e. It is possible to brute force this by applying years of computational power - hence the discussion comes about how quantum computing will make this trivial to crack - but currently this is counted as a hard problem.

Thanks for reading!

Resources