[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index][Thread Index]

From: | <nega@xxxxxxxxxxxxxx> |

Date: | Thu, 20 Jan 2005 12:57:44 -0500 |

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.

**Follow-Ups**:**Re: RSA vs DSA***From:*walt

**References**:**RSA vs DSA***From:*Jonathon McKitrick

**Re: RSA vs DSA***From:*Joerg Sonnenberger

**Re: RSA vs DSA***From:*Kris Maglione

**Re: RSA vs DSA***From:*Joerg Sonnenberger

**Re: RSA vs DSA***From:*nega

**Re: RSA vs DSA***From:*Atte Peltomaki

[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index][Thread Index]