# Some point counting results from Twisted Edwards curves

*From*: CatId <mrcatid@xxxxxxxxx>*Date*: 19 Aug 2009 13:14:06 GMT

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

square.

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

square.

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

small.

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

cofactor.

h = 4 (small and friendly)

q =

28948022309329048855892746252171976963460214495261123947512342497934

128211237

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

q =

4000000000000000

0000000000000000

6b5e8ce16c9c823c

34ddb12668e46525

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.

http://catid.org

--

--------------------------------- --- -- -

Posted with NewsLeecher v3.95 Beta 3

Web @ http://www.newsleecher.com/?usenet

------------------- ----- ---- -- -

.

- Prev by Date:
**Re: Crypto'09 Rump session to be webcast** - Next by Date:
**Re: modified factoring problem.** - Previous by thread:
**modified factoring problem.** - Next by thread:
**Was anybody actually able to watch the Crypto2009 video cast?** - Index(es):