Page 2 of 3
Public key cryptography
Modern symmetric key cryptography works very well but it suffers from the problem of transporting the keys and keeping the keys secret. Imagine that you want to buy something from a website. If you want to send your credit card number using a symmetric cipher then either you have to send the website your key or it has to send you its.
Forget for a moment the transport problem which could presumably be solved by sending a letter, i.e. using the post, or by paying it a visit in person. If key transport were the only way to make things work even existing institutions like banks would take on the job of securely transporting keys – for a fee of course!
Even if you can transport keys there is still a problem – once the website has your key it can use it to encode information to be sent to you and decode information you send to it but it can also use it to decode any message you send using that key!
The key both locks and unlocks the message and it doesn’t matter whom the message was intended for. What this means is that you would need to set up a different key for every website you wanted to work with.
So many keys are bound to make the system less secure and error prone and it is lucky for us that there is an alternative.
Public key encryption seems so unlikely a process that you have to see it in action to believe that it works! The basic idea is that now we have two keys – a public key and a private key.
The public key can be freely handed out to anyone who wants it and it is used to code a message and send it to the destination.
The magic is that the coding procedure mixes up the message and the public key in such a way that even knowledge of the public key doesn’t help in the task of unmixing.
To unmix the public key and the message you need a second key – the private key – which is, of course, kept secret. Using the private key you can easily undo the mixing and retrieve the message.
Not only does the encryption process hide the original text in a way that cannot be undone by the public key even knowledge of the public key doesn’t give any clue as to what the private key, its unique counterpart, might be.
This is all very mysterious! How exactly does this work?
The whole thing relies on an idea called a "trapdoor" function. This is a function of the data that is very difficult to reverse - in other words the inverse function is much more difficult to compute than the function itself. However in some cases if you provide a tiny bit of extra information then finding the inverse function becomes easy.
For example, if I multiply two primes together (recall that a prime number is one that doesn’t have any factors – so 7 is prime as no integer exactly divides it but 9 isn’t because it is divisible by 3) e.g. 3 times 7 giving 21 then to compute the function all I need is simple multplication.
To perform the inverse operation I have to find the prime factors of 21 and this is more difficult and it gets much more difficult as the size of the numbers involved goes up. Essentially the only direct way of doing it is to try each of the primes in turn until you find one that divides the number exactly.
However if I tell you that one of the primes was 3 all you have to do is divide by three to recover the 7. The problem of prime factoring has a "trap door" that leads you straight to the answer if you know one of the primes involved.
There are a number of public key systems based on exactly this prime factor principel and one of the best known is the RSA cipher so lets take a look at this in detail.
To create the key you first start out by picking two large prime numbers.
Finding large primes isn’t too difficult but to keep the arithmetic simple let's pick small primes for our example: p=3 and q=11.
The product of 3 and 11 is 33 and this is the first part of our key
As well as the product of the primes we also use the product of one less than each of them, i.e.
as another part of a key.
Next we need another prime, d, in the interval [max(p,q)+1,n-1]. In our case the interval is [12,32] and we can pick d=13 as a suitable prime. That is
d=13 is a prime in the interval [max(p,q)+1,n-1]==[12,32]
This all sounds complicated but we are almost done. We just need one more number to complete the keys.
We need a value e such that
e*d=1 Mod m
If you need a refresher on the Mod function then see Mod function.
But put as simply as possible the n Mod m is the remainder when you divide n by m. Another way of think of this is to "clock arithmetic" and allow values to wrap round at m.
In this particular case we need to find a number e, an integer, that when you multiply by d and allow the result to wrap round at m you get the result 1.
For example, 4*2 Mod 7 = 8 Mod 7 = 1 Mod 7
.Modular arithmetic in action
There is a fairly simple well-known algorithm for working out modular inverses, as e in the formula above is called, so in practice you don't have to guess or spend hours working it out from scratch.
In our case the problem is to find an e such that
e*13 Mod 20 =1
and you can verify that e=17 gives the required result.
Now we have a lot of numbers and it is worth summarizing what they all are:
- From two primes p and q we compute
- We pick another prime d = 13 and work out e so that
e*d mod m =1
i.e. e=17 in this case
The two numbers e and n can be published as the public key (e,n) and d and m are keep secret as the private key (d,m).
If you want to send a coded message all you have to do is use:
C=(M^e) mod n
where M is the value that corresponds to the data C is the encrypted value and M^e means raise M to the power of e. Notice that to encode the value we use both parts of the public key e and n.
For example, the letter “E” is the fifth letter i.e. M=5 and our public key is (17,33) therefore the encrypted character is:
C=5^17 mod 33 = 762939453125 mod 33 =14
So to transmit an encrypted “E” we send a “14”.