Some point counting results from Twisted Edwards curves

When using the friendly pseudo-Mersenne modulii of the form p = 2^
256 - c...

Something I haven't noticed in any papers yet on Twisted Edwards
curves over Fp but is important in practice is the fact that the
addition and doubling laws have no exceptions for a=-1 and any
suitable d that generates a large prime order subgroup with cofactor
4 so long as the field prime p = 1 mod 4. Any p = 3 mod 4 seems to
lead to exceptions. It sucks that square root becomes a lot more
difficult, but this guarantees that the addition and doubling laws
have no exceptions that an attacker could exploit.

The complete (has no exceptional points) and unified (works if both
input points are the same) addition and doubling laws for Twisted
Edwards curves over Fp require either a parametrization where 'a' is
a square and 'd' is not a square, or they require that the points
are of odd order.

Since in most ECC protocols (EC-DH for example) a point is provided
by an untrusted node somewhere on the network and scalar point
multiplication is performed on that point, it cannot be guaranteed
that the point is of odd order. I mean, the usual approach is to
just multiply the input by the cofactor of the order of the curve.
So far I've been using a large prime subgroup with a cofactor of 4,
so I just double the input point twice. But in my understanding the
doubling operation may fail if the input point is not of odd order
if the curve parameters 'a' and 'd' are not chosen well to begin
with. I haven't seen this in practice yet but this is what papers I
have read seem to indicate, so I am erring on the side of caution...

These desirable curve parameters place some limitations on the field
prime p:

If p = 3 mod 4, all values of d that generate large prime subgroups
with cofactor 4 are square. Also in this case, a = -1 is never

So far I have been using primes of this form because it leads to a
simple square root law which doesn't work if p = 1 mod 4.

If p = 1 mod 4, all values of d that generate large prime subgroups
with cofactor 4 are NOT square, as desired. And a = -1 is always

So a simplified way to put it is, in order to avoid exceptional
points when using Twisted Edwards curves, choose a value for the
field prime that is 1 mod 4.

Note that I don't offer any proof of this -- it's just what I've
seen for a large number of experiments with p = 2^256 - c where c is

Numerical example, for the largest suitable p = 2^256 - 435:

Recall the Twisted Edwards curve equation:
a * x^2 + y^2 = 1 + d * x^2 * y^2 over Fp

a = -1 is a square (as desired)

d = 2649 is not a square (as desired)

Satisfies the MOV condition and is not anomalous.

The order of this curve = h*q, where q is a large prime and h is the

h = 4 (small and friendly)

q =

In hex with 64-bit words starting from the most significant:
q =

If anyone knows of other conditions for secure curves, please let me
know too!

I haven't finished writing a new square root algorithm that works
for this kind of modulus, so I haven't yet generated points for this
curve and verified that performing scalar multiplication on the
generator point by q+1 yields the generator point again.

As an aside, I found it odd at first that you have to multiply by q+
1 to get the generator back but I guess it makes sense. For the
simple example with integers modulo 3, the order of the subgroup
generated by g = 1 is 3 containing {0, 1, 2}, and g+g+g+g = g*4 mod
3 = g again.

--------------------------------- --- -- -
Posted with NewsLeecher v3.95 Beta 3
Web @
------------------- ----- ---- -- -