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.

Powered by vBulletin® Version 4.2.2 Copyright © 2020 vBulletin Solutions, Inc. All rights reserved.