# RSA key-gen???

Jack McKinney jackmc-gnupg-users@lorentz.com
Thu, 21 Sep 2000 09:54:52 -0500

```-----BEGIN PGP SIGNED MESSAGE-----

Big Brother tells me that Simpson, Sam wrote:
> For a start:  Elgamal keys are (currently thought to be...) stronger than
> RSA keys of the same size?
>

This document is a good example of what I was talking about.
Go to this link to verify the following:

Paragraph 3:
% It is, in fact, slightly harder to compute discrete logs modulo an
% appropriate prime than to factor a "hard" integer of the same size -
% so RSA would appear slightly weaker than DHP [Odl95], [Sch97c]. From
% [Sch99a]: "RSA users have to choose a larger key size those using than
% DH over GF(p), for equivalent security.

Paragraph 7:
% Another relevant quote [Wie98]: "The most important factor in choosing a
% public-key technology is security. Based on the best attacks known, RSA
% at 1024 bits, DSA and Diffie-Hellman at 1024 bits, and elliptic curves
% at about 170 bits give comparable levels of security.

"slightly weaker".  "comparable levels of security".

I point out that this part of the article is talking about DH, not
ElGamal.  They are NOT the same thing.  DH is a methodology of key exchange
that depends on selection of a finite group.  From earlier in the FAQ:

% ... ElGamal [ElG85], which is a public-key encryption variant of the
% Diffie-Hellman Problem (DHP)

...

% The security of the DH system is based upon the DH Problem (DHP). This
% problem is conjectured (but not proven) to be equivalent to the Discrete
% Logarithm Problem (DLP)

...

% DHP is equivalent to the DLP under the "Diffie-Hellman assumption"

Earlier in the article, it talks about the downsides of DH:

% b.Signature Strength. Current implementations of DH only offer DSS as
% the signature algorithm. This limits key length to 1,024-bits which may,
% on its own, be insufficient for long term security. RSA signatures utilise
% a key of up to 2048 or 4096 bits (depending on the implementation).

The only significant entries in the contrast (the downside of RSA) are:

% d. RSA offers less "security-per-bit" of key material than both DH/DSS.
% e. DH appears to be based upon more solid mathematical theory (see the
%    section "Any recent developments?" for details).

For my opinion on these, see the earlier quotes.  As for the other
downsides, a) is defunct as of Sep 6; b) does not apply if you don't
choose to shoot yourself in the foot as it describes (key signing and
trust prevent a man-in-the-middle exploit of this); c) does not apply
in a document signing situation (though ssh has been using it anyway);
and f) is an implementation issue.  What if _I_ want to save the
transactions.  With DH, I can encrypt the data on my end, but then
someone could _still_ coerce my encryption key...

I could go on for a while on this.  I have not taken the time yet
to study ElGamal mathematically (I am a mathematician), so I have no
inherent opinion.  The opinions I give above are just a demonstration
of how the FAQ is dancing around the security issue.  Somewhere in
that FAQ (I need to look again) is a paragraph that really made me
wary of using GnuPG.  If I find it, I'll post it.

- --
"Of course its your fault. Everything that goes wrong  Jack McKinney
-Quark to his brother Rom, DS9                http://www.lorentz.com
F4 A0 65 67 58 77 AF 9B  FC B3 C5 6B 55 36 94 A6

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBOcohJEZx0BGJTwrZAQFPtwP+If0CYDOmB5p2A51Suf0BbJbh3O8JZdV6
gGTxwsux6yehoSg6zNWqD8mz5kTruAxSV/ItJSOlct/pSC445SCGCEHGioFdIdwv
/KDy3XDrnW9vO/uICIcy696aTcFue2HYYotY0gHBwtcfq3EmxtFUsfgOS+jsNCHv
jhWlUxaYziw=
=UKZi
-----END PGP SIGNATURE-----

--
Archive is at http://lists.gnupg.org - Unsubscribe by sending mail
with a subject of  "unsubscribe"  to gnupg-users-request@gnupg.org

```