Elliptic Curve Point Addition Question

[Tanagi]

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.

https://i.stack.imgur.com/6bh88.png

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.

[1715282005]

1715282005

[1715282005]

1715282005

[1715282005]

1715282005

[NotATether]

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

Implement a check before you do the modulus (I assume you made your own Point class) looking something like this:

Code:

x = # x point calculation
y = # y point calculation

if x > p_order:
   print("X out of range: {}".format(x))
if y > p_order:
   print("Y out of range: {}".format(y))

x %= p
y %= p

This will make your point addition much slower but it's also the only way to detect whether the addition went outside the field.

[j2002ba2]

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 point at infinity is not "outside the field", since by definition it is included.

For secp256k1 adding two points results in the infinity point (zero), if and only if the x coordinates are equal, and y coordinates differ: x1 = x2, and y1 ≠ y2. In jacobian coordinates you'd need to check some intermediate calculations for equality: x1*z2^2 = x2*z1^2, and y1*z2^3 ≠ y2*z1^3.

Usually the point at infinity is denoted as (0,0), or (0,0,1) in jacobian coordinates. Check if y is zero.

[NotATether]

This is not point is outside becouse after this you do modulo.
The question propably was when the point are outside after finished addition -> so after reduction modulo.
that what have you below describe is not right, please show how to get point outside of the field after reduction modulo. I will give you 100 BTC:) becouse then I can break ECDSA

Not sure what you're referring to with the italic text because he never asked to get a point outside the field after modulo.

[Tanagi]

This is not point is outside becouse after this you do modulo.
The question propably was when the point are outside after finished addition -> so after reduction modulo.
that what have you below describe is not right, please show how to get point outside of the field after reduction modulo. I will give you 100 BTC:) becouse then I can break ECDSA

Not sure what you're referring to with the italic text because he never asked to get a point outside the field after modulo.

Thanks.

Again I'm sorry as I am so new to this.

What I meant was during the public key addition.

So I know that when you add 2 public keys together it always results in a valid point on the curve, but sometimes the calculation goes "around" and then back in the other side (if that makes sense) before finding the new point. As in the picture I put in my first post.

I don't think this breaks anything does it as it's only on the public side.

[Tanagi]

Would it be possible for some amazing kind person to write the script for me? I can't code.

It would be fantastic for my project to show this principal in action.

So basically I would put in 2 public keys, for example:

044BDC661EFDC05C536E1E116B9E059D0E36AA3A25253E18DFC0DDEFD4FACF36F322D570A7D46E4 F19E3D94869FEF6894ADFA93771837F36B03D3E8341FB15B62C

and

0405FC50574C83CC70A20BDE37F637F76EC53F7780A8FE6C4A4EA7EE9641FD5D39C9523862EBE58 3E5A9B1423DDC54C789EB332DD9D30A2939CB10258D88987C1F

and the script would add them normally, but also tell me if it went outside the field during the addition process.

I have  just learned that it doesn't actually go "outside" the field, but more like past 0 and starts again.

Thank you so much in advance if someone could do this  

[ymgve2]

As others have explained, if it was possible to see when it went past "0" during addition, that would be equal to breaking all private keys. So of course no one is able to tell you a way to do that.

[Tanagi]

As others have explained, if it was possible to see when it went past "0" during addition, that would be equal to breaking all private keys. So of course no one is able to tell you a way to do that.

Oh, I don't really understand why, but ok thank you.

[BlackHatCoiner]

Would it be possible for some amazing kind person to write the script for me? I can't code.

What kind of script? You can calculate the addition of those public keys really easily. Just take a program, such as Secp256k1 Calculator and fill the proper fields.

Once you add those two points:

Code:

x: 4BDC661EFDC05C536E1E116B9E059D0E36AA3A25253E18DFC0DDEFD4FACF36F3
y: 22D570A7D46E4F19E3D94869FEF6894ADFA93771837F36B03D3E8341FB15B62C

x: 05FC50574C83CC70A20BDE37F637F76EC53F7780A8FE6C4A4EA7EE9641FD5D39
y: C9523862EBE583E5A9B1423DDC54C789EB332DD9D30A2939CB10258D88987C1F

You'll get this one as a result:

Code:

x: 937192A2BA413909EA6AED1CA53E0AA294736BBB6F41164D159E0A7392926C00
y: 56AFE970031AD898FE0AAD818C133E131122EE682E8FF9C3F1DAB493754999EF

Since it returns you coordinates, it's not outside the curve.

[Tanagi]

Would it be possible for some amazing kind person to write the script for me? I can't code.

What kind of script? You can calculate the addition of those public keys really easily. Just take a program, such as Secp256k1 Calculator and fill the proper fields.

Once you add those two points:

Code:

x: 4BDC661EFDC05C536E1E116B9E059D0E36AA3A25253E18DFC0DDEFD4FACF36F3
y: 22D570A7D46E4F19E3D94869FEF6894ADFA93771837F36B03D3E8341FB15B62C

