6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The Birthday Paradox does not apply if there is a specific result you need such as 88 leading zero bits. $\endgroup$ – zaph Jun 24 '18 at 1:04
  • 1
    $\begingroup$ Did they prove that they had the corresponding private key by signing something? $\endgroup$ – forest Jun 24 '18 at 2:37
  • $\begingroup$ Someone saying they "found" a public key probably really means they found a key pair with a certain public key... if they're being honest and know what they're talking about. The contrary sounds a lot more plausible. The point of a public key being public is that anyone can know it without being able to recover the private key. If you don't know the corresponding private key then you don't have anything the rest of the world doesn't have. And if you don't sign something with a public key then you have no proof that it is your public key. $\endgroup$ – Future Security Jun 24 '18 at 4:22
  • $\begingroup$ @Future Security I edited my question $\endgroup$ – arulbero Jun 24 '18 at 6:02
  • $\begingroup$ @zaph With the Birthday Paradox in the Pollard Rho method to find a private key for a specific 256 bit public key it takes $2^{128}$ steps, why to find a private key for a "specific" 88 bit public key Birthday Paradox does not apply? $\endgroup$ – arulbero Jun 24 '18 at 6:07
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Conrado thanks a lot! Mystery solved! I edited my question again. $\endgroup$ – arulbero Jun 25 '18 at 17:38
3
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ But in this way I would need to perform $2^{88}$ additions/doublings to get a 88 leading zero bits coordinate, it is not possible... There must be another way $\endgroup$ – arulbero Jun 24 '18 at 12:50
  • $\begingroup$ The "other way" is luck, very good luck. That is why most vanity bitcoin addresses only have a few leading vanity characters. I understand what you want, I have a couple of vanity bitcoin addresses. $\endgroup$ – zaph Jun 24 '18 at 22:05
  • $\begingroup$ @fgrieu "The following concludes that the public key with the text form of the first line does not match the public key with the hex form of the third line." That thread is about vanity addresses (= hashes of pub keys), not about vanity pubkeys. The first line (on topic) is not related at all with the second-third line (off-topic), I know that, this is obvious. Now I repeat: it is very simple to provide a pub key with as many leading zeros as you want, so I don't think that G. Maxwell (developer of Bitcoin Core) posted a pub key like this without having the private key too. $\endgroup$ – arulbero Jun 25 '18 at 4:50
  • $\begingroup$ @arulbero: After reflection I have pretty much turned around my answer. $\endgroup$ – fgrieu Jun 25 '18 at 5:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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