Talk:ElGamal encryption

Missing image Key-crypto-sideways.png WikiProject on Cryptography

This article is part of WikiProject Cryptography, an attempt to build a comprehensive and detailed guide to cryptography in the Wikipedia. If you would like to participate, you can choose to edit the article attached to this page, or visit the project page, where you can join the project and see a list of open tasks.

	Pending tasks for [[Template:Articlespace:ElGamal encryption]]: (https://academickids.com:443/encyclopedia/index.php?title=Talk:ElGamal_encryption&action=purge)	edit (https://academickids.com:443/encyclopedia/index.php?title=Talk:ElGamal_encryption/to_do&action=edit) - watch (https://academickids.com:443/encyclopedia/index.php?title=Talk:ElGamal_encryption/to_do&action=watch) - purge (https://academickids.com:443/encyclopedia/index.php?title=Talk:ElGamal_encryption&action=purge)
	Add references

We should point out that without padding Elgamal is malleable. --Imran

Contents

1 Should be named?? 2 Which algorithm is described here, anyway???? 3 error in el-gamal decryption scheme 4 Many fixes needed in this article 5 Fixed this article

Should be named??

The title of this article is misleading and should be changed. This is an algorithm, a primitive used to build crypto systems. It is not itself a crypto system. Perhaps a pointer from this title to this article under the better title of 'ElGamal encryption algorithm'. See the cross reference (currently a dangling link) at article cryptography. user ww

I agree. ElGamal is not a complete cryptosystem. Taw 19:58, 6 Apr 2004 (UTC)

Any suggestions for a better name? — Matt 02:36, 3 Aug 2004 (UTC)

It depends on how you define "cryptosystem." To theorists, a cryptosystem is rigorously defined to be a key generator, encryption algorithm, and decryption algorithm. ElGamal fits the bill... On the other hand, I dislike the phrase "discrete log" in the title. Security of ElGamal surely relies on the discrete log assumption, but in fact it needs something stronger (the Decisional Diffie-Hellman assumption, to be precise). --Chris Peikert 22:10, 18 Nov 2004 (UTC)

Chris, while you're right about cryptosystem in a strict sense, the term is used far more by applied crypto people than theory people, so IMHO wikipedia should use that definition. Arvindn 22:45, 19 Nov 2004 (UTC)

How about ElGamal cryptosystem then (also applying the principle that shorter names are better)? — Matt 23:31, 19 Nov 2004 (UTC)

I am OK with either ElGamal cryptosystem or ElGamal encryption or ElGamal encryption algorithm. I think Arvindn's right that cryptosystem, at least on wikipedia, should be reserved to mean a "full package". --Chris Peikert 06:33, 22 Nov 2004 (UTC)

OK, I've plumped for ElGamal encryption and added redirects for the others. — Matt 07:02, 22 Nov 2004 (UTC)

In my opinion the name should be Elgamal cryptosystem. That is the name I used for the german version of the article (Elgamal-Kryptosystem) from which this text is translated. Encryption is misleading, because the text both explains the encryption and decription (I hope this is correct english :-). A cryptosystem perhaps includes encryption and decription. As far as I know the name is spelled "Elgamal" and not "ElGamal".Stern 23:21, 30 Jan 2005 (UTC)

Which algorithm is described here, anyway????

It would seem to me that the algo that is described is the DH encryption, not the ElGamal signature scheme on which DSA is based. user mmy

error in el-gamal decryption scheme

hello there, the very simple explanation for decrytpting the message m:=(c1,c2) with c2/(c1^x) is apparently not correct.

here is a little example:

Bob:

p:= 11; phi(11) = 10; 10=2*5;

g:=2 (2^5 mod 11 !=1 and 2^2 mod p !=1 and therefore order(2,11)=10)

x:= 5 (0<=x<p-1)

y:= g^x = 2^5 mod 11 = 10;

now PK(p,g,y) = (11,2,10) and SK(11,2,5) = (p,g,x)

Alice:

encrypts m:=7 with randomly chosen k:=9

c:=(g^k,m*y^k) = (2^9 mod 11, 7*10^9 mod 11) = (c1,c2) = (6,4)

and sends (c1,c2)

Bob:

tries to decrypt with in your opinion:

m:= c2/c1^x = 4/6^5 mod 11 = 4/10 != 7

while the original intention was:

m:=(c1^x)^-1 * c2 = (c1^-1)^x * c2 = c1^-x * c2

where ^-1 refers to the inverse of c1 in Z11

therefore:

m:= ([6]^-1)^5 * [4] = ([2]^5 *[4]) = 32 mod 11 * 4 mod 11 = 7

note: 2*6 mod 11 = 1 and then again 2 is the inverse of 6

we hope that helps

Many fixes needed in this article

The description of ElGamal is incomplete and has some errors.

First, there isn't any discussion of how the parameters p,g are generated. In fact, p should be chosen to be prime, such that p-1 has a large prime factor q (p=2q+1, where q is also prime, is a typical choice). Then g should be chosen to have order q in Z_p. That is, g is not a generator of all of Z_p, but is a generator of a prime-order subgroup of Z_p. If setup is not done this way, ElGamal can be insecure (at least, according to the definition of semantic security).

(The incomplete description of the parameters may be the reason for the bug described above; I haven't looked at it closely.)

Key setup (the choice of x) is merged into the encryption algorithm when it shouldn't be. Also, it should be said that x is chosen at random from Z_q^*.

Bob's message should not be encoded as an arbitrary element of Z_p, but as an element from the subgroup generated by g. Otherwise the scheme may be insecure.

Bob's choice of k should be random from Z_q^*.

It is claimed that breaking the security of ElGamal is as hard as finding discrete logs. This is not known to be true, nor believed to be true. In fact, breaking the semantic security of ElGamal is equivalent to breaking the Decisional Diffie-Hellman (DDH) assumption in the subgroup pf Z_p generated by g.

--Chris Peikert 22:29, 18 Nov 2004 (UTC)

I have translated the German version of the article, but given the accuracy concerns, this should be merged in by someone with a little more knowledge -- for now, it is just there at the end of the article. Mpolo 16:35, Nov 21, 2004 (UTC)

Thanks -- unfortunately, it appears that the German version has many of the same errors that I describe above. One of these days when I have time I will attempt to fix this article... --Chris Peikert 21:34, 21 Nov 2004 (UTC)

That'd be much appreciated, if you have the time. — Matt 21:40, 21 Nov 2004 (UTC)

Fixed this article

Hi all, I rewrote this article with accuracy and security in mind, and I think it is alright now (two of the edits I accidentally submitted as anonymous, rather than via my account). I included discussions of malleability (as suggested above) and efficiency (from the German translation).

However, I haven't done my homework vis-a-vis links to other wiki pages. It would be great if someone could go through the text and take advantage of good linking opportunities.

--Chris Peikert 06:29, 22 Nov 2004 (UTC)

Thanks, it's great work. I've gone through and added a few wikilinks. — Matt 07:02, 22 Nov 2004 (UTC)