Quote from: ByteCoin on May 30, 2011, 11:12:55 PM

Quote from: gmaxwell on May 30, 2011, 10:37:23 PM

RSA-512 is horribly week, many people (including myself) have cracked it on their own at home.

.... and while I can trivially crack RSA-512 at home ....

That's a very interesting claim considering that the a 512 bit factorization would come in at number 5 on the GNFS records page on
http://xyyxf.at.tut.by/records.html#gnfs

If you can really factor 512 bit numbers trivially, then the project would greatly benefit from your ability.
Please let me know the size and weight of an average matrix for the linear algebra step for your 512-bit factoring program.

I think may be misunderstanding what I meant by 'trivally'. I can't do it in under a day, for example. Using EC2 prior to spot pricing I cracked RSA-512 for about $160 for the sieveing step and then did the linear algebra at home. in the total of about ~40 hours.

It only takes about 4gb memory or so for the linear algebra. On some random _single core_ machine, e.g. not using the MPI block-wiedemann you can extract a candidate solution in an hour or two once you've done enough sieving.

I can do the whole process at home in about three days now though I'm perhaps a bit more overpowered compared to most homes. Wink

I'll gladly prove this to you in private (e.g. by signing a message using a key or two I previously compromised from the pgp well connected set), if you'll share confirmation of this with the forum.

The point being RSA-512 is too weak for any non-ephemeral usage, and yet even if bitcoin was using it right now it wouldn't be completely fatal to the system, but sure as hell would be if the public keys were disclosed. E.g. The coin at 1PZjfkLZBT7Q3UFmyEWH8QtuzTMi3MUiBj would be mine by now if the system used RSA-512 and the public key were disclosed. But without they public key I'd still be stuck even though I can compromise RSA-512.

Quote

Quote from: gmaxwell on May 30, 2011, 10:52:17 PM

I mean we already know how to compromise ECDSA in about 4 billion operations. It's "Just an engineering problem".

Even using the British "billion" = million million, 4 billion operations is less than a 42 bit keyspace. Please outline the attack you have in mind.

Modified Shor's algorithm on the EC discrete logarithm problem of n=256bits takes a system of around 1500 error free q-bits (god knows how many for a error correcting system) and something like 6e9 operations (http://cdsweb.cern.ch/record/602816/files/0301141.pdf). I was _abundantly clear_ than I am not claiming that there _currently exists_ an effective attack, and that the benefit was purely a theoretical reduction in brittleness. At the same time no one of any repute is arguing that large scale quantum systems are physically impossible, we just don't know how to build one yet.

Publickeyhash raises a point I hadn't considered: I'd thought of the collision attack as being both a full collision across the big composite hash _and_ a ecc compromise, I hadn't considered the possibility of colliding to a weak key. Thats interesting. I'm cluessless about how common weak keys would be on the curve bitcoin uses.