8 of 15 Clarify

The birthday problem can't help to find "vanity" public/private key pairs; where "vanity" is some arbitrary characteristic/metric of the public key, like (in the question) having as low as possible a $X$ in Cartesian coordinates, or (more often) a long recognizable string in the text representation of the public key.

The only known methods essentially try many key pairs, and keep the "best" according to the vanity metric. We do not know how to make the tries better than random, hence if the vanity of a random public key has probability $p$ to be satisfactory, we'll need to test about $1/p$ public keys. The cost to compute each key tested can be reduced to one elliptic curve group operation, but not much less (in particular, with the customary format of public keys in Bitcoin, it seems we need at least one inversion in the base field).

A simple method can be:

  • draw a random $u$ in $[1,n)$ where $n$ is the order of $G$, with $n=2^{256}-\mathtt{14551231950b75fc4402da1732fc9bebf_h}$ for secp256k1
  • compute associated point $P_0=u\times G$
  • keep adding $G$ to that point, computing $P_i=P_{i-1}+G$ until that's a public key with suitable vanity
  • find the corresponding private key as $u+i\bmod n$ (the modulus step is unnecessary in practice).

Usually point addition is more costly than point doubling, and it might be better to use:

  • draw a random $u$ in $[1,n)$
  • compute associated point $P_0=u\times G$
  • keep doubling that point, computing $P_i=P_{i-1}+P_{i-1}$ until that's a public key with suitable vanity
  • find the corresponding private key as $2^i u\bmod n$.

The post linked in the question cryptically reads:

1KATWALSHTHECuz5DFHoNqJax6hnDbL6KN  (I can sign with it if you want)
Any vanity pubkeys category? If so, I win:
0200000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63

The following concludes that the public key with the hex form of the third line does not match the text string[*] of the first line. My reading is thus that it is not even alleged that it is known how to make a signature that verifies against a public key with an $x$ having 90 leading zero bits (as the one in the third line does). And, for the reasons in the first part of this answer, I doubt that it is.

[*] an address, that is the hash of a matching public key among about $2^{257-320}=2^{97}$.


That helpful schematic shows how the public key and its text form relate.

The first string is the Base58Check encoding of a "Bitcoin pubkey hash", that is the Base58 encoding of 1+20+4 bytes (obtained using this tool) with the last 4 bytes equal to the first 4 bytes of the SHA-256 hash of the SHA-256 hash of the first 1+20 bytes.

00 c73c219421726619b3d680cbcf07d70783a91d40 b2f57ab5

The last string is a point in compressed coordinate (as recognizable from the leading 02) with $x$ (in hex)

00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63

We compute $y$ as the solutions to $y^2=x^3+7\bmod p$ with $p=2^{256}-2^{32}-977$, and that is (hex)

3f3979bf72ae8202983dc989aec7f2ff2ed91bdd69ce02fc0700ca100e59ddf3
c0c686408d517dfd67c2367651380d00d126e4229631fd03f8ff35eef1a61e3c

The leading 02 in the compressed form means to select the even (second) value of $y$, therefore the uncompressed public key complete with 04 prefix is

 04 00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 c0c686408d517dfd67c2367651380d00d126e4229631fd03f8ff35eef1a61e3c

which, hashed by SHA-256 then RIPEMD-160, gives (according to this tool) 2a8cfefd81c810f789e2f75c4fce37922c939310 which does not match c73c219421726619b3d680cbcf07d70783a91d40 from the text representation. I tried with the other $y$ coordinate and the compressed form, no match.