pre-knowledge:
Every online bank transaction in the world, every secure webshop or website is using this algorithm! It is the most widely used algorithm in the world and a good example of encryption with prime numbers. It is called RSA Encryption. People often directly want to know what RSA is, and what the relationship is with public and private keys. I am going to show the idea of the public and private keys in this algorithm, but first the main idea of the algorithm:
step 1:
step 2:
step 3:
step 4:
step 5:
This algorithm is rediscovered by Rivest-Shamir-Adelman, therefore it is called (RSA). However, I like to give credits to the mathematician who first came up with this algorithm, Clifford Cocks.
So, why do need prime numbers?
Okay, the above information is just the idea. Finding a mathematical way of defining this algorithm is a more difficult task. Because: how to create a lock, in mathematical terms, that could be immediately opened by the key-owner and not by some hacker? In the previous example it is important to see:
This idea of sending some easy equations to the receiver and getting back some difficult equations, for everyone without a key, is essential. To establish this in mathematical terms, Clifford Cocks invented an algorithm that is hard to compute one way and easy in the other direction. How can you do that? Cocks had a smart solution in which he used factorization and multiplication. You could say that factorization is the same thing as undoing the multiplication.
What Cocks used was the fact that it takes more computing time to do factorizations for large number as multiplications. For example, multiplying a number with over 200 digits takes less than a second using a normal computer. However, the factorization of this huge outcome takes thousands of years (in 2020).
With this information in mind, Cocks invented a super-smart algorithm, the trapdoor function. Why its called like this and other random facts can be found on Wikipedia. For now:
1) The output of the trapdoor function = Z
2) AND WHY SHOULD WE USE PRIME NUMBERS!?
Okay, prime numbers…
Cocks used one of Euler’s functions about prime numbers (the so-called phi-function). With this function, Cocks was able to use one of the properties of the prime numbers to make his encryption work.
how does this work then?
Different from the story about locks we have now, 2 keys. Why? Because it is necessary, because we now doing this problem with a mathematical approach. But the idea remains the same! So, to give a small example, take 2 super large prime numbers, let’s call them P1 and P2, these 2 variables are set as the private key. We multiply them:
P1 * P2 = X
X is then an extremely large number. This X is part of the public key. For sake of simplicity, we will have a more simple version of the private key in this case.
private key: P1 and P2 (prime numbers)
public key: X
how the RSA Process works
step 1:
step 2:
step 3:
step 4:
in the case of a hacker
?:
?:
?:
Cool, right? The hacker has no chance of receiving the actual message, right?…
There is one side note. Because there is a relation between the public and the private key. As shown, the X variable in the public key is made of:
=> the P1 and P2 variables in the private key, so there should exist a kind of relation between the public and private key right? The answer is true, and theoretically, it is possible to crack the code. So, what was the reason again that we can’t undo that multiplication (= same as doing a factorization)? Well, because a factorization for a number that is that big, it will cost more than a thousand years. So there is (at this point in time, 2020) no way you can crack this algorithm!
Okay, I didn’t say exactly how you could calculate this RSA algorithm. If you want to know how this is done, check these 2 videos. The videos will exactly explain all the details on how to compute the RSA algorithm: