1
$\begingroup$

$p$ - is the order of the finite field

$n$ - is the order of the group. Private keys can range from $1$ (the generator point $G$) to $n - 1$.

All the private keys ($Priv$) lie in certain ranges of 2.

$2^{a} < Priv < 2^{b}$

If we know the $a$ then after converting our private key to the public key ($Pub$), we can divide the $Pub$ by 2, $a$ times to get $Pub2$ (using elliptic curve divisions of course, $PubOld *(2^{-1}\mod{n}) = PubHalved$ ).

$Priv2$ would be the corresponding private key to $Pub2$ and it'd look like:

$1 \le {Priv2\over 2^{a}} < 2$

We know for sure, that we have 1 in the wholes place, and that it is the only digit we have in the wholes place. Also If $Priv$ was an odd integer then there would be the same number of digits in the decimals place (in $Priv2$) as there were divisions by 2 (in this case it is $a$ number of digits).

But if $Priv$ was an even integer, then the number of digits in the decimals place would be $a$ minus the index number of the division by 2 where the corresponding private key integer became an odd number. Like if we had $250$ as our $Priv$, then $Priv2$ would have 6 digits in the decimals place, because $2^{7} < 250 < 2^{8}$, and it became an odd number right after the 1st division, hence, $7 - 1 = 6$

A special case would be perfect square numbers, where we would never get an odd number, except at the end, and that would be 1 as the final division result.

Another property, is that $Priv2$, if $Priv$ is odd, would have either 75 or 25, as the 2 final digits at its end.

Take a look at $Priv = 247$ for example

$2^{7} < 247 < 2^{8}$

After all the divisions:

$1 \le {247 \over 2^{7}} = 1.9296875 < 2$

Now suppose that we don't know the value of the private key. The things that we know are:

Integers $a$ and $b$, $2^{a} < Priv < 2^{b}$

There are 2 questions:

  1. Is there a way to find out the number of digits of $Priv2$ (division result) in the decimals place?
  2. How can we separate the last 2 digits at the end of the decimal part, and find out whether these are 25 or 75?

To imagine the situation better, suppose that we are making the calculations in the ℤp field, and our curve is secp256k1

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 1. No, there is not. 2. By subtracting an appropriate multiple of $G$ from the public key and iterating the non-existent procedure used in 1. $\endgroup$
    – Daniel S
    Commented Mar 24 at 10:33
  • 1
    $\begingroup$ The usual look at such problems is solvable, try a reduction to the discrete log problem. $\endgroup$
    – kelalaka
    Commented Mar 24 at 10:34
  • $\begingroup$ @kelalaka Thanks for the tip :) $\endgroup$
    – Maltoon Yezi
    Commented Mar 29 at 15:53

0

Reset to default

Your Answer

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