Page 3 of 3
Cracking the Code?
This might not seem very secure but consider the problem of someone wanting to crack the code.
They know the public key (e,n) and they know the code word – 14 and to recover the message they have to solve:
C=14=M^17 mod 33
That is, they have to find M such that it gives 14 when raised to the 17 power mod 33. This turns out to be a very difficult problem – unless you happen to know d.
In fact any solution to the problem is equivalent to knowing d. If you do know d then you can write down the solution at once:
M=C^d mod 33 = 14^13 mod 33 =
793714773254144 mod 33 =5
which is of course the number we first thought of as a letter “E”.
Now suppose that you don’t know d but want to find it to crack the code.
This should be easy as we all know that
e*d mod m=1
and this is reasonably easy to solve, but wait, we don’t know m!
If you recall the private key is (d,m) and all we know is (e,n). However surely knowing n we can work out m because n is just p*q and m is just (p-1)*(q-1). So all we have to do is find the prime factors of n, use these to construct m and finally solve to find d and again - all is lost!
This may sound complicated but to gain the information that has been encrypted it is worth it and after all factoring a number is easy – wrong.
Factoring a small number is easy.
For example, in our case we can find the prime factors of 33 by trial and error. All we have to do is test to see if each prime smaller than 33 divides 33. In fact most of us are so good at arithmetic that we immediately notice that 33=3*11 and so p=3 and q=11. From this we can recover the first part of the private key m=(p-1)*(q-1)=20 and from this we can find d as the solution to
e*d mod m = 17*d mod 20 =1
which is very easy.
So the security of the entire scheme depends on how hard it is to factor a number.
To see just how hard, try factoring 53357, which I promise is the product of two primes.
If you manage that try 62773913 and so on.
Public key cryptography generally uses very big primes which makes the task of recovering them very, very difficult. So it all works and it is all secure – unless you know how to factor numbers really fast!
Currently this is still a problem that is difficult although mathematicians are finding short cuts public key cryptography seems to be secure and quantum computing promises to solve the problem in just one weird quantum step - A Quantum Computer Finds Factors
Finally one last complication because public key cryptography is computationally intensive it generally isn't used to encode lots of data. Instead it is used to exchange keys which are then used in symmetric encryption methods. In this sense public key cryptography is the answer to the key exchange problem we mentioned earlier. That is you use public key cryptography to start the transaction and then shift to a good old symmetric key method once the keys have been exchanged.
Public key encryption is really used to send keys which are then used to send the real data