Mathematical Foundations for Cryptography: Part II

In part I of this series, we introduced the idea of a cipher for encrypting and decrypting text between two entities. We now continue with part II, where we will learn how two different parties can establish a shared secret.

PART II: A SHARED SECRET

Mathematical tools: The modulus and the power

The first mathematical tool we are going to use is called the modulus function. To understand the modulus function, let’s look at an example. We want to know the value for 29 modulus 8, or 29 mod 8 for short (or 29%8 for even shorter). The modulus is the remainder after dividing the first number (29) by the second number (8). So 29/8 = 3 with a remainder of 5. We don’t care about the 3; we care about the 5. That is the modulus: 29 mod 8 = 5.

Some more examples:

• 7 mod 2 = 1; 7/2 = 3 with remainder of 1. We just care about the 1
• 54 mod 20 = 14; 54/20 = 2 with remainder of 14. We just care about the 14

Note that the result must always be less than the second number.

If the first number evenly divides the second, then the result is 0.

• 14 mod 7 = 0
• 6 mod 2 = 0

If the first number is less than the second number, the result is simply that first number.

• 3 mod 10 = 3
• 56 mod 948 = 56

We also need to make sure we understand powers. For example, 2 to the power 5 means we multiply 2 * 2 * 2 * 2 * 2 = 32. We multiply it 5 times: 2⁵ = 32

Another example: 3⁶ = 3 * 3 * 3 * 3 * 3 * 3 = 729

Finally, 1 to the power of any number is always 1: 1⁷⁸ = 1

We are going to use both of these mathematical tools to come up with a shared secret between Alpha and Beta.

Key Exchange

First of all, Alpha and Beta are going to share some information publicly (they have no other choice). Alpha is going to write the following on the whiteboard:

Alpha: Hey Beta, Diffie-Hellman: 3ˣ mod 17

Beta (and everyone else) will see this and understand what is meant, and we will also understand very soon.

Alpha and Beta will now choose their own private numbers. They will not share this number with anyone else, not even each other. Let’s suppose Alpha chooses 4, and Beta chooses 2. They will now plug this number into the “x” on the equation that they shared publicly (3ˣ mod 17). The “x” is simply a placeholder for another possible value.

• Alpha chose x = 4, and she will get: 3⁴ mod 17
• First she needs to calculate 3⁴ = 3 * 3 * 3 * 3 = 81
• Then she takes 81 mod 17 = ?
• 81 divides 17 four times with a remainder of 13 (4*17 + 13 = 81), so the result is 13: 3⁴ mod 17 = 13
• Beta does the same thing with his private number: 3² mod 17 = 9

They will then share these results publicly, while still keeping their private numbers private. So Alpha will write 13 on the whiteboard, and Beta will write 9.

Now Alpha is going to take the number that Beta shared (9) and “mix” it with her private number of 4 in the following way: 9⁴ mod 17 = 6561 mod 17 = 16

Likewise, Beta is going to take the number that Alpha shared (13) and mix it in with his private number (2) in the same way: 13² mod 17 = 169 mod 17 = 16.

Alpha and Beta both get the number 16. This is a shared key! Is it a coincidence? Not at all! Let’s see why:

Beta shared the number 9, which was generated from his private number of 2 and the formula of 3ˣ mod 17 that they shared: 3² mod 17 = 9.

So 3² = 9, and 9 = 3². When Alpha mixed that in with her own private number 4, she did: 9⁴ mod 17. Since 9 = 3², this is the same as doing (3²)⁴— we replaced the 9 with 3². The mathematical rule for when you have powers to other powers is that you can simply multiply them together, so really Alpha had 3⁸ mod 17 = 16.

Conversely, Alpha gave Beta the number 13, which was generated from her private number 4: 3⁴ mod 17 = 13. So when Beta mixes that with his own private number of 2, it was the same as doing: (3⁴)² mod 17, which is the same as 3⁸ mod 17, which is exactly what we saw with Alpha.

So Alpha and Beta were able to get the shared number of 16 using this method. They never once shared their private numbers, only the results that got generated from those numbers. This is called a Diffie-Hellman Key Exchange. Recall that Alpha wrote the following on the whiteboard:

Alpha: Hey Beta, Diffie-Hellman: 3ˣ mod 17

