Notes on Public Key Cryptography

Prepared by Dr C. H. Lindsey

4th July 2000

Public Key Encryption explained.

Alice wishes to receive encrypted messages.
So she creates a self-locking box  and a key 

Anybody can shut it, but she has the only key to open it. The box is known as her "Public Encryption Key", and she distributes copies of it to all her friends. The key is known as her "Private Encryption Key", and she keeps it secure.

Bob wishes to send an encrypted message to Alice 
So he obtains one of Alice's Public boxes, and puts his message inside it 

And shuts it (it gives a nice click). 

He send it to Alice  Who opens it with her key 
And reads the message 

Lots of people send messages to Alice using copies of her box. So if her one and only Private Key should fall into the wrong hands, all her messages from all the people who write to her would be at risk from whoever had stolen it.

Note that even Bob cannot read his own message once it has been shut inside the box, so if the message is intercepted (lawfully, we hope) and the Police want to serve a Section 47 notice to decrypt the message, it is no use serving it on Bob (even though he may be the party under suspicion). They have to serve it on Alice.

Session Keys

But, actually, the example above was simplified. What really happens in this:

Bob creates a brand new temporary conventional box  with its own unique key 

He puts his message in the temporary box  and locks it with his key 

Then he obtains one of Alice's Public boxes  puts his key inside it 
and locks it  (with a nice click again)

He sends both boxes to Alice 

Who opens the first box with her key   and uses the key inside it to unlock the second box  so that she can read the message 

N.B. Each message that is sent to Alice has its unique Session Key, so disclosure of a Session Key in response to a Section 47 notice has not compromised any of the other messages sent to Alice, whether from Bob or from anyone else. The Government has confirmed that disclosure of a Session Key (as opposed to a Private Key) will always be sufficient to satisfy the requirements of a Section 47 notice.

Digital Signatures

Bob wants to be able to sign his messages, so that his correspondents can be sure that messages indeed came from him, and that they have not been tampered with.

So he creates a seal  from which he can make lots of wax images 

The seal is his "Private Signature Key", which he keeps secure so that only he can make the wax images. He distributes photographs of the wax image (his "Public Signature Key") so that everybody can recognise it.

Bob wishes to sign his message to Alice 

So he puts it in a transparent box  and seals it with his seal  and sends it to Alice.

Alice receives the message  She compares the seal with Bob's Public Key (now she knows it came from Bob), she checks that the seal is intact (she knows it has not been tampered with) and she reads the message (the box being transparent).

N.B. It is technically possible to use a Signature pair of keys (Public + Private Signature Key) as an Encryption pair of keys (Public + Private Encryption Key), though best practice is to generate separate key pairs for the two purposes.

Keeping Private Keys Secure

To keep his Private Signature Key secure, Bob locks it away in a box whose key  is actually a "passphrase" that Bob carries in his head. So what Bob actually keeps is  One would expect Alice to protect her Private Encryption Key in a similar manner.

Now the Bill specifically exempts (in S47(9)(a)) Private Signature Keys, such as  from being demanded under Section 47 notices. BUT hold on! The Bill also says that anything hidden in a non-transparent box is "protected information" (S54(1)), and anything that is protected data can be subject to a Section 47 notice (S47(1)) requiring disclosure of its key. So, although the authorities cannot ask directly for  if they come across  (by lawful seizure of Bob's computer, for example) then they can demand to see contrary to the clear intent of S47(9)(a). Amendment #157 (Committee Stage marshalled list) was intended to close this loophole.

Session key loophole

There used to be a similar loophole regarding Session keys. Recall that Bob sent to Alice the combination  one consequence of which is that Alice, when served with a Section 47 notice, can choose to disclose just the Session Key 

BUT if the authorities hold  they can say "look, that is protected information" and, if the notice is one of those "special" ones (S49(2)(a)), they can then demand to see the key that opens it, namely  which could cause extreme problems for Alice.

However, the government rewording of S47(2)(d) has now resolved this problem.

Keys for large Corporations

Large Corporations have particular problems with those Private Keys (both for Signature and Encryption) which may have to be used by many of their employees. It is a bad idea just to protect them with passphrases, because there are just too many people who would need to know those passphrases, and complications would arise when one of those people left the company, and so on.

Therefore, a large company might well keep all its valuable Private Keys in a tamper-proof iron box, and insist that all signatures and decryptions were only ever performed inside that iron box. The problem then reduces to establishing means whereby the iron box knows who is allowed to use which keys and for what purposes.

So suppose, this time, that Alice plc is a large Bank, and Bob is a senior manager with responsibility for handling electronic funds transfers. Fred is one of the humble clerks who actually processes such transfers as they come in. So Bob constructs a chit  which probably says something like "Fred is entitled to use the iron box to decrypt electronic cheques with values not exceeding £100,000; this authority expires on 31st July 2000" (but probably in some obscure notation understood by the software in the box, rather than in plain English). Bob signs the chit with his Private Signature Key  and gives it to Fred: 

Now Fred receives some encrypted message addressed to Alice plc  (there was probably a Session Key involved as well, but I haven't bothered to show it). So Fred presents the message, plus the signed chit  to the iron box.

The iron box, which knows Bob's Public Signature Key  and, of course, also knows the Private Encryption Key of Alice plc  then checks the signature on the chit and, knowing that Bob is entitled to authorise such things, proceeds to decrypt the message, and returns  to Fred (well, that particular one didn't look much like a cheque, but you get the idea).

Now I have shown this example to illustrate the complex ways in which Public Key technology can be used. In fact, it would be more complex than I have shown. How, for example, did the iron box know what sort of decryptions Bob was allowed to authorise, and what happens when Bob leaves the company? So there are probably other chits around the system signed by the directors of the company  (yes, some chits may require several signatures) saying who is allowed to authorise what.

BUT now there is another loophole. Anybody who has Bob's Private Signature Key  can write a chit authorising himself to have a message decrypted by the iron box. Therefore, according to the present definitions in S54,   is a key which "facilitates the putting of the data into an intelligible form", the data here being  and hence that key can then be subject to a Section 47 notice. Amendments #180 and #181 (Committee Stage marshalled list) were intended to close this loophole.

Underlying technology

Of course, it is not really done with wooden boxes, and string and sealing wax. There is some complex mathematics underlying this technology. Suffice it to say that, in the scheme most widely adopted (the RSA method), and simplifying things ever so slightly, a Private Key (whether for Encryption or Signature) consists of just two very large prime numbers (each about 160 digits long) and the matching Public Key is those two numbers multiplied together. The point is that, whereas multiplying two large numbers together is quite easy (if tedious), if you are given just the public key (320 digits long) then there is no practical way for you to find out its two factors, and without doing that you cannot break the code. And obviously, passing Public Keys around is just a matter of copying and distributing large numbers, rather than the copying and distributing of self-locking boxes that I described.

As for the keys used for Session Keys, they are just numbers around 40 digits long (they don't have to be prime, so any number will do).