Ron Rivest, Adi Shamir, and Leonard Adleman were the creators of the RSA encryption that we use many times, possibly hundreds of times, a day. They gave the first letters of their surnames to name it.
Encryption has been around ever since people wanted to send secret messages. An early cipher is the Caesar cipher that we all probably tried to use when we were kids. It is a simple cipher where you shift the letters of the alphabet by an agreed amount. So, if we want to write, “attack at dawn” with a shift of 3, we move all of the letters three points along the alphabet and we end up with “dwwdfn dw gdzq”. The problems with this system is the other person has to know how many letters it is shifted by and it is fairly easy to crack because we know the most common letters are “e” and it always uses the same letter for the same letter. There have been many advances in ciphers over the years, but the problem was always that if the other person didn’t know the key, they had no way to unlock the cipher. Even the enigma machine in the Second World War, which had an enormous number of possible combinations of letters, had to have a secret book of key settings. That is always the weakness of any cipher. If people can get the key, they can read the cipher.
The invention of powerful computers and the Internet made it possible to have more complex ciphers and made it necessary for a way to send a message to someone that couldn’t have a key. If you send an email to a friend, they could have the key, but if you send an email to someone you have never met, there is no way for them to have a key. Likewise, without a system that doesn’t need the other party to have a key, credit card transactions online would not be possible.
Ron Rivest, Adi Shamir, and Leonard Adleman wrestled with this problem in the 1970s. In 1976, Whitfield Diffie and Martin Hellman had come up with the idea of asymmetric encryption. The regular encryption that we used before powerful computers was symmetric encryption. That is where the same key is used to encrypt the data and to unencrypt it. For example, with my earlier Caesar cypher, the key is 3 and both sides need that key. Asymmetric data, as the name suggests, doesn’t use the same key. The sender uses one key to encrypt the data and the receiver uses another key to unencrypt the data. Diffie and Hellman came up with the idea, but they couldn’t work out how to do it. Rivest, Shamir, and Adleman worked at the Massachusetts Institute of Technology and they started to work on the problem.
Ron Rivest is an American computer scientist. Adi Shamir is an Israeli computer scientist. Leonard Adleman is an American engineer and mathematician. Rivest and Shamir tried to work out different ways of doing it and Adleman used his mathematical skills to break each type of encryption. Some systems were more difficult than others, but he managed to break every single one. They couldn’t find any way to do it and were starting to think that it was impossible. All that changed after a lot of wine in 1977. They gathered for Passover at a friend’s house and drank a lot of wine before going home. At about midnight, Ron Rivest had an idea and he called up Leonard Adleman to ask if it would work. Adleman said it would and the next day Rivest came into work with most of the paper written. That is why the order of the names is RSA. Names on a research paper usually go in order of contribution. Adleman didn’t think he contributed much and originally asked them to take his name off it. They refused because of all his work trying to break each code. It took some time to get it working, but in December 1977, they filed the patent.
So, what did they come up with? Rivest realized that prime numbers were literally the key. He realized that it was very easy to calculate the total when two prime numbers are multiplied together, but it is almost impossible to work out what those original prime numbers were if you only have the total. For example, if I give you the prime numbers 1823 and 9341, you could use a calculator and very quickly tell me that the total when these two numbers are multiplied together is 17028643. I used google and, apparently, it took google 0.36 seconds to do that and find over 10 million search results at the same time. However, if I give you the number 17028643 and ask you what prime numbers were multiplied together to make it, that will be more difficult. (An online factoring calculator just did it for me in less than a second).
Let’s think about two people, John and Fred, messaging each other. It is a little more complicated than this, but RSA encryption works like this. John’s computer creates two random prime numbers. The numbers are far longer than the examples I used here, usually about 150 numbers long. Then the two numbers are multiplied and the total is sent to Fred. Fred uses the total to encrypt the message and he sends it back to John. John uses the original two prime numbers to decrypt the message. If someone intercepts the message, they only have the total of the two numbers, and it would be too hard for them to factor such a long number and work out what the original primes are. It would take a regular computer billions of years to do. And that is RSA encryption. However, quantum computers could do it potentially in seconds.
So, Ron Rivest, Adi Shamir, and Leonard Adleman created the RSA encryption system that we use every day. And this is what I learned today.
Image By Ronald L. Rivest – Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=44374880
Sources
https://www.cloudflare.com/learning/ssl/what-is-asymmetric-encryption/
https://www.techtarget.com/searchsecurity/definition/RSA
https://cryptii.com/pipes/caesar-cipher
https://en.wikipedia.org/wiki/RSA_(cryptosystem)
https://www.techtarget.com/searchsecurity/definition/RSA
https://www.invent.org/inductees/leonard-adleman
https://amturing.acm.org/pdf/AdlemanTuringTranscript.pdf
https://www.splunk.com/en_us/blog/learn/rsa-algorithm-cryptography.html
https://www.mathpapa.com/factoring-calculator/
https://hal.science/hal-01397035/document