0
$\begingroup$

Suppose we talk about NIST P-256 elliptic curve, and since finite field of an elliptic curve is a known prime number $P$, then approximately half of the Weierstrass equation results will be quadratic residues. But what I need is the probability of a single result of a Weierstrass equation to be a quadratic residue on an encoded message? For this purpose I should know the distribution of the X coordinates on a finite field. As an example, I could have a message encoded as X=10, but solving for Weierstrass equation it will return a quadratic non-residue, so then I try with X=11 and so on, until I eventually got a quadratic residue, when, let's say, X=23. So there is a gap of 13 iterations. That in turn means, that I should somehow know ahead how many bits should I reserve for the encoding of a message, i.e. how many times should I do +1 to the X coordinate in order to eventually receive a quadratic residue from a Weierstrass equation. What is this probability?

P.S. Encoding and decoding are both in use, so no one-way approach is used. Obviously it would be super good to be able to perform that encoding without having to iterate, but seems that it is impossible using Weierstrass equation.

Improve this question
$\endgroup$
4
  • $\begingroup$ Why do you want to encode messages as points? We have better options use ECIES otherwise you need Koblits Encoding or its variants $\endgroup$ Commented Aug 14, 2024 at 22:16
  • $\begingroup$ @kelalaka ECIES is another encryption algorithm, for my work I use ElGamal, as it allows regular/distributed/homomorphic encryption. That is why I use EC ElGamal $\endgroup$ Commented Aug 14, 2024 at 22:20
  • $\begingroup$ The probability is $(\ell-1)/2p$ $\endgroup$ Commented Aug 15, 2024 at 5:24
  • $\begingroup$ @DanielS thanks a lot! Could you provide a reference to this equation and then I could accept your answer as it is what exactly I have asked for $\endgroup$ Commented Aug 15, 2024 at 7:26

1 Answer 1

Reset to default
1
$\begingroup$

Firstly note that there are no 2-torsion ($y=0$) points on NIST P-256. It follows that the $\ell-1$ points on the curve (not counting the point at infinity) can be divided into $(\ell-1)/2$ pairs where $x$-coordinates are equal if points belong to the same pair and distinct otherwise. We thus have $(\ell-1)/2$ valid $x$-coordinates out of a possible $p$ choices of input, giving a probability of $(\ell-1)/2p$.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.