Bitcoin Forum

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.

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.

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.

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.

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  :)

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.

What kind of script? You can calculate the addition of those public keys really easily. Just take a program, such as Secp256k1 Calculator (https://github.com/MrMaxweII/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.

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.

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.

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.

Thank you Danny.

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

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

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.

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.

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

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 =
From your example

b =
b is added as a new auxiliary variable.

c =
From your example

a*c =

b*c =


a*c+b*c =


(a+b) =

(a+b)*c =


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?

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

3)438371248006172392089992674183543681
 pub key 04811cfaa321171426ac4fc20a3a43f8ab4e9579923fafab4630039d7bb4daa2637f7e8c86ecb69 05e449804b7a85731343618f5a92582e3a7713e038a980d1544

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

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.

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.

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.

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.

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:

Take that number mod p, and you get:

Thanks again for your help.

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


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

I don't quite understand, sorry.

Thank you.

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

but I totally don't uderstand this

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.

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.