3
$\begingroup$

Let us take example of secp256k1 curve. The current known public key with most leading zero (in x cordinate) is:

pubKey = (0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63,
          0x3f3979bf72ae8202983dc989aec7f2ff2ed91bdd69ce02fc0700ca100e59ddf3)
private = 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1 (half of order)

My question is whether is it possible to have pubKeys with leading zeros? For example:

private = 0x7ADD48F07237A85230BE8FE44E1F7E36FEAF649672AEEFAA0F5ABBAD1721A994
pubKey = (0x00006fcf15e8d272d1a995af6fcc9d6c0c2f4c0b6b0525142e8af866dd8dad4b,
          0xe6aca70f61450bb377bf212b8863f5aa2ff50675d3c72c1d84519f2b5b19e7fc)

OR to further explain my question, I know that the following publicKey is a valid pubKey for secp256k1:

pubKey = (0x00000351c77ba68ec21856ff85284e7ddd5a1b83d41fc6a1278c67ad9f2f5e7f,
          0x09624c553c74b14cde21f80ab4a2cc4dc2cb314d40515b7445a9e1f31a873a7d)

Does there exist an efficient attack to calculate private key for given pubKey, by the fact, that pubKey has leading zeros?

$\endgroup$
6
  • $\begingroup$ Not all $x$ values constitute a point on the curve, however, this may not prohibit desired leading zeros. Being able to control the output leaks information about the key, right? If you can do it, I can do it, too, BOM! $\endgroup$
    – kelalaka
    Nov 28, 2023 at 13:57
  • $\begingroup$ The public key consists of the base point G multiplied with a random vector $s$ which represents the private key. As these are modulo operations the likelihood to have multiple zero byte values is about 1/255 for the first point, 1/65536 for the next one etc. The operation is not reversible so I think that brute force is the only way for you or an adversary to get the "desired" public points. However, I'm not answering as I'm 100% sure that there isn't a mathematical equation that can be used to select private keys if you can control all of them. $\endgroup$
    – Maarten Bodewes
    Nov 28, 2023 at 16:08
  • $\begingroup$ I'd be both pleased and surprised if the present question could be conclusively answered either way! Independently: that "current known public key with most leading zero" is the result of a deliberate design choice of generator $G$ that was not documented when made AFAIK. Knowing this design choice, a (small) speedup is possible when computing $k\,G$ (because $k\,G=2k\,(\frac12\,G)$ and adding $\frac12\,G$ is made a tad faster by the form of it's $x$). See mildly related question. $\endgroup$
    – fgrieu
    Nov 28, 2023 at 17:57
  • $\begingroup$ @fgrieu I think the generator may allow special attack. If something makes calculation easy, it can also make reversing easy. It is only a matter of time that this attack might come into public $\endgroup$
    – madhurkant
    Nov 29, 2023 at 1:41
  • $\begingroup$ Given a private key and public key, a bit setting oracle on the public key, that also returns the corresponding private key is equal to discrete log oracle. on the other hand, I cannot talk about the equality to xLeading Oracle. $\endgroup$
    – kelalaka
    Nov 29, 2023 at 5:49

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.