3
$\begingroup$

Suppose that I've solved the Discrete Logarithm problem. Can someone explain to me in terms of the example below how to arrange values of Elliptic Curve secp256k1 in a reverse form so that I can calculate a private key from a public key?

Here is the minimal example: $5^x \bmod 17 = 13$ . Then I'd be able to calculate that $x = 4$.

$\endgroup$
4
  • 1
    $\begingroup$ Is this some weird hypothetical (if discrete log was broken over the integers, is there a way to break discrete log over elliptic curves?) or do you really think you've broken discrete log? $\endgroup$
    – Mikero
    Commented Jan 29, 2023 at 7:52
  • 1
    $\begingroup$ 256k1 is an Elliptic Curve group - i.e. it's an additive group rather than the multiplicative group in your example. i.e. $nG =m$ ==> Given $G$ & $m$ find the scalar $n$. This is called the ECDLP - elliptic curve discrete log problem. Much smaller numbers also in elliptic curves. DLP uses 2048 bit keys while ECDLP uses 224 bit keys. That said, I am pretty sure you haven't broken DLP & nor will you break ECDLP $\endgroup$
    – user93353
    Commented Jan 29, 2023 at 8:00
  • 4
    $\begingroup$ A solution for discrete logarithm over finite fields does not always translate into a break of discrete logarithms over elliptic curves. But even solving finite field DLs would be a huge breakthrough, as long it applies to standard fields currently believed to be secure. $\endgroup$ Commented Jan 29, 2023 at 8:00
  • 4
    $\begingroup$ This question has been extensively edited as to remove spurious information out of it, including the claim that the author has solved the DLP problem. Reversing that process or excessive commenting is prohibited on this site. To the author, please try and state your question in the fewest possible words next time and welcome. $\endgroup$
    – Maarten Bodewes
    Commented Jan 29, 2023 at 13:24

3 Answers 3

9
$\begingroup$

The first thing to do in such a case would be to test that your method really achieves something new by replicating existing prime field DLog records. At the time of writing, the largest public discrete log computation in a prime field is credited to Boudot, Gaudry, Guillevic, Heninger, Thomé and Zimmermann. Doing something similar with less than thousands of core years of computing time would qualify as a breakthrough. Using known methods and open-source software, about 400-bit problems should be within reach of amateurs; just replicating that with a new method would still be extremely interesting.

If your method cannot replicate the performance of NFS-based methods, it could still be scientifically interesting if it is sufficiently novel; however, that would be much harder to ascertain than certifying competitive performance.

The discrete logarithm problem in the point group of an elliptic curve does in most cases not have a known polynomial-time reduction to solving a finite field discrete logarithm. Elliptic curve discrete logarithms could be hard even if discrete logarithms in all finite fields turned out to be easy.

$\endgroup$
0
6
$\begingroup$

We can make a valid analogy between solving $5^x \bmod 17 = 13$ and breaking Elliptic Curve cryptography on secp256k1:

  • $x$ is a Private Key
  • $13$ is the matching Public Key
  • $17$ is the curve's parameters ($p$, $a$, $b$, $n$ in secp256k1 parameters)
  • $5$ is the generator point ($G$ in these parameters)

The analogy extends to some of the computations involved in computing $17$ (Public Key) from the other inputs including $x$ (Private Key):

  • Computing $u\times v\bmod 17\mapsto w$ (modular multiplication) is Elliptic Curve point addition $U\hat+V\mapsto W$ (ECadd in this comment). But see the first qualitative difference below, which is why $\hat+$ is not (ordinary or modular) addition $+$. For details on what that does, lookup the math.

  • Computing $u^2\bmod17\mapsto w$ (modular squaring) is Elliptic Curve point doubling $U\hat+U\mapsto W$ (ECdouble), with the same caveats.

  • Computing $u^s\bmod 17\mapsto w$ is Elliptic Curve point multiplication by the integer $s$ (ECmultiply) which computes $s\hat\times U=\underbrace{U\hat+U\hat+\ldots\hat+U}_{s\text{ terms}}\mapsto W$. In this, $\hat\times$ is significantly different from (ordinary or modular) integer multiplication $\times$, in particular because $s\hat\times U$ combines two things of different nature, only one of which is an ordinary integer (much like when we consider 5 stones we are not multiplying integers, nor multiplying stones).

  • Organizing the computation of $u^s\bmod 17$ into a small number of modular squarings and multiplications is directly analogous to organizing $s\hat\times U$ (ECmultiply) into a small number of point doubling (ECdouble) and additions (ECadd). For example, to compute $u^9\bmod 17$ we can compute $u^2\bmod 17$ by modular squaring of $u$, then $u^4\bmod 17$ by modular squaring of the previous result, then $u^8\bmod 17$ by modular squaring of the previous result, then $u^9\bmod 17$ by modular multiplication of the previous result by $u$. Similarly, we can compute $9\hat\times U$ with three ECdouble to get $2\hat\times U$, $4\hat\times U$, $8\hat\times U$, then one ECadd to get $9\hat\times U$.

    Note: my use of $\hat+$ and $\hat\times$ for Elliptic Curve addition and (scalar) multiplication is not standard. More often it's used $+$ and $\times$, with several variations for the later, including $\cdot$ and omission. I hope that a visibly distinguishable notation avoids confusion when getting introduced to Elliptic Curve arithmetic.

