Key Generation Step 1: Alice generates an efficient description of a multiplicative cycle group G of order q with generator g.

What in the world does this mean? First off, let's define a Group. A group satisfies these properties:

1. The group is a collection of numbers.
2. The group must have an operation that we'll denote with •. That's not multiplication, that's just an anonymous operation - we don't know what it does yet. This operation has some rules:
   1. The result of a•b must be in the collection.
   2. (a•b)•c must be equal to a•(b•c) (That's associativity, and examples are addition and multiplication.)
   3. There has to be an element in the collection (we call it e), such that e•a = a•e = a. So e essentially does nothing to a - it's called the Identity.
3. Finally, for every element in our collection (call it x) there must be another element (call it x^-1) such that x•x^-1 = e. It is the Inverse, and vice versa. Every element must have an inverse, and the inverse is denoted with an exponent of negative 1..

Let's put this into an example.

• Let's make the collection of numbers the positive integers less than 7: 1,2,3,4,5,6
• Let's make the mysterious • operation something concrete - multiplication mod 7. Examples: 2*3 mod 7 = 6. 3*3 mod 7 = 2 (definition of modulo)
• Now we can see that because it's multiplication (even modulo something) associativity holds.
• And we can see that we have an e that does nothing to a number - 1. Anything times 1 is the same thing.
• And let's look at that last rule about inverses. Let's just solve it by brute force:
  • 1*α mod 7 = 1. Solve for α → 1.   1*1 mod 7 = 1
  • 2*α mod 7 = 1. Solve for α → 4.   2*4 mod 7 = 1
  • 3*α mod 7 = 1. Solve for α → 5.   3*5 mod 7 = 1
  • 4*α mod 7 = 1. Solve for α → 2.   4*2 mod 7 = 1
  • 5*α mod 7 = 1. Solve for α → 3.   5*3 mod 7 = 1
  • 6*α mod 7 = 1. Solve for α → 6.   6*6 mod 7 = 1

For every number x,there exists an inverse x^-1, such that x•x^-1 = 1. I can make a group another way:

• Let's make the collection of numbers the integers 0,1,2,3,4,5
• Let's make the mysterious • operation something concrete - addition mod 6. Examples: 2+3 mod 6 = 5. 3+3 mod 6 = 0
• Now we can see that because it's addition (even modulo something) associativity holds.
• And we can see that we have an e that does nothing to a number - 0. Anything plus 0 is the same thing.
• And let's look at that last rule. Let's just solve it by brute force:
  • 0+α mod 6 = 0. Solve for α → 0.   0+0 mod 6 = 0
  • 1+α mod 6 = 0. Solve for α → 5.   1+5 mod 6 = 0
  • 2+α mod 6 = 0. Solve for α → 4.   2+4 mod 6 = 0
  • 3+α mod 6 = 0. Solve for α → 3.   3+3 mod 6 = 0
  • 4+α mod 6 = 0. Solve for α → 2.   4+2 mod 6 = 0
  • 5+α mod 6 = 0. Solve for α → 1.   5+1 mod 6 = 0

Sidebar: Now there's a property you might have assumed by accident. I'm going to mention it to try and help you out, but it's not too important for the purpose of the blog post. Commutativity doesn't have to hold. a•b doesn't have to equal b•a. It does in these examples, but that's a coincidence. If it does hold, the group gains an extra property and is called an Abelian Group.

So, now we know what a Group is. "Multiplicative Group" simply means we're going to be using multiplication modulo a number, just like our first example. What about Cyclic?

Well just like I mentioned an Abelian Group was a Group with an extra property, so too is a Cyclic Group. This one's a little trickier though. A cyclic group has an element called a generator (usually denoted with g), that can be used to generate a group when the • is applied to it successively. Screw that definition, here's your examples:

• • is multiplication mod 7
• 3 = 3
• 3•3 = 2
• 3•3•3 = 6
• 3•3•3•3 = 4
• 3•3•3•3•3 = 5
• 3•3•3•3•3•3 = 1

• • is addition mod 6
• 1 = 1
• 1•1 = 2
• 1•1•1 = 3
• 1•1•1•1 = 4
• 1•1•1•1•1 = 5
• 1•1•1•1•1•1 = 0

So these are both cyclic groups - they have a generator g such than when the operation • is applied successively to it, yields all the members of the group.

One more piece of notation. When we're working with a multiplicative group, it's easier to use exponentiation than to write out 5•5•5•... We can do this because it's just a shorthand notation - in fact we can apply the modulo after each multiplication or once at the end and it doesn't make a difference. So because we'll be working with multiplicative groups, the shorthand we'll be using will be exponentiation to denote successive multiplication mod x, and we'll use the * sign without mentioning the modulo. We're still taking the modulo, but it's just to make the equations cleaner.

Key Generation Step 1: Alice generates an efficient description of a multiplicative cycle group G of order q with generator g.

Hang on, we're back to terminology. What do "efficient description" and "of order q" mean? The order of a group means the number of elements in it. So a group of order 7 has 7 elements. Our first example was a group of order 6 (1,2,3,4,5,6) and our second was also of order 6 (0,1,2,3,4,5). What about "efficient description"? Well that's actually not a math term. They mean Alice doesn't write out all the numbers - she's efficient! This will make sense when we work with a group with a lot of elements.

So, Alice has generated a multiplicative group G of order q with generator g. Here it is: {1,2,4,5,7,8}, the order is 6, • is multiplication mod 9, and the generator is 2

Key Generation Step 2: Alice chooses a random x from {0 - (q-1)}.

This set, the size of the order of the group (but starting counting at 0), allows her to calculate any number in the group - because every number in the group corresponds to the generator g raised to some power. She chooses x=3

Key Generation Step 3: Alice computes h = g^x or 2³ or h=8

Key Generation Step 4: Alice publishes h=8, G={1,2,4,5,7,8}, q=6, g=2 and keeps 3 a secret.

Now Bob enters the picture and wants to send a message.

Encryption Step 0: Bob gets the data Alice published

Encryption Step 1: Bob chooses a random y from {0 - (q-1)} also. He chooses 1. He calculates c₁ = g^y or c₁ = 2¹ or c₁ = 2

Encryption Step 2: Bob calculates the shared secret s = h^y or 8¹ or s=8

Encryption Step 3: Bob wants to send Alice the secret '5'.

Encryption Step 4: Bob calculates c₂ = 5*s mod 9 or c₂ = 5*8 (mod 9) or c₂ = 4

Encryption Step 5: Bob sends (c₁, c₂) to Alice. So he sends (2, 4)

Now Alice wants to decrypt. Here's where we're going to be proving stuff using all the theory at the top.

Decryption Step 1: Alice computes s = c₁^x or s = 2³ or s = 8.
Now Alice and Bob both know s, but without having ever exchanged it. That's why I called it the shared secret.

Decryption Step 2: Alice computes m = c₂ * s^-1.
But what's the inverse of 8? We'll brute force it this time, and discover 8^-1 * 8 mod 9 = 1. So 8 is its own inverse!
So m = c₂ * s^-1 mod 9 or m = 4 * 8 mod 9 or m = 5 - Our secret!

How did that work?! We're going to play a game of substitution. I'm going to write everything about the encryption and decryption in terms of the original variables, rather than renaming them - it's a lot easier to follow:

Encryption Step 0: Bob gets the data Alice published

Encryption Step 1: Bob chooses a random y from {0,1,2,3,4,5}. He chooses 1. He calculates g^y and refers to it by c₁, but we're not going to.

Encryption Step 2: Bob calculates the shared secret s = h^y. But remember, h = g^x (where x was the number Alice never told anyone). So s = (g^x)^y. We can rearrange that thanks to associativity: (g^x)^y = g^xy. Bob refers to this as s but we're not going to.

Encryption Step 3: Bob wants to send Alice the secret '5'.

Encryption Step 4: Bob calculates 5*s = 5*g^xy and calls it c₂

Encryption Step 5: Bob sends (g^y, 5*g^xy) to Alice.

Decryption Step 1: Alice computes s = (g^y)^x. Lets rearrange that to g^yx and then g^xy

Decryption Step 2: Alice takes (5*g^xy) * (g^xy)^-1. Let's use associativity again: 5 * (g^xy * (g^xy)^-1).
Remember the definition of an inverse: an element •-ed its inverse is 1. 5 * (g^xy * (g^xy)^-1) is 5 * 1 = 5

Tada!

Now let's do it with real values instead of such a contrived example.

Now at this point, we have to find the inverse of s, but s is very large. In the interest of time I'll tell you the trick to find the inverse, but not show you the proof. For an element t in G (where G is a multiplicative cyclic group defined by a prime), t^-1 = t^p-2 (mod p) - that is the inverse of t equals t^phi(p)-1 mod p or written another way when p is prime: t^p-2 mod p.
For the proof of this, start here, which will lead you here.

Now at this point you should be asking - why is this secure? In RSA, you have the primes p and q, and distribute pq - relying on the fact that factoring pq into p and q is difficult. Here, we have a secret x, and distribute g^x - so we must be relying on the fact that deriving x from g^x is hard. And it is.

This problem is called the Discrete Logarithm Problem, and just like integer factorization - no known polynomial time algorithm exists. But it's an open problem. In fact, it hasn't been proven that a polynomial time algorithm does or doesn't exist.

Update Mar 5, 2013: Thanks to Daniel 'koolfy' Faucon for pointing out a minor mistake in the explanation.