Beta knew to follow the steps that we just took in order to generate a shared key with Alpha. Now that they have a shared key that no one else can see, they can use this as a polyalphabetic cipher with that shared key as follows.

Alpha writes the following on her whiteboard:

Alpha: N E S K B R O G N K J Y B R J I F

Since Beta has the shared key of 16, he can work backwards to decrypt the ciphertext back into the original message. Here is a diagram of the process:

Cracking the Code

Technically this works to create a shared secret, but it has a severe practical drawback. Let’s consider it from our attacker, Omega’s, point of view. She sees the following information exchanged on the whiteboard:

Alpha: Hey Beta, Diffie-Hellman: 3ˣ mod 17

Beta: Ok Alpha

Alpha: 13

Beta: 9

Alpha: N E S K B R O G N K J Y B R J I F

While Omega may not be able to figure out the key of 16 right off the bat, she has two avenues to cracking it. First she can try to crack it by looking for patterns in the ciphertext. It’s a polyalphabetic cipher that only has length 2, and the shorter the cipher key, the less time it takes to crack. Alternatively, she could use the information they shared publicly to try to crack the key of 16. She knows the formula they used: 3ˣ mod 17. She knows that Alpha picked some number for x that resulted in 3ˣ mod 17 = 13. So now all she needs to do is cycle through values for x until she gets the result of 13:

• She tries 1: 3¹ mod 17 = 3 — nope
• She tries 2: 3² mod 17 = 9 — nope
• She tries 3: 3³ mod 17 = 10 — nope
• She tries 4: 3⁴ mod 17 = 13 — bingo!

She now knows Alpha picked a key of 4. She takes the 9 that Beta publicly shared and gets the key: 9⁴ mod 17 = 16. The code is cracked. She can look at any of the encrypted text shared between Alpha and Beta, and easily decrypt it.

So why did we spend all that time learning about the modulus when Omega was able to crack it after 4 simple calculations? The important thing to note here is that Omega needed to use trial and error . She tested 1, and it didn’t work, then she tested 2, 3, and 4. In the worst case, she would’ve had to test all the way up to 16, since we used mod 17, which still isn’t too bad.

Bigger Numbers

But what if instead of mod 17, Alpha and Beta chose a much higher number, say 3659. So Alpha writes:

Alpha: Hey Beta, Diffie-Hellman: 3ˣ mod 3659

Beta agrees and they choose their private numbers:

• Alpha chooses 28: 3²⁸ mod 3659 = 2233. The value 2233 is shared publicly
• Beta chooses 11: 3¹¹ mod 3659 = 1515. The value 1515 is shared publicly
• Alpha mixes Beta’s public portion with her own private number: 1515²⁸ mod 3659 = 1576
• Beta mixes Alpha’s public portion with his own private number: 2233¹¹ mod 3659 = 1576

Once again, Alpha and Beta have established a shared key, which they can now use with a polyalphabetic cipher. If Omega wants to crack it, she needs to play the same game as before — trial and error. She must iterate from 1 to 3658, looking for a number that gives 3ˣ mod 3659 = 28. This could take an extremely long time, even for an expert mathematician such as herself. She realizes it would take way too long, so she doesn’t even bother. Alpha and Beta now have a successful encryption system. This is called “Symmetric” encryption, since they use the same key (1–5–7–6) to encrypt and decrypt the messages.

This method could work quite well in our microcosm, but if Omega really wants to intercept what Alpha and Beta are communicating, she has one more trick up her sleeve. Recall one of the important facts we acknowledged about this scenario: The members are all wearing big cloaks that cover their bodies and mask their faces. It is impossible to tell who is who, unless they write their name on the board, as a sort of signature.

But what if Omega suspected that Alpha and Beta wanted to talk, and decided to pose as Beta by simply signing her name as Beta on everything she writes. Being bound by his vow, Beta has no way to prove that he is the real Beta. All he can really do is write “No I’m Beta” on the whiteboard, and Alpha must guess who is the true Beta. If Alpha guesses wrong, then all the other measures taken to encrypt the message are meaningless! The messages can be encrypted, but the communication is happening with the wrong person. We’re missing authentication. Once again, we must reach even further into our mathematical toolkit to solve this problem. This is where we will begin in the 3rd and final part of the series.