3
$\begingroup$

As alluded to here (split-key vanity addresses for bitcoin), ECCDSA-keys can be merged such that the sum of two private keys $S=S_1+S_2$ yields a public key which is the sum of the respective public keys $P=P_1+P_2$. Thus, given a key pair it is trivial to construct all public keys that are integer multiples of that public key $P_n \equiv n\cdot P \pmod N$. Does this mean there is a skeleton key with public key $1$ that could derive all keys? Or at least "low numbers" that can be used to crack public keys that are very "composite"? Of course since it is infeasible to obtain the secret key to any given public key that's probably pure theory, but one worth much more to invest in than a single specific target...

$\endgroup$
1
  • 2
    $\begingroup$ +1, although I strongly suspect that all keys are "skeleton keys" :) - the problem is more in the enumeration than the calculation. $\endgroup$
    – Maarten Bodewes
    Jul 3, 2020 at 10:52

1 Answer 1

3
$\begingroup$

ECCDSA-keys can be merged such that the sum of two private keys $S=S_1+S_2$ yields a public key which is the sum of the respective public keys $P=P_1+P_2$.

This is true, however it doesn't mean what you think it means; the $+$ operators in the two equations are two different operations.

The first one is simple addition (modulo the order of the elliptic curve group). However, the second is elliptic curve addition, which is not at all addition modulo some number.

Thus, given a key pair it is trivial to construct all public keys that are integer multiples of that public key $P_n \equiv n\cdot P \pmod N$.

Nope; one can certainly compute $P_n = n \cdot P$, where $\cdot$ is elliptic curve multiplication, that is, short hand for $n$ copies of the point $P$ added together, however the actual values of $P_n$ are 'unpredictable' in the sense that, if you have a target point $Q$, it is a hard problem to find an $n$ such that $Q = P_n = n \cdot P$ (or rather, we hope that's a hard problem; if it isn't, all elliptic curve cryptography falls apart).

Does this mean there is a skeleton key with public key $1$ that could derive all keys?

No, or at least, we hope not. If there is an elliptic curve point $1$ for which solving $Q = n \cdot 1$ was an easy problem, at least solvable a nontrivial part of the time (and not easy in the sense that "it hardly ever exists"), then again, all elliptic curve cryptography falls apart (and we don't need to know the private key corresponding to $1$).

Of course since it is infeasible to obtain the secret key to any given public key that's probably pure theory, but one worth much more to invest in than a single specific target...

Actually, it can be proven that the problem "given this large number $k$ of public keys, find one public key (and we don't care which one)" is not anymore difficult (that is, no more than an addition $O(k)$ work effort) then the problem "given this public key, find the private key".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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