Beyond these analogies there are huge differences:

  1. Qualitative, which could make the question's method inapplicable:
    • The group in which $5^x \bmod 17 = 13$ operates is the multiplicative group of a prime field. The secp256k1 group is an Elliptic Curve (group) over a prime field. And we know methods to solve the Discrete Logarithm Problem for multiplicative groups that do not work for other kinds of group. To illustrate the importance of that, we know methods that solve the DLP in practice for any multiplicative group up to size of about 240 decimal digits, when we know nothing practical above about 58 decimal digits for general groups.
    • The order (number of elements) of the group in the question's example is 16, which only has small factors, when the order of secp256k1 is prime. Similarly, there are algorithms that work only for groups with order having only small prime factors, that are inapplicable to groups of prime order.
  2. Quantitative, which could make the question's method hopelessly slow: secp256k1 involves integers up to 78 decimal digits (versus, generously, 2 in the question's example), and the difficulty of solving the DLP in groups built as secp256k1 by available computing means is believed to grow roughly as $10^{d/2}$ where $d$ is the number of decimal digits in the integers involved. $10^{38}$ times more difficult is a helluva of a quantitative difference. For comparison, $10^{26}$ drop of water is more than the oceans contain.

The above differences are why the hypothetical "solved the Discrete Logarithm problem" in the question is a far cry from allowing to "arrange values of Elliptic Curve secp256k1 in a reverse form so that [we] can calculate a private key from a public key".


If a gigantic Public Key can be generated from another gigantic private key with gigantic dots on finite field and it is being done with a 20kb program and within few seconds, why [can't it] be done otherwise?

Solving the DLP is not performing that calculation of Public Key from Private Key "otherwise". It's computing the Private Key from the Public Key, that is performing the reverse computation.

That a reverse computation is much harder than the original is far from unique in math. For example, given two large haphazard primes $p$ and $q$ with $p<q$ (Private Key), performing the ordinary multiplication $p\times q\mapsto n$ (Public Key) is reasonably easy (with pen an paper it can be done up to many dozens of digits using the standard schoolbook algorithm; try it with $84991\times91541$). But finding $p$ or $q$ from $n$ (computing Private Key from Public Key) requires much more effort (try it with $7744548971$). As far as we know, the gap between the two tasks grows fast with the size of $p$. Modern RSA public key cryptography is based on the assumption that finding $p$ or $q$ from $n$ is unfeasible even with powerful computers when $p$ is $300$ decimal digits or more.

ECC public key cryptography with secp256k1 is based on the assumption that computing Private Key $x$ from Public Key $x\hat\times G$ where $\hat \times$ is computed per the parameters of secp256k1, and $G$ is the generator, has difficulty growing about as $10^{d/2}$ where $1\le d<78$ is the number of decimal digits in $x$. And that such computation is infeasible for $x$ about $77$ digits.

$\endgroup$
3
  • $\begingroup$ Well, you all are saying 100% correct. I, being at the first step of something, just asked the next step, and here I've been told how much high next step is? I think whether I am lunatic or just everyone else got no common sense. If a gigantic Public Key can be generated from another gigantic private key with gigantic dots on finite field and it is being done with a 20kb program and within few seconds, why it can be done otherwise?? Why you are thinking that I am talking about brute forcing each and every key on universe? $\endgroup$ Commented Jan 30, 2023 at 5:59
  • $\begingroup$ All I need is the reverse form of ECadd, ECdouble and ECmultiply equations, thats's exactly I asked at the first place. $\endgroup$ Commented Jan 30, 2023 at 6:01
  • 1
    $\begingroup$ @UnpluggedTrio: I have expanded my analogy to include ECadd, ECdouble and ECmultiply. I also added a final section about your "why can't it be done otherwise??". $\endgroup$
    – fgrieu
    Commented Jan 30, 2023 at 7:38
3
$\begingroup$

secp256k1 Elliptic Curve

$E:y^2=x^3+7$ over $\mathbb F_p$ with

$p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$

Generator $G = E(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)$

ECDLP is $rG = P$

$P = E(x,y)$ with $P.x = 115660414424092852739774689410671739462086977293256206809544563743959327999239$

Find $r$

I have taken these numerical values from here - https://asecuritysite.com/ecdh/python_secp256k1ecdh

You can use your algorithm to calculate $r$ & verify it against the value which you can calculate from the site also (because all private keys are given on the page).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.