ECC math/code, bizzare problem

Mike Rosing (eresrchmendota.terracom.net)
Fri, 29 Oct 1999 10:34:28 -0500 (CDT)

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
• Next message: Ian Sparkes: "Re: Password mangling"
• Previous message: Ian Grigg: "Re: 56 Bits?????"

I have an interesting problem with the math associated with
counting points on elliptic curves and I hope that someone
out there can explain why I get the results I do.

First, let me explain where the math comes from, then I'll
describe some implementation details, then I'll describe my
problem.

In Menezes' book "Elliptic Curve Public Key Cryptosystems" (ECPCK)
he describes Schoof's algorithm in Chapter 7. One of the
steps includes finding an eigenvalue of the Frobenius map
(if one exists). This involves using "division polynomials".
I have checked my generation of these polynomials using
Koblitz' formulas and this section of code appears to be ok.
The Frobenius map is found by taking x^q where q = 2^10 for
my examples. This allows me to compute things by hand,
and I can also let the computer brute force the polynomials.

To find an eigenvalue, Menezes sets (x^q, y^q) = wP and
uses a formula involving the division polynomials for the
x and y components of wP. This gets me to equation 7.4 on
page 105 in ECPKC:

g1 = gcd( (x^q + x)f[w]^2 + f[w-1]f[w+1], f[l])

g1 has degree (l-1)/2 when either w or -w is an eigenvalue.
I get g1 to be a polynomial of degree 8 for l = 17, and the
eigenvalues for which this happens are correct by hand
calculation. So far so good.

To determine the sign of the eigenvalue, Menezes proceeds to
compare the -wP y component to the Frobenius y component (y^q).
This gives a formula with powers of y and x, but since
y^2 = x^3 + a_6 + xy we can compute y^q = a(x) + b(x)y by
substitution after every squaring operation. For my example,
I find b(x) = x^1023 and a(x) ~ x^1536 (the hand calculation
agrees with the computer via the brute force method).

Menezes says y^q can be reduced modulo g1. When I divide b(x)
by g1, I get *exactly* xf[w]^3 + f[w-1]f[w]f[w+1] mod g1.
This means the b_bar(x) term on page 106 is zero! Since he
takes y = a_bar(x)/b_bar(x), the math fails to determine the
sign of the eigenvalue. This happens for *every* w that gets
to this point in the code, so it's independent of l.

It turns out that all the eigenvalues for my simple example
are for l's greater than 10. Is it possible that the math only
works (i.e. b_bar(x) is not zero) when l < n in GF(2^n)?
I suspect I have a rather bizzare bug in my code, but I haven't
got a clue how to go look for it. Can anyone give me a
hint on how to go about looking for bugs, or else explain why
b_bar(x) must be zero?

I am using the polynomial field (u^11 + 1)/(u+1) which allows
me to use the "ring math" described in Joe Silverman's paper
at CHES. The example curve is a_6 = 0xa = u^2 + u.

Usually when I get bugs, things turn into garbage. But getting
zero is just too perfect, and must be either an obvious math
error on my part, or else my example is too small. Any hints
appreciated!

Patience, persistence, truth,
Dr. mike

• Next message: Ian Sparkes: "Re: Password mangling"
• Previous message: Ian Grigg: "Re: 56 Bits?????"

This archive was generated by hypermail 2.0b3 on Fri Oct 29 1999 - 13:22:46 CDT