Abstract Algebra presented in a non-intimidating way (esp. for developers) - cryptography

Hi!

Hopefully you read the last post, and if you didn't, you really should (http://poincare101.blogspot.com/2011/12/abstract-algebra-presented-in-non.html), because I'll be building on that stuff this time around.

This time, we'll be going over an very interesting and applicable subject (if you've ever used a computer, you've experienced it in action), called cryptography, and more specifically, public-key cryptography.

Let's get started.

From the dawn of humans, there's always been one human who wants another one dead, and as time as gone has gone by, we have invented better and better (or, worse and worse) of accomplishing this.

One of such inventions was cryptography.

Communication is incredibly important in war, and Caesar (yes, that Caesar, the guy from Rome you learned about in history class and promptly forgot about after the test) needed a way to communicate with his generals spread out throughout the Roman empire in way such that even if the messenger was captured, the bad guys wouldn't be able to read the message.

So, he (and presumably his team of scholars he kept handy) developed the Caesar cipher. I won't go into a ton of detail here, mostly because I wrote an entire blog entry about it (http://poincare101.blogspot.com/2011/10/encryption-and-ciphers-part-1-this-is.html).

Basically, you shift over the alphabet over the message by a certain amount (that certain amount is called the key) to get the encrypted message, and, the person who wants to decrypt it shifts back the message by that certain key.

There worked for a little bit, but, it involved the fact that the people who Caesar sent his messages to had to be told of the key and Caesar didn't trust them enough for that, so this system was abandoned, and Caesar most likely returned to the time-tested and expensive method of sending a messenger with soldiers armed to the teeth.

People entirely overlooked this (rather important, as we'll see later) problem, and instead concentrated on the fact that the Caesar Cipher was easily cracked with statistical methods (all of this is explained quite thoroughly in the blog post I linked above).

Slowly, cryptography turned into a pastime for amateurs and enthusiasts, and it was not much of a subject by itself, until more and more developments followed, and the subject was looked upon by mathematicians.

One of these new and better ciphers is called the Vigenere (I refuse to take the time to put the accents in the right places) Cipher.

I wrote a blog post about this one too: http://poincare101.blogspot.com/2011/10/encryption-and-ciphers-part-2.html

The basic idea was that it no longer kept the frequency of the original text (often called plaintext) intact, making it immune to the statistical methods that could be used on the Caesar Cipher, but, there were other methods it was vulnerable to.

One very large problem was still overlooked: both parties need to transact the key before hand, or this procedure wouldn't work.

Finally, some clever chap came up with the revolutionary (like, really revolutionary) idea of public key cryptography.

The concept is quite brilliant.

Say, you have Alice and Bob and they want to transact encrypted messages. In public key cryptography, both Alice and Bob each have a public key and a private key. 

The public keys are published somewhere that *everyone* can access them (not necessarily only Alice and Bob).

Now, Alice wants to send Bob a message. She finds Bob's public key and encrypts her message with it, and the sends off this encrypted message to Bob, who then decrypts it with his private key.

That means that the key that is used to decrypt the messages is never transacted, and Alice never needs to know it!

That means that if Caesar had used public key cryptography, he wouldn't have faced the problem he had, because his generals would never have to know his private key!

Of course, there's a problem (actually, a few of them) with that (otherwise there wouldn't be a NSA). 

The private key and the public key must somehow be related to each other, so, theoretically, given as much time as needed, it would be possible to derive the private key from the public key, so, the solution to that is to use a computationally hard problem to generate the public and private keys, so it would take much too long to get the private key from the public key for it to be practical.

You might have noticed that I've been quite vague so far; I haven't specified HOW the keys are actually generated, and the encryption is carried out to turn plaintext into ciphertext.

That's where the math begins.

I mentioned that we had to generate the keys with a "computationally hard" problem. What on earth does that mean?!

Its a pretty simple idea, it means that as you increase some parameter, the time taken to complete the problem skyrockets (not a perfect definition, but, it will suffice).

One such problem is called the Discrete Logarithm Problem (DLP, for short).

Basically, you have a prime $p$, and $g, h$ such that both are part of the $mod p$ set (i.e. between $0$ and $p-1$ inclusive).

The problem is to find an $x$ such that:

$h \equiv g^{x} \pmod {p}$

Let's see why that's so hard.

Let's set:

$p = 7$

$h = 6$

$g = 3$

Basically, the only approach to this is we try different values for $x$, find $g^x$, then find $g^x \pmod {p}$, and keep going until we find an $x$ such that

$h \equiv g^{x} \pmod {p}$

If you try this (and I highly encourage you to do this), you will find that $x = 3$ works. This is a pretty small example, but, turn up the numbers, and it becomes a pretty formidable problem.

Let's look a bit more deeply into this matter, why is this so hard?

Well, because we don't have any way find out an answer without brute-force.

Okay, why don't we have another way?

Because it deals with $\mod p$, for which we don't have a ton of tools to deal with.

Exactly! Primes often occur in such problems, because we don't have a complete picture of how primes operate, because as far as we understand it today, they don't form some kind of equation that we can plug numbers in and get (all) primes out.

Alright, now, how are we going to turn this into a key?

There's something called the Diffie Hellman key-exchange system, which is outlined as follows (with Alice and Bob trying to communicate):

1. There's a publicly listed prime number that is decided, in our example, it will be 19 ($p = 19$), and $g=2$, which is also publicly declared.

2. Alice picks a secret number (say, 6), and computes:

    

    $2^6 \equiv 64 \equiv 7 \pmod 19$

    

    and, sends this result off to Bob, and we call this result $A$.

3. Bob does the same (but, with his secret number, which is 13),

    $2^13 \equiv 3 \pmod 19$

    

    We'll call this $B$.

4. Now, Alice takes the number she received ($B$), and raises it to her secret number (call it $a$):

    

    $B^a \equiv 3^6 \equiv 7 \pmod 19$

5. Bob does similarly:

  

    $A^b \equiv 7^13 \equiv 7 \pmod 19$ 

As you can see, at the end, both of them share one key, despite having started from completely different keys, and since this is based on the DLP, it is incredibly hard to solve, even with a supercomputer for (very) large values for $p$ (200+ digits).

So, what does any of this have to do with groups?

Well, I'm glad you asked.

Groups (and abstract algebra in general), lets us generalize.

Using the definitions of cyclic groups that define only the properties we need, we can say this (quoted verbatim from Wikipedia):

1. Alice and Bob agree on a finite cyclic group G and a generating element g in G. (This is usually done long before the rest of the protocol; g is assumed to be known by all attackers.) We will write the group G multiplicatively.
2. Alice picks a random natural number a and sends g^a to Bob.
3. Bob picks a random natural number b and sends g^b to Alice.
4. Alice computes (g^b)^a.
5. Bob computes (g^a)^b.

This immediately makes the system a LOT more powerful, because now, instead of dealing with just numbers, we can deal with ANY cyclic group we want, they can even be chess moves, if you can somehow wrangle them into a cyclic group.

Why is that helpful?

Well, if you're using natural numbers to do your bidding (since they form a cyclic group), you're still not fully secure, and there are other cyclic groups thought to be "more secure" (because of various properties of the groups themselves), and a popular such cyclic group are the points on an elliptic curve.

To explain *why* this actually happens, requires a great deal more knowledge, but, the idea of using groups to specify how the system works is profound; you can swap in any system you'd like to make a "cyclic group"

Hopefully you enjoyed that :)

All feedback is greatly appreciated!

If you have any questions (or feedback), please drop a comment below, and I'll do my best at answering them!