Quote from: jonald_fyookball on April 27, 2017, 03:09:01 AM

Quote from: aso118 on April 27, 2017, 01:59:30 AM

Quote from: phatsphere on April 26, 2017, 11:06:47 PM

Bitcoin has nothing to do with prime numbers.

I am not an expert, but doesn't the private key-public key combination involve prime numbers in some sense?
Irrespective of that, I don't believe prime factorization can be cracked.

RSA does. Not ECDSA.

Indeed. One of the reasons to switch from RSA to ECDSA was exactly that elliptic groups are not sensitive to solving the prime factorisation problem. However, there are links between *some* elliptic groups and the prime factorisation problem. Some classes of elliptic groups are known where the difficult discrete logarithm problem can be reduced to a factorisation problem, and these should *not* be used for ECDSA, and are usually called "weak elliptic curves". The problem is that nobody knows if there are not *other*, not (publicly?) known classes of elliptic groups that are weak in such a sense. In fact, in order to *test* for some known classes of weak groups (so as to avoid them), one actually has to solve the factorisation problem in the group, but as ECDSA groups are way, way smaller than RSA type groups (see key size: 256 bits vs 3072 bits for RSA for the same level of security), this is actually feasible: it also shows the problem if ever there's a discovered link, because it can be done.

There's an interesting story about the class of curves from which Satoshi picked the one for bitcoin: secp256k1. NIST published standard curves to be used. One class are "Koblitz curves", and are a very peculiar class of curves, there's not much choice about them. secp256k1 is one such curve. The potential problem with them is that they are a specific mathematical class of which extra properties may induce vulnerabilities.
A reasoning was that if "special classes" are to be avoided because their special properties may help mathematicians to break them, the best to do is to select *random* curves. So NIST also published random curves, like secp256r1. However, they didn't really explain HOW they chose them "randomly" (well, they used a hash function, but they used a seed value fallen from the sky with no explanation). So people got wary about them: they may in fact be "randomly" chosen in a very specific way, that could be broken. Nobody knows. But these may also have been really honestly chosen random curves, at which point they would most probably be more secure than the "k" variants.

There's an interesting read on that here:
https://crypto.stackexchange.com/questions/18965/is-secp256r1-more-secure-than-secp256k1

In fact, if you're paranoid, it would have been better to avoid the NIST curves all together. At bitcoin's invention time in 2008, there were provably random curves available already, like brainpool curves:
http://www.ecc-brainpool.org/

That said, most probably secp256k1 is more than good enough for what bitcoin wants to do.