RSA vs DSA

[nega at exmachinae.net]

Atte Peltomaki writes:
 > 
 > I gathered from the rsasecurity.com docs that there is a technique to
 > break RSA, but as of today it has not been succesfully incorporated.
 > Which to my understanding would mean that RSA is a bad choice of
 > algorithm when thinking about the future, when someone figures out how
 > to (easily) use the technique.
 > 
 > ..of course I could've as well interpreted the text below completely
 > wrong..
 > 
 > *clip*
 > Another way to break the RSA cryptosystem is to find a technique to 
 > compute eth roots mod n. Since c = me mod n, the eth root of c mod n 
 > is the message m. This attack would allow someone to recover encrypted 
 > messages and forge signatures even without knowing the private key. 
 > This attack is not known to be equivalent to factoring. No general 
 > methods are currently known that attempt to break the RSA system in 
 > this way. However, in special cases where multiple related messages 
 > are encrypted with the same small exponent, it may be possible to 
 > recover the messages.
 > *clip*
 > 
 > 
 > Atte


There is more than one way to "break" RSA. There is also more than one
way to "break" DSA, which I'll get to in a bit. I certainly wouldn't
call either a "bad choice", but one should always assess the risks of
using *any* crypto system.

Factorization of the public key can result in the discovery of the
private key. In the equation that you quote above (which should read c
= m^e mod n), c is the resulting ciphertext, m is the message to be
encrypted, e is part of the public key pair (the "exponent), and n is
the other part of the public key pair (the "modulus"). The number n is
also part of the private key pair. So, once n has been factored down
to it's two prime number components (p and q), d can be discovered
because e, d, p and q are trivially related. This is discussed in the
paragraph in the one before the *clip* you quoted.

Factorization is much easier than finding the e-th root of c mod n,
and with apropriatly chosen prime numbers, factorization is near
impossible. It would take more than just faster computers to make
factorization easier, since faster computers also make it easier to
choose larger and more prime numbers (and large prime numbers[1] are
the important components of RSA and defeating factorization). New
mathematical techniques would need to be discoverd that reduce
factorization time.

Of course there are otherways of "breaking" RSA. Guessed plaintext
attack, chosen ciphertext attack and chose message attackes all
involved comparing know messages or ciphertexts. One can also attack
the impementation of RSA (or any other crypto system.) And, there is
everyone's favorite method, social engineering.

Section 3.4.2 of rsasecurity.com's FAQ which follows the section I
previously posted, addresses the question "Is DSA secure?". In it,
they mention two specific weaknesses of DSA. 1.) that DSA uses the
computation of discrete logarithms with in a finite field. Attacking
this problem is about as efficient as calculting the "e-th root of c
mod n". IE: until they invent new math, don't bother. 2.) There are
known "weak primes" that will cripple DSA. This is similar to using
weak ISV's to defeat WEP. (Please note, I'm not comparing DSA's
security to WEP's!)

All encryption/signature methods can be 'broken'. Some will take more
time than others. Some will require new math to be invented. Many will
be implemented poorly. Do you trust the implementor of your method? 
The important things to consider when choosing any encryption or
digital signature method is what your (you as in the user of the
method) application of the method is, and what the value is of the
thing you're applying the message to.

If you want to keep a secret, don't share it.


Footnotes:

[1] An important part of the Prime Number Theorem
(http://mathworld.wolfram.com/PrimeNumberTheorem.html) states that the
number of primes less than or equal to n is asymptotically
n/ln(n). This means that the number of prime numbers of length 512 bits
or less is about 10^150, and that's a whole lot of anything.