Imagine that, On an Elliptic Curve cryptography scheme where $P=a\times G$, Bob shares his public key $P$ with Eve (the devil who wants to know secrets he is not supposed to). Bob has also revealed a clue about $a$ accidentally. The clue can be one or a combination of items from the following list:
- The number $a$ is ODD/EVEN integer.
- The number $a$ is GREATER/SMALLER than half of the group order $N/2$.
- The number $a$ has $x$ meaningful bits when written as binary. (there $x$ is the count of bits of $a$, for example if $a=152=10011000$ then $x=8$
- The number $a$ is quadratic RESIDUE/NON-RESIDUE modulo $N$.
Will knowledge of such a clue be considered a significant weakness for the public key of Bob so that we should say it is not safe anymore to use it?
Clues mentioned above are very little information about $a$ I suppose. Am I right? What if we can reveal them for all points on the curve by using a magic algorithm?
I know that, for items 1-3, knowledge of a general algorithm that for any given $P=a\times G$ it can tell us for sure that $a$ is ODD/EVEN or $a$ is GREATER/SMALLER than $N/2$ or $a$ has $x$ bits will completely break the security of Elliptic Curves and by which it will be possible to retrieve $a$ from $P$.
But what about item 4? I mean if one can discover an algorithm by which they can determine that for any given $P$, $a$ is or is not a quadratic residue modulo $N$, will they be able to completely retrieve $a$ and break the cryptographic scheme?
What if the algorithm can also tell the square root of $a$ modulo $N$?
These questions arose when I was studying risks of private key database being partially compromised. That is what happens if an attacker knows clues of our private keys.