Topic: Curve point divided by integer - is it possible? - page 2. (Read 651 times)

Thank you very much for the demonstration.

It turns out that the modulus function in my bigint dependency library is broken and spits out negative numbers that aren't mod the curve prime. After adding the prime to these negative numbers (and making my addition/multiplication check for points at infinity properly), I get the same results as your example.

No, it should be:
I don't know how you get these numbers from your example. Maybe try implementing it by using smaller numbers and later just increase them? Some related article: https://www.coindesk.com/markets/2014/10/19/the-math-behind-the-bitcoin-protocol/.

We start from base point:
Then we double that point:
As you can see, we have:
That matches 2*G:
Then, we add these two points:
As you can see, we have:
That matches 3*G:

A related problem, I'm implementing secp256k1 multiplication now that I completed and tested add & double, and this is the pseudocode Wikipedia has  about the subject:


I initially thought that d is just a binary decomposition of the multiplicand i.e. 3 => 11b, 6 => 110b, etc. But this doesn't seem to produce the correct results.

3*G (G+G+G) should give me this result (mod p):

Hex:
-6cf75fe6da73cefb6cbb07a0762add64ace37ba7c90664f79fe0eeb431fc536
-c77084f09cd217ebf01cc819d5c80ca99aff5666cb3ddce4934602897b4715bd

decimal:
-3080428797605589366822325834758234751155007324101155494826970452699058783542 -90209061256745311731914079131285931446821116410824268969537695047367247992253

but my implementation of Montgomery ladder is not returning that, so I'm wondering if the d array is supposed to be something else.

She cannot. All she can do is multiplying his public key by her private key.

Edit: for example Alice only has that things:
And Bob only has that things:

If you are Alice, you know "a" and "bG", so you can do "a*bG" that is equal to "abG". If you are Bob, you know "b" and "aG", so you can do "b*aG" that is equal to "abG". In this way, Alice and Bob can create shared secret that is unknown to everyone else. If public key multiplication would be directly possible, then anyone could calculate that shared key and read the whole traffic between Alice and Bob.

It doesn't have to do (directly) with the transaction, you only need the public keys; if they reused their addresses then their public keys would be exposed (so that's how you'd get them). As said by the folks above, if elliptic curve point multiplication was possible you could raise to any power as well. Using Pohlig-Hellman in conjunction with Pollard-Rho would lead you to k with only 2⁵⁴ multiply operations. Knowing k means, you're one equation away for finding out the private key (d).

Since a and b are private keys, then aG is Alice's public key and bG, Bob's public key.

For key agreement the passive observer sees aG sent by alice, and bG sent by bob.  The observer cannot compute abG -- their shared secret.  If they could multiply points they could multiply what they saw aG and bG and get the shared secret and read their traffic.

Multiplying two points allows us to square as well, and consequently rise to any power. Then we can work in the multiplicative group, which has order N-1, and excludes the point at infinity (0,0). ​The biggest factor of N-1 is only 108 bits. Using Pohlig-Hellman in conjunction with Pollard-Rho (or BSGS for smaller factors, and exhaustive search for the smallest) we find k with cost O(2⁵⁴) multiply operations.

I'm no familiar with ECDH, but why would an observer want to compute aG and bG assuming he knows about abG? He can't do anything with aG & bG even if he divides abG to get them. It's like saying that if you had a public key, which was result from the multiplication of two others, and I somehow could reveal them I could also sign from them.

The observer could not compute the shared secret, could he?

How can you defeat the system if you're able of multiplying two points instead of a number and a point?

If you wanted to be silly you could also implement dividing a point by a scalar more directly.

One efficient way of computing a modular inverse is to use the extended GCD algorithm. A GCD starts with a vector of the number to be inverted and the modulus and applies a series of primitive transformations to the numbers which preserve their GCD and reduce their magnitude, until eventually you end up with the [1,0] vector. An extended GCD has an additional vector of numbers mod n which runs along side it and which it applies the same primitive transformations to, which ends up being the modular inverse at the end.  If the GCD you use is a binary GCD then all the transformation operations you perform are simple operations you can perform on curve points. So if you slap ecc points in place of this this secondary vector, the algorithm will divide a curve point by a number directly.

However, given that scalar operations are so much faster than curve operations, this would be slower than computing the inverse and then using a fast scalar/point multiply algorithm.  But I think it could be fairly said to be an algorithm for directly dividing a curve point by a scalar, although a rather silly one.

You cannot.  As garlonicon noted that it would break a lot of ECC protocols if you could.  Probably the simplest example is that in ECDH key agreement: Alice has private key a and sends aG and Bob has private key b and sends bG, and their joint shared secret is H(abG) which they can both compute by multiplying what they received with their own private key and hashing it.  But a passive observer can't multiply the two points, and so they can't compute the shared secret.

In pairing cryptography which is built with specialized elliptic curves that have a precisely engineered weakness you effectively gain an ability to multiply curve points, but only once: the result is in a different group.  But this extra ability alone lets you create all kinds of fancy cryptographic protocols that you can't create with plain ECC (or only exist in interactive form for plain ECC).

One thing that can be done if I know three points and their discrete logs: A=aG, B=bG, C=abG, I can write a proof that convinces you that C is the product of A and B (and that I know their discrete logs), without revealing to you anything else.  But you can't perform the computation yourself.

No it is 1/2 (mod N).
Since we don't exactly have a division defined each [point divided by number] operation is changed into [point] * [modular multiplicative inverse of the divisor].
So P/2 becomes P*2^-1 where 2^-1 is computed by solving 2*x ≡ 1 (mod N)
And x is 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1

FWIW: N/2 = 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0

Apologies for my ignorance but I might recognize this constant from somewhere, is this number n/2 (which means for halfing I can just do k^n-1 I think)?

Yes, of course. For example you can double a point or halve a point by multiplying it by 7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1. It's that simple, for example after halving Satoshi's key you can get:
The same you can do for any number. Division is just multiplication by inverse.
No, because then ECDSA would be broken.

Basically, we can already do kP, so I want to know if P/k = k-1P is doable.

When I said:


I was wondering if two points could be multiplied with each other, as opposed to a point and a number e.g. P*Q.

Modulo prime number for every number (except zero) there's unique inverse. That is, the sequence of all inverse is a permutation of all positive numbers.


Since the curve order is n, then k^-1 is mod n as well.



I cannot guess what you mean.

I am building a secp256k1 class in Node.js to use in my tools, and I know that numbers in a group already have a multiplicative inverse - and how to calculate it - I have point multiplication already implemented but I am not sure if there is such a factor k^-1 such that

k^-1P * kP = P

Is it simply the inverse of k mod curve order n?

This is supposed to be to implement the division operation P/k.

Also - I don't think multiplicative inverse of points (i.e. P^-1, not group numbers) exists, does it?