Elliptic Curve Point Addition Question

[elvis13]

1)876742496012344784179985348367087362
*57896044618658097711785492504343953926418782139537452191302581570759080747168=50759922668204382934134837660716306466228361205929188691171789049422319851611495761608191356750899783486890090816
2)5075992266820438293413483766071630646622836120592918869117178904942231985161149 5761608191356750899783486890090816:115792089237316195423570985008687907852837564279074904382605163141518161494336=438371248006172392089992674183543681

3)438371248006172392089992674183543681
 pub key 04811cfaa321171426ac4fc20a3a43f8ab4e9579923fafab4630039d7bb4daa2637f7e8c86ecb69 05e449804b7a85731343618f5a92582e3a7713e038a980d1544

[1714661674]

1714661674

[1714661674]

1714661674

[1714661674]

1714661674

[1714661674]

1714661674

[MixMAx123]

Can we agree to provide numbers here in hexa-decimal?
I can not follow the last bill.
Could you write something?

[sdp]

I am doing a school project about Bitcoin and more specifically point addition on the Elliptic Curve. I am very new to all this so please forgive my mistakes.

I have been reading that when adding points together the result can go "outside of the bounds before intersecting a third point" as in this image.



This is fascinating but also a little confusing and I would like to know more.

So my questions are:

1. Is it possible to know when the point addition process has gone outside of the field?

And

2. Is there a way (like a Python script or something) that I could use to add 2 points and it would tell me if the result went outside of the field?

I know that the result of the addition is still a valid point on the curve, but I would love to know if it passed out of bounds first.

This would be fantastic for my project to show others how this works.

I hope that made sense and thanks in advance for your help.

The math involves different kinds of objects and so the meaning which is understood as "add" is different.  When we say add two numbers in a finite field, which is what you have to do for this to work, we really mean add like integers and then divide by the special modulus value and keep the remainder. 

So take the clock and consider neither the minute nor day but only the hour.  7+7 is considered 2 rather than 14.  So they're right.  You cannot get above 12.  But 7+7 is 14 (in normal addition).  So I think you want to know whether you can determine when the you get different results.  In the case of the clock, you overflow at 12.  Now not only is addition different but so is division, multiplication and subtraction. 

[1] You can calculate the slope the normal way, find the other point on the graph and you'll get some rational number for the slope and the x and y for the new point may not even be integers.  If they are not both integers, this means you would have to follow the slope outside of the field size and wrap around (perhaps many times) in order to get to the field bounded answer.

Follow the instructions of how to calculate a sum of points (now the points have yet another different meaning for add).   Start with say y^2=x^3-x+7.   Figure out two integer points with trial and error.  The desmos graph will give you some points to try.  Plug in numbers that look like they are in integer spots.  Do your point addition as if they are all real numbers.  Post your third point here.  You'll most probably get some non-integer value.

Use a small modulus like 1999 or 113.  Do this the modulus way and you'll get integers smaller than 113.  How to do division modulus 113 is something you should search for yourself also.  Go search for finite fields.

[Tanagi]

Thanks so much for everyone's input so far.

Could I ask if someone would be able to provide a manual step by step example of the point addition process using actual numbers?

Here are 2 random EC points to use from secp256k1.

Privkey: DBD5EBF749EDF69369B251A9434E9B782534294066797AEF1D25ED9B9672E821

x - 109493922098989287353358202596299422915042473617120228714701225409342421241792
y - 109899546570013792669570062242083808994383794323190482590108937934309418520644

+

Privkey: 9A309407E5266673F677C583BF1068615810AF4C1B90D5A8DBB335CC15D05959

x - 69395938208587572292363152174054021882846778300880058382874375807278603471216
y - 88660534177150263324537226657815045924854945333470172921739521551593497336256

I just need the (public key) point addition. No need to do anything with the private keys, they are just there for reference if needed.

I haven't seen this done anywhere (and I've looked a lot). This would be amazing to include in my project and for me to learn what this process actually looks like on paper.

Thanks so much in advance.

[pooya87]

Could I ask if someone would be able to provide a manual step by step example of the point addition process using actual numbers?

You can use any of the open source ECC libraries and find their point addition method then open it in a debugger to call the method and "step through" the code to see what happens on each step. For example in c# using Visual Studio we simply place a break point on that line and then keep pressing F10 to see each step.

[j2002ba2]

Thanks so much for everyone's input so far.

Could I ask if someone would be able to provide a manual step by step example of the point addition process using actual numbers?

Here are 2 random EC points to use from secp256k1.

Privkey: DBD5EBF749EDF69369B251A9434E9B782534294066797AEF1D25ED9B9672E821

x - 109493922098989287353358202596299422915042473617120228714701225409342421241792
y - 109899546570013792669570062242083808994383794323190482590108937934309418520644

+

Privkey: 9A309407E5266673F677C583BF1068615810AF4C1B90D5A8DBB335CC15D05959

x - 69395938208587572292363152174054021882846778300880058382874375807278603471216
y - 88660534177150263324537226657815045924854945333470172921739521551593497336256

I just need the (public key) point addition. No need to do anything with the private keys, they are just there for reference if needed.

I haven't seen this done anywhere (and I've looked a lot). This would be amazing to include in my project and for me to learn what this process actually looks like on paper.

Thanks so much in advance.

Code:

L = (y2 - y1) / (x2 - x1)
x3 = L^2 - x1 - x2
y3 = L(x1 - x3) - y1

      y2 - y1 = 94553076844452666078538149424419144783741135675920254371088167625192913487275
      x2 - x1 = 75694105346914480362575934586442506821074289349400393707630734405845016901087
