Coding - Encryption
8.4. The key distribution problem

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).

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.

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.

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.

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.

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).

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 $n$ ("Number of digits"), we need to write $n$ rows. For each of those $n$ rows, we will need to do around $n$ multiplications. That gives us $n \times n$ little multiplications. We need to add the $n$ 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 $O(n^2)$ algorithm, where $n$ 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 $O(10^n)$ 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!

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.