I understand that the public key does not expose the private key. That is not th
ID: 652593 • Letter: I
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?
Explanation / Answer
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.