Twisted Edwards curves1 have the form $ax^2 + y^2 = 1 + dx^2y^2$ (for fields with characteristic not 2) where the curve order 2 can be represented as $l \cdot 2^c$, where $c$ is a natural number and $l$ is a big prime number. So, it is obvious that our elliptic group has two subgroups, and for cryptographic purposes, we may always select the group defined by the large prime $l$.
Nevertheless, an attacker can select points from the smaller subgroup, and these points will be eligible for use in group operations. To ensure that this can never happen, the verifier in the EdDSA protocol additionally uses the $2^c$ cofactor to increase the security of the equation $2^c\cdot rG = 2^c\cdot aG + 2^c t \cdot K$. It ensures that all points are in the larger prime curve subgroup; otherwise, multiplication by the cofactor results in the point at infinity.
For the EdDSA signature protocol (which is based on the Schnorr identification protocol), it is necessary to understand why and how the challenge is generated. I’ve mentioned earlier that for the challenge generation in the non-interactive protocol we use the Fiat-Shamir heuristic. The basic idea is to generate challenges using the hash of all input data. It is necessary to highlight that we have to include all input data in the hash; otherwise, a malicious user may be able to manipulate information that was not included and fixed in the hash.
Let’s take a look at an example of challenge generation in EdDSA: it uses $c = Hash(aG, K, m)$ and $r = a + c* k$ to verify later that $rG = aG + \hat{c}K$. Using such an approach, the signer cannot manipulate the signature $(A, r)$ because its data is fixed in the challenge. But imagine if we did not include $aG$ in the challenge. Then, a malicious signer without any knowledge of the private key $k$ could select a random $r$ and set the signature as $( A = rG - cK, r)$. It’s easy to check that such a signature passes verification because the verifier cannot check that the $A$ value has been generated randomly and before challenge generation.
In addition, let’s take a look at a useful feature that Edwards curves allow. As I said earlier, Ed25519, for example, is defined over the $F_{2^{255}-19}$ field, where every value requires 255 bits for its binary representation. So every point will take about 510 bits. Using the point compression algorithm, we can encode every point using only 256 bits by transferring only the $y$ coordinate.
Using the Edwards curve equation $ax^2 + y^2 = 1 + dx^2y^2$, we can express the $x$ coordinate (with the assumption that $a = -1$) as $x^2 = \frac{y^2 - 1}{dy^2 + 1}$, which means that $x$ can have two possible solutions (+ and -). In modular terms (since we have an odd modulus $q$), it means that $x$ can have odd and even representations. This information can be encoded into one bit.
Then, to decode the point coordinates, after separating the parity bit from the $y$ coordinate, we have to calculate the square root. There are several methods to deal with the square root in $F_q$. One of them 3 is to use the feature that $q = 2^{255} - 19 \equiv 5 (mod 8)$. In the $F_q$ multiplicative group we have $q - 1$ elements (then for every $x \in F_q: x^q = x$), so for every square $\alpha = \beta^2$ we have $\alpha^4 = \beta^8 \rightarrow \alpha^{p+3} = \beta^8 \rightarrow \alpha^\frac{p+3}{8} = \beta$. From the equation $\alpha^4 = \beta^8$ we can observe that there can be two possible solutions $\pm\alpha = \beta^2$. In the case where the calculated $\beta$ satisfies $\beta^2 = -\alpha$, we should multiply it by $\sqrt{-1}$.
For the $\sqrt{-1}$ we can follow the same transformations: $x^2 = -1 \rightarrow x^4 = 1 \rightarrow x^4 = 2^{q-1} \rightarrow x = 2^\frac{q-1}{4}$. The base $2$ element was selected as the most convenient element for multiplication.
So finally, for the equation $x^2 = \frac{u}{v}$ we can calculate $x’ = \sqrt{u/v}$ and check that $v\cdot x’ = -u$ and, if so, multiply $x’$ by $\sqrt{-1}$. At the final stage, we use the parity bit to check that we’ve recovered the same coordinate with the same parity.