Securism Blog

Consider the problem where you need to know for sure that information you are looking at has not been altered since it was first created. A simple example that kids can relate to is a report card from school. The model for report cards is that the school gives a kid his/her report card, they bring it home and their parents sign it to show that they read the report card. An obvious problem that the school has is to be certain that the report card isn’t changed while the kid has it.

In cryptography, this problem is referred to as ‘data integrity.’ Cryptographic systems solve this problem by creating a representation of the information that is unique. This representation is referred to as a ‘hash’ (or checksum). A good way to think of a hash is as a digital fingerprint that looks totally different for each set of data that it represents. Functions that are used to create hashes from information are called hash functions. There are a couple of important points about hash functions:

• The result of the hash function MUST be unique for each message that it processes. That is, you should never be able to get the same result from a hash function if you feed in two different messages.
• The result of the hash function MUST not look anything like the message that it processed.
• It MUST be impossible, given the result of a hash function, to determine what the original message was.
• The result of the hash function is usually smaller than the message that it processed.

If you wanted to exchange a message with another person and be sure that the message hasn’t been changed along the way, you could use a hash function as follows:

1. Create a message.
2. Feed that message into a hash function.
3. Send the message to the recipient along with the hash.
4. The recipient feeds the message into the same hash function used by the sender.
5. The recipient compares their hash with the sender’s hash. If they are identical, the recipient is sure that the message wasn’t changed.

Of course this exchange isn’t secure as the hash could be changed in transit as well, but it illustrates how such a system works. I’ll explain how to make this exchange secure in a future post. To find out more about the basics of hash functions, read more.

(more…)

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:

1. The current time is 9pm.
2. Alice picks a value of 84.
3. Bob picks a value of 1156.
4. 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!).
5. Alice get’s Bob’s value of 1156 and calculates 1156 / 9 = 128 remainder 4. 4 is Bob’s encryption key.
6. Bob get’s Alice’s value of 84 and calculates 84 / 9 = 9 remainder 3. 3 is Alice’s encryption key.
7. 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.