Talk:ElGamal encryption

From Wikipedia, the free encyclopedia

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.

	To-do list for ElGamal encryption:	edit  · history  · watch  · refresh
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 6 A few questions 7 ElGamal signatures vs. ElGamal encryption 8 Spelling 9 Encryption questions 10 big problems 11 insecurity of G := F_p^*

[edit] 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)

[edit] 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

[edit] 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

[edit] 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)

[edit] 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)

[edit] A few questions

I think r should be equal to g^k (mod p).

Why do you say hcf (highest common factor) ? Most people talk of GCD or Greatest common divisor. You should link to Extended Euclidean algorithm. -- Nroets 8 July 2005 11:26 (UTC)

[edit] ElGamal signatures vs. ElGamal encryption

It didn't make sense to have ElGamal signatures and ElGamal encryption on the same page. There are not many similarities between the two schemes other than both are by Taher ElGamal and are based on discrete logarithm. But there are many differences between the schemes, especially when one looks at the the parameter choices. For example choosing g=2 is ok for the encryption scheme but an insecure choise for the signature scheme. A group for which the Decision Diffie Hellman problem is solvable is a problem for the encryption scheme but not a problem for the signature scheme.

Yep, sounds like the right thing to do. — Matt Crypto 21:36, 22 July 2005 (UTC)

[edit] Spelling

The name is spelled Elgamal, not ElGamal. Stern 19:00, 31 July 2005 (UTC)

See Talk:Taher Elgamal for further discussion. I agree with Matt on this one. It's referred to virtually everywhere as "ElGamal". alerante ✆ 00:14, 19 October 2005 (UTC)

Wikipedia goes with most common usage (see Wikipedia:Use common names). All major textbooks I've seen spells this ElGamal, so that is what this article should be named. I agree with User:Matt Crypto and User:Alerante. —Lowellian (reply) 03:20, 20 October 2005 (UTC)

[edit] Encryption questions

I'm trying to relate the generalized description in the article to with specific implementations of encryption (like in GnuPG and Applied Cryptography), and I'm wondering about the following:

The article says, Bob chooses a random y from , then calculates.... The implementations I've seen ensure that y and p − 1 are relatively prime. Is this somehow implicit in the article's description?

Also, there is a warning that care must be taken to properly encode the message m as an element of G, and not, say, as just an arbitrary element of Z_p. How exactly can one do that? (I'm asking about using subgroups of Z_p, not elliptic curves.) Wmahan. 07:12, 26 May 2006 (UTC)

To your first question: When using a group G whose order is a prime q (as recommended in the article) then one should choose y randomly in the interval 0..q-1. Then g^y will be a random element in G. The restriction that y is chosen relatively prime in GnuPG is a leftover from sharing code between ElGamal signatures and ElGamal encryption. These two schemes are actually quite different when one considers security requirements. For ElGamal signatures to work one must choose y (rsp. the identifier k is used there) relatively prime to the group order. No such requirement is necessary for ElGamal encryption. Thus sharing code is a risky idea and lead for example to a very severe attack against GnuPG discovered by Phong Nguyen.

To your second question: You can for example choose p=2q+1 where both p and q are prime. Then choose G as the multiplicative subgroup of Z_p of order q i.e. the quadratic residues. Now messages m in the range 1..q can be mapped into G by mapping m to where is a Legendre symbol. Also note that the resulting cryptosystme is only semantically secure, but not secure against chosen ciphertext attacks. Thus more considerations on the padding would be necessary for a real life implementation. 62.167.39.178 19:53, 28 May 2006 (UTC)

Thank you very much. The second edition of Schneier's Applied Cryptography (1996) says to do the relatively prime thing for encryption too, not just for signing. But I checked the reference linked at the bottom of the article and it says you're right, of course. I suppose GnuPG's extra constraint on y doesn't weaken the algorithm, even if it isn't necessary. Thanks again for the informative answers. Wmahan. 19:01, 31 May 2006 (UTC)

perhaps the above could be added to the article. Since its not always easy to test if a elemet in is in the subgroup generated by g. --The preceding unsigned comment was added by 131.130.79.169 (talk) 11:23, 19 December 2006 (UTC).

[edit] big problems

the mods are left off the equations. how is anyone going to know how to use this? --The preceding unsigned comment was added by 155.91.28.232 (talk) 23:42, 14 March 2007 (UTC).

No. There are not mod operations missing. The article is written in a general form using a group G written multiplicatively. If G is the multiplicative subgroup then all operations are done modulo p. However, G can be some other group, e.g. the group of points on an elliptic curve. 85.2.121.89 12:20, 24 March 2007 (UTC)

[edit] insecurity of G := F_p^*

I have tagged this statement as "citation needed". The currently referenced "Handbook of Applied Cryptography" specifically states that ElGamal with G=F_p^* is believed to be secure. If this information is out of date, a reference should be supplied to show that.

Also note that some current implementations do use F_p^*, so this is quite important to get right! Mbays 18:49, 22 March 2007 (UTC)

Good point. The statement is at least ambigous, because the term "insecure" itself is unclear without stating an adversarial model. First, the DDH assumption in does indeed not hold, because for a generator g it is possible to distinguish tuples g^a,g^b,g^ab from g^a,g^b,g^c with a nonnegligible probability, by computing Legendre symbols of the values. Similarly, from an encryption (g^r,y^rm) we can derive the Legendre symbol of m as follows. Computing the Legendre symbol (g^r | p) tells us if r is odd or even. The Legendre symbol (y | p) = (g^x | p) tells us whether x is odd or even. Thus we know the parity of xr and thus also the value of (y^r | p). Hence, we know the Legendre symbol (m | p) = (y^rm | p) / (y^r | p). Hence ElGamal encryption over is not semantically secure. Note that if RSA has a same problem when used without padding. Given c = m^emod n one can easily derive the Jacobi symbol (m | n) = (c | n). Using prime order subgroups instead of gives sematic security, but not security against adaptive chosen ciphertext attatcks. Therefore, ElGamal encryption (as well as RSA encryption) must use a padding scheme in order to be secure against adaptive chosen ciphertext attacks. 85.2.11.148 21:18, 22 March 2007 (UTC)

OK yes, I see the argument that the group has to be of prime order. I still think it needs a citation, though. As an aside: any idea how serious a problem this actually is? Presumably it depends on how small is the largest prime you can expect to be a factor of p-1. As a further aside: would you suggest that this be reported as a bug to developers of implementations which use F_p^*? Mbays 16:53, 23 March 2007 (UTC)

My previous comment wasn't very clear. While ElGamal over appropriate prime order subgroups is semantically secure and ElGamal over is not we should not conclude that any ElGamal implementation using the group is immediately insecure and any system using a prime order subgroup is secure. It all depends on what padding scheme is used. For example, DHAES does not require groups for which the Decisional Diffie-Hellman assumption holds and still achieves security against chosen plaintext attacks. (Unfortunately, DHAES is not exactly ElGamal, just similar. But it should make the point clear. Anyway, I'll continue to look for a better example.) Also, I haven't found a reference for the sementically secure/not semantically secure comment above. It seems to be general knowledge, however. Who is using ElGamal encryption in their implementation? 85.2.99.179 18:57, 23 March 2007 (UTC)

Would Appendix A of that paper do as a reference for the statement? Mbays 20:16, 23 March 2007 (UTC)

Yes, indeed. I didn't notice the appendix. 85.2.57.232 00:54, 24 March 2007 (UTC)

OpenPGP is an implementation that uses for ElGamal to exchange key packages. These key packages are padded using PKCS #1 encryption padding. Since PKCS #1 encryption padding adds randomness this does take care of fact that ElGamal over is not semantically secure. Using a prime order subgroup would still be slightly nicer, because then one would have a proof that the scheme is sematically secure. But at least in the case of OpenPGP it is not wrong (or at least not immediatly obvious) to use . (However, I'd prefer OAEP padding instead of PKCS #1 padding.) 85.2.121.89 12:52, 24 March 2007 (UTC)

A good citation for DDH holding in certain groups would be Dan Boneh's nice survey article. The second page has a quick list of groups believed to have the DDH property. The reduction from DDH to Elgamal's semantic security (CPA) is very common and very simple. An example proof can be seen here for instance (from a site I have quite an investment in, actually!). Blokhead 05:27, 24 March 2007 (UTC)

The link to the proof looks very useful. Boneh's paper is already referenced on the DDH page. 85.2.121.89 12:52, 24 March 2007 (UTC)

I was thinking of updating the section on the security, but there is still a reference missing. In particular, I'm looking for a reference that shows that assuming the computational Diffie-Hellman assumption for a group (or family of groups) implies that inverting ElGamal encryption is hard. This statement seems easy to prove. I.e., assume we are given an oracle that on input g,g^a,y = g^x,mg^ax returns m Then we can use this oracle to find g^ab given g,g^a,g^b as follows: Choose a random group element r and call the oracle with g,g^a,g^b,r. Assume it returns m' as result. Then we can compute g^ab from m'g^ab = r. The "Handbook of Applied Cryptography" probably refers to something similar when it states that ElGamal over is believed to be secure. Unfortunately, the book doesn't make a clear statement and doesn't give a reference. 85.2.110.35 07:20, 29 March 2007 (UTC)