Some point counting results from Twisted Edwards curves
 From: CatId <mrcatid@xxxxxxxxx>
 Date: 19 Aug 2009 13:14:06 GMT
When using the friendly pseudoMersenne 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 (ECDH 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 64bit 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):
Relevant Pages
