Title: Why point by point multiplication is undefined in ECDSA? Post by: garlonicon on July 23, 2023, 10:44:45 AM Many people wonder, why we cannot multiply point by point in ECDSA. We can add points, subtract them, multiply point by some number, or divide it (by using inversion). The main reason for that, is this operation requires a hidden argument, that is often missed: the base point.
Many times, people think about things like "halving a point" in a similar way, as how we can do that on integers in many programming languages: if we have 9/10, it gives us zero as the result. In ECDSA world, this is not the case. To better explore, how point by point multiplication could be defined, we can take an elliptic curve you can see in my avatar: "p=79,n=67,base=(1,18),bits=7". It is quite simple, every coordinate takes only one byte, and it can be fully explored, without applying any optimizations, and just by brute forcing everything. So, we start with our p=79. We can easily check if it is prime, and then find the nearest point, meeting famous equation: y^2=x^3+7. All numbers are small enough, so we can even easily create some 79x79 black bitmap, and set pixel color to white, if for a given (x,y) pair, our left and right side is equal modulo 79. We can even try this for some bigger values, then we could get a nice picture for our desktop background, similar to the stars on the sky at night. In this way, we can easily grab the nearest point, being (1,18) in this case. Also, we can count all dots, and note that we have 66 points, and the 67th value is just (0,0), point at infinity, which we can reach later, after trying to add the first, and the last point. So, let's start from the base point, and create the full list of points: Code: d= 1, x= 1, y=18 Code: (1,18)+(1,61)=(0,0) Now, we have everything we need to see, why we cannot multiply point by point. Let's write some multiplications with private keys, and then convert them to corresponding public keys: Code: 2* 3= 6 Code: d= 1, x=75, y=41 Code: 2* 3= 6 Code: (60,10)*(15, 8)=(59,12) Title: Re: Why point by point multiplication is undefined in ECDSA? Post by: digaran on August 02, 2023, 02:56:38 AM So this is the reason when I multiply G by itself I can't figure out what is the result! I wonder if there is a way to find the result private key?🤔
Edit, Ok, I admit that I didn't spend enough time to figure it out, after posting this I went out to find out G * G is what? Here it is public key : Code: 0353854510f675922eb4d1ed3fd044c54d161c85852be5bf8074a8a8b1f2ee5273 Private key : Code: 79be667ef9dcbbac55a06295ce870b098d3e430dcf3ce861da4dc441768b9516 I hope by multiplying point by point, you meant public keys by public keys? if I misunderstood and this is off topic, apology. Title: Re: Why point by point multiplication is undefined in ECDSA? Post by: garlonicon on August 02, 2023, 04:25:59 AM Quote I wonder if there is a way to find the result private key? Only if you know all of them upfront, or you know all relations between all of your public keys. In other cases, not really, because your private key is always relative to your base point. Let's assume you have some (x,y) point, and you start changing your base point. What could happen?Code: 1*1=1 //if you use the same point as a base point Code: Point multiply(Point first,Point second); Code: Point multiply(Point first,Point second,Point base); Quote after posting this I went out to find out G * G is what? In general, if you multiply one by one, you should get one. That means, squaring base point should not change anything, and return the same point. That also means point addition is different than point multiplication, because if you add two points, then you don't have to know the base point.Quote I hope by multiplying point by point, you meant public keys by public keys? Yes, of course. If you have private keys, it is perfectly defined operation. The same is true if you combine some public key with some private key.Title: Re: Why point by point multiplication is undefined in ECDSA? Post by: COBRAS on August 02, 2023, 04:47:45 AM O fu-k !!!
You get a real point in result: How you get (8,19) ? What filormula for multiplication ? (27,16)*(19,54)=( 8,19) (21,74)*(63,16)=(43,44) ( 9,74)*(29, 8)=(43,44) Title: Re: Why point by point multiplication is undefined in ECDSA? Post by: garlonicon on August 02, 2023, 07:23:53 AM https://www.coindesk.com/markets/2014/10/19/the-math-behind-the-bitcoin-protocol/
Quote Point addition of p + q to find r is defined component-wise as follows: c = (qy - py) / (qx - px) rx = c2 - px - qx ry = c (px - rx) - py And point doubling of to find r is as follows: c = (3px2 + a) / 2py rx = c2 - 2px ry = c (px - rx) - py Title: Re: Why point by point multiplication is undefined in ECDSA? Post by: COBRAS on August 02, 2023, 12:35:35 PM https://www.coindesk.com/markets/2014/10/19/the-math-behind-the-bitcoin-protocol/ Quote Point addition of p + q to find r is defined component-wise as follows: c = (qy - py) / (qx - px) rx = c2 - px - qx ry = c (px - rx) - py And point doubling of to find r is as follows: c = (3px2 + a) / 2py rx = c2 - 2px ry = c (px - rx) - py Bro, can you show calculation on this example: (27,16)*(19,54)=( 8,19) ? I NOT UNDERSTAND FORMULA'S WHAT YOU PROVIDE THX Title: Re: Why point by point multiplication is undefined in ECDSA? Post by: COBRAS on August 02, 2023, 06:22:38 PM https://www.coindesk.com/markets/2014/10/19/the-math-behind-the-bitcoin-protocol/ Quote Point addition of p + q to find r is defined component-wise as follows: c = (qy - py) / (qx - px) rx = c2 - px - qx ry = c (px - rx) - py And point doubling of to find r is as follows: c = (3px2 + a) / 2py rx = c2 - 2px ry = c (px - rx) - py Bro, what formula you use for multiply one point to enother point ? Title: Re: Why point by point multiplication is undefined in ECDSA? Post by: casinotester0001 on August 02, 2023, 07:28:22 PM What you need, is something like that: Code: Point multiply(Point first,Point second,Point base); Very interesting. Maybe we should ask user ranochigo. He could know if this is possible. [I will DM him] Title: Re: Why point by point multiplication is undefined in ECDSA? Post by: COBRAS on August 02, 2023, 08:46:45 PM https://www.coindesk.com/markets/2014/10/19/the-math-behind-the-bitcoin-protocol/ Quote Point addition of p + q to find r is defined component-wise as follows: c = (qy - py) / (qx - px) rx = c2 - px - qx ry = c (px - rx) - py And point doubling of to find r is as follows: c = (3px2 + a) / 2py rx = c2 - 2px ry = c (px - rx) - py Can show point's multiplication example ? Multiplication is not classic double and add.... Title: Re: Why point by point multiplication is undefined in ECDSA? Post by: digaran on August 02, 2023, 10:24:17 PM https://www.coindesk.com/markets/2014/10/19/the-math-behind-the-bitcoin-protocol/ Quote Point addition of p + q to find r is defined component-wise as follows: c = (qy - py) / (qx - px) rx = c2 - px - qx ry = c (px - rx) - py And point doubling of to find r is as follows: c = (3px2 + a) / 2py rx = c2 - 2px ry = c (px - rx) - py Can show point's multiplication example ? Multiplication is not classic double and add.... So why are you asking for something that doesn't exist? Title: Re: Why point by point multiplication is undefined in ECDSA? Post by: COBRAS on August 02, 2023, 10:34:39 PM https://www.coindesk.com/markets/2014/10/19/the-math-behind-the-bitcoin-protocol/ Quote Point addition of p + q to find r is defined component-wise as follows: c = (qy - py) / (qx - px) rx = c2 - px - qx ry = c (px - rx) - py And point doubling of to find r is as follows: c = (3px2 + a) / 2py rx = c2 - 2px ry = c (px - rx) - py Can show point's multiplication example ? Multiplication is not classic double and add.... So why are you asking for something that doesn't exist? How you calculate this ? (27,16)*(19,54)=( 8,19) ????? Title: Re: Why point by point multiplication is undefined in ECDSA? Post by: garlonicon on August 03, 2023, 04:19:20 AM Quote How you calculate this ? (27,16)*(19,54)=( 8,19) ????? Simple, I just used private keys first, and then converted everything to public keys, just to show, why multiplication is undefined. If you take (27,16) and multiply it by (19,54), then you can get (8,19), but only if your base point is (75,41), and only if you know all points, or all relations between private and public keys. If you change your base point, you will reach something different. That means, by having two public keys alone, you don't know, what is the result.Addition: you change your base point, everything stays the same Multiplication: you change your base point, your results are now different That's why you cannot multiply two public keys directly. Also note that in my examples, I can convert any public key to private key, but this is true only because there are only 67 points on this small curve, and I can easily just check all of them, which is obviously not the case in secp256k1. But after converting it back when using a different base point, you can easily see, why those results are wrong. Edit: Quote Multiplication is not classic double and add.... Of course it is. And you have all examples in the linked article, also with signatures, and their verification. |