Revision history [back]

Eliptic Curves - How to check that substract points cross/exceeds the order of curve n?

We have curve: The elliptic curve domain parameters over Fp associated with a Koblitz curve secp256k1 are specified by the sextuple T = (p,a,b,G,n,h) where the finite field Fp is defined by:

  p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
    = 2256 - 232 - 29 - 28 - 27 - 26 - 24 - 1

The curve E: y2 = x3+ax+b over Fp is defined by:

a = 0

b = 7

The base point G form is:

G = (Gx,Gy)
Gx = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 
Gy = 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Finally the order n of G :

n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

I must perform calculate of substract two points:

Let G be the generator point and;

P1=[1]G= (x1,y1)

P2=[2]G= (x2,y2)

When I will subtract P1−P2 -> I will move Point to N-1 with negative y1 of P1

second: Let G be the generator point and;

P5=[5]G= (x1,y1)

P2=[2]G= (x2,y2)

P3=[3]G=(x3,y3)

When I will subtract P2−P5 -> I will take result P3 with negative y3 of P3

it looks like P2−P5 it "similiar" to integer 2 minus integer 5 = we get minus 3 - and in this example -3 it is N-3 .

How to check that substract points cross the order of curve n? without checking y is negative? how to check that substract point is crossed by Point of Infinity and order of the curve?

how to implemented :

Addition in prime fields is the sum of two integers modp. The prime numbers are added word by word and if the sum exceeds p-1, we subtract p from the sum. After each word addition, we carry a bit for the next word addition and add it to the next sum. Implementation of modular subtraction is similar to the implementation of modular addition. But the carry in addition is the borrow in subtraction. If we have a borrow from the word subtraction, we subtract it from the next word operation

exactly I mean check when if the sum exceeds p-1 during substracting and adding point? and

How to check that substract points cross the order of curve n? without checking y is negative? how to check that substract point is crossed by Point of Infinity and order of the curve?

Ps. Sorry for long question.

Eliptic Curves - How to check that substract points cross/exceeds the order of curve n?

We have curve: The elliptic curve domain parameters over Fp associated with a Koblitz curve secp256k1 are specified by the sextuple T = (p,a,b,G,n,h) where the finite field Fp is defined by:

  p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
    = 2256 - 232 - 29 - 28 - 27 - 26 - 24 - 1

The curve E: y2 = x3+ax+b over Fp is defined by:

a = 0

b = 7

The base point G form is:

G = (Gx,Gy)
Gx = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 
Gy = 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Finally the order n of G :

n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

I must perform calculate of substract two points:

Let G be the generator point and;

P1=[1]G= (x1,y1)

P2=[2]G= (x2,y2)

When I will subtract P1−P2 -> I will move Point to N-1 with ~~negative y1 of P1~~( n- y1) of P1 where n is modulus = order of curve

second: Let G be the generator point and;

P5=[5]G= (x1,y1)

P2=[2]G= (x2,y2)

P3=[3]G=(x3,y3)

When I will subtract P2−P5 -> I will take result P3 with ~~negative y3 of P3~~( n- y3) of P3 where n is modulus = order of curve

it looks like P2−P5 it "similiar" to integer 2 minus integer 5 = we get minus 3 - and in this example -3 it is N-3 .

How to check that substract points cross the order of curve n? ~~without checking y is negative?~~ how to check that substract point is crossed by Point of Infinity and order of the curve?

how to implemented :

Addition in prime fields is the sum of two integers modp. The prime numbers are added word by word and if the sum exceeds p-1, we subtract p from the sum. After each word addition, we carry a bit for the next word addition and add it to the next sum. Implementation of modular subtraction is similar to the implementation of modular addition. But the carry in addition is the borrow in subtraction. If we have a borrow from the word subtraction, we subtract it from the next word operation

exactly I mean check when if the sum exceeds p-1 during substracting and adding point? and

How to check that substract points cross the order of curve n? without checking y is negative? how to check that substract point is crossed by Point of Infinity and order of the curve?

Ps. Sorry for long question.

Eliptic Curves - How to check that substract points cross/exceeds the order of curve n?

We have curve: The elliptic curve domain parameters over Fp associated with a Koblitz curve secp256k1 are specified by the sextuple T = (p,a,b,G,n,h) where the finite field Fp is defined by:

  p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
    = 2256 - 232 - 29 - 28 - 27 - 26 - 24 - 1

The curve E: y2 = x3+ax+b over Fp is defined by:

a = 0

b = 7

The base point G form is:

G = (Gx,Gy)
Gx = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 
Gy = 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Finally the order n of G :

n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

I must perform calculate of substract two points:

Let G be the generator point and;

P1=[1]G= (x1,y1)

P2=[2]G= (x2,y2)

When I will subtract P1−P2 -> I will move Point to N-1 with ( n- y1) of P1 where n is modulus = order of ~~curve~~curve and the same value of x

second: Let G be the generator point and;

P5=[5]G= (x1,y1)

P2=[2]G= (x2,y2)

P3=[3]G=(x3,y3)

When I will subtract P2−P5 -> I will take result P3 with ( n- y3) of P3 where n is modulus = order of ~~curve~~curve and the same value of x

it looks like P2−P5 it "similiar" to integer 2 minus integer 5 = we get minus 3 - and in this example -3 it is N-3 .

How to check that substract points cross the order of curve n? how to check that substract point is crossed by Point of Infinity and order of the curve?

how to implemented :

Addition in prime fields is the sum of two integers modp. The prime numbers are added word by word and if the sum exceeds p-1, we subtract p from the sum. After each word addition, we carry a bit for the next word addition and add it to the next sum. Implementation of modular subtraction is similar to the implementation of modular addition. But the carry in addition is the borrow in subtraction. If we have a borrow from the word subtraction, we subtract it from the next word operation

exactly I mean check when if the sum exceeds p-1 during substracting and adding point? and

How to check that substract points cross the order of curve n? without checking y is negative? how to check that substract point is crossed by Point of Infinity and order of the curve?

Ps. Sorry for long question.