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 < Priv2/(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 < 247/(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:
- Is there a way to find out the number of digits of Priv2 (division result) in the decimals place?
- 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
