Why point by point multiplication is undefined in ECDSA?

[garlonicon]

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
d= 2, x=60, y=10
d= 3, x=15, y= 8
d= 4, x=49, y= 5
d= 5, x=42, y=54
d= 6, x=59, y=12
d= 7, x=61, y=10
d= 8, x=43, y=35
d= 9, x=37, y=69
d=10, x=26, y=19
d=11, x=18, y=54
d=12, x=12, y=47
d=13, x=39, y=47
d=14, x= 9, y= 5
d=15, x=63, y=63
d=16, x=19, y=25
d=17, x=75, y=41
d=18, x=21, y=74
d=19, x=68, y=63
d=20, x=29, y= 8
d=21, x= 6, y=12
d=22, x=45, y=19
d=23, x=35, y=71
d=24, x=66, y=41
d=25, x=28, y=32
d=26, x=17, y=41
d=27, x=14, y=67
d=28, x=74, y=35
d=29, x=23, y=18
d=30, x=55, y=61
d=31, x=41, y=35
d=32, x= 8, y=60
d=33, x=27, y=63
d=34, x=27, y=16
d=35, x= 8, y=19
d=36, x=41, y=44
d=37, x=55, y=18
d=38, x=23, y=61
d=39, x=74, y=44
d=40, x=14, y=12
d=41, x=17, y=38
d=42, x=28, y=47
d=43, x=66, y=38
d=44, x=35, y= 8
d=45, x=45, y=60
d=46, x= 6, y=67
d=47, x=29, y=71
d=48, x=68, y=16
d=49, x=21, y= 5
d=50, x=75, y=38
d=51, x=19, y=54
d=52, x=63, y=16
d=53, x= 9, y=74
d=54, x=39, y=32
d=55, x=12, y=32
d=56, x=18, y=25
d=57, x=26, y=60
d=58, x=37, y=10
d=59, x=43, y=44
d=60, x=61, y=69
d=61, x=59, y=67
d=62, x=42, y=25
d=63, x=49, y=74
d=64, x=15, y=71
d=65, x=60, y=69
d=66, x= 1, y=61
d=67, x= 0, y= 0
d=68, x= 1, y=18

After handling corner cases, we can convert any private key "d" to "(x,y)" pair, representing our public key, and make it rolling ad infinitum:

Code:

(1,18)+(1,61)=(0,0)
(1,18)+(0,0)=(1,18)

As we can see, we started from p=79, and y^2=x^3+7, nothing else. We reached n=67, and now we can be 100% sure that it is not just some result we picked. It is the only valid result, that makes things tick, and meets our criteria, being as close to secp256k1 as possible, and using smaller numbers to demonstrate things. By going into bigger numbers, we can get even more convinced, that "n" was not arbitrarily chosen: it was just calculated, by using very well optimized code.

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
 5* 7=35
11*13=35 (mod 67)

(60,10)*(15, 8)=(59,12)
(42,54)*(61,10)=( 8,19)
(18,54)*(39,47)=( 8,19)

And now, let's assume we want to use a different base point, for example (75,41), instead of (1,18). Let's generate the full list of points again, and see, how everything was suddenly changed:

Code:

