Elliptic curve and "vanity" public keys

Question

I want to find an algorithm to get a private/public key pair where one coordinate of the public key has some specific prefix (for example: 20 leading zeroes). In the secp256k1 case (the Bitcoin curve), G. Maxwell has found a public key with coordinate

x = 00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63

( see https://bitcointalk.org/index.php?topic=90982.msg13789635#msg13789635).

In that case 22 zeroes means 88 bits, and he claimed to have found the private key too. Obviously $2^{88}$ random tries are computationally infeasible, then I think that the Birthday Paradox should be used (to reduce the steps from $2^{88}$ to $2^{44}$). But I can't understand how to apply the Pollard Rho algorithm (the classic Birthday Paradox - based algorithm) to this specific task. Any ideas?

EDIT1:

It is very simple to find only a public key with as many leading zeros as you want without the private key, for example:

x = 0000000000000000000000000000000000000000000000000000000000000001

y = 4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee

are the coordinates of a valid point of the secp256k1 curve because they fulfill the equation $y^2 = x^3 + 7$ mod $p$

That's why I'm pretty sure that G.Maxwell has the private key too (otherwise his public key would have nothing special)

For now I know that if I generated about $2^{44}$ random points, I would find a "partial" collision, i.e. I would find a couple of points $P_1$, $P_2$ with $x_{P_1}$ and $x_{P_2}$ that share the first 88 bits. How do I use this information to find a point $P_3$ with 88 leading zero bits?

EDIT2:

Very strange: it seems that it takes $2^{88}$ steps to find a private key to any public key with a specific 88 bit prefix,

but it takes only $2^{128}$ steps to find a private key to a single specific public key (with a specific 256 bit "prefix") using the Pollard Rho algorithm (see http://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/ or https://blog.coinfabrik.com/wp-content/uploads/2016/06/ECDSA-Security-in-Bitcoin-and-Ethereum-a-Research-Survey.pdf)

Then to find a private key to any public key with a specific m bit prefix, with $m> n/2$, Pollard Rho is the best shot, with $m\leq n/2$ the fgrieu method is the best.

Answer 1

Maxwell's vanity public key is a result of how the generator of the secp256k1 was chosen; as explained by Maxwell himself.

For some reason, the generator $G$ is the double of the point:

x = 0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63, 
y = 0xc0c686408d517dfd67c2367651380d00d126e4229631fd03f8ff35eef1a61e3c

which is exactly Maxwell's vanity public key. Its private key is 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1 which is $1/2$, i.e. the inverse of $2$ modulo the curve order $n$. This is also equal to $(n+1)/2$.

The big question is: why was the secp256k1 generator chosen like that? I have no idea. But note that it's not difficult to find a generator with a lot of leading zeroes.

Answer 2

The birthday problem can't help to find public/private key pairs with "vanity" address (hash of public key in text form). Here, "vanity" is some arbitrary characteristic/metric, like plausibly matching a first name.

I retract an hasty claim that the above extends to public/private key pairs with "vanity" defined as having as low as possible the $x$ of the public key point (which the question is about), especially on secp256k1 with $p=2^{256}-2^{32}-977$ so close to a power of two. I do not entirely rule out that there is something better than brute force (below), which is the better I have to propose (Edit: for random generator. It turns out that the one used for secp256k1 is not).

---

The only methods that I know essentially try many key pairs, and keep the "best" according to the vanity metric. Tries are made essentially at random (necessarily so for addresses since they involve a hash), and if 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$.