Why isn't f(G) uniform in ECDSA? In ECDSA, $f(G)=r$, where $r$ is the $x$-coordinate of group element $G$. My question is, how to prove this $f$ is not uniform? In other words, how to prove that, given a random element $G$ with different x-coordinates on an elliptic curve, $r=f(G)$ is not uniform over $\mathbb{Z}_q$? I would like to stress that here we see the group elements that share the same x-coordinate as the same ones.
I know in the paper ''On the Provable Security of (EC)DSA Signatures'', the author has talked about this. But I could not understand what they mean(&quot;On elliptic curves, for only about every second $x$-value a corresponding curve point exists; this is responsible for a
huge bias of the $x \bmod q$ function&quot;?). Can anybody give a more clear explanation?
Hasse's bound tells that the order $n$ of [that is, number of elements in] an Elliptic Curve group is about the same as the order $p$ of the underlying field [note: $x$ and $y$ coordinates are elements of the field, points $(x,y)$ are elements of the group].
For every $x$ in the field with $(x,y)$ in the group, there is exactly one other point in the group with the same $x$: $(x,-y)$.
Therefore, about one value of $x$ in the field out of two is such that there exist $y$ in the field with $(x,y)$ [and $(x,-y)$] in the group. Like, if you have $n$ nuts and $p$ persons, with $n\approx p$, and you give two nuts to each person, then only about half the persons get a nut.
Therefore, $f$ as defined in the question is not uniform in the field, for it only reaches about half of the field elements.