Any ideas How to find "k" in system of equations ?

[COBRAS]

This is a y^2=x^3+7 elliptic curve points - Q,G_1,G_2,G_3. k_1,k_2,k? - secret exponents:

k_1*G1( x_1,y_1) = Q(X,Y)

k_2*G2( x_2,y_2) = Q(X,Y)

k?*G3( x_3,y_3) = Q(X,Y)

How to find a "k?"

Q - public key, G1,G2,G3 - base points.

Q(x,y),G_1,G_2,G_3. k_1,k_2 - are known !!!

k? - need to find.

Big Thank You

[miner2251]

It is impossible. For example, let's assume that k1=2, k2=3. Then, if you take Q=GenesisPubKey, you would have:

2*halfGenesisPubKey=GenesisPubKey
3*oneThirdOfGenesisPubKey=GenesisPubKey
genesisPrivKey*G=GenesisPubKey

Finding "genesisPrivKey" is impossible in this case, the same for any other public key. If it would be possible, then ECDSA would be gone instantly.

[NotATether]

k represents the private key so it's not supposed to have a trivial calculation for it. The only way to find k in the equation Q=kG would be to find its discrete logarithm. Now finding the discrete logarithm of a point relative to the base point of the curve is what makes the entire process of finding the private key difficult. While it's not theoretically impossible, it takes such an astronomical amount of time that the universe is going to end before you find nearly any discrete logarithm, so for all purposes finding it - and thus the private key - is practically impossible (it's NP-Hard).

[gmaxwell]

I prove your problem is unsolvable assuming the hardness of the discrete logarithm (in the group in question) via blackbox reduction:

Lets assume that someone has a black box BB that solves your problem with some non-negligible probability. When you invoke  BB(k1,G1,k2,G2,G3,Q) it returns k3 (or it fails).

Now I convert BB into a function that solves the discrete log problem for Q with respect to G:

I pick two random numbers r1 and r2.   I now invoke BB(r1, 1/r1 * Q, r2, 1/r2 * Q, G, Q).  If it fails I pick new random numbers and try again.  If it is successful the result is the discrete log of Q with respect to G.

(I suppose to be precise you'd want to randomize the G and Q inputs in case BB just didn't work for some specific G and Q, but I leave the tiny bit of additional algebra as an exercise for the reader).

Thus, no function BB can exists for groups where the DLP cannot be solved, and your question is equivalent to asking how to solve the discrete log problem -- which isn't an answer you're going to find on Bitcointalk.

[COBRAS]

Additional answer to my question from. crypto.stackexchange.com


https://crypto.stackexchange.com/questions/88138/how-to-find-k-in-system-of-equations

[NotATether]

(I suppose to be precise you'd want to randomize the G and Q inputs in case BB just didn't work for some specific G and Q, but I leave the tiny bit of additional algebra as an exercise for the reader).

You'd need some reference base point in order to randomize both G and Q, right? I can choose a random number r3 and set G = 1/r3 * Q, or if G is well-known, G3 is already specified and I could set Q = G*(some arbitrary k) and from there also derive G1 and G2, but I don't see how both G and Q can be randomized at the same time.

Additional answer to my question from. crypto.stackexchange.com


https://crypto.stackexchange.com/questions/88138/how-to-find-k-in-system-of-equations

It appears that that is your Stack Exchange question and you've got the answer to it already:

This reduces to a case of tri-party Diffie-Hellman. So without further information, it's unsolvable.

[gmaxwell]

You'd need some reference base point in order to randomize both G and Q, right? I can choose a random number r3 and set G = 1/r3 * Q, or if G is well-known, G3 is already specified and I could set Q = G*(some arbitrary k) and from there also derive G1 and G2, but I don't see how both G and Q can be randomized at the same time.

You can can multiply both with a single number which preserves the DL, you can also multiply Q by r and the resulting DL by 1/r.

The reason to randomize is just because it makes it obvious how strong the black box reduction is:   Even if the BB could only solve one in a million inputs, you could make it solve _any_ DLP just by invoking it a few million times...  So, unless DLP is broken you can't even have a "kinda sorta works" version of BB, it basically can't work at all.

[COBRAS]

(I suppose to be precise you'd want to randomize the G and Q inputs in case BB just didn't work for some specific G and Q, but I leave the tiny bit of additional algebra as an exercise for the reader).

You'd need some reference base point in order to randomize both G and Q, right? I can choose a random number r3 and set G = 1/r3 * Q, or if G is well-known, G3 is already specified and I could set Q = G*(some arbitrary k) and from there also derive G1 and G2, but I don't see how both G and Q can be randomized at the same time.

Additional answer to my question from. crypto.stackexchange.com


https://crypto.stackexchange.com/questions/88138/how-to-find-k-in-system-of-equations

It appears that that is your Stack Exchange question and you've got the answer to it already:

This reduces to a case of tri-party Diffie-Hellman. So without further information, it's unsolvable.

Q is not randomised. Q is constant. raandomised baseponts(BR), only one BP is not randomised - this is a BP for "k?".For "k?" - G3 is a standart BP for ecp256k1.

This understand ? Idea fined k for standart base point, I have enough randomized GZ so what"- kz*GZ=PUBLIC KEY I not need randomized Q

[bigvito19]

What's black box?

[j2002ba2]

What's black box?

https://en.wikipedia.org/wiki/Black_box

[NotATether]

What's black box?

https://en.wikipedia.org/wiki/Black_box

TL;DR - it's an abstraction of some function for which you don't know it's definition beforehand. It's useful to model things like Discrete Log which don't have a function to compute them generally.

Because they're abstract you don't have to find a single function that works for all of the inputs. You can make the black box a piecewise function and assign to each "piece" a function that works on some inputs, and combine them together like that.