1
$\begingroup$

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:

  1. The number $a$ is ODD/EVEN integer.
  2. The number $a$ is GREATER/SMALLER than half of the group order $N/2$.
  3. 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$
  4. The number $a$ is quadratic RESIDUE/NON-RESIDUE modulo $N$.

Question 1:

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?

Question 2:

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$?

Update 1:

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.

$\endgroup$
5
  • 1
    $\begingroup$ What is the origin of this question? What is meaningful in (3)? How do you quantify this? 1 and 2 reduce the space to 1/4. The effect of 4 cannot be perfectly be told if $N$ is not given. $\endgroup$
    – kelalaka
    Oct 11, 2021 at 15:20
  • 1
    $\begingroup$ Can you explain (3)? If it's the number of ones and zeros in a key, this is a serious risk. $\endgroup$
    – Titanlord
    Oct 12, 2021 at 8:45
  • $\begingroup$ @kelalaka I updated the question and tried to address your questions, please look. $\endgroup$
    – PouJa
    Oct 12, 2021 at 11:15
  • $\begingroup$ @Titanlord If I give you my public key $P$ and also tell you that my private key has $124$ ones and $130$ zeros will you be able to calculate my private key? What if I don't tell the number of zeros and ones and I just tell the total sum in this example $254$. $\endgroup$
    – PouJa
    Oct 12, 2021 at 11:20
  • $\begingroup$ Why should a private key with a good random source have a problem of leaking 3 bit, expect (3), still not clear how these are leaked. $\endgroup$
    – kelalaka
    Oct 12, 2021 at 13:36

1 Answer 1

1
$\begingroup$

The impact on security from 1 and 2 can be considered as not significant. Say you have 256 Bit security, that implies $2^{256}$ different keys to chose from. If you know the key is odd, this is reduced to $2^{255}$ different keys. For 2 it is similar.

Knowing how many ones and zeros there are can be considered as a significant risk. Let's assume you have a 256 Bit key containing one 1. Only 256 possible keys remain. This results in the question of how many permutations there are. For binary numbers with a given length X and a given number if ones N this leads to the numbers of key, that can be calculated using:

$$ number\ of\ keys=\frac{(X!)}{ (N! * (X-N)!)} $$

In the best case this results in $\approx 2^{252}$ possible keys, for 128 ones. But for a different numbers of ones this only gets worse. Timing Attacks often try to find out how many different ones and zeros there are (or even try to locate some). These attacks are often a serious problem. Some of these attacks tried to guess the starting 1 of elliptic curve keys, because some old algorithms had different computing time depending on the position of the leading 1. This must not be a risk, e.g. the 1 is the first or second bit. But if the leading one was at position $i$ the security would drop to $2^{256-i}$. Depending on $i$ this can be a significant risk, especially if keys are completely chosen at random. You definitely don't want these risks.

For 4 I'm unsure. I will edit this, if I find a good answer.

$\endgroup$
4
  • $\begingroup$ Thank you for responding. Did you find out about 4? $\endgroup$
    – PouJa
    Oct 23, 2021 at 11:12
  • $\begingroup$ Any update about 4?! $\endgroup$
    – PouJa
    Apr 15, 2022 at 23:29
  • $\begingroup$ Sorry, I am not able to prove my assumption, but I think it would not make a significant difference. Depending on the setting, there may already be efficient algorithms to obtain that knowledge. $\endgroup$
    – Titanlord
    Apr 19, 2022 at 9:52
  • $\begingroup$ Thanks, do you know of any efficient algorithm that for a given $P$ it can tell if $a$ is quadratic residue for a curve of your own choice? $\endgroup$
    – PouJa
    Apr 23, 2022 at 22:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.