[Crypto] Order of Edwards curve and its twist
Solution 1:
Regarding the [B] and [C] parts of the question per the comments:
I'm not sure how exactly did Mike Hamburg find the curve, but from what I know it's usually easier to find the order of the matching Montgomery curve. Recall that Montgomery curves have the form $By^2 = x^3 + Ax^2 + x$. If $B$ is 1, then it fits into the generalized Weierstrass form, and most SEA algorithm implementations work with any curve in the generalized Weierstrass form. (If it's not 1 then you can easily map into a curve with $B = 1$, the same way that short Weierstrass curves can be mapped into $a = -3$)
So basically:
- Search for a Montgomery curve matching the criteria;
- Then convert it into Edwards form.
One optimization is to instruct SEA to quickly discard curves whose order it knows beforehand that have a small factor (other than 4 or 8), see the tors parameter of the ellsea PARI/GP function, for example.
The paper "A note on high-security general-purpose elliptic curves" has a Magma implementation of the process (though IIRC it uses a slightly different approach). RFC 7748 has a Sage script that also searches for a Montgomery curve (though it will probably be much slower, since it doesn't seem to support that optimization).
Solution 2:
Do your experiments count points at infinity? When $d$ is a quadratic nonresidue over $\mathbb{F}$, the curve
$y^2 + x^2 = 1 + d x^2 y^2$
has no points at infinity over $\mathbb{F}$. But if $-1$ is also a quadratic nonresidue, then the curve
$y^2 - x^2 = 1 - d x^2 y^2$
has two of them, roughly of the form $(\pm\sqrt{-1/d}, \infty)$.
Solution 3:
Answering on the subquestion:
Why $|E_d|+|E'_d|=2\cdot p+2$ ?
It follows from the definition of quadratic twist. In fact, let's consider all possible $\tilde{x}$ coordinates for points, that is all the values in $\mathbb{F_p}$, and an elliptic curve $E$ with equation $y^2=x^3+ax+b$, then:
Case $\tilde{x}^3+a\tilde{x}+b\neq0$:
So either $\tilde{x}^3+a\tilde{x}+b$ is a square and thus its square root provides us two points belonging to $E$, namely $(\tilde{x},\pm\sqrt{\tilde{x}^3+a\tilde{x}+b})$ or it is not a square. If it's not a square then it will be a square for the twist curve $E'$ of equation $y^2=x^3+d^2ax+d^3b$ with $d\neq0$ and non-square in $\mathbb{F}_p$, thus providing two points belonging to $E'$.
Case $\tilde{x}^3+a\tilde{x}+b=0$:
In this case the point lies on the $x$ axis and belongs both to $E$ and $E'$.
So, when you consider all possible $\tilde{x}$ values in $\mathbb{F}_p$, you have for each of them two points belonging to $\{E \cup E'\}$, if you add also the point at infinity for each curve, you end up with $|E_d|+|E'_d|=2\cdot p+2$