Topic: Elliptic Curve Point Addition Question - page 2. (Read 869 times)

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.

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.

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.

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:

You'll get this one as a result:

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

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

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.

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  

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.

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

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.

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


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

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.