d= 1, x=75, y=41
d= 2, x=27, y=16
d= 3, x=19, y=54
d= 4, x= 1, y=18
d= 5, x=21, y=74
d= 6, x= 8, y=19
d= 7, x=63, y=16
d= 8, x=60, y=10
d= 9, x=68, y=63
d=10, x=41, y=44
d=11, x= 9, y=74
d=12, x=15, y= 8
d=13, x=29, y= 8
d=14, x=55, y=18
d=15, x=39, y=32
d=16, x=49, y= 5
d=17, x= 6, y=12
d=18, x=23, y=61
d=19, x=12, y=32
d=20, x=42, y=54
d=21, x=45, y=19
d=22, x=74, y=44
d=23, x=18, y=25
d=24, x=59, y=12
d=25, x=35, y=71
d=26, x=14, y=12
d=27, x=26, y=60
d=28, x=61, y=10
d=29, x=66, y=41
d=30, x=17, y=38
d=31, x=37, y=10
d=32, x=43, y=35
d=33, x=28, y=32
d=34, x=28, y=47
d=35, x=43, y=44
d=36, x=37, y=69
d=37, x=17, y=41
d=38, x=66, y=38
d=39, x=61, y=69
d=40, x=26, y=19
d=41, x=14, y=67
d=42, x=35, y= 8
d=43, x=59, y=67
d=44, x=18, y=54
d=45, x=74, y=35
d=46, x=45, y=60
d=47, x=42, y=25
d=48, x=12, y=47
d=49, x=23, y=18
d=50, x= 6, y=67
d=51, x=49, y=74
d=52, x=39, y=47
d=53, x=55, y=61
d=54, x=29, y=71
d=55, x=15, y=71
d=56, x= 9, y= 5
d=57, x=41, y=35
d=58, x=68, y=16
d=59, x=60, y=69
d=60, x=63, y=63
d=61, x= 8, y=60
d=62, x=21, y= 5
d=63, x= 1, y=61
d=64, x=19, y=25
d=65, x=27, y=63
d=66, x=75, y=38
d=67, x= 0, y= 0
d=68, x=75, y=41

Then, let's write the same multiplications again:

Code:

 2* 3= 6
 5* 7=35
11*13=35 (mod 67)

(27,16)*(19,54)=( 8,19)
(21,74)*(63,16)=(43,44)
( 9,74)*(29, 8)=(43,44)

See? Everything is completely different. Everything was changed. We can even take our old points, and see, what private keys are hidden behind them, when we calculate it under our new base point:

Code:

(60,10)*(15, 8)=(59,12)
(42,54)*(61,10)=( 8,19)
(18,54)*(39,47)=( 8,19)

8*12=24
20*28=6
44*52=6

See? Point by point multiplication leads to completely wrong results, if it is done directly, based on two points, without calculating things relatively to the base point. I hope this topic will help to better understand, why some operations cannot be done in ECDSA, and how implicit things like base point can change everything, if we forget to consider them in our calculations.

[1714249401]

1714249401

[1714249401]

1714249401

[1714249401]

1714249401

[1714249401]

1714249401

[digaran]

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.

[garlonicon]

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
2*2=4 //if you use half of that point as a base point

And then, if you have only (x,y) coordinates, then without a base point, you don't know if after multiplication by itself, you should get the same point, or some different point. That means, if you want to write any point-by-point multiplication, this is not enough:

Code:

Point multiply(Point first,Point second);

What you need, is something like that:

Code:

Point multiply(Point first,Point second,Point base);

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.

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.

[COBRAS]

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, =(43,44)

[garlonicon]

https://www.coindesk.com/markets/2014/10/19/the-math-behind-the-bitcoin-protocol/

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

[COBRAS]

https://www.coindesk.com/markets/2014/10/19/the-math-behind-the-bitcoin-protocol/

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

[COBRAS]

https://www.coindesk.com/markets/2014/10/19/the-math-behind-the-bitcoin-protocol/

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 ?

[casinotester0001]

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]

[COBRAS]

https://www.coindesk.com/markets/2014/10/19/the-math-behind-the-bitcoin-protocol/

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....

[digaran]

https://www.coindesk.com/markets/2014/10/19/the-math-behind-the-bitcoin-protocol/

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....

There is no such a thing as multiplying 2 public keys to have a valid result, you can't multiply public key 3 with 2 to have the public key of private key 6.

So why are you asking for something that doesn't exist?

[COBRAS]

https://www.coindesk.com/markets/2014/10/19/the-math-behind-the-bitcoin-protocol/

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....

There is no such a thing as multiplying 2 public keys to have a valid result, you can't multiply public key 3 with 2 to have the public key of private key 6.

So why are you asking for something that doesn't exist?

How you calculate this ? (27,16)*(19,54)=( 8,19) ??

[garlonicon]

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:

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.