PDA

View Full Version : Question about ECC points addition...


SeanC
October 15th, 2002, 06:29
Hi,
After study some essays about ECDSA, one question bother me as following:

For an ecc curve, y^2 + x*y = x^3 + a*x^2 + b over E(F2m),
Points P(x1, y1) and Q(x2, y2) are both belong to E(F2m),
If P==Q, P + Q = 2*P = (x3, y3),
x3 = r^2 + r + a, where r = x1 + y1/x1.
y3 = x1^2 + (r+1) * x3.

My target is to calculate 2^n * P, where n is a large integer.
My question is: r = x1 + y1/x1 should not be always an integer. I set the value of y1/x1 to be an integer instead. So after my calculation, 2^n * P is not correct.

For example, x1 = 2, y1 = 6, a = 8, b = 8, order n = 101.
2^1 * P = (38, 30)
2^2 * P = (36.4xxx, 64.8xxx) <= Not integer.
.................................................<= So the next is not correct if set the previous x3 and y3 to integers.

Does anyone help me to correct it?

Thnks

SeanC

mike
October 16th, 2002, 03:02
Why do you need integers? If you use real numbers, they ought to work just fine. If, on the other hand, you're trying to do ECC on a finite field like GF(2^n), then you do division with inverses:

a/b = a*inv(b)

Multiplication and division work a little differently on finite fields than on reals. I can refer you to some number theory pages on that, if you'd like.

Also, have you read certicom's ECC tutorial?

SeanC
October 17th, 2002, 06:01
Yes, please. I read some papers from certicom already. What paper could see detail about this part?

For a/b, I just check add one or not. How to do it real number if a , b are big integers.

mike
October 18th, 2002, 05:19
A thread on galois fields:

http://www.woodmann.net/forum/showthread.php?threadid=3217#post17209

Here's an easy example to show how to do 1/2 with modular arithmetic. Take n=7. Then 1/2 = inv(2) = x such that x*2=7k+1, where k is an integer. x=4 is one solution. To see that it behaves like 1/2, take 6*4 = 24 = 3*7 + 3 = 3 mod 7.

Something similar happens in galois fields.

For real numbers, don't set the coordinates to integers. Leave them as reals. That's all.

SeanC
October 18th, 2002, 07:07
Oh!

It's Euclidean alogrithm, isn't it? I use it before.

ax = 1 mod b => x = a^-1 mod b.

For finite field over F2^m, the irreducible f(x)=x^m + x^k + 1.
such as sect113r1 in SECG, ecc Curve y^2 + xy = x^3 + ECCa * x^2 + ECCb,
m=113, k=9
ECCa="003088250CA6E7C7FE649CE85820F7"
ECCb="00E8BEE4D3E2260744188BE0E9C723"
Base point: G(Gx0, Gy0)
Gx0="009D73616F35F4AB1407D73562C10F"
Gy0="00A52830277958EE84D1315ED31886"
Order
n="0100000000000000D9CCEC8A39E56F"

2*G: Gx = r^2 + r + ECCa, which r = Gx0 + Gy0 / Gx0.

If I want calculate r, which is correct?
use r = Gx0 + Gy0 * (Gx0^-1 mod n), is it correct for using order?
or
use r = Gx0 + Gy0 * (Gx0^-1 mod f(x))?

I confused above. Also, what goal for compressed base point and compressed order.

Thanks.

mike
October 20th, 2002, 23:42
Quote:
use r = Gx0 + Gy0 * (Gx0^-1 mod f(x))
if by ^-1 mod f(x) you mean the inverse in the field, then yes.
Quote:
Also, what goal for compressed base point and compressed order.
Sorry, I don't know what that means (I know very little about ECC).

SeanC
October 22nd, 2002, 03:12
Thanks a lot.

Certicom use a compressed base point G, which is half length of bit string. I don't know what do they do.

Also, we didn't use the order n. It is the maximum order of G, isn't it? Maybe not.