Subject: [Cfrg] one question about ElGamal encryption over a subgroup

From: "Wang, Steve" <[email-masked]>
Date: Thu, 11 Sep 2003 10:14:21 -0400

I have one question about the security of ElGamal encryption over a
subgroup. The original ElGamal encryption uses a large prime p and a
generator g. What will happen if the order of g is not p-1 but another
prime q, which divides p-1? Is the encryption secure if q is 160-bit
long?

It sounds to me that the same logic is used in DSS and thus it should be
fine.

Thanks, Steve

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Gé Weijers <[email-masked]>
Date: Tue, 14 Oct 2003 16:10:40 -0700

>It sounds to me that the same logic is used in DSS and thus it should be
Keep in mind the attacks presented in:

http://citeseer.nj.nec.com/boneh00why.html

and mangle your messages....

Ge'

-- 
Gé Weijers                mailto:[email-masked]
Sun Linux Security Group  Tel: (877)240-7611 x69536
Sun Microsystems, Inc.    Fax: (877)240-7611

---

From: "David Kravitz" <[email-masked]>
Date: Wed, 15 Oct 2003 12:09:13 -0400

Steve,

Although ElGamal encryption and DSS signing use similar math, this does
not imply that they are equivalent with respect to security.  In
particular, in ElGamal the factorization of (p-1)/q is relevant and,
depending on the application, small-subgroup attacks by non-compliant
encryption taking advantage of oracles may have to be considered.

--- David

David W. Kravitz, Ph.D.
Chief Scientist,
SPARTA, Inc.
5875 Trinity Parkway
Centreville, VA 20120
703.988.8606 (voice)
703.988.8599 (fax)
[email-masked]

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Wang, Steve
Sent: Thursday, September 11, 2003 9:14 AM
To: [email-masked]
Subject: [Cfrg] one question about ElGamal encryption over a subgroup

Thanks, Steve

---

From: "Anton Stiglic" <[email-masked]>
Date: Wed, 15 Oct 2003 13:09:03 -0400

----- Original Message ----- 
From: "David Kravitz" <[email-masked]>
To: "'Wang, Steve'" <[email-masked]>; <[email-masked]>
Sent: Wednesday, October 15, 2003 12:09 PM
Subject: RE: [Cfrg] one question about ElGamal encryption over a subgroup

> encryption taking advantage of oracles may have to be considered.

Another difference is that for encryption it's o.k. to use the generator
g = 2, but for signatures it's very bad.

See
http://citeseer.nj.nec.com/bleichenbacher96generating.html

--Anton

---

From: "David Kravitz" <[email-masked]>
Date: Wed, 15 Oct 2003 13:38:31 -0400

As Bleichenbacher points out in the cited paper, DSS is not susceptible
to this attack, although ElGamal signing (not to be confused with
ElGamal encryption) is.

--- David

David W. Kravitz, Ph.D.
Chief Scientist,
SPARTA, Inc.
5875 Trinity Parkway
Centreville, VA 20120
703.988.8606 (voice)
703.988.8599 (fax)
[email-masked]

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Anton Stiglic
Sent: Wednesday, October 15, 2003 12:09 PM
To: [email-masked]
Subject: Re: [Cfrg] one question about ElGamal encryption over a
subgroup

----- Original Message ----- 
From: "David Kravitz" <[email-masked]>
To: "'Wang, Steve'" <[email-masked]>; <[email-masked]>
Sent: Wednesday, October 15, 2003 12:09 PM
Subject: RE: [Cfrg] one question about ElGamal encryption over a
subgroup

See

--Anton