Can I generate two similar ECDSA public keys?

Octetz

8/4/23, 5:27 AM

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?

317

0 + 0

elliptic-curves

dsa

fgrieu

8/4/23, 7:03 AM

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?

kelalaka

8/5/23, 6:21 PM

Are you asking in the context of cryptocurrency?

Octetz

8/7/23, 5:39 AM

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.

Score:5

Crypto

Daniel S

8/4/23, 8:27 AM

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.