x: 05FC50574C83CC70A20BDE37F637F76EC53F7780A8FE6C4A4EA7EE9641FD5D39
y: C9523862EBE583E5A9B1423DDC54C789EB332DD9D30A2939CB10258D88987C1F

You'll get this one as a result:

Code:

x: 937192A2BA413909EA6AED1CA53E0AA294736BBB6F41164D159E0A7392926C00
y: 56AFE970031AD898FE0AAD818C133E131122EE682E8FF9C3F1DAB493754999EF

Since it returns you coordinates, it's not outside the curve.

Thanks so much, but I wanted to know if, during the calculation, it had to go past "0" to calculate the result like in the image I attached in my first post.

I think I was using the wrong language by saying outside of the field or curve.

I know that the addition always results in a valid point, but did it have to go "around the clock" to get there?

I am trying to show the results in my school project so the Python script (or something) would be fantastic to show it in action.

Thanks again.

[DannyHamilton]

Ok, lots of people telling you it can't be done, and saying that it would break ECDSA, but not a lot of explanation about why or how to think about that.

Let's look at it this way....

I assume when you say "around the clock" what you really mean is that you've come back through the base point G, or rather that the point you've generated is equal to G plus something greater than the order of the curve.

Here lies the problem.  If you can look at a point (a public key) and know that you had to add G more than a set number of times to get there, then you could calculate the private key from the point:
Was it greater than half the order? No? Ok, how about greater than a fourth of the order? Yes? Ok, how about greater than three-eighths of the order? Yes? Ok, how about greater than seven-sixteenths of the order...  and so on until you narrowed in on the exact value of the private key.

There is no way to look at 2 points, and determine which one has the greater private key.

Points are added by calculating the line that passes between both of them, and then calculating where else that line intersects the curve. If you knew the private keys for those two points to start with, then you could figure out if the sum of the two private keys was greater than the order of the curve, but if you don't know the private keys, then you don't have any way of finding out what all the points are for all the private keys that you skipped over when you added the points together. As such, there's no way to know if any of those points were G.  Again, if you could know that some given private key existed "in between" the private keys of 2 given points, then you could use that information to quickly and easily narrow in on the private key of any given point.

Does this help you understand why your question isn't going to have an answer?  You are thinking about private keys, and how if the private key exceeds the order of the curve then it "wraps around" giving the same results as the new private key minus the order of the curve, but you aren't asking about private keys.  You're asking about public keys.  Since there is no way to calculate the private key from the public key, there's no way to know what the relationship is between the private keys for 2 given public keys.  Which is greater?  How far apart are they?  You either need to know the private keys to start with, or you need to calculate every point in between to see if any of them are G.

Now, if you want to do your demonstration by picking 2 private keys, and then calculate the public keys from them... That's a different story.  In that case, you already KNOW both the private keys.  If the sum of those two integers is larger than the order of the curve, then you've wrapped around, if it isn't, then you haven't.  That's a simple calculation, and doesn't need a script.

[j2002ba2]

Thanks so much, but I wanted to know if, during the calculation, it had to go past "0" to calculate the result like in the image I attached in my first post.

I think I was using the wrong language by saying outside of the field or curve.

I know that the addition always results in a valid point, but did it have to go "around the clock" to get there?

I am trying to show the results in my school project so the Python script (or something) would be fantastic to show it in action.

Thanks again.

Two different numbers in a modular field are both bigger and smaller than each other - there are infinite bunch of numbers corresponding to each one, positive, negative, imaginary. So comparing them makes no sense. Any operation passes through zero any number of times in both directions. Furthermore, the real x and y from the equation y² = x³ + 7 are never both integer (or rational). They have integer representation when taken modulo p, but that's all.

[Tanagi]

Ok, lots of people telling you it can't be done, and saying that it would break ECDSA, but not a lot of explanation about why or how to think about that.

Let's look at it this way....

I assume when you say "around the clock" what you really mean is that you've come back through the base point G, or rather that the point you've generated is equal to G plus something greater than the order of the curve.

Here lies the problem.  If you can look at a point (a public key) and know that you had to add G more than a set number of times to get there, then you could calculate the private key from the point:
Was it greater than half the order? No? Ok, how about greater than a fourth of the order? Yes? Ok, how about greater than three-eighths of the order? Yes? Ok, how about greater than seven-sixteenths of the order...  and so on until you narrowed in on the exact value of the private key.

There is no way to look at 2 points, and determine which one has the greater private key.

Points are added by calculating the line that passes between both of them, and then calculating where else that line intersects the curve. If you knew the private keys for those two points to start with, then you could figure out if the sum of the two private keys was greater than the order of the curve, but if you don't know the private keys, then you don't have any way of finding out what all the points are for all the private keys that you skipped over when you added the points together. As such, there's no way to know if any of those points were G.  Again, if you could know that some given private key existed "in between" the private keys of 2 given points, then you could use that information to quickly and easily narrow in on the private key of any given point.

