RSA Encryption
In a previous article I described how public cryptography works. Public cryptography occupies asymmetric key algorithms to encrypt and and decrypt the messages.
I.e Public key of the receiver is used to encrypt the message so that using his own private key, the receiver can then decrypt the message once he receive the message. If you feel like you need a brush up to your memory about public key cryptography please read that article too, before continuing with this.
OK, but how such algorithms work ? one key to lock a file and another to unlock ? aren’t these two keys related at all ? if they are related why cannot hackers calculate a private key of a key pair when they can perfectly access the public key of anyone ?
These are the questions I aim to address in this article, using one of the most famous asymmetric Encryption algorithms of all time. The RSA encryption.
The RSA algorithm is the basis of many modern day cryptosystems (a suite of cryptographic algorithms) which enables public key encryption. It is widely used to secure sensitive data, particularly when it is being sent over insecure channels such as the internet. Many end to end encrypting communication services and banking systems uses RSA as their base too.
THE HISTORY
The first major development towards what we now call public-key cryptography was published at the early 70’s by James H. Ellis and it was expanded upon by his colleague Clifford Cocks.
All of this work was undertaken at the UK intelligence agency, the Government Communications Headquarters (GCHQ), which kept the discovery classified. The GCHQ couldn’t see a use for public-key cryptography at the time,so the development sat idly on the shelf gathering dust. It wasn’t until 1997 that the work was declassified and the original inventors of RSA were acknowledged.
At the same time, similar concepts were beginning to develop elsewhere too. Ralph Merkle created an early form of public-key cryptography, which influenced Whitfield Diffie and Martin Hellman in the design of the Diffie-Hellman key exchange.
Diffie and Hellman’s ideas were missing one important aspect that would make it a foundation of public key cryptography,a one-way function that would be difficult to invert.
In 1977, Ron Rivest, Adi Shamir and Leonard Adleman, whose last names form the RSA acronym, came up with a solution after a year of laboring on the problem.
The MIT-based academics made their breakthrough after a Passover party in 1977. The idea was patented in 1983 by MIT, but it wasn’t until the early days of the internet that the RSA algorithm began to see widespread adoption as an important security tool.
How does RSA encryption work?
In RSA cryptography, both the public and the private keys of a key pair can encrypt a message. And the opposite key of the one used to encrypt the message, is used to decrypt it. Each RSA user has a key pair consisting of their public and private keys. As the name suggests, the private key must be kept secret.
This attribute provides a method to assure the confidentiality, integrity, authenticity, and non-repudiation of electronic communications and data storage.
How is it used in modern day communications
RSA encryption is often used in combination with other encryption schemes, or for digital signatures which can prove the authenticity and integrity of a message. It isn’t generally used to encrypt entire messages or files, because it is less efficient and more resource-heavy than symmetric-key encryption
To make things more efficient, a file will be encrypted with a symmetric-key algorithm, and then the symmetric key will be encrypted with RSA encryption. Under this process, only an entity that has access to the RSA private key will be able to decrypt the symmetric key. ( this article explains it all — link)
Without being able to access the symmetric key, the original file can’t be decrypted. This method can be used to keep messages and files secure, without taking too long or consuming too many computational resources.
As one of the first widely used public-key encryption schemes, RSA has laid the foundations for much of our secure communications. It was traditionally used in TLS / SSL and was also the original algorithm used in many crypto systems. Though there are new algorithms followed later on, RSA is still seen in a range of web browsers, email, VPNs, chats and other communication channels.
RSA is also often used to make secure connections between VPN clients and VPN servers. Under protocols like OpenVPN, TLS handshakes can use the RSA algorithm to exchange keys and establish a secure channel.
The Mathematics behind it
To keep the math from getting too out-of-hand, we will be simplifying some concepts and using much smaller numbers. In reality, RSA encryption uses prime numbers that are much larger in magnitude and there are a few other complexities.
There are several different concepts you will have to get about before we can explain how it all fits together. These include trapdoor functions, generating primes, Carmichael’s totient function and the separate processes involved in computing the public and private keys used in the encryption and decryption processes.
RSA algorithm has gained it’s asymmetrical property from the difficulty of factorizing large integers, that each are the product of two large prime numbers. This calculation is easy to compute in one direction, but almost impossible in reverse.
As an example, if you were told that 614,987 is a product of two prime numbers, would you be able to figure out what those two numbers are?
Quite challenging isn’t it ? Even with a calculator, most of us wouldn’t have any idea of where to start. But if we flip things around, it becomes much easier.
What’s the result of: 839 x 733
This 839 and 733 are the prime numbers that answer our first question, which shows us that certain equations can be easy to figure out one way, but almost impossible the other way.
Other interesting thing about this equation is that it is simple to figure out one of the prime numbers if you already have the other one, as well as the product. If you are told that 614,987 is the result of 839 multiplied by another prime number, you can figure it out the other prime with the following equation:
614,987 ÷ 839 = 733
And what if this number is 100 digits long ? or even 200 digits long ? manually that calculation is almost impossible. And even with the super computers we have now a days, such operation would take a thousands of years to finish such calculation.
And that is the reason why it is known as a trap door function. Be aware that while the above example is hard for people to figure out, computers can do the operation in a trivial amount of time.
Because of this, RSA uses much larger numbers. The size of the primes in a real RSA implementation varies. In 2048-bit RSA version, they would come together to make keys that are 617 digits long. To help you visualize it, a key used would be long as this.
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Generating primes
The first step of encrypting a message with RSA is to generate the keys. To do this, we need two prime numbers (p and q) which are selected with a primality test. A primality test is an algorithm that efficiently finds prime numbers, such as the Rabin-Miller primality test algorithm — it selects two distinct and relatively far apart prime numbers to be used in the process.
Numbers that are small or closer together are much easier to crack. Despite that, in our example we will use two smaller numbers to make things easier to follow and compute.
Let’s say that the primality test gives us the prime numbers 907 and 773. The next step is to discover the modulus (n), by multiplying them
n = p x q
Where p = 907 and q = 773
Therefore:
n = 907 x 773 = 701 ,111
This number n is used by both the public and private keys and provides the link between them. Length of this number is usually expressed in bits, and it is called the key length.
Carmichael’s totient function
Once we have n, we use Carmichael’s totient function on n:
λ(n) = LCM (p − 1, q − 1)
if you are not working closed with mathematics much, the above might look a bit confusing. But its just simple. it says that λ(n) — Carmichael’s totient of n, is equal to the least common multiple of p -1 and q-1
Anyway just trust that the math works, and stick with us for a few more calculations. Everything will be explained in as much detail as possible to head around the basics.
To find the LCM of large numbers you can use this advanced LCM calculator hosted online, if it ever encounters you.
public key (n,e)
Now that we have Carmichael’s totient of our prime numbers, it’s time to figure out our public key. Under RSA, public keys are made up of a prime number e, as well as n. The number e can be anything between 1 and the value for λ(n) ( in our case 349716 )
Because the public key is shared openly, it’s not so important for e to be a random number. In practice, e is generally set at 65,537, because when much larger numbers are chosen randomly, it makes encryption much less efficient. For our example , lets keep it much smaller. Let’s say e = 11
in this example we are using some notations,
Our final encrypted data, the cipher-text is denoted by — c .
our plain-text message is denoted by — m,
we compute c for a given m as follow
c = m^e mod n
We have already come up with e and we know n as well. Mod n refers to the usual modulo operation, which essentially means the remainder left over when you divide one side by the other. For example: 10 mod 3 = 1
Coming Back to our equation. To keep things simple, let’s say that the message (m) that we want to encrypt and keep secret is just a single number, 4.
Now lets substitute the real numbers.
c = m^e mod n
c = 4^11 mod 701,111
c = 4,194,304 mod 701,111
Again, to make the modulo operation easy, we will be using an online Modulo operator, but you are welcome to figure it out for yourself.
It turns out that c = 688,749
Therefore when we use RSA to encrypt our message, 4, with our public key, it gives us the cipher-text of 688,749.
We had a message , which we wanted to keep secret. We applied a public key to it, which gave us the encrypted result of 688,749.
Now that it is encrypted, we can securely send the number 688,749 to the owner of the key pair. They are the only person who will be able to decrypt it with their private key. When they decrypt it, they will see the message that we were really sending, 4.
Now lets see how things are getting done at that end.
private key (n ,d)
Private keys are comprised of d and n. We already know n, and the following equation is used to find d:
d = 1 / e mod λ(n)
In the Generating the public key section above, we already decided that in our example, e would equal 11. Similarly, we know that λ(n) equals 349,716 from our earlier work under Carmichael’s totient function. Things get a little more complicated when we come across this section of the formula:
1/e mod
**this symbolizes modular inverse operation. It essentially means that instead of performing a standard modulo operation, we will be using the inverse. This is normally found with the Extended Euclidean Algorithm, but it’s a little outside of the scope of this article, so we will use an online calculator instead.
And it turns out that,
d =1/11 mod 349,716 = 254, 339
To perform this operation in the given online calculator, simply input e where it says Integer and λ(n) where it says Modulo.
Now that we have the value for d, we can decrypt messages that were encrypted with our public key using the following formula:
m = c^d mod n
substituting the real numbers,
m = 688,749^254,339 mod 701,111
now trying to take a number to the 254,339th power might be tricky for most normal calculators. Instead, u can use this online RSA decryption calculator.
In the calculator linked above, enter 701,111 where it says Supply Modulus: N,
254,399 where it says Decryption Key: D, and 688,749 where it says Cipher-text Message in numeric form.
Once you have entered the data, hit Decrypt, which will put the numbers through the decryption formula that was listed above. This will give you the original message in the box below. If you have done everything correctly, you should get an answer of 4, which was the original message that we encrypted with our public key.
Summary
If we summarize this process keeping the math aside,
The public key consists of the modulus n and a public exponent e
The private key consists of the modulus n and the private exponent.
Remember Alice and Bob, suppose Bob wants to send Alice an encrypted message m.
Alice’s computer generates her RSA keys by selecting two primes: p and q. then the modulus and e are generated. Alice’s computer then generates n and e values and make them visible to every one.
Bob obtains this RSA public key (n, e).
His message is just the number 4 and is encrypted into a cypher text c, as follows:
c = m^e mod n
When Alice receives Bob’s message, she decrypts it by using her RSA private key (d, n) as follows:
m = c^d mod n
we know that calculating d involves λ(n) : d = 1 / e mod λ(n)
and calculating λ(n) involves p and q : λ(n) = LCM (p − 1, q − 1)
p and q are only known by Alice, hence anyone else cannot find the value of d.
and hence anyone else cannot perform the operation of decrypting the cypher text.
That’s it in oversimplified simple terms.
Further details
Encryption systems have never been unbreakable. Instead, their security is based on the huge amount of time it would take for a classical computer to do the job. Modern encryption methods are specifically designed so that decoding them would take so long they are practically unbreakable.
RSA security relies on the computational difficulty of factoring large integers. As computing power increases and more efficient factoring algorithms are discovered, the ability to factor larger and larger numbers also increases.
Encryption strength is directly tied to key size, and doubling key length can deliver an exponential increase in strength, although it does impair performance. RSA keys are typically 1024- or 2048-bits long, but experts believe that 1024-bit keys are no longer fully secure against all attacks. The larger the number of bits in a key, the more difficult it is to crack through attacks such as brute-forcing and factoring.
This is why the government and some industries are moving to a minimum key length of 2048-bits. Also, a team of researchers which includes Adi Shamir, a co-inventor of RSA, has successfully created a 4096-bit RSA key using acoustic crypt-analysis already.
Barring an unforeseen breakthrough in quantum computing, info sec industry is about to hit some huge changes. The thing about quantum computers is that they have extreme capabilities of calculating such step heavy operations in less amount of time compared to the classical computers. Shore’s algorithm has proved to be able to factorize prime numbers with much ease when running on a quantum computer.
But still, a 2048 bit encryption would need a fully tolerating quantum computer with an estimated number of 20 million qbits, to break it. And that is many decades away because even the IBM’s quantum computer being operated today has only 50 qbits yet and even with that amount, fault tolerance is a huge problem to manage.
Plus, according to what we hear, people in academia have already composed other methods that can even sustain quantum machines aided attacks, even though they are not yet used in usual practices due to performance considerations. Quantum based encryption methods have also been developed already, to secure the communication channels by means of the laws of quantum physics, which are theoretically and absolutely unbreakable, unlike these breakable(somehow) methods.
Read about quantum communication methods that uses entanglement to find out more, if you are interested.