Why rsa works

Now let us explain the RSA algorithm with an example Nobody other than a browser will decode data because it is asymmetrical, except through a third party has a browser public key.

With the RSA algorithm examples, the principle of the RSA algorithm explained that the factoring of a big integer is difficult. There are two numbers in the public key where there are two large main numbers multiplied by one. Also, from the same two prime numbers comes a private key. Therefore the private key is compromised if anyone can factor in the high number.

Thus, the encryption strength depends solely on the key size, and whether the key size is double or triple, the encryption strength increases exponentially.

RSA keys will typically be or bits long, but experts think bit keys will be broken quickly. The application of the RSA algorithm derives its security from factoring the large integral elements, which are the product of two large numbers. Still, the calculation of the initial primary numbers from the sum or variables is complicated because the time it takes even using supercomputers is the drawback of the RSA algorithm. The most problematic feature of RSA cryptography is the public and private key generation algorithm.

They primarily test algorithm generated using the Rabin Miller test, which are p and q, the two large numbers. A module, n, is computed by multiplying p and q. This number is used for a private and public key and provides the link between them is called the key length, and the length of the key is typically expressed in bits.

The public key is the n modulus and the e-public representative, which are typically set to , as the number of people is not too high. The MIT-based academics made their breakthrough after a Passover party in After a night of drinking, Rivest went home, but instead of sleeping, he spent the evening feverishly writing a paper that formalized his idea for the necessary one-way function. The following is going to be a bit of a simplification, because too many readers have probably been scarred by their high school math teacher.

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 your head around before we can explain how it all fits together. RSA encryption works under the premise that the algorithm is easy to compute in one direction, but almost impossible in reverse. As an example, if you were told that , is a product of two prime numbers, would you be able to figure out what those two numbers are?

But if we flip things around, it becomes much easier. If you were bored enough, you would have been able to whip out your phone or maybe calculate it in your head to discover that the answer is the previously mentioned , This and are the prime numbers that answer our first question, which shows us that certain equations can be easy to figure out one way, but seemingly impossible in reverse.

Another interesting aspect of 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 , is the result of multiplied by another prime number, you can figure it out the other prime with the following equation:. Since the relationship between these numbers is simple to compute in one direction, but incredibly hard in reverse, the equation 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, but in bit RSA, they would come together to make keys that are digits long. To help you visualize it, a key would be a number of this size:. The trap door functions mentioned above form the basis for how public and private-key encryption schemes work.

Their properties allow public keys to be shared without endangering the message or revealing the private key. They also allow data to be encrypted with one key in a way that can only be decrypted by the other key from the pair.

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.

The prime numbers in RSA need to be very large, and also relatively far apart. Numbers that are small or closer together are much easier to crack. Despite this, our example will use smaller numbers to make things easier to follow and compute. The next step is to discover the modulus n , using the following formula:. You can skip over this part and just trust that the math works, otherwise stick with us for a few more calculations.

Everything will be explained in as much detail as possible to help you get your head around the basics. There are a few different ways to figure this out, but the easiest is to trust an online calculator to do the equation for you.

Under RSA, public keys are made up of a prime number e , as well as modulus n we will explain what modulus means in a few paragraphs. In practice, e is generally set at 65, , because when much larger numbers are chosen randomly, it makes encryption much less efficient.

Our final encrypted data is called the ciphertext c. We derive it from our plaintext message m , by applying the public key with the following formula:. As we mentioned, e mod n is the public key.

We have already devised e and we know n as well. The only thing we need to explain is mod. For example:. Back to our equation. Again, to make the modulo operation easy, we will be using an online calculator , but you are welcome to figure it out for yourself.

By entering 4,, into the online calculator, it gives us:. Therefore when we use RSA to encrypt our message, 4 , with our public key, it gives us the ciphertext of , We had a message of 4 , which we wanted to keep secret.

We applied a public key to it, which gave us the encrypted result of , Now that it is encrypted, we can securely send the number , 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. In RSA encryption, once data or a message has been turned into ciphertext with a public key, it can only be decrypted by the private key from the same key pair. Private keys are comprised of d and n. We already know n, and the following equation is used to find d :.

In the Generating the public key section above, we already decided that in our example, e would equal Things get a little more complicated when we come across this section of the formula:. This essentially means that instead of performing a standard modulo operation, we will be using the inverse instead. If you have done it correctly, you should get a result where:. Now that we have the value for d , we can decrypt messages that were encrypted with our public key using the following formula:.

We can now go back to the ciphertext that we encrypted under the Generating the private key section. When we encrypted the message with the public key, it gave us a value for c of , From above, we know that d equals , We also know that n equals , This gives us:. As you may have noticed, trying to take a number to the ,th power might be a little bit much for most normal calculators.

Instead, we will be using an online RSA decryption calculator. If you wanted to do use another method, you would apply the powers as you normally would and perform the modulus operation in the same way as we did in the Generating the public key section.

In the calculator linked above, enter , where it says Supply Modulus: N , , where it says Decryption Key: D , and , where it says Ciphertext Message in numeric form , as shown below:.

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.

The above sections should give you a reasonable grasp of how the math behind public key encryption works. In the steps listed above, we have shown how two entities can securely communicate without having previously shared a code beforehand. First, they each need to set up their own key pairs and share the public key with one another.

The two entities need to keep their private keys secret in order for their communications to remain secure. Once the sender has the public key of their recipient, they can use it to encrypt the data that they want to keep secure.

Once it has been encrypted with a public key, it can only be decrypted by the private key from the same key pair. This is due to the properties of trap door functions that we mentioned above.

This statement is not true. In RSA, both the public and the private keys will encrypt a message. If that message is to be decrypted, then the opposite key that was used to encrypt it must be used to decrypt it. Underlying this statement is this fundamental equation:. Multiplication is commutative, which means it can happen in any order. Why is this important? I will give a correct and more formal proof below L6 , but for the sake of what follows, consider these arguments:.

With respect to the public and private keys, when carrying out a RSA operation either encryption or decryption , all that really happens is that the message is raised to an exponent value of the key. That is, decrypting a message with the private key that was encrypted with the public key is the same as decrypting a message with the public key that was encrypted with the private key.

This can be easily shown:. I have bold-ed the crucial part of the math above, namely the comutative property of the exponent. The math above can be stated in English like so:. This may seem simple and obvious when reading, but it is the reason behind RSA's two atomic uses:. It is the second use in my opinion that makes RSA so useful.

Things like electronic voting , digital signatures , mix nets etc become possible because of this. This is not to play down the importance of the first use, which is critical for things like SSL. It is not only fundamental to RSA, but to any encryption atomic. In fact, I would say that the first thing a person would have to prove if they invent a new cryptographic algorithm is that it conforms to the correctness equation.

Helpful hint : I would advise the reader who is serious about this topic to get a pen and paper and work through the below math as I present it.