ElGamal vs RSA

7 views
Skip to first unread message

F. Arndt

unread,
Mar 6, 1999, 3:00:00 AM3/6/99
to
A novice question: Is it generally accepted that the ElGamal is much
less secure than the RSA for comparable key lengths?

DJohn37050

unread,
Mar 7, 1999, 3:00:00 AM3/7/99
to
ElGamal is based on the (normal) discrete logarithm problem, RSA is based on
the integer factorization problem. Most people think that the discrete log
problem is slightly harder, but they are considered equivalent for most
purposed. For example, ANSI X9 mandates that RSA and DSA (revision) keys be at
least 1024 bits long. For ECDSA, keys must be at least 161 bits long.
Don Johnson

ssim...@hertreg.ac.uk

unread,
Mar 7, 1999, 3:00:00 AM3/7/99
to
In article <36E1D3...@NOSPAMusa.net>,

"F. Arndt" <nli...@NOSPAMusa.net> wrote:
> A novice question: Is it generally accepted that the ElGamal is much
> less secure than the RSA for comparable key lengths?

No. DH /Elgamal offers slightly more security per key bit than RSA.

Sam Simpson
Comms Analyst
-- http://www.scramdisk.clara.net for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own

Wei Dai

unread,
Mar 7, 1999, 3:00:00 AM3/7/99
to
In article <19990306234247...@ng08.aol.com>, djohn37050
@aol.com says...

I think this "slightly harder" conclusion is probably based on a
comparison of the NFS index calculus algorithm versus the NFS factoring
algorithm. But has there been any published experimental results for
discrete log using NFS? It would be nice to know the constants in the
running time more precisely. Perhaps someone could set up a discrete log
challange series, similar to the RSA factoring challenges?

P.S. I did find one published result, available at
http://cdc-server.cdc.informatik.tu-darmstadt.de
/home/LiPS/LiPS/documentation/objects/doc/html/etc/McCurleyChallenge
/cryptoPaper/cryptoPaper.html, but the challenge used a prime modulus of
special form that makes NFS especially easy.

bo...@rsa.com

unread,
Mar 8, 1999, 3:00:00 AM3/8/99
to
In article <7buglm$a6g$1...@nnrp1.dejanews.com>,

ssim...@hertreg.ac.uk wrote:
> In article <36E1D3...@NOSPAMusa.net>,
> "F. Arndt" <nli...@NOSPAMusa.net> wrote:
> > A novice question: Is it generally accepted that the ElGamal is much
> > less secure than the RSA for comparable key lengths?
>
> No. DH /Elgamal offers slightly more security per key bit than RSA.

Please. For my edification and enlightenment, define what you mean by
"slightly more". Please explain why you think the claim is true.

I have heard this remark before. While it is true, "slightly" should be
"very slightly". And the reason why is subtle. And it depends if the
field is GF(p) or GF(2^k).

I'd like to find out if anyone in this newsgroup knows the REAL reason
why solving a DL problem over Z_p is slightly harder than factoring N = st
when log(N) ~ log(p). Note that solving a DL problem over GF(2^k) where
k ~ log_2(N) is EASIER than factoring N.

bo...@rsa.com

unread,
Mar 8, 1999, 3:00:00 AM3/8/99
to

DJohn37050

unread,
Mar 8, 1999, 3:00:00 AM3/8/99
to
ANSI X9 requires a prime field, not a prime power field. IEEE P1363 allows
either a prime field or a characteristic 2 field (ie.e., of form 2**m) as
elements can be represented by a bit string of a certain length. Obviously,
for a certain length bit string, there is exactly one 2**m number, but many
primes. Some have hypothesized about the potential to build a field cracker HW
device, so use of a prime allows use of many fields for a specific element
size, say 1024 bits.
Don Johnson

Michael Sierchio

unread,
Mar 8, 1999, 3:00:00 AM3/8/99
to
bo...@rsa.com wrote:

> I'd like to find out if anyone in this newsgroup knows the REAL reason
> why solving a DL problem over Z_p is slightly harder than factoring N = st
> when log(N) ~ log(p). Note that solving a DL problem over GF(2^k) where
> k ~ log_2(N) is EASIER than factoring N.

