CSFG
English Deutsch Beta Español Beta język polski (2.6.0)
Chapters Curriculum Guides Appendices

Coding - Encryption
8.4. The key distribution problem

Coding - Encryption

  • 8.1. What's the big picture?
  • 8.2. Substitution ciphers
  • 8.3. Cryptosystems used in practice
  • 8.4. The key distribution problem
    • Public key systems
  • 8.5. Storing passwords securely
  • 8.6. The whole story!
  • 8.7. Further reading
Who are Alice, Bob, and Eve? Curiosity

When describing an encryption scenario, cryptographers often use the fictitious characters "Alice" and "Bob", with a message being sent from Alice to Bob (A to B). We always assume that someone is eavesdropping on the conversation (in fact, if you're using a wireless connection, it's trivial to pick up the transmissions between Alice and Bob as long as you're in reach of the wireless network that one of them is using). The fictitious name for the eavesdropper is usually Eve (E).

A xkcd comic on protocols
Source

There are several other characters used to describe activities around encryption protocols: for example Mallory (a malicious attacker) and Trudy (an intruder). Wikipedia has a list of Alice and Bob's friends.

If Alice is sending an encrypted message to Bob, this raises an interesting problem in encryption. The ciphertext itself can safely be sent across an "unsafe" network (one that Eve is listening on), but the key cannot. How can Alice get the key to Bob? Remember the key is the thing that tells Bob how to convert the ciphertext back to plaintext. So Alice can’t include it in the encrypted message, because then Bob would be unable to access it. Alice can’t just include it as plaintext either, because then Eve will be able to get ahold of it and use it to decrypt any messages that come through using it. You might ask why Alice doesn’t just encrypt the key using a different encryption scheme, but then how will Bob know the new key? Alice would need to tell Bob the key that was used to encrypt it... and so on... this idea is definitely out!

Remember that Alice and Bob might be in different countries, and can only communicate through the internet. This also rules out Alice simply passing Bob the key in person.

Are we being paranoid? Curiosity

In computer security we tend to assume that Eve, the eavesdropper, can read every message between Alice and Bob. This sounds like an inordinate level of wire tapping, but what about wireless systems? If you're using wireless (or a mobile phone), then all your data is being broadcast, and can be picked up by any wireless receiver in the vicinity. In fact, if another person in the room is also using wireless, their computer is already picking up everything being transmitted by your computer, and has to go to some trouble to ignore it.

Even in a wired connection, data is passed from one network node to another, stored on computers inbetween. Chances are that everyone who operates those computers is trustworthy, but probably don't even know which companies have handled your data in the last 24 hours, let alone whether every one of their employees can be trusted.

So assuming that somone can observe all the bits being transmitted and received from your computer is pretty reasonable.

Distributing keys physically is very expensive, and up to the 1970s large sums of money were spent physically sending keys internationally. Systems like this are call symmetric encryption, because Alice and Bob both need an identical copy of the key. The breakthrough was the realisation that you could make a system that used different keys for encoding and decoding. We will look further at this in the next section.

Some additional viewing Curiosity

Simon Singh's video gives a good explanation of key distribution.

Additionally, there's a video illustrating how public key systems work using a padlock analogy.

8.4.1.

Public key systems

One of the remarkable discoveries in computer science in the 1970s was a method called public key encryption, where it's fine to tell everyone what the key is to encrypt any messages, but you need a special private key to decrypt it. Because Alice and Bob use different keys, this is called an asymmetric encryption system.

It's like giving out padlocks to all your friends, so anyone can lock a box and send it to you, but if you have the only (private) key, then you are the only person who can open the boxes. Once your friend locks a box, even they can't unlock it. It's really easy to distribute the padlocks. Public keys are the same – you can make them completely public – often people put them on their website or attach them to all emails they send. That's quite different to having to hire a security firm to deliver them to your colleagues.

Public key encryption is very heavily used for online commerce (such as internet banking and credit card payment) because your computer can set up a connection with the business or bank automatically using a public key system without you having to get together in advance to set up a key. Public key systems are generally slower than symmetric systems, so the public key system is often used to then send a new key for a symmetric system just once per session, and the symmetric key can be used from then on with a faster symmetric encryption system.

A very popular public key cryptography system is RSA. For this section on public key systems, we will use RSA as an example.

Generating the encryption and decryption keys

Firstly, you will need to generate a pair of keys using the key generator interactive. You should keep the private key secret, and publicly announce the public key so that your friends can send you messages (e.g. put it on the whiteboard, or email it to some friends). Make sure you save your keys somewhere so you don’t forget them – a text file would be best.

RSA Key Generator

Key Size
Format Scheme

Warning: Keys larger than 512 bits may take longer than a second to create.

Public Key:
Private Key:
What do those characters mean? Curiosity

When you generate a key in the components format, the interactive gives you five variables required for the RSA algorithm. We won't go into the algorithm itself, nor how these values are calculated. But, if you are curious, these are what the variables represent:

  • e: Public key exponent.
  • n: The product of two large prime numbers, p & q.
  • p: Large prime number #1.
  • q: Large prime number #2.
  • d: Private key exponent.

When you generate a key in one of the PKCS (Public Key Cryptography Standards) formats, the interactive gives you the same keys in a format that is nicer for computers to use. These keys are what get passed around in actual RSA cryptography, but are a lot harder to understand just by looking at them.

Remember that all of this data is just stored in binary (base2). We use hexadecimal (base16) to display the components because it is a common way of presenting numbers. Base64 is the accepted way to display PKCS keys, chosen because it is more space-saving than base16. If we tried to go higher (for example to base128 ASCII), we would encounter characters with no visual representation, such as space or tab, which are much harder to interpret as text.

You can find out more about the algorithm and variables used on Wikipedia.

Encrypting messages with the public key

This next interactive is the encrypter, and it is used to encrypt messages with your public key. Your friends should use this to encrypt messages for you.

RSA Encryption

Mode:
Key Format Scheme:
Padding:

Warning: Do not trust this interactive for any real encryption purposes.

Key:
Plain Message:

Encrypted Message:

To ensure you understand, try encrypting a short message with your public key. In the next section, there is an interactive that you can then use to decrypt the message with your private key.

Padding? Curiosity

You may have noticed "padding" as an option in the interactive. Padding is extra data used to stop known plaintext attacks.

With padding, the same plaintext encrypted with the same public key can result in a different ciphertext. So a hacker with access to the plaintext and ciphertext can't guess values used in the cipher by just comparing their new encryptions to the original.

It is not important at this level, but still worth mentioning because it is another layer of security applied in real-world cryptography. You can read more about various types of padding on Wikipedia.

Decrypting messages with the private key

Finally, this interactive is the decrypter. It is used to decrypt messages that were encrypted with your public key. In order to decrypt the messages, you will need your private key.

RSA Decryption

Mode:
Key Format Scheme:

Warning: Do not trust this interactive for any real decryption purposes.

Key:
Encrypted Message:

Decrypted Message:

Despite even your enemies knowing your public key (as you publicly announced it), they cannot use it to decrypt your messages which were encrypted using the public key. You are the only one who can decrypt messages, as that requires the private key which hopefully you are the only one who has access to.

Note that this interactive’s implementation of RSA is just for demonstrating the concepts here and is not quite the same as the implementations used in live encryption systems.

Can we reverse the RSA calculations? Curiosity

If you were asked to multiply the following two big prime numbers, you might find it a bit tiring to do by hand (although it is definitely achievable), and you could get an answer in a fraction of a second using a computer.

97394932817749829874327374574392098938789384897239489848732984239898983986969870902045828438234520989483483889389687489677903899
34983724732345498523673948934032028984850938689489896586772739002430884920489508348988329829389860884285043580020020020348508591

If on the other hand you were asked which two prime numbers were multiplied to get the following big number, you’d have a lot more trouble! (If you do find the answer, let us know! We’d be very interested to hear about it!)

3944604857329435839271430640488525351249090163937027434471421629606310815805347209533599007494460218504338388671352356418243687636083829002413783556850951365164889819793107893590524915235738706932817035504589460835204107542076784924507795112716034134062407

Creating an RSA code involves doing the multiplication above, which is easy for computers. If we could solve the second problem and find the multiples for a big number, we'd be able to crack an RSA code. However, no one knows a fast way to do that. This is called a "trapdoor" function – it's easy to go into the trapdoor (multiply two numbers), but it's pretty much impossible to get back out (find the two factors).

So why is it that despite these two problems being similar, one of them is "easy" and the other one is "hard"? Well, it comes down to the algorithms we have to solve each of the problems.

You have probably done long multiplication in school by making one line for each digit in the second number and then adding all the rows together. We can analyse the speed of this algorithm, much like we did in the algorithms chapter for sorting and searching. Assuming that each of the two numbers has the same number of digits, which we will call ("Number of digits"), we need to write rows. For each of those rows, we will need to do around multiplications. That gives us little multiplications. We need to add the rows together at the end as well, but that doesn’t take long so lets ignore that part. We have determined that the number of small multiplications needed to multiply two big numbers is approximately the square of the number of digits. So for two numbers with 1000 digits, that’s 1,000,000 little multiplication operations. A computer can do that in less than a second! If you know about Big-O notation, this is an algorithm, where is the number of digits. Note that some slightly better algorithms have been designed, but this estimate is good enough for our purposes.

For the second problem, we’d need an algorithm that could find the two numbers that were multiplied together. You might initially say, why can’t we just reverse the multiplication? The reverse of multiplication is division, so can’t we just divide to get the two numbers? It’s a good idea, but it won’t work. For division we need to know the big number, and one of the small numbers we want to divide into it, and that will give us the other small number. But in this case, we only know the big number. So it isn’t a straightforward long division problem at all! It turns out that there is no known fast algorithm to solve the problem. One way is to just try dividing by every number that is less than the number (well, we only need to go up to the square root, but that doesn’t help much!). There are billions of billions of billions of numbers we need to check. Even a computer that could check 1 billion possibilities a second isn’t going to help us much with this! If you know about Big-O notation, this is an algorithm, where n is the number of digits – even small numbers of digits are just too much to deal with! There are slightly better solutions, but none of them shave off enough time to actually be useful for problems of the size of the one above!

The chapter on complexity and tractability looks at more computer science problems that are surprisingly challenging to solve. If you found this stuff interesting, do read about complexity and tractability when you are finished here!

Encrypting with the private key instead of the public key — digital signatures! Curiosity

In order to encrypt a message, the public key is used. In order to decrypt it, the corresponding private key must be used. But what would happen if the message was encrypted using the private key? Could you then decrypt it with the public key?

Initially this might sound like a pointless thing to do – why would you encrypt a message that can be decrypted using a key that everybody in the world can access!?! It turns out that indeed, encrypting a message with the private key and then decrypting it with the public key works, and it has a very useful application.

The only person who is able to encrypt the message using the private key is the person who owns the private key. The public key will only decrypt the message if the private key that was used to encrypt it actually is the public key’s corresponding private key. If the message can’t be decrypted, then it could not have been encrypted with that private key. This allows the sender to prove that the message actually is from them, and is known as a digital signature.

You could check that someone is the authentic private key holder by giving them a phrase to encrypt with their private key. You then decrypt it with the public key to check that they were able to encrypt the phrase you gave them.

This has the same function as a physical signature, but is more reliable because it is essentially impossible to forge. Some email systems use this so that you can be sure an email came from the person who claims to be sending it.

Previous:
Cryptosystems used in practice
Next:
Storing passwords securely

Looking for something for primary schools? Check out CS Unplugged.

The Computer Science Field Guide is an online interactive resource for high school students learning about computer science.

Useful Links

  • About
  • Chapters
  • Interactives
  • Curriculum Guides

Community

  • Twitter
  • YouTube
  • GitHub

Help

  • Search
  • Glossary
  • Feedback

Switch to teacher mode

English | Deutsch | Español | język polski (2.6.0)

The Computer Science Field Guide material is open source on GitHub, and this website's content is shared under a Creative Commons Attribution-ShareAlike 4.0 International license. The Computer Science Field Guide is a project by the Computer Science Education Research Group at the University of Canterbury, New Zealand. Icons provided generously by icons8.

3.12.6

This definition is not available in English, sorry!