[Gllug] RSA or DSA

Richard Jones rich at annexia.org
Mon May 16 13:36:56 UTC 2005


On Mon, May 16, 2005 at 01:32:12PM +0100, John Winters wrote:
> The utility ssh-keygen offers you the choice of RSA or DSA keys, with no
> default selection and no clues about why you might choose one over the
> other.
> 
> Can anyone offer any advice about which is the better choice, and why?

RSA is the "classic" public key encryption algorithm.  If you did a
degree in maths or CS then you probably learned exactly how it works.
It's been extensively studied.  It's well understood that the
difficulty of breaking it depends on the integer factorization problem
(IFP) - basically if I give you a very very large number (N), how
easily can you find two numbers (p and q) such that p * q = N.

RSA can be used for signing or encryption.

DSA (Digital Signature Algorithm) is a a US govt standard for signing,
invented by a former NSA employee.  Although it's specified just for
signing, you can also use it for encryption because signing and
encryption are just inverse operations for each other.  Difficulty of
breaking it depends on what's known as the discrete logarithm problem
(DLP), which is slightly more difficult to explain in layman's terms.
If you can solve the DLP, you can also solve the IFP.  However it is
not known if the reverse is true.  The upshot is that is someone finds
a fast way to factorize large integers, then they 0wn your RSA keys,
but they do not immediately 0wn your DSA keys.

However, it's very likely that the new maths created to solve the IFP
would also be applicable to solving DLP, since they are both similar
enough problems.  If someone did solve IFP, there would be a rapid
scramble away from both RSA and DSA to other techniques.

All this probably doesn't matter, because even the IFP is really
really hard.  Just think about it geometrically - I'm going to give
you a huge number of square bricks (N), and I want you to arrange them
into an exact rectangle (p*q), with no bricks left over.  Oh, and by
the way, the number of bricks I'm going to give you is similar to the
number of atoms in the universe.  Easy, right?

It's much more likely that bugs exist in the ssh daemon itself which
would expose you to attack.  If I was going to crack ssh, then I'd
concentrate on finding bugs (buffer overflows, poor implementation,
and the like) in the source code, rather than attacking the IFP or
DLP.

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com
-- 
Gllug mailing list  -  Gllug at gllug.org.uk
http://lists.gllug.org.uk/mailman/listinfo/gllug




More information about the GLLUG mailing list