307 digit number factored

[Nate Lawson]

travis+ml-cryptography at subspacefield.org wrote:
> On Mon, May 21, 2007 at 04:32:10PM -0400, Victor Duchovni wrote:
>> On Mon, May 21, 2007 at 02:44:28PM -0400, Perry E. Metzger wrote:
>>> My take: clearly, 1024 bits is no longer sufficient for RSA use for
>>> high value applications, though this has been on the horizon for some
>>> time. Presumably, it would be a good idea to use longer keys for all
>>> applications, including "low value" ones, provided that the slowdown
>>> isn't prohibitive. As always, I think the right rule is "encrypt until
>>> it hurts, then back off until it stops hurting"...
>> When do the Certicom patents expire? I really don't see ever longer RSA
>> keys as the answer, and the patents are I think holding back adoption...
> 
> They already expired.

Not true (counterexample: ECMQV).

> Some EC primitives in the latest OpenSSL.

Because various standard forms of EC were never covered by patents.
This has been rehashed many times, for example:
http://www.xml-dev.com/pipermail/fde/2007-July/000450.html

> But why assume short ECC keys are stronger than long RSA?
> 
> AFAIK, the only advantage of ECC is that the keys are shorter.
> The disadvantage is that it isn't as well studied.

Again, this is well covered.  The reason is the fundamental difference
in the performance of the best-known attacks (GNFS vs. Pollard's rho).
http://www.vaf.sk/download/keysize.pdf

Also, EC public operations are typically faster than private, although
not on the order of the difference between RSA public and private ops.

> Although every time I read up on ECC, I understand it, and then within
> a few days I don't remember anything about it.  I think they teflon
> coated those ideas somehow, because they don't stick.
> 
>> With EECDH one can use ECDH handshakes signed with RSA keys, but that
>> does not really address any looming demise of 1024 bit RSA.
> 
> Why can't they do something like El-Gamal?
> 
> I'm not comfortable with RSA somehow.  It seems fundamentally more
> complicated to me than DLP, and it's hard to get right - look at how
> many things there are in the PKCS for it.

The RSA or EC primitives are *not* usable cryptographic schemes by
themselves, thus it isn't fair to compare them this way (RSA+PKCS#1 !=
EC point multiplication).

ECDSA, for example, is intentionally constrained to be signing-only and
the hash signed is a fixed size.  It's more fair to compare RSA+PKCS#1
with EC+DSA/DH.  In that sense, I think the complexity of implementation
is similar.

I'm not saying that one of these schemes is better than the other.  They
each have their own tradeoffs.  I just object to your methodology of
claiming RSA is fundamentally more problematic than EC.

-- 
Nate

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com