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

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?

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.

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.

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.

if by ^-1 mod f(x) you mean the inverse in the field, then yes.Sorry, I don't know what that means (I know very little about ECC).

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.