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.

I understand that the public key does not expose the private key. That is not the question.

The question is: Given a EC public key, can a different, but plausible and functional private key be derived to match the public key?

In other words:

In basic arithmetic, if you know a x b = c, and you know any two variables, then you can calculate the third. But in ECC, we have a public key q, a well known point G, and a private number d. The public key is derived from the private key by ECPoint q = CreateBasePointMultiplier().Multiply(parameters.G, d);. I have to assume Multiply is a special form of multiplication, such that knowing q and G do not result in knowing d. Maybe it's essentially looping over a finite field many times over, or something like that. But could a different private key be selected that would result in the same public key?

In other words, specifically, let Alice and Bob both have ECDH keypairs, and exchange public keys. They each remember the other's public key for later authentication. When somebody claims to Alice "I am Bob, and here's my public key," then Alice confirms the public key matches what she remembers, and she challenges him, "Ok, prove it. Here is my (Alice) public key. Use it to derive our shared secret, and HMAC sign the following challenge. Send me back the result as a challenge response. If you can do that, you must know your private key corresponding to the exposed public key." Could Eve capture Bob's public key, then derive some different private key to correspond to it, and then impersonate Bob by saying "I am Bob, and here's my public key." Even though Eve doesn't have Bob's private key, she's able to produce some other private key that's compatible with Bob's public key?

share|improve this question

3 Answers 3

up vote 4 down vote accepted

Given a EC public key, can a different, but plausible and functional private key be derived to match the public key?

No, a public key will correspond to only one private key (with one minor exception, which I will explain below). With Elliptic Curve systems, the private key is an integer $d$ between 1 and $q$ (the order the generator point $G$), and the public key is most commonly the point $dG$, which defined to be $\underbrace{G + G + ... + G}_\text{d copies}$.

Now, the order of the generator has this property: all multiples less than the order will be distinct. That is, if we consider the sequence of points $G, 2G, 3G, 4G, ..., (q-1)G, qG$, there will be no duplicates in that sequence. What this means is that, since a public key occurs somewhere in the sequence, that is the only occurance; there won't be another private key (less than $q$) that will also yield that public key.

Now, the minor exception I mentioned: some elliptic curve systems don't use the full point $dG$ as the public key, sometimes they use only the x-coordinate as the public key.

It turns out, in that case, there is a second private key value that would yield the same public key; the value $q-d$. There are no others, and that second key turns out to be of no use to an attacker; recovering that value is no easier than recovering the original value of $d$.

share|improve this answer
    
d+q for 0<d<2^n-q gives the same pubkey as d. –  Willem Hengeveld Jul 20 at 6:59

I obviously don't understand the mathematics behind ECC, but I am quite certain that the mentioned Multiply is not as simple as regular multiplication, nor as simple as wrapping around a finite field many times over. Because:

When Alice and Bob exchange ECDH public keys, and then they each do DeriveKeyMaterial() or CalculateAgreement(), the result is supposed to be a shared secret that is known to Alice and Bob, and not known by any evesdropper.

If it were possible for Eve to derive any private key (even different from Bob's) that were plausible and functional with Bob's public key, then Eve would be able to derive the same result from DeriveKeyMaterial() or CalculateAgreement(), which means Eve is able to discover Alice & Bob's shared secret, which is assumed to be implausible. If this property did not hold, then ECDH would be completely broken.

share|improve this answer
1  
Bah to the downvoter. This answer uses a sound qualitative argument which is correct while simultaneously acknowledging not knowing the internals of ECC math. –  Edward Ned Harvey Jul 20 at 14:09

Could Eve capture Bob's public key, then derive some different private key to correspond to it, and then impersonate Bob by saying "I am Bob, and here's my public key." Even though Eve doesn't have Bob's private key, she's able to produce some other private key that's compatible with Bob's public key?

No, not unless the public key system is broken.

In many public key systems there is exactly one private key that corresponds with Bob's public key, i.e. the private key Bob knows. This is the case in e.g. RSA and the ECC systems I know of. That means there is no other private key that's compatible with Bob's public key that Alice could find.

With hash-based signatures, like Lamport signatures and Merkle trees, there can be multiple private keys that match the public key (second preimages). However, even there knowing another matching private key would allow you to forge signatures, so the system would clearly be broken if you were able to find them. With strong hash functions you cannot.

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.