ECC: Question about figuring out the y value of a point when I have the x value

AARRRGH

Hello

I know this is an absolute long shot posting this here, but it's driving me nuts. Maybe some of the handful of people who know ECC (Elliptic Curve Cryptography) browse boards... who knows!

I have a question about figuring out the y value of a point when I have the x value. For some reason, even if I already know the y value, I cannot get both sides of the curve equation to match.

I cannot figure out why this is. My calculations are correct.

The formula for my curve is as follows -

y^2 + xy = x^3 + ax^2 + b

x is the character "a", or decimal 97, or 0110 0001, or x^6 + x^5 + 1.
a is 3 or x + 1
b is 5 or x^2 + 1
The prime polynomial is 69959 or x^16 + x^12 + x^8 + x^6 + x^2 + x + 1
My field size is 65789 or x^16 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 1 (note 65789 is a prime number but not a prime polynomial)

I happen to know the y value is 2584 or x^11 + x^9 + x^4 + x^3

I then work out each side of the equation as follows -

RHS:

y^2 + xy = x^3 + ax^2 + b
(x^6 + x^5 + 1) * (x^6 + x^5 + 1) * (x^6 + x^5 + 1) = x^18 + x^17 + x^16 + x^15 + x^12 + x^10 + x^6 + x^5 + 1

y^2 + xy = x^3 + ax^2 + b
(x^6 + x^5 + 1) * (x^6 + x^5 + 1) = x^12 + x^10 + 1

y^2 + xy = x^3 + ax^2 + b
(x + 1) * (x^12 + x^10 + 1) = x^13 + x^12 + x^11 + x^10 + x + 1

y^2 + xy = x^3 + ax^2 + b
(x^18 + x^17 + x^16 + x^15 + x^12 + x^10 + x^6 + x^5 + 1) ^ (x^13 + x^12 + x^11 + x^10 + x + 1) = x^18 + x^17 + x^16 + x^15 + x^13 + x^11 + x^6 + x^5 + x

y^2 + xy = (x^3 + ax^2) + b
(x^18 + x^17 + x^16 + x^15 + x^13 + x^11 + x^6 + x^5 + x) ^ (x^2 + 1) = x^18 + x^17 + x^16 + x^15 + x^13 + x^11 + x^6 + x^5 + x^2 + x + 1

Now I reduce via the irreducible polynomial
(x^18 + x^17 + x^16 + x^15 + x^13 + x^11 + x^6 + x^5 + x^2 + x + 1) divided by (x^16 + x^12 + x^8 + x^6 + x^2 + x + 1) = x^2 + x + 1 remainder x^15 + x^14 + x^12 + x^11 + x^10 + x^9 + x^7 + x^5 + x^4 + x

RHS after reduction: x^15 + x^14 + x^12 + x^11 + x^10 + x^9 + x^7 + x^5 + x^4 + x


LHS:

y^2 + xy = x^3 + ax^2 + b
(x^11 + x^9 + x^4 + x^3) * (x^11 + x^9 + x^4 + x^3) = x^22 + x^18 + x^8 + x^6

y^2 + xy = x^3 + ax^2 + b
(x^6 + x^5 + 1) * (x^11 + x^9 + x^4 + x^3) = x^17 + x^16 + x^15 + x^14 + x^11 + x^10 + x^9 + x^8 + x^4 + x^3

(y^2) + (xy) = x^3 + ax^2 + b
(x^22 + x^18 + x^8 + x^6) ^ (x^17 + x^16 + x^15 + x^14 + x^11 + x^10 + x^9 + x^8 + x^4 + x^3) = x^22 + x^18 + x^17 + x^16 + x^15 + x^14 + x^11 + x^10 + x^9 + x^6 + x^4 + x^3

Now I reduce via the irreducible polynomial
(x^22 + x^18 + x^17 + x^16 + x^15 + x^14 + x^11 + x^10 + x^9 + x^6 + x^4 + x^3) / (x^16 + x^12 + x^8 + x^6 + x^2 + x + 1) = x^6 + x + 1 remainder x^15 + x^13 + x^11 + x^10 + x^6 + x^4 + 1

LHS after reduction: x^15 + x^13 + x^11 + x^10 + x^6 + x^4 + 1

...

So as you can see, both my remainders have the correct power, but they are different polynomials.

Assuming my calculations are correct, am I doing the right thing?

Have I missed some important detail?

Damnit.

MOH

I'm completely over my head here, but shouldn't there be a x^11 term in here:

RHS:

y^2 + xy = x^3 + ax^2 + b
(x^6 + x^5 + 1) * (x^6 + x^5 + 1) * (x^6 + x^5 + 1) = x^18 + x^17 + x^16 + x^15 + x^12 + x^11 + x^10 + x^6 + x^5 + 1

(I'm assuming this crazy-ass ECC stuff doesn't care about the coefficients)

[edit]
And shouldn't this:
y^2 + xy = x^3 + ax^2 + b
(x^6 + x^5 + 1) * (x^6 + x^5 + 1) = x^12 + x^10 + 1

include an x^11, x^6 and x^5 ?

(Again, I haven't a clue what this is all about)

AARRRGH

Hi MOH

Thanks for the reply.

Sorry, I should have mentioned the coefficients are reduced modulo 2.

For example -

x^12 + 2x^11 + x^10 + 2x^6 + 2x^5 + 1
gets reduced to
x^12 + x^10 + 1

As you can see, anything with a value of 2 is removed.

Cheers.

MOH

Ah, makes a lot more sense now. Well, a bit

Figured you wouldn't have missed something that obvious.

Have you tried the Maths forum with this?

Martyr

yeah dublindude, you'd probably get answer quicker on mathematics forum, but try sci.crypt group

AARRRGH

I actually figured it out

I calculated the points on the curve using natural numbers such as 1, 2, 3 etc., and naturual number maths such as "normal" addition and multiplication.

I should have calculated the points using polynomial numbers and polynomial maths.

It seems the type of maths you use determines the points on the curve. This makes absolutely no sense to be, but it seems to be the case.

Cheers!