2
$\begingroup$

I am using a system that relies on base64 encoded ECDSA public keys. I have managed to brute-force a public key that when encoded starts with a word I like. Is it possible for me, given the private key, generate similar public keys?

$\endgroup$
3
  • $\begingroup$ Think in this direction: if one keeps doing what they have done when they "managed to brute-force a public key that when encoded starts with a word (they) like", will they succeed again? And if so, what are the odds that they generate the same public key? $\endgroup$
    – fgrieu
    Apr 4, 2022 at 7:03
  • $\begingroup$ Are you asking in the context of cryptocurrency? $\endgroup$
    – kelalaka
    Apr 5, 2022 at 18:21
  • $\begingroup$ No, I guess that for most cryptocurrency people want their hashed public key to look cool which seems like a different problem as similar public keys would result in different hashes. $\endgroup$
    – Octetz
    Apr 7, 2022 at 5:39

1 Answer 1

5
$\begingroup$

It's possible to generate one extremely similar public key. If your private key is $s$ and your public key is the point $(x,y)$ then another valid private/public key pairs is $\ell-s$ and $(x,p-y)$. Here $\ell$ is the curve order and $p$ is the characterstic of the field. If you write your public key in compressed form, the representations will differ only in a single bit (the compression bit)!

Some elliptic curves also permit other simple endomorphisms due to their complex multiplication structure e.g. curves of the form $Y^2=X^3-aX$ allow one to generate the additional private/public pair $js$ and $(-x,\pm iy)$ where $i$ is a square root of -1 mod $p$ and $j$ is a square root of -1 mod $\ell$.

For more general similarities, the ability to produce private keys from small perturbations of public keys would allow an attacker to solve discrete logarithms by hillclimbing, which is not thought to be possible due to hard-core predicates on discrete logarithms.

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