Skip to content

RSA Encryption

April 7, 2016

We would all like our phone communications to be secure. To ensure that eavesdroppers cannot listen in easily, most of our digital conversations are encrypted. Encryption goes back millenia – when Julius Cesar wanted to write a secret message to, say, Brutus he would replace every letter with one that appears a number of places down in the alphabet. When shifting by 5 positions, he would replace an A by an F, a B by a G, and so on. An interceptor would see a garbled note. But Brutus would shift each letter five spaces back in the alphabet and recover the original message.

Since Cesar’s time ciphers have become far more sophisticated. But until the 1970s, they had a serious problem. The sender and recipient of a message had to share the key to encrypt and decrypt the message. For example, Cesar and Brutus both knew to shift each letter in the alphabet by five spaces. They either had to agree to this in advance, or had to communicate this key in secret. If the key was intercepted, communications were not secure.

Now imagine a bank that wants to receive sensitive information from its customers. Sharing a separate key with millions of clients would be cumbersome, and storing all these keys safely would be difficult. But what if customers were all given a single key to encrypt their messages, but only the bank had the key to decrypt them. In such asymmetric cryptography, the key that locks the message is different from the key that unlocks it.

Such asymmetric encryption schemes may seem impossible. However, mathematicians have shown that they can be used in cryptography. The main idea is to find an operation that is easier to perform than it is to undo. For example, mixing oil and vinegar in a dish is easy. However, trying to get the oil out of the mixture is far harder.

There is a mathematical equivalent of this idea – the bank can give all its customers the same number, and they all use the same recipe to scramble their messages. However, only the bank keeps the number that can be used to unscramble the messages – think of it as a secret ingredient able to remove all the vinegar out of a mixture and recover only the oil. Without this secret ingredient, anybody wanting to separate the mixture would have to do it droplet by droplet.

The mathematicians Ron Rivest, Adi Shamir and Leonard Adleman were the first to describe a practical way to do this. They used ideas from number theory – one of the most abstract fields of mathematics. Similar schemes are now used widely. Indeed, as in the original scheme, the secrecy of our messages often relies on the fact that nobody knows how to quickly find two prime factors of a large number that is the product of the two.

If you have bought something online, or accessed your bank account over the internet you have used some version of such asymmetric encryption. Abstract mathematical ideas developed centuries ago have kept your interactions safe. But sophisticated ideas are also being used to break these schemes. And mathematics and computers remain the main weapons in this centuries long war between code makers and code breakers.

 

Notes:

RSA encryption was first proposed by Ron Rivest, Adi Shamir and Leonard Adleman publicly in 1978. However, it was discovered in 1974 by the English mathematician Clifford Cocks while working for a UK intelligence agency. This early discovery remained classified until 1997.

An excellent video explaining RSA encryption is available here 

Even the best encryption schemes can be vulnerable to attacks unless implemented well.

With so much of our lives (both on and off line) being recorded and documented, secure encryption is more important than ever. Indeed, encryption has been in the news recently: The FBI requested that Apple decrypt an iPhone used by one of the attackers in the December, 2015 mass killing in Bernardino, CA. The FBI reportedly decrypted the phone without help from Apple. The person behind the Panama Paper leak communicated only through encrypted channels, and remains anonymous. But encryption is essential even if you don’t do anything dangerous or illegal.

Advertisements

From → Uncategorized

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: