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

Re: SSH keys: DSA vs RSA (was: Alioth and SSH: restored)

On Thu, May 15, 2008 at 02:00:25AM +0200, Steinar H. Gunderson wrote:
On Wed, May 14, 2008 at 11:12:26PM +0000, brian m. carlson wrote:
If one can solve the Discrete Logarithm Problem, then one can
factor, but the reverse is not true.

This is the first time I've ever heard anyone claim this; I've seen people
and textbooks claim they're roughly equivalent, but not that this is a
one-way street. Do you have any references?

I read it somewhere, probably on a PGP forum, but apparently that was
incorrect.  According to http://portal.acm.org/citation.cfm?id=894497 :

  To summarize: solving the discrete logarithm problem for a composite
  modulus is exactly as hard as factoring and solving it modulo primes.

I stand corrected.

brian m. carlson / brian with sandals: Houston, Texas, US
+1 713 440 7475 | http://crustytoothpaste.ath.cx/~bmc | My opinion only
troff on top of XML: http://crustytoothpaste.ath.cx/~bmc/code/thwack
OpenPGP: RSA v4 4096b 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187

Attachment: signature.asc
Description: Digital signature

Reply to: