Sender authentication part 23: Secret key encryption and one-way functions

We saw in my previous post that substitution ciphers are a method of encoding a message such that its contents are unintelligible (much like the ramblings of many of the presidential candidates), and they are fairly easy to break with computers that can iterate over them very quickly.

Enter the concept of one-way functions.  A one-way function is a mathematical function that is easy to calculate one way but very difficult to calculate the inverse.  For example, consider the process of squaring a number.  It is easy to calculate x2 (x to the power of two) but it is difficult to calculate the square root of x, √x.  The algorithm for a square root is more complicated than squaring a number and takes longer to evaluate.  Another example would be a logarithm.  It is easier to calculate 10 to the power of x than it is to evaluate log base 10 of x.

A good encryption algorithm, then, makes use of these one-way functions.  A message sender would encrypt his message using a one-way function and send it to the receiver and even if somebody intercepted the message in transit, they would have a difficult time decrypting it.  The algorithm is computationally intensive which makes breaking it cost-prohibitive (in terms of time).  The non-intended recipient could break the message since all it takes to break it is a matter of time and enough computing power, however, the idea is that by the time they did this, the contents of the message would be stale.  In other words, it would not be useful to the non-intended recipient.

So, if you want to encrypt the contents of an email message, you use an algorithm that takes a long time decrypt.  This is all well and good for the people who you don't want reading your message, but what about the person who you do want to read it?  What good is it if it takes them forever to read the message?  You might as well not send it at all.

This is where secret key encryption comes in.  With secret key encryption, you use a mathematical algorithm to encode your message, and use a secret key to do it.  So, a message would be scrambled by using the mathematical function that returns a different result each time you use a different key.

Here's a very basic example.  Suppose you wanted to encode the number sequence:

4 8 15 16 23 42

Let's suppose your secret key, n, is 2 and you are using the algorithm f(x) = xn (x to the power of n).  So, we'd encode the sequence this way:

16 64 225 256 529 1764

If our secret key were 4, we would encode the sequence this way:

256 4096 50625 65536 279841 3111696

The recipient would receive the encoded message and would also know the algorithm.  Therefore they also would know the decryption algorithm (in our case, the square root of x or the 4th root of x).  Secret key encryption works not by keeping the algorithm secret (as is the case of a substitution cipher) but by keeping the key secret.  If you don't know the key, it will take you a long time to figure out the contents of the message.  By the time you do, the data will no longer be useful.  In my example above, that doesn't look too difficult to break.  What would happen if our secret key were 8?  Or 16?  Or 3.14159?  There are still algorithms out there that are computationally expensive for computers break.

This brings me to my next point: in order to increase the security of an encrypted message, you don't need to change the algorithm, you only need to increase the length of the key.  For example, it is easier to calculate the inverse of x4 (x to the power 4) than x4.5 (x to the power of 4.5), which is easier still than x4.59 (x to the power of 4.59), which is easier than x4.591234 (x to the power of 4.591234), and so forth.

Finally, with secret key encryption, even though you might know what the key is to decrypt a message, encryption time vs decryption time are not the same and don't increase linearly with each other.  If a message takes twice as long to encrypt when you lengthen the key, it will take three times as long to decrypt.  In other words, decryption time vs encryption time increases exponentially.  Of course, breaking-the-algorithm-time-without-the-key increases even more when the size of the key increases.