Quick quiz, what do the following sequence of numbers have in common: 19, 3763, 31, and 67? The answer is, they are all the same! Ok, well obviously that’s not strictly true. More correctly, these numbers all represent the same value in modular arithmetic (7 modulo 12). When you take each of these numbers and divide them by 12, you end up with a remainder of 7 (19 / 12 = 1 remainder 7, 3763 / 12 = 313 remainder 7, 31 / 12 = 2 remainder 7, and 67 / 12 = 5 remainder 7).
Another simple way to think of modular arithmetic is clock arithmetic. Consider the problem when you are looking at an analog 12 hour clock. You need to figure out what time it is going to be 7 hours from now. If the current time is 3 o’clock PM, you add 7 hours and end up with 10 o’clock PM. But, what if it’s 8pm? You don’t simply add 7 hours as there is no such thing as 15 o’clock pm. Instead, when you pass 12 o’clock AM, you restart your counting. So 8 o’clock PM + 7 hours = 12 o’clock AM + 3hrs = 3 o’clock AM.
So what does clock arithmetic have to do with security? Going back to our original sequence of numbers, notice that you cannot possibly determine that these numbers all represent the same mathematical value without having a key piece of information, the modulo value (which in this case is 12). When you think about it, this property is useful from a secrecy perspective because you have 2 pieces of information that have a common value, but you can’t tell what that common value is unless you know some other information. This basic property of modular arithmetic forms the basis of many of the key negotiation and encryption algorithms in use today.
So, for fun, here’s a simple cryptosystem (secure enough to keep your 10 year old little sister from reading your journal) that uses this property. Note this cryptosystem doesn’t authenticate the two parties, but it at least allows them to exchange a pair of secret keys no matter who is listening.
- Alice and Bob want to exchange a secret message, but they can only talk to each other over an open communication channel.
- Beforehand, Alice and Bob agree to use the current time as the modulo value for determining the secret value. For example, if the current time is 4pm and Alice and Bob want to agree on a secret key, they will divide their values by 4. Note that the method they are using for choosing a modulo value must remain secret for this system to work.
- Alice sends her value to Bob in an open channel. Bob calculates the value she sent modulo the current time. The result is Alice’s encryption key.
- Bob sends his value to Alice again in an open channel.
- Alice calculates the value she got from Bob modulo the current time. The result is Bob’s encryption key.
- Now, Alice and Bob can communicate securely using each other’s encryption key to encrypt messages being sent back and forth (using some pre-determined encryption algorithm).
To see the system in action:
- The current time is 9pm.
- Alice picks a value of 84.
- Bob picks a value of 1156.
- Alice and Bob send a message to each other via a open channel (normal phone call, ads in the newspaper, or even yelling at each other in a park!).
- Alice get’s Bob’s value of 1156 and calculates 1156 / 9 = 128 remainder 4. 4 is Bob’s encryption key.
- Bob get’s Alice’s value of 84 and calculates 84 / 9 = 9 remainder 3. 3 is Alice’s encryption key.
- Now Bob and Alice can encrypt their messages using their respective encryption keys.
The real beauty of this type of system is that no matter who learns the values that Alice and Bob selected in steps 2 & 3, they will never be able to figure out how they are related without knowing what the modulo value is. In a future post, I’ll expand on this a bit more to show how modular arithmetic is used in non-toy cryptosystems.
Tags: cryptography