Skip to main content
added 273 characters in body
Source Link
PouJa
  • 324
  • 4
  • 15

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.

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

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.

Source Link
PouJa
  • 324
  • 4
  • 15

On an Elliptic Curve is that possible that from $P$ we can tell if $a$ is quadratic residue modulo $N$?

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