tech > security > adventures in (in)security > ElGamal Encryption
9 Nov 2010 17:11:15 EST

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 .
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 = gx or 23 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 c1 = gy or c1 = 21 or c1 = 2

Encryption Step 2: Bob calculates the shared secret s = hy or 81 or s=8

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

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

Encryption Step 5: Bob sends (c1, c2) 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 = c1x or s = 23 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 = c2 * 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 = c2 * 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 gy and refers to it by c1, but we're not going to.

Encryption Step 2: Bob calculates the shared secret s = hy. But remember, h = gx (where x was the number Alice never told anyone). So s = (gx)y. We can rearrange that thanks to associativity: (gx)y = gxy. 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*gxy and calls it c2

Encryption Step 5: Bob sends (gy, 5*gxy) to Alice.

Decryption Step 1: Alice computes s = (gy)x. Lets rearrange that to gyx and then gxy

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

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

Key Generation Step 1: Alice generates an efficient description of a multiplicative cycle group G of order q with generator g:
G is the group defined by {1,2,3...p} where p is a prime.
p = 142950481577612897377251366207350601085193026787763232208511322259955075211826388565191137969675785957228922178875744018870301928203434246727650650452188476517559379655516949015006180412307375960073546778478575555767086902406147563214485604901264760329721957156402926704404814419844454185694597535438114709207
The order is p-1. The generator g=5.
Key Generation Step 2: Alice chooses a random x from G. She chooses
x = 1114401462012054950832966919462174467153899340826309262725755458877000939896
Key Generation Step 3: Alice computes h = gx (mod p)
h = 51114401462012054950832966919462174467153899340826309262725755458877000939896
h = 20732874354899136216825777434161663051553860711014670584248653011489656009467628509581048747591474789135946239050452009093035314073281698027968886385471389940052553975051380077967473851027498623041665770681125462128819876799725748785297520780109561584249335930256469019459299507238701599790434670873090853866
Key Generation Step 4: Alice publishes (p, g, h) and keeps x a secret.

Encryption Step 0: Bob gets the data Alice published
Encryption Step 1: Bob chooses a random y from G. He chooses:
y = 7727084968753430501706963495961564950083327108274695943487389495551181109532486104792964989290024834809842316544132464386015687855241190234306012971910662444366323986006178235507076733067158781400201405045492745614817417493546764400476279299615351793001488330220752123954277422118134143821228756038829927938
He calculates c1 = gy (mod p)
c1 = 57727084968753430501706963495961564950083327108274695943487389495551181109532486104792964989290024834809842316544132464386015687855241190234306012971910662444366323986006178235507076733067158781400201405045492745614817417493546764400476279299615351793001488330220752123954277422118134143821228756038829927938
c1 = 70238597584213005153588674425819287571604753724120373924800011734873401764498809817490919748937893910264281907045326236567986463776410701367277492929569196314414408981286828276493587347168630779932375751286738293166945752566546676435600698182730679198091053383767036017144993127100295387701448278798234280152
Encryption Step 2: Bob calculates the shared secret s = hy (mod p).
s = 207328743548991362168257774341616630515538607110146705842486530114896560094676285095810487475914747891359462390504520090930353140732816980279688863854713899400525539750513800779674738510274986230416657706811254621288198767997257487852975207801095615842493359302564690194592995072387015997904346708730908538667727084968753430501706963495961564950083327108274695943487389495551181109532486104792964989290024834809842316544132464386015687855241190234306012971910662444366323986006178235507076733067158781400201405045492745614817417493546764400476279299615351793001488330220752123954277422118134143821228756038829927938
s = 101711785219505366443932885678885697797034842166333124186672159410485901291967418243172974173155944724729778982662908531712136091220515388892538813684950609576431220370176673699201744197276769711696780878242585118432221431978262022077570676618548611420550727480161912118486452270820273312386666166162676004339
Encryption Step 3: Bob wants to send Alice the secret m.
m = 6164659183586533865297396685427443804243915357261128582822359701762911601220784669937216567397356263699462300256043514069973009051035020945190796763258677261008595539232581136979432466539193960051472226014859162727037772275792812420929488958993864170154634477538930770485503543602699949823676882970022782
Encryption Step 4: Bob calculates c2 = m*s (mod p).
c2 = 6164659183586533865297396685427443804243915357261128582822359701762911601220784669937216567397356263699462300256043514069973009051035020945190796763258677261008595539232581136979432466539193960051472226014859162727037772275792812420929488958993864170154634477538930770485503543602699949823676882970022782  *  101711785219505366443932885678885697797034842166333124186672159410485901291967418243172974173155944724729778982662908531712136091220515388892538813684950609576431220370176673699201744197276769711696780878242585118432221431978262022077570676618548611420550727480161912118486452270820273312386666166162676004339
c2 = 68946654570806789973444696760367712586247422940741050384737518057551321589041388723907382443656618425983158354284335591870712569592598928174400006823554264854184640939842700544750070783010313978857114770206610401563473102295632389350278680865422244067091327749653967204410215097637596195454616193522657700864
Encryption Step 5: Bob sends (c1, c2) to Alice.
(70238597584213005153588674425819287571604753724120373924800011734873401764498809817490919748937893910264281907045326236567986463776410701367277492929569196314414408981286828276493587347168630779932375751286738293166945752566546676435600698182730679198091053383767036017144993127100295387701448278798234280152  ,  68946654570806789973444696760367712586247422940741050384737518057551321589041388723907382443656618425983158354284335591870712569592598928174400006823554264854184640939842700544750070783010313978857114770206610401563473102295632389350278680865422244067091327749653967204410215097637596195454616193522657700864)

