3
$\begingroup$

I am wondering if there is a feasible way that, given a specific elliptic curve (such as secp256r1), I could create a keypair where the public key has a given $x$-coordinate. If it is not possible, is there a way to choose the most significant digits of that coordinate?

For example, is there a way to make a secp256r1 ECC keypair with the $x$-coordinate of the public key having the form 04 0000....1234?

Thank you.

$\endgroup$
4
  • 2
    $\begingroup$ What are you free to choose? Are you free to choose the generator? The definition of the curve? (i.e., the equation defining the curve) Or are those fixed? Please edit your question to clarify -- as it stands it can't be answered definitively, as the answer depends on those constraints. $\endgroup$ – D.W. Jun 7 '15 at 4:00
  • $\begingroup$ In fact, I need to solve this problem specifically using the Elliptic Curve type Google is using (Public Key 04 ea ac b0 ...) which is a secp256r1 A.K.A. prime256v1. I don't exactly know what parameters I can choose, though I suspect Generator should be one of those. Giving this information, is it possible to reach my goal? $\endgroup$ – Gerardo Jun 7 '15 at 13:47
  • 1
    $\begingroup$ @Gerardo The generator is part of the curve parameters; secp256r1's specification includes the generator. $\endgroup$ – cpast Jun 7 '15 at 17:16
  • $\begingroup$ @cpast You're right of course. That said, it is possible to use the resulting curve if you change the generator. $\endgroup$ – Maarten Bodewes Jun 10 '15 at 10:02
8
$\begingroup$

If that were possible, that is, if you could take an x-coordinate, and find the private key $k$ such that $kG$ has that x-coordinate, well, you've just solved the discrete log problem. If you can do that, you've just shown that the curve is insecure.

If you're thinking "I'm not specifying the y-coordinate; doesn't this make it easier than the discrete log problem", actually, no it doesn't. There are at most two points that have a specific x-coordinate, and those two points are inverses of each other. If you known the discrete log of one of the points, you immediately know the discrete log of the other.

As for choosing the most significant digits of the coordinate, I don't know of any easier way that brute force (that is, start at an arbitrary place $kG$ and test $kG, (k+1)G, (k+2)G, ...$ until you stumble across a point that meets the condition.

$\endgroup$
5
  • 4
    $\begingroup$ It is possible if the generator is not fixed beforehand. (Choose a public key and a private, exponent, then invert the exponent to compute the generator.) Choosing an arbitrary generator may or may not be possible depending on the specifics of OP's situation. $\endgroup$ – fkraiem Jun 7 '15 at 3:13
  • $\begingroup$ In fact, I need to solve this problem specifically using the Elliptic Curve type Google is using (Public Key 04 ea ac b0 ...) which is a secp256r1 A.K.A. prime256v1. I don't exactly know what parameters I can choose, though I suspect Generator should be one of those. Giving this information, is it possible to reach my goal? $\endgroup$ – Gerardo Jun 7 '15 at 13:25
  • 1
    $\begingroup$ Yes, if you can pick the generator, then it's easy; you just select your public key $X$, pick a random number $r$ and compute $r^{-1} \mod q$ (where $q$ is the order of the curve), and then set the generator to be $G = r^{-1}X$; the public key is now $r$ (as $rG = X$) $\endgroup$ – poncho Jun 7 '15 at 16:52
  • 2
    $\begingroup$ @Gerardo That said, you cannot pick your own generator if you use secp256r1, as the generator point is part of the curve specification. $\endgroup$ – cpast Jun 7 '15 at 17:20
  • $\begingroup$ @Gerardo the generator is part of the curve specification. It is a shared parameter. If you change the generator or curve values then it isn't secp256r1. As pointed out you only option is brute force. Depending on how specific you need the significant digits will define how many attempts it will take on average to produce a public key which meets your requirements. $\endgroup$ – Gerald Davis Jun 8 '15 at 14:07
2
$\begingroup$

Poncho's answer explains why finding a specific $Q$ in $Q = k x G$ is not feasible. If you could do this so could anyone else for any keypair and ECC would have no security. The short answer is ECC is secure specifically because there is no known method short of brute force to find $k$ for a given $Q$. Of course an exhaustive search (brute force) is always an option but this is made infeasible due to the size of the search space. The fastest search algorithms are $O(SQRT(n)) so for 256 bit ECC key that is 2^128 operations.

So if you needed to find k for a single specific Q you couldn't do it. However because you are looking for a range of potential public keys which meet your requirements it would be possible to brute force that. The output of the x value of the public key is uniformly distributed. In the leading 16 bits there are 4660 values in the range of 0x0000 to 0x1234. 4660 of the 65,536 possible values means the expected number of tries before generating a key which meets your conditions is 65,536/4660 ~= 14. Even with an unoptimized software implementation (and most general purpose crypto libraries are not optimized for large scale key generation) execution time would be something on the order of 100ms. Just a keypair check if matches your requirements if not increment the private key and keep checking until you find one which matches your requirements.

If you had more specific requirement it would is still possible given sufficiently powerful hardware. A lot will depend on how many keys you need and how long you can wait to find a matching key. It is simply a probability game. The more selective the match criteria the more attempts required before finding a match. If you needed the leading 32 bits to be all zero then it would take on average 2^32 attempts before generating a key with that prefix. A modern x64 cpu running well optimized code should be able to generate on the order of 50K to 200K keypairs per second per core. So generating a 00000000 prefix would take about an hour using eight core processor.

Using OpenCL code executing on a GPU you can get 10x to 50x higher throughput and higher power efficiency (in terms of keys/J). While NVidia cards usually have superior FP capabilities in OpenCL, AMD GPU's tend to have higher throughput in cryptographic processing due to the some key rotate and add instructions available in their architecture.

You may want to look at a piece of open source software called VanityGen. This software is used to generate "vanity" Bitcoin addresses, which are addresses which start with a specific prefix (i.e. "1MyMoney....."). Bitcoin uses secp256k1 not secp256r1 and VanityGen matches against Bitcoin addresses which are a base58 encoded hash of the public key but the computationally intensive part is the sequential keypair generation. It just takes a lot of attempts to find a match so the OpenCL code is optimized for high throughput.

$\endgroup$

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.