1 / (x2 - x1) = 57109544797366026611537207709745816878454354988638946088653096565731074851657
            L = 26260209610829739695182151635707675950033180086458470318530731088353219693361
          L^2 = 85396884292048511216639145930585800795235676868516676403763378131573495159908
           x3 = 22299113221787846994488776168920263850616409616156953345645360922861305118563
      x1 - x3 = 87194808877201440358869426427379159064426064000963275369055864486481116123229
   L(x1 - x3) = 114457103505967127914246148065726475976734011734324777350232007537745534737470
           y3 = 4557556935953335244676085823642666982350217411134294760123069603436116216826

[Tanagi]

Code:

L = (y2 - y1) / (x2 - x1)
x3 = L^2 - x1 - x2
y3 = L(x1 - x3) - y1

      y2 - y1 = 94553076844452666078538149424419144783741135675920254371088167625192913487275
      x2 - x1 = 75694105346914480362575934586442506821074289349400393707630734405845016901087
1 / (x2 - x1) = 57109544797366026611537207709745816878454354988638946088653096565731074851657
            L = 26260209610829739695182151635707675950033180086458470318530731088353219693361
          L^2 = 85396884292048511216639145930585800795235676868516676403763378131573495159908
           x3 = 22299113221787846994488776168920263850616409616156953345645360922861305118563
      x1 - x3 = 87194808877201440358869426427379159064426064000963275369055864486481116123229
   L(x1 - x3) = 114457103505967127914246148065726475976734011734324777350232007537745534737470
           y3 = 4557556935953335244676085823642666982350217411134294760123069603436116216826

Thanks so much and please excuse my lack of math skills.

How did you get y2-y1 to equal that? When I did it it ends up being a negative number.

Also, where does modp come into it all?

Thanks again.

[o_e_l_e_o]

How did you get y2-y1 to equal that? When I did it it ends up being a negative number.

Also, where does modp come into it all?

You've answered your own question here.

The secp256k1 curve which bitcoin uses is defined over the field p. So all calculations must be done modulo p. p is defined as:

FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
2²⁵⁶ - 2³² - 2⁹ - 2⁸ - 2⁷ - 2⁶ - 2⁴ - 1
115792089237316195423570985008687907853269984665640564039457584007908834671663

With the coordinates you have given above, y2 - y1 gives:

Code:

-21239012392863529345032835584268763069528848989720309668369416382715921184388

Take that number mod p, and you get:

Code:

94553076844452666078538149424419144783741135675920254371088167625192913487275

[Tanagi]

Code:

L = (y2 - y1) / (x2 - x1)
x3 = L^2 - x1 - x2
y3 = L(x1 - x3) - y1

      y2 - y1 = 94553076844452666078538149424419144783741135675920254371088167625192913487275
      x2 - x1 = 75694105346914480362575934586442506821074289349400393707630734405845016901087
1 / (x2 - x1) = 57109544797366026611537207709745816878454354988638946088653096565731074851657
            L = 26260209610829739695182151635707675950033180086458470318530731088353219693361
          L^2 = 85396884292048511216639145930585800795235676868516676403763378131573495159908
           x3 = 22299113221787846994488776168920263850616409616156953345645360922861305118563
      x1 - x3 = 87194808877201440358869426427379159064426064000963275369055864486481116123229
   L(x1 - x3) = 114457103505967127914246148065726475976734011734324777350232007537745534737470
           y3 = 4557556935953335244676085823642666982350217411134294760123069603436116216826

Thanks again for your help.

To get L, can you break this down further for me please?

Code:

1 / (x2 - x1) = 57109544797366026611537207709745816878454354988638946088653096565731074851657
            L = 26260209610829739695182151635707675950033180086458470318530731088353219693361

If L = (y2 - y1) / (x2 - x1) what does 1 / (x2 - x1) mean?

I don't quite understand, sorry.

Thank you.

[NotATether]

If L = (y2 - y1) / (x2 - x1) what does 1 / (x2 - x1) mean?

It means that you take the result of x2 - x1 = xdiff, and then raise it to the (p-2)th power: xdiff^p-2 mod p. (xdiff^p-1 % p would be equal to 1, while xdiff^p % p is simply xdiff) where p is the curve characteristic.

It's just a shorthand way of writing the above expression as division doesn't really exist in elliptic curves but modular inverses do.

[Tanagi]

If L = (y2 - y1) / (x2 - x1) what does 1 / (x2 - x1) mean?

It means that you take the result of x2 - x1 = xdiff, and then raise it to the (p-2)th power: xdiff^p-2 mod p. (xdiff^p-1 % p would be equal to 1, while xdiff^p % p is simply xdiff) where p is the curve characteristic.

It's just a shorthand way of writing the above expression as division doesn't really exist in elliptic curves but modular inverses do.

I get this

It means that you take the result of x2 - x1 = xdiff

but I totally don't uderstand this

then raise it to the (p-2)th power: xdiffp-2 mod p. (xdiffp-1 % p would be equal to 1

I need this explained in the simplest possible terms please.

That's why I asked for a step by step breakdown (every step) would be much appreciated.

[o_e_l_e_o]

You cannot divide in the normal way on an elliptic curve. Instead you have to use something called the multiplicative inverse.

To find the multiplicative inverse of a number on a elliptic curve, then you are looking for another number so that when the two are multiplied together modulo p, then the answer is 1.

For example, if we consider a curve modulo 17, then the multiplicative inverse of 2 would be 9, since 2*9 = 18, modulo 17 = 1. The multiplicative inverse of 5 would be 7, since 5*7 = 35, modulo 17 = 1.

So 1 / (x2 - x1) is finding the multiplicative inverse of (x2 - x1.) Once you've found the multiplicative inverse, then instead of doing (y2 - y1) divided by (x2 - x1), you instead do (y2 - y1) multiplied by the multiplicative inverse of (x2 - x1).

All of these operations will be modulo p.