Decryption Step 1: Alice computes s = c1x (mod p).
s = 702385975842130051535886744258192875716047537241203739248000117348734017644988098174909197489378939102642819070453262365679864637764107013672774929295691963144144089812868282764935873471686307799323757512867382931669457525665466764356006981827306791980910533837670360171449931271002953877014482787982342801521114401462012054950832966919462174467153899340826309262725755458877000939896
s = 101711785219505366443932885678885697797034842166333124186672159410485901291967418243172974173155944724729778982662908531712136091220515388892538813684950609576431220370176673699201744197276769711696780878242585118432221431978262022077570676618548611420550727480161912118486452270820273312386666166162676004339
This matches the s Bob computed, but again, without having exchanged it.
Decryption Step 2: Alice computes m = c2 * s-1 (mod p).

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 = tp-2 (mod p) - that is the inverse of t equals tphi(p)-1 mod p or written another way when p is prime: tp-2 mod p.
For the proof of this, start here, which will lead you here.

Decryption Step 2: Alice computes m = c2 * s-1 which can be rewritten m = c2 * sp-2 (mod p)
sp‑2 = 101711785219505366443932885678885697797034842166333124186672159410485901291967418243172974173155944724729778982662908531712136091220515388892538813684950609576431220370176673699201744197276769711696780878242585118432221431978262022077570676618548611420550727480161912118486452270820273312386666166162676004339142950481577612897377251366207350601085193026787763232208511322259955075211826388565191137969675785957228922178875744018870301928203434246727650650452188476517559379655516949015006180412307375960073546778478575555767086902406147563214485604901264760329721957156402926704404814419844454185694597535438114709205
sp‑2 = 135841643893792007625349059578993882193891093424935250981401740806314054854110110152637346922833578016458969353018818729374533258764447039996853093498079654915505010780620517738115860413168310072679542579936978587119601026246646427587027934638062288772291179774004950752966762896621967908051002752777437520621
m = c2 * sp-2
m = 68946654570806789973444696760367712586247422940741050384737518057551321589041388723907382443656618425983158354284335591870712569592598928174400006823554264854184640939842700544750070783010313978857114770206610401563473102295632389350278680865422244067091327749653967204410215097637596195454616193522657700864 * 135841643893792007625349059578993882193891093424935250981401740806314054854110110152637346922833578016458969353018818729374533258764447039996853093498079654915505010780620517738115860413168310072679542579936978587119601026246646427587027934638062288772291179774004950752966762896621967908051002752777437520621
m = 6164659183586533865297396685427443804243915357261128582822359701762911601220784669937216567397356263699462300256043514069973009051035020945190796763258677261008595539232581136979432466539193960051472226014859162727037772275792812420929488958993864170154634477538930770485503543602699949823676882970022782
Which is the same value Bob wants to send to her.

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 gx - so we must be relying on the fact that deriving x from gx 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.

 you type: you see: *italics* italics **bold** bold [stolen from reddit!](http://reddit.com) stolen from reddit! * item 1* item 2* item 3 item 1item 2item 3 > quoted text quoted text Lines starting with four spacesare treated like code:    if 1 * 2 < 3:        print "hello, world!" Lines starting with four spacesare treated like code:`if 1 * 2 < 3:    print "hello, world!"`