Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

What are the increased possibilities (if any) of being able to crack a private key given the following:

  1. The associated bitcoin (ECDSA Secp256k1-based) public key is known.
  2. The private key has been used to generate a public key from a different ECDSA curve and that public key is also known.
  3. It is known that the two public keys are derived from the same private key.
  4. It is known which ECDSA curves were used to generate the public keys.
  5. It is known which ECDSA curve was used to generate which public key.

Does it make any more difference if there is data that is known to have been signed by the private key and the signature(s) are known and the raw data is known?

EDIT: I should have pointed out that the conditions are ANDed, I.e. All conditions are known. Sorry, I should have been clearer the first time.

share|improve this question

1 Answer 1

I'll start with the last point and use the notation for ECDSA from the wikipedia article.

Does it make any more difference if there is data that is known to have been signed by the private key and the signature(s) are known and the raw data is known?

When using a digital signature scheme, the parameters (used group, e.g., elliptic curve group) as well as the public key, signatures and all corresponding messages are public knowledge and a secure digital signatures scheme needs to be even secure if the adversary is allowed to obtain signatures for arbitrary messages of its choice (ECDSA is secure against such existential forgeries under adaptively chosen message attacks if the used hash function is collision resistant - AFIK the proof is in the generic group model, but should still give enough evidence that it is secure).

In ECDSA your private key $d_A$ is an integer from $Z_q^*$, i.e., from the set of integers $\{1,\ldots,p-1\}$, where $q$ is the order of your elliptic curve group and your public key is a point $Q_A=d_A\cdot G$ on the curve where $G$ is a generator of your elliptic curve group and part of the public parameters.

The problem you are focused when you want to extract the private key $d_A$ from a given public key $Q_A$ is the elliptic curve discrete logarithm problem (ECDLP). Consequently, ECDSA must be used with an elliptic curve group where the ECDLP is hard enough (also excluding curves that allow efficient pairings to reduce the ECDLP to the DLP in a related field (MOV attack). But this is not the case if you use standardized curves such as SEC or NIST curves).

Observe also, that when you want to extract the private key from a given signature you also have to break the ECDLP for point $kG$.

So for your question you have different public keys $d_A\cdot G_1, \ldots d_A\cdot G_n$ on $n$ different curves, where the public keys share the same private key $d_A$. Additionally, you may know corresponding message-signatures pairs.

Then, to recover the private key you can use either the public key or the signatures you have available on every curve separately, as you cannot do arithmetic between points on different curves. Even if it happens that there are efficient mappings between the curves, then you could simply take a single public key (e.g., of someone else) and map it to all the other curves and this attack would then also apply to a "single public key setting". Consequently, you rely on the strength of the ECDLP on the weakest of your $n$ used curves and from my point of view the most efficient way to recover the private key in this scenario is to attack the ECDLP on the weakest of the used curves.

In general, when using ECDSA it is far more dangerous to re-use the randomness $k$ when producing signatures on the same curve, as two signatures for different messages with same $k$ allows to recover the private key instantaneously as it happened to Sony back in 2011.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.