COBRAS (OP)
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 905
Merit: 22
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
February 10, 2021, 08:14:17 AM Last edit: February 10, 2021, 08:36:25 AM by COBRAS Merited by NotATether (1) |
|
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?" ![Huh](https://bitcointalk.org/Smileys/default/huh.gif)
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
Jr. Member
Offline
Activity: 34
Merit: 87
|
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
Legendary
Offline
Activity: 1722
Merit: 7203
In memory of o_e_l_e_o
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
February 10, 2021, 10:36:22 AM |
|
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
Moderator
Legendary
Offline
Activity: 4242
Merit: 8672
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
February 10, 2021, 11:27:33 AM Last edit: February 10, 2021, 11:40:37 AM by gmaxwell Merited by ABCbits (2), o_e_l_e_o (2) |
|
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 (OP)
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 905
Merit: 22
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
February 10, 2021, 11:55:44 AM |
|
|
[
|
|
|
NotATether
Legendary
Offline
Activity: 1722
Merit: 7203
In memory of o_e_l_e_o
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
February 10, 2021, 11:59:41 AM |
|
(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.
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
Moderator
Legendary
Offline
Activity: 4242
Merit: 8672
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
February 10, 2021, 12:25:28 PM |
|
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 (OP)
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 905
Merit: 22
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
February 10, 2021, 02:41:02 PM |
|
(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.
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
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
February 10, 2021, 03:12:14 PM |
|
What's black box?
|
|
|
|
|
NotATether
Legendary
Offline
Activity: 1722
Merit: 7203
In memory of o_e_l_e_o
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
February 11, 2021, 05:50:35 AM |
|
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.
|
|
|
|
|