Does this help you understand why your question isn't going to have an answer?  You are thinking about private keys, and how if the private key exceeds the order of the curve then it "wraps around" giving the same results as the new private key minus the order of the curve, but you aren't asking about private keys.  You're asking about public keys.  Since there is no way to calculate the private key from the public key, there's no way to know what the relationship is between the private keys for 2 given public keys.  Which is greater?  How far apart are they?  You either need to know the private keys to start with, or you need to calculate every point in between to see if any of them are G.

Now, if you want to do your demonstration by picking 2 private keys, and then calculate the public keys from them... That's a different story.  In that case, you already KNOW both the private keys.  If the sum of those two integers is larger than the order of the curve, then you've wrapped around, if it isn't, then you haven't.  That's a simple calculation, and doesn't need a script.

Thank you Danny.

The time and care you have taken to explain this is very much appreciated.

[Tanagi]

Does anyone know of a website or app where I can input the EC points and it will visually show the addition on a graph of the curve/field?

This would greatly help with my school presentation.

Thanks.

[_Counselor]

Does anyone know of a website or app where I can input the EC points and it will visually show the addition on a graph of the curve/field?

This would greatly help with my school presentation.

Thanks.

you can try to use this tool - https://www.desmos.com/calculator/ialhd71we3

[Tanagi]

you can try to use this tool - https://www.desmos.com/calculator/ialhd71we3

Thanks so much. I was looking at this on Desmos. It looks like a very useful tool.

I want something for the finite field where I can input actual secp256k1 points.

[MixMAx123]

Does anyone know of a website or app where I can input the EC points and it will visually show the addition on a graph of the curve/field?

This would greatly help with my school presentation.

Thanks.

I also have a tool for you, which may be able to use it.
This allows you to carry out all possible bills on the SECP256K1 curve.

https://github.com/MrMaxweII/Secp256k1-Calculator

[Tanagi]

I also have a tool for you, which may be able to use it.
This allows you to carry out all possible bills on the SECP256K1 curve.

https://github.com/MrMaxweII/Secp256k1-Calculator

Thank you.

[elvis13]

Your calculator is not counting correctly! Check x = f196d3200d66872e9573cab8117b3943f482fc2d4ac53be85b34ffad9e8d640c
y = 6bd66e5ca7201d9d22717b1b70719955ca94e864bcedaba2c28d3d0083b5c167
I multiply by scalar 7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0
And I cry x = 811cfaa321171426ac4fc20a3a43f8ab4e9579923fafab4630039d7bb4daa263
y = 8081737913496fa1bb67fb4857a8cecbc9e70a56da7d1c588ec1fc7467f2e6eb
This is the wrong result. Should be x = 811cfaa321171426ac4fc20a3a43f8ab4e9579923fafab4630039d7bb4daa263
y = 7f7e8c86ecb6905e449804b7a85731343618f5a92582e3a7713e038a980d1544

[MixMAx123]

Thank you for using the Calculator and feedback. :-) How did you calculate it? Is there an alternate SECP256K1 Calculator with which I could compare the result?


Distributive rule

a*c + b*c = (a+b)*c

a =

Code:

f196d3200d66872e9573cab8117b3943f482fc2d4ac53be85b34ffad9e8d640c
6bd66e5ca7201d9d22717b1b70719955ca94e864bcedaba2c28d3d0083b5c167

From your example

b =

Code:

d39da1d0d1e5bcc80c4b4bf28701d4b611d412a9c353b1aaae763e9c79fa7440
eace7dbd056c7387a5e722618a1e1ca5847c8ae5f34dbdd055c3c2e82c7c8df9

b is added as a new auxiliary variable.

c =

Code:

7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0

From your example

a*c =

Code:

811cfaa321171426ac4fc20a3a43f8ab4e9579923fafab4630039d7bb4daa263
8081737913496fa1bb67fb4857a8cecbc9e70a56da7d1c588ec1fc7467f2e6eb

b*c =

Code:

db0480ae98d0e58c33d3cc688903ff97e969294205c803cbc335e205925015c7
f5929b8c91e93238e97d49015c75dc167b78fa5b4cb3ca940109ec7678268f06

a*c+b*c =

Code:

c06505b3654507829b89e29cf23aaac01d63475e557aaf5bc459b9695ca43534
fb204d5b4fadabbadfcace89bf83e2bb55716c35baa07e513b2d451ef1cf0b4

(a+b) =

Code:

b3e33118e17710de40d779d3bf42fdd25fdd45c7c380cf321e07998af5452079
80b110cb68c2cb8cec778213c4a651671f422fb07441da842149faa46a7fb47e

(a+b)*c =

Code:

c06505b3654507829b89e29cf23aaac01d63475e557aaf5bc459b9695ca43534
fb204d5b4fadabbadfcace89bf83e2bb55716c35baa07e513b2d451ef1cf0b4

I think it's right.
Because the distributive law proves it.
Is there anyone who keeps it wrong or that it can confirm the result?