Quote from: porcupine87 on March 10, 2014, 08:30:32 PM

Quote from: DeathAndTaxes on March 10, 2014, 07:39:23 PM

Brute forcing a 256 bit ECDSA key (has 128 bit security) is infeasible

Sorry, why is it only 128bit security?

The fastest known algorithms to derive a private ECC key from the public key are O ( 2^(n/2) ) where n is key length. Now if the attacker ignores this faster solution and simply tried random (or sequential) private keys until a match was found then it would take much longer (2^256 not 2^128) however security is based on the fastest possible solution.

It is important to point out that the fastest algorithms require the PubKey to be known. If the PubKey is not known then the only method would be an exhaustive attack on the private key and computing the PubKey. This is another good reason to not reuse addresses (and thus the pubkey remains unknown).

Key size doesn't necessarily equal security.

All of these key/digest sizes have 128 bit security
128 bit AES (symmetric encryption)
128 bit SHA-2 (hashing algorithm)
256 bit ECC (public key cryptography - elliptical curve)
3,072 bit RSA (public key cryptography - Integer factorization)

Generally hashing algorithms and symmetric key systems have a security equal to their key length (unless they have vulnerabilities or weaknesses). However due to the nature of public key systems (the public key has a mathematical relationship to the private key) this not true for public key systems. The key size will always be larger than the effective security (or key strength). How much larger depends on how difficult it is to derive the private key from the public key. If you look at RSA and ECC you can see that to achieve the same security RSA requires much larger keys (and signatures). This makes ECC based systems more useful in decentralized systems like Bitcoin.