Twisted Edwards curves1 has a form of $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, $l$ is a big prime number. So, it is obvious that our elliptic group has two subgroups and for the cryptography purposes wew always may select the group defined by the large prime $l$.
Nevertheless, an attacker can select points from smaller subgroup and this points will be eligible for using in group operations. To ensure that this never can happen, in EdDSA protocol verifier 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 lager prime curve subgroup, otherwise multiplication by the cofactor results with infinite point.
For the EdDSA signature protocol (that is based on Schnorr identification protocol) it is required to understand why and how the challenge is generated. I’ve mentioned earlier that for the challenge generation in the non-interactive protocol we are using the Fiat-Shamir heuristics. 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 into the hash, otherwise malicious user can be able to manipulate information that was not included and fixed in hash.
Let’s take a look to the example of challenge generation in EdDSA: it uses the $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 can not manipulate signature $(A, r)$ because it’s data is fixed in the challenge. But imagine if we are not including the $aG$ into the challenge. Then, malicious signer without any knowledge of private key $k$ can select a random $r$ and put the signature as $( A = rG - cK, r)$. It’s easy to check that such signature passes the verification because verifier can not check that $A$ value has been generated randomly and before challenge generation.
In addition, lats take a look on a useful feature that Edwards curves allow. As I said earlier, the Ed25519 for example, is defined over $F_{2^{255}-19}$ field, where every value requires 255 bit for the binary representation. So every point will take about 510 bit. Using the point compression algorithm, we can encode every point using only 256 bits by transferring only the $y$ coordinate.
Using the Edwards curves equation $ax^2 + y^2 = 1 + dx^2y^2$ we can express the $x$ coordinate (with an 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 the modular terms (since we have an odd modulo $q$) it means that $x$ can have the odd and even representations. This information can be encoded into one bit.
Then, to decode the point coordinates, after separating parity bit from $y$ coordinate, we have to calculate the root square. 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 when calculated $\beta$ satisfies $\beta^2 = -\alpha$ we should multiply it on $\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 comfortable 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 the $x’$ on $\sqrt{-1}$. On the final stage, we use the parity bit to check that we’ve recovered same coordinate with same parity.