Have you posted a follow-up that I missed? I am familiar with, for
example, Coppersmith's approach to evaluating logs, so I understand your
last assertion to be provisionally true -- meaning that there is an (more)
efficient known algorithm for finding discrete logs in GF(2^k). The
conjecture about the difficulty of calculating discrete logarithms
still rests on the absence of a general method that is not in P or NP.

I had the impression, though, that the order of magnitude of solving
the discrete log in GF(p^k) where p^k is an odd prime power of k bits
is still "roughly equivalent" to factoring a k-bit composite.

Both RSA and ElGamal have their merits. I'd
say that RSA certainly has a lead in terms of maturity, marketing,
licensing and reference implementation. These factors often matter
more for security's sake than the algorithm itself. The beauty of
Diffie-Hellman key exchange, though, esp. in a system like SKIP where
the shared secret is never directly used (zero-message master key update),
is undeniable.

Roger Schlafly

unread,
Mar 8, 1999, 3:00:00 AM3/8/99
to
Michael Sierchio wrote in message <36E44809...@dnai.com>...

>Both RSA and ElGamal have their merits. I'd
>say that RSA certainly has a lead in terms of maturity, marketing,
>licensing and reference implementation. These factors often matter
>more for security's sake than the algorithm itself.

These factors are important, but they do not give RSA a clear-cut
edge. When people say "ElGamal" they usually mean encryption,
in which case it is nearly identical to Diffie-Hellman. Diffie-Hellman
predates RSA and is widely used commercially. Licensing is cheaper
and easier with Diffie-Hellman because the patent has expired and
it is in the public domain.


whg...@no.openpgp.net.spam.please

unread,
Mar 8, 1999, 3:00:00 AM3/8/99
to
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

In <7c2572$e...@enews1.newsguy.com>, on 03/08/99

Well my experience with RSADSI:

In the few times that I have talked with them everyone has been
universally arrogant.

They do *not* release source code for their toolkits.

I find their licensing requirements unacceptable.

IMHO I have not seen anyone present a good case to use RSA over ElGamal.

- --
- ---------------------------------------------------------------
William H. Geiger III http://www.openpgp.net
Geiger Consulting Cooking With Warp 4.0

Author of E-Secure - PGP Front End for MR/2 Ice
PGP & MR/2 the only way for secure e-mail.
OS/2 PGP 5.0 at: http://www.openpgp.net/pgp.html
Talk About PGP on IRC EFNet Channel: #pgp Nick: whgiii
- ---------------------------------------------------------------

Tag-O-Matic: This is a TAG-O-Matic
Multi-line Sample
Tag

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i OS/2 for non-commercial use
Comment: Registered_User_E-Secure_v1.1b1_ES000000
Charset: cp850

wj8DBQE25Li6lHpjA6A1ypsRAujLAJ99mYR017FyNrAa96qFyxHokOTK7QCgprnh
QNhVeXn+NZktKEGbg7qUDwM=
=JCVz
-----END PGP SIGNATURE-----


Sam Simpson

unread,
Mar 9, 1999, 3:00:00 AM3/9/99
to
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

"Discrete logarithms are, with the present state of knowledge,
slightly more difficult to compute modulo an appropriately chosen
prime than it is to factor a "hard" integer of the same size".
- -- The future of integer factorization by A.M.Odlyzko (1995). Is
this information now out of date?

Well, I asked on sci.crypt a couple of months ago to clarify on
this point and got similar responses from Roger Schlafly:
"Breaking a 512-bit DSA key is significantly more difficult [than
an RSA key]"..."The asymptotics are similar. But breaking DH
(ElGamal or DSA) requires some large tables. Much larger RSA
keys have been broken than DH keys."
- -- "Re: Opinions on S/MIME", sci.crypt, ~30 Dec 98


BTW does anyone still use GF(2^n)? It said as long as 14-years
ago that GF(2^n) ought to be avoided in all cryptographic
applications - who would still consider it in the same breath as
GF(p)?


Look forward to any pointers to more recent literature you may be
able to provide.


- --
Sam Simpson
Comms Analyst
http://www.scramdisk.clara.net/ for ScramDisk hard-drive


encryption & Delphi Crypto Components. PGP Keys available at the
same site.

If you're wondering why I don't reply to Sternlight, it's because
he's kill filed. See http://www.openpgp.net/FUD for why!

bo...@rsa.com wrote in message
<7bvhm6$4t1$1...@nnrp1.dejanews.com>...


>In article <7buglm$a6g$1...@nnrp1.dejanews.com>,
> ssim...@hertreg.ac.uk wrote:
>> In article <36E1D3...@NOSPAMusa.net>,
>> "F. Arndt" <nli...@NOSPAMusa.net> wrote:
>> > A novice question: Is it generally accepted that the
ElGamal is much
>> > less secure than the RSA for comparable key lengths?
>>
>> No. DH /Elgamal offers slightly more security per key bit
than RSA.
>
>Please. For my edification and enlightenment, define what you
mean by
>"slightly more". Please explain why you think the claim is
true.
>
>I have heard this remark before. While it is true, "slightly"
should be
>"very slightly". And the reason why is subtle. And it depends if
the
>field is GF(p) or GF(2^k).
>

>I'd like to find out if anyone in this newsgroup knows the REAL
reason
>why solving a DL problem over Z_p is slightly harder than
factoring N = st
>when log(N) ~ log(p). Note that solving a DL problem over
GF(2^k) where
>k ~ log_2(N) is EASIER than factoring N.

-----BEGIN PGP SIGNATURE-----
Version: PGP 6.0.2

iQA/AwUBNuTebu0ty8FDP9tPEQJFiwCfbXIHc2GIky8pPYVDBs3KBuJrNXIAnjqA
Ya4bkPRbNOzevW74mXA+0TV7
=pSiB
-----END PGP SIGNATURE-----


Michael Sierchio

unread,
Mar 9, 1999, 3:00:00 AM3/9/99
to
William H. Geiger III wrote:

> Well my experience with RSADSI:
>
> In the few times that I have talked with them everyone has been
> universally arrogant.

I have to say that this was not my experience. But I was working
at the time in Sun's Network Security Products Group, and they
obviously had an incentive to maintain a good relationship.

> They do *not* release source code for their toolkits.

Of course not. RSAREF is available as source. BSAFE and JSAFE represent
considerable effort at improving on the reference implementation.
Maybe they consider their source code to be intellectual property?

> I find their licensing requirements unacceptable.

I myself did balk at $2500 for a JSAFE license for my own work.
If I were engaged in making a commercial product, I might have
been able to justify the expense.



> IMHO I have not seen anyone present a good case to use RSA over ElGamal.

I guess it just depends on what you're willing to accept. Installed
base is one reason. RSADSI happens to be a good supplier of information
and an enthusiastic advocate for strong encryption.

Medical Electronics Lab

unread,
Mar 9, 1999, 3:00:00 AM3/9/99
to
Sam Simpson wrote:
>
> BTW does anyone still use GF(2^n)? It said as long as 14-years
> ago that GF(2^n) ought to be avoided in all cryptographic
> applications - who would still consider it in the same breath as
> GF(p)?
>
> Look forward to any pointers to more recent literature you may be
> able to provide.

Check out "Elliptic Curve Public Key Cryptosystems" for use of
GF(2^n). Who said it should be avoided? Have you got a reference
for that?

Patience, persistence, truth,
Dr. mike

whg...@no.openpgp.net.spam.please

unread,
Mar 9, 1999, 3:00:00 AM3/9/99
to
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

In <36E56207...@dnai.com>, on 03/09/99

at 10:01 AM, Michael Sierchio <ku...@dnai.com> said:

>William H. Geiger III wrote:

>> Well my experience with RSADSI:
>>
>> In the few times that I have talked with them everyone has been
>> universally arrogant.

>I have to say that this was not my experience. But I was working at the
>time in Sun's Network Security Products Group, and they obviously had an
>incentive to maintain a good relationship.

Yes I am sure that they are quite nice if you are M$, IBM, SUN, Netscape,
...ect, and have millions of dollars to spend.

>> They do *not* release source code for their toolkits.

>Of course not. RSAREF is available as source. BSAFE and JSAFE represent
>considerable effort at improving on the reference implementation. Maybe
>they consider their source code to be intellectual property?

Why "of course not"? there is a simple adjudge in this field "No Source,
No Trust". I will not use and do not trust *any* crypto product that does
not come with *full* source code for review.

>> I find their licensing requirements unacceptable.

>I myself did balk at $2500 for a JSAFE license for my own work. If I were
>engaged in making a commercial product, I might have been able to
>justify the expense.

I have not looked at the JSAFE but last time I looked at BSAEF IIRC the
going price was $60,000 + royalties. Price alone was not a consideration,
more troubling was the licensing requirements. You can not license the use
of the RSA algorithm but you *must* license and use the BSAFE toolkit (or
one of their other toolkits all without source code). I find it *very*
troubling that the patent holders for an algorithm will only allow it's
use via a Toolkit that no one has seen the source code for.

>
>> IMHO I have not seen anyone present a good case to use RSA over ElGamal.

>I guess it just depends on what you're willing to accept. Installed base
>is one reason. RSADSI happens to be a good supplier of information and
>an enthusiastic advocate for strong encryption.

Well that are an enthusiastic advocate for *selling* encryption, strong or
not. They have no problem selling weak crypto for use in SSL libraries and
their S/MIME protocol included the use of weak 40bit crypto (was an actual
MUST in the original drafts). While that may talk a good talk about
supporting strong crypto they don't have second thoughts about selling
weak crypto.

- --
- ---------------------------------------------------------------
William H. Geiger III http://www.openpgp.net
Geiger Consulting Cooking With Warp 4.0

Author of E-Secure - PGP Front End for MR/2 Ice
PGP & MR/2 the only way for secure e-mail.
OS/2 PGP 5.0 at: http://www.openpgp.net/pgp.html
Talk About PGP on IRC EFNet Channel: #pgp Nick: whgiii
- ---------------------------------------------------------------

Tag-O-Matic: Windows is to OS/2 what Etch-a-Sketch is to art.

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i OS/2 for non-commercial use
Comment: Registered_User_E-Secure_v1.1b1_ES000000
Charset: cp850

wj8DBQE25YftlHpjA6A1ypsRAp4oAJ9PVZzQZpXbHWeBML2+K9PnLjYZPwCgv9dr
XFRxpxlL/rJAnXWKtNu2caQ=
=UlX8
-----END PGP SIGNATURE-----


ssim...@hertreg.ac.uk

unread,
Mar 9, 1999, 3:00:00 AM3/9/99
to
In article <36E566...@physiology.wisc.edu>,

Would I dare offer such advice on sci.crypt without a citation ;-)

"Discrete logarithms in finite fields and their cryptographic significance"
A.M.Odlyzko

Though this paper may pre-date EC based systems.......

Regards,

Sam

Daniel Bleichenbacher

unread,
Mar 10, 1999, 3:00:00 AM3/10/99
to
RSA has definitively the advantage over ElGamal encryption/signatures
that good standards for RSA (IEEE, ANSI, PKCS) are available. I'm not
aware of a good standard for either ElGamal signatures or ElGamal
encryption. I'm not talking about derivated algorithms, such as DSA or
elliptic curve ElGamal encryption, which have been included into
standards. I'm talking about the original schemes proposed by ElGamal.

When no standard is available people design there own ad-hoc schemes,
and usually there are enough pitfalls to go wrong. That's the case for
the ElGamal schemes too. For example, let p be the prime modulus for
an ElGamal encryption, g be a generator of the multiplicative subgroup
mod p and y=g^x (mod p) be Alice's public key. Encrypt M by choosing k
randomly, compute A=g^k (mod p) and B=M*y^k (mod p) and send the
ciphertext (A,B). It is well known that, ElGamal encryption is
malleable, i.e. assume Eve has an encryption (A,B) but does not know
the plaintext M. Then she can nevertheless compute (A,cB (mod p)) and
she knows that this new ciphertext is an encryption for cM (mod p).

So, is this a problem?
It should be noted that the property above is exactly the property
that could be used against the PKCS #1 version 1.5 (= old version
of the RSA standard) and SSL. Hence, if someone would come up
with the idea to use PKCS #1 version 1.5 padding for ElGamal
encryption then he would face the same chosen message attacks
that were possible against some SSL implementations.

There are problems with ElGamal signatures, that have to be avoided
too. I'm not saying RSA as a trapdoor one-way function is stronger
than ElGamal or vice versa. But as an implementor I'd certainly
prefer RSA, because there are standards available that tell me
how to avoid pitfalls. And this is what finally will count.

Daniel Bleichenbacher
--
Daniel Bleichenbacher
Bell Laboratories
600 Mountain Av.
Murray Hill, NJ 07974

DJohn37050

unread,
Mar 10, 1999, 3:00:00 AM3/10/99
to
I would say that the correct comparison to make is the hard problem each is
based on. There are papers on how to do all these things in good way for all
hard problems.

For ANSI X9.30 defines DSA (DL), X9.31 defines rDSA (RSA and RW sigs) and X9.62
defines ECDSA, all are now ANSI standards. X9.42 defines DL-based key
agreement, X9.44 defines RSA key establishment and X9.63 defines EC key
establishment, all are drafts going thru the standardization process.

IEEE P1363 defines IF (RSA/RW), DL, and ECC signatures and RSA encryption and
DL/ECC key agreement. P1363a is expected to define RSA key agreement and DL/EC
encryption.

ISO DIS 14888-3 defines RSA/RW, DSA and ECDSA signature standards. These are
more general than ANSI, if one meets the ANSI standard then one will meet the
ISO standard, but not necessarily vice versa.
Don Johnson

bo...@rsa.com

unread,
Mar 11, 1999, 3:00:00 AM3/11/99
to
In article <36E566...@physiology.wisc.edu>,
Medical Electronics Lab <ros...@physiology.wisc.edu> wrote:
> Sam Simpson wrote:
> >
> > BTW does anyone still use GF(2^n)? It said as long as 14-years
> > ago that GF(2^n) ought to be avoided in all cryptographic
> > applications - who would still consider it in the same breath as
> > GF(p)?
> >
> > Look forward to any pointers to more recent literature you may be
> > able to provide.
>
> Check out "Elliptic Curve Public Key Cryptosystems" for use of
> GF(2^n). Who said it should be avoided? Have you got a reference
> for that?


The discussion is about using GF(2^n) itself for ElGamal, not Elliptic
Curves over GF(2^n). Coppersmith's algorithm applied to the former makes it
unsuitable for cryptographic use.

I am one such reference.

Roger Schlafly

unread,
Mar 11, 1999, 3:00:00 AM3/11/99
to

bo...@rsa.com wrote in message <7c9kgt$3a$1...@nnrp1.dejanews.com>...

>The discussion is about using GF(2^n) itself for ElGamal, not Elliptic
>Curves over GF(2^n). Coppersmith's algorithm applied to the former makes
it
>unsuitable for cryptographic use.

I don't agree with this. Coppersmith's algorithm has the same asymptotics
as the best factoring method. For a given key size, DH over GF(2^n) is
slight less secure than RSA, but users can compensate for this by
choosing a larger key size. It is analogous to the way RSA users
have to choose a larger key size those using than DH over GF(p),
for equivalent security.


Roger Schlafly

unread,
Mar 12, 1999, 3:00:00 AM3/12/99
to

bo...@rsa.com wrote in message <7ccn0j$ltm$1...@nnrp1.dejanews.com>...
> [usual ad hominem attack snipped]

>> Coppersmith's algorithm has the same asymptotics
>> as the best factoring method.
>
>Wrong. The constant for Coppersmith's algorithm is (32/9)^1/3.
>The best factoring algorithm for RSA keys has constant (64/9)^1/3.

I was ignoring the constant. Your statement implied that DL over GF(2^n)
was easy.

>> For a given key size, DH over GF(2^n) is
>> slight less secure than RSA, but users can compensate for this by
>

>No!!! It is significantly less secure. DL over GF(2^1024) is almost
>within reach now. DL over GF(p) where p is an odd 1024-bit prime is NOT
>in reach.

DL over GF(p), p = 1024 bit prime, is more secure than 1024 bit RSA.
1024-bit RSA is more secure than DL over GF(2^1024). Agree? Good.

If someone wants to use DL over GF(2^n), and his application is such
than n = 1024 is not safe enough, then he can pick n = 2048 or even
a larger value, if he wishes.


bo...@rsa.com

unread,
Mar 13, 1999, 3:00:00 AM3/13/99
to
In article <7ca2r5$p...@enews1.newsguy.com>,

"Roger Schlafly" <schl...@cruzio.com> wrote:
>
> bo...@rsa.com wrote in message <7c9kgt$3a$1...@nnrp1.dejanews.com>...
> >The discussion is about using GF(2^n) itself for ElGamal, not Elliptic
> >Curves over GF(2^n). Coppersmith's algorithm applied to the former makes
> it
> >unsuitable for cryptographic use.
>
> I don't agree with this.

You don't know enough about the subject to agree or disagree.


> Coppersmith's algorithm has the same asymptotics
> as the best factoring method.

Wrong. The constant for Coppersmith's algorithm is (32/9)^1/3.
The best factoring algorithm for RSA keys has constant (64/9)^1/3.

Solving DL's over GF(2^n) via Coppersmith's algorithms is a lot easier than
solving DL over GF(p) using the Number Field Sieve to EXACTLY the same extent
that factoring 2^n-1 is easier via the Special Number Field Sieve than is
factoring N = pq by the General Number Field Sieve.

Next time I suggest you read about the subject before making such
pronouncements.

> For a given key size, DH over GF(2^n) is
> slight less secure than RSA, but users can compensate for this by

No!!! It is significantly less secure. DL over GF(2^1024) is almost
within reach now. DL over GF(p) where p is an odd 1024-bit prime is NOT
in reach.

-----------== Posted via Deja News, The Discussion Network ==----------

Michael Sierchio

unread,
Mar 13, 1999, 3:00:00 AM3/13/99
to
Daniel Bleichenbacher wrote:
>
> RSA has definitively the advantage over ElGamal encryption/signatures
> that good standards for RSA (IEEE, ANSI, PKCS) are available.

Bingo.

> When no standard is available people design there own ad-hoc schemes,
> and usually there are enough pitfalls to go wrong.

Ditto.

Michael Sierchio

unread,
Mar 13, 1999, 3:00:00 AM3/13/99
to
bo...@rsa.com wrote:

> > For a given key size, DH over GF(2^n) is
> > slight less secure than RSA, but users can compensate for this by
>
> No!!! It is significantly less secure. DL over GF(2^1024) is almost
> within reach now. DL over GF(p) where p is an odd 1024-bit prime is NOT
> in reach.

Bob -

My news host is expiring these posts faster than I can read them --
I may have missed something.

Can you answer the following:

If you select a large p for GF(p), does the choice of
a generator g for g^x mod p matter, so long as it is
a generator of GF(p)? It's often said that it is not
necessary for g to be a generator of the whole field,
but it is better.

Why (esp. when 2 is used as a generator) is p selected
such that (p-1)/2 is also prime?

Roger Schlafly

unread,
Mar 13, 1999, 3:00:00 AM3/13/99
to

Michael Sierchio wrote in message <36EAAAD7...@dnai.com>...

>Daniel Bleichenbacher wrote:
>>
>> RSA has definitively the advantage over ElGamal encryption/signatures
>> that good standards for RSA (IEEE, ANSI, PKCS) are available.
>
>Bingo.

This is really a silly statement. The standardization work in ANSI and
IEEE for ElGamal-like signatures predated that for RSA. The most
popular ElGamal variant is commonly called DSA. As Johnson pointed
out, there are perfectly good standards for DSA and there have been
for years.

Bleichenbacher knows this, but argues that DSA and ECDSA are
"derivated algorithms", while PKCS #1 version 1.5. I am not sure this
distinction makes any sense, but it is useless even if it does.


Roger Schlafly

unread,
Mar 13, 1999, 3:00:00 AM3/13/99
to

bo...@rsa.com wrote in message <7cf8k4$mg2$1...@nnrp1.dejanews.com>...
>Asserting that someone does not have the technical background to
>provide an opinion on some subject is not an ad hominem attack.

My dictionary defines "ad hominem" as:
1 : appealing to feelings or prejudices rather than intellect
2 : marked by an attack on an opponent's character rather than by an answer
to the contentions made
http://www.m-w.com/

I have a PhD in Mathematics from U. California at Berkeley. How much
additional background is required to have an opinion on this subject?

>> Your statement implied that DL over GF(2^n) was easy.
>

>I said no such thing. The only easy problems in CS are polynomial time.
>I never said Coppersmith's algorithm is in P. What I said was that
>solving DL over FG(2^n) is significantly easier than DL over GF(p) for
>n ~ log(p).

And you also said:

"Coppersmith's algorithm applied to the former [GF(2^n)] makes it
unsuitable for cryptographic use."

Your statement is wrong. It might be correct if DL over GF(2^n) were
easy, but Coppersmith's algorithm leaves many reasonable values of n
outside its practical range.


>> If someone wants to use DL over GF(2^n), and his application is such
>> than n = 1024 is not safe enough, then he can pick n = 2048 or even
>> a larger value, if he wishes.
>

>And slow down encryption/decryption by at least a factor of 4 in the
process.
>And take up more space in certificates. And more bandwidth in key
exchange.

All of which might be mitigated by other factors in a particular
application.
After all, some people still use RSA even though EC has much lower
bandwidth.


bo...@rsa.com

unread,
Mar 14, 1999, 3:00:00 AM3/14/99
to
In article <36EAAA9B...@dnai.com>,

ku...@dnai.com wrote:
> bo...@rsa.com wrote:
>
> > > For a given key size, DH over GF(2^n) is
> > > slight less secure than RSA, but users can compensate for this by
> >
> > No!!! It is significantly less secure. DL over GF(2^1024) is almost
> > within reach now. DL over GF(p) where p is an odd 1024-bit prime is NOT
> > in reach.
>
> Bob -
>
> My news host is expiring these posts faster than I can read them --
> I may have missed something.
>
> Can you answer the following:
>
> If you select a large p for GF(p), does the choice of
> a generator g for g^x mod p matter, so long as it is
> a generator of GF(p)?

No, it doesn't matter.

> It's often said that it is not
> necessary for g to be a generator of the whole field,
> but it is better.
>
> Why (esp. when 2 is used as a generator) is p selected
> such that (p-1)/2 is also prime?


There are attacks which work in small(er) subgroups that are more efficient
than solving a DL problem over the entire group. One wants the group
the DL problem resides in to be as large as possible.

bo...@rsa.com

unread,
Mar 14, 1999, 3:00:00 AM3/14/99
to
In article <7cd013$i...@enews1.newsguy.com>,

"Roger Schlafly" <schl...@cruzio.com> wrote:
>
> bo...@rsa.com wrote in message <7ccn0j$ltm$1...@nnrp1.dejanews.com>...
> > [usual ad hominem attack snipped]

Asserting that someone does not have the technical background to


provide an opinion on some subject is not an ad hominem attack.

How many DL problems have you solved?

> >> Coppersmith's algorithm has the same asymptotics
> >> as the best factoring method.
> >
> >Wrong. The constant for Coppersmith's algorithm is (32/9)^1/3.
> >The best factoring algorithm for RSA keys has constant (64/9)^1/3.
>

> I was ignoring the constant.

Which shows why you don't know what you are talking about.
If T is the time for breaking RSA with NFS, then the time to break
a DL for GF(2^n) for the same sized problem is T^ (cuberoot of 1/2) ~
T ^ .79


> Your statement implied that DL over GF(2^n) was easy.


I said no such thing. The only easy problems in CS are polynomial time.
I never said Coppersmith's algorithm is in P. What I said was that
solving DL over FG(2^n) is significantly easier than DL over GF(p) for
n ~ log(p).

> >> For a given key size, DH over GF(2^n) is


> >> slight less secure than RSA, but users can compensate for this by
> >
> >No!!! It is significantly less secure. DL over GF(2^1024) is almost
> >within reach now. DL over GF(p) where p is an odd 1024-bit prime is NOT
> >in reach.
>

> DL over GF(p), p = 1024 bit prime, is more secure than 1024 bit RSA.

The time difference is insignificant. And is platform and implementation
dependent.With respect to CPU time, they are virtually the same. What makes
DL slightly harder than factoring is that for DL, the matrix must be solved
mod p, rather than mod 2. This takes a factor of log p more SPACE and a
constant factor (depending on the wordsize of the machine solving the matrix)
more time to solve the matrix. The sieving times are virtually the same.

This is what I referred to earlier when I said that DL for odd fields was
harder than the equivalent sized factoring problem. Solving the matrix
requires much more SPACE.

People seem to forget that CPU time is not the only resource required by these
algorithms.


> 1024-bit RSA is more secure than DL over GF(2^1024). Agree? Good.
>

> If someone wants to use DL over GF(2^n), and his application is such
> than n = 1024 is not safe enough, then he can pick n = 2048 or even
> a larger value, if he wishes.

And slow down encryption/decryption by at least a factor of 4 in the process.
And take up more space in certificates. And more bandwidth in key exchange.


Of course one can always use larger keys. At a cost.

Wei Dai

unread,
Mar 14, 1999, 3:00:00 AM3/14/99
to
In article <7cf8k4$mg2$1...@nnrp1.dejanews.com>, bo...@rsa.com says...

> The time difference is insignificant. And is platform and implementation
> dependent.With respect to CPU time, they are virtually the same. What makes
> DL slightly harder than factoring is that for DL, the matrix must be solved
> mod p, rather than mod 2. This takes a factor of log p more SPACE and a
> constant factor (depending on the wordsize of the machine solving the matrix)
> more time to solve the matrix. The sieving times are virtually the same.

Ok, that explains why DL results have lagged so far behind factoring
results - it must be hard to get time on computers with that much
memory.

However I don't understand why it takes only a contant factor more time
to solve a matrix mod p instead of mod 2. Shouldn't it take at least a
factor of log p more time? I guess most of the time in matrix solving is
spent on multiplying integers mod p, so the factor should be closer to
(log p)^2.

Andrew Haley

unread,
Mar 15, 1999, 3:00:00 AM3/15/99
to
bo...@rsa.com wrote:
: In article <7cd013$i...@enews1.newsguy.com>,

: "Roger Schlafly" <schl...@cruzio.com> wrote:
: >
: > bo...@rsa.com wrote in message <7ccn0j$ltm$1...@nnrp1.dejanews.com>...
: > > [usual ad hominem attack snipped]

: Asserting that someone does not have the technical background to
: provide an opinion on some subject is not an ad hominem attack.

Certainly not.

However, if you argue against some assertion by attacking the person
who made the assertion, then you have committed the abusive form of
argumentum ad hominem. A personal attack isn't a valid argument,
because the truth of an assertion doesn't depend on the virtues of the
person asserting it.

Andrew.
[Lifted from mathew's alt.atheism FAQ]

Daniel Bleichenbacher

unread,
Mar 15, 1999, 3:00:00 AM3/15/99
to
In article <7cegq4$ktg$1...@camel25.mindspring.com>,

Let me try to clarify my previous post here.
As pointed out there are good standards by IEEE, ANSI, etc for
DL based cryptosystems. There is no doubt that DL based
have received similar attention as RSA and that the
standards committees have done a good job creating DL based
standards.
Just, these schemes are not called ElGamal and the
original question was about a comparison of ElGamal
vs. RSA. Now, for RSA encryption we can find standards
using OAEP, whereas (to my knowledge) no such standard
for ElGamal encryption has been proposed. The best, I know,
is the ElGamal encryption included in the openpgp standard.
This one uses a simple 2 byte checksum and hence is at
most marginally secure against chosen ciphertext attacks.
Hence, I still prefer RSA over ElGamal because of the
standards situation.
RSA vs. DLSVDP-DH or DHES is a different question.

Reply all
Reply to author
Forward
0 new messages