Could a 2nd EC private key be derived from a public key?

Question

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?

Answer 1

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$.

Answer 2

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.

Answer 3

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.

Answer 4

In the curves that are actually used for cryptography, it is not believed that any public key corresponds to more than one private key. You can intentionally create a curve with parameters that break with this convention (for example, you can make P not prime, or you you can choose a base point that isn't actually on the curve). But the curves selected for cryptography are carefully chosen to avoid that. It is possible that a public key would give up some information about the private key which would make its discovery more feasible. For example, it may be possible to determine whether a point on the curve (which a public key is) is the result of an even number of base point additions or an odd number. But if such determination is possible, no one has figured out how to make that determination, yet. People searching for vulnerabilities in ECC face the same problem that people trying to hack it face - it is infeasible to test a possible vulnerability over every possible key pair.