Can you find the private key from a signed public key?
Satoshi [Dr. Wright] says:If the ephemeral key (k) has been reused in the signing of multiple keys or has a poorly designed RNG this is possible. The SN keys are public and block 9 was used in a transaction that leaves the Public Key visible and not just the Key hash.
http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.htmlNow, where a bitcoin address has not been used in the signing and movement of coin, the double hash of the public key does actually make the pubkey value secret and not able to be discovered (prior to use or other leakage).
The recovery of keys using a quantum computer is not possible in the near term and even was a 1,000,000 Qubit system developed, it would require months (or longer) of compute time.
There is a LOT of FUD around QC and cryptography. There is NO threat in the near term, and in contradiction to what is stated by many (using this as a reason to try to move to other protocols and away from the reference protocol), QC is not a means to suddenly crack ECDSA keys.
The following is the response from one of the scientists quoted by the Economist a few years back that lead to this BS:
Your article regarding D-Wave's demonstration of a "practical quantum computer", sets a new standard for sloppy science journalism. Most egregious is your assertion that quantum computers can solve NP-complete problems in "one shot" by exploring exponentially many solutions at once. This mistaken view was put to rest in the infancy of quantum computation over a decade ago when it was established that the axioms of quantum physics severely restrict the type of information accessible during a measurement. For unstructured search problems like the NP-complete problems this means that there is no exponential speed up but rather at most a quadratic speed up.
Your assertions about D-Wave are equally specious. A 16 qubit quantum computer has smaller processing power than a cell phone and hardly represents a practical breakthrough. Any claims about D-Wave's accomplishments must therefore rest on their ability to increase the number of qubits by a couple of orders of magnitude while maintaining the fragile quantum states of the qubits. Unfortunately D-Wave, by their own admission, have not even tested whether the qubits in their current implementation are in a coherent quantum state. So it quite a stretch to assert that they have a working quantum computer let alone one that potentially scales. An even bleaker picture emerges when one more closely examines their algorithmic approach. Their claimed speed up over classical algorithms appears to be based on a misunderstanding of a paper my colleagues van Dam, Mosca and I wrote on "The power of adiabatic quantum computing". That speed up unfortunately does not hold in the setting at hand, and therefore D-Wave's "quantum computer" even if it turns out to be a true quantum computer, and even if it can be scaled to thousands of qubits, would likely not be more powerful than a cell phone.
Umesh Vazirani
IF and I mean IF a 1 million QBit computer is made in my life time and this is a big if (equal to winning the lottery for the next 20 days without buying a ticket) then it will AT BEST take months if not decades to solve ECC.
Bitcoin addresses would need to have a system that can break ECC is seconds.
Such a system is NOT even theoretically possible.
So, please never listen to the FUD. Forget ideas such as Lamport Signatures. Bitcoin is as it is for a reason and the reason that these others who worry about science fiction did not create it is the reason we need to maintain it as the protocol was created.
It needs to be simple.
http://www.economist.com/blogs/theinbox/2007/02/quantum_computing_3Edit: Quantum computing is even less effective on the solutions to hashes.
The trouble that seems to be misunderstood is that a working Quantum computer cannot take an ECDSA signature and reverse this in a single operation as is proposed. All of the QC algorithms are multistep and multistage. The system needs to be reset following each process used in the calculation of a valid ECDSA Signature. This is not something akin to the existing methods used in computer science now.
We have current issues, thinking of possibilities out of theory 20 years hence is the least of the issues we face.
Edit 2: [oh, I can't get Satoshi to stop once he gets going]:
Just as a further edit:
http://www.nature.com/articles/npjqi201523In the Nature article, the talk of how a Billion Qbit quantum computer "could" possibly solve a 2000bit RSA key in a day.
This is still far smaller than a 256 Bit ECC based cryptosystem. The result is that the current research support the position I took in 2007. It is a shame we simply trust others to tell us what is true authoritatively rather than seeking the answers in a scientific manner.
