1
$\begingroup$

I'm looking at source code for BitcoinJ that derives a public key from the private key.

  /**
     * Create the public key from the private key
     *
     * @param       privKey             Private key
     * @param       compressed          TRUE to generate a compressed public key
     * @return                          Public key
     */
    private byte[] pubKeyFromPrivKey(BigInteger privKey, boolean compressed) {
        ECPoint point = ecParams.getG().multiply(privKey);
        return point.getEncoded(compressed);
    }

Since "G" is known, and published for each given curve, what prevents someone from dividing (or multiple consecutive subtractions) to determine the private key?

If possible, would you explain it in layman's terms, and also provide additional concepts I can research the relevant background.

$\endgroup$
8
  • 3
    $\begingroup$ The short answer is that there is no (known) efficient algorithm that can solve $A = a G$ for $a$, even when $A$ and $G$ are known. $\endgroup$ – CodesInChaos Feb 11 '14 at 16:26
  • $\begingroup$ @CodesInChaos Thanks. From my algebra background I see A = aG as simple variables. Is the difficulty inherent in the fact we're looking at a multiplicative cyclic group? My intent with this question is to study the simplest approaches to key recovery with crypto the following categories: 1: integer factorization, 2: discrete logarithm, 3: ECC discrete logarithms. $\endgroup$ – halfbit Feb 11 '14 at 16:34
  • $\begingroup$ I'm not sure if this kind of key recovery applies to the 3 scenarios. Again this is all self study so if you have a better path to learning, please do share. $\endgroup$ – halfbit Feb 11 '14 at 16:35
  • $\begingroup$ I used additive notation. If you prefer multiplicative notation you'd say it's hard to solve $A=G^a$ for $a$. This problem (with either notation) is the discrete logarithm problem, which is believed to be hard on (the commonly used) finite fields and elliptic curves). DLP is easy in some groups and hard in others. We use those where it's hard, because else this kind of crypto would be trivially broken. $\endgroup$ – CodesInChaos Feb 11 '14 at 16:37
  • 1
    $\begingroup$ @makerofthings7 DLOG and ECC DLOG are conceptually the same Problem. It is 'logarithms in groups'. You can see an elliptic curve as a fancy way to specify a group. As this group is abelian it is common to denote it additively. $\endgroup$ – gmoktop Feb 11 '14 at 18:41
4
$\begingroup$

Concerning your notation problem, yes that is kind of an issue. First, elliptic curves in cryptography are usually noted in additive notation. That's why the function call is called "multiply" and is not just a "simple multiplication" but in practice it uses the same principle as exponentiation for "normal numbers" (implemented mostly as "square and multiply", or in additive notation "double and add").

In the basic finite fields, however, people use mostly multiplicative notation to imply, that the DLOG problem is hard, because the equivalent problem based on the addition of numbers is quite easy (given numbers $a$ and $b$, everyone can calculate $a\cdot b$).

To answer your problem with the understanding: In elliptic curves, the "division" operation is not possible (well, computationally hard). This is based on the fact, that in elliptic curves we have only one group structure and we have to work with only this. Finite fields, however, offer us two group structures and they are linked by the distributive property, which in return makes the Diffie-Hellman problem easy for the additive group structure.

$\endgroup$
1
-4
$\begingroup$

Generating a public key from a given public key is what is known as a trap door function. The process is easy to compute private key to public key but not public key to private key because the process uses an elliptic curve and modular (like a clock) arithmetic that throws information away when deriving the public key from the private key.

# Super simple Elliptic Curve Presentation. No imported libraries, wrappers, nothing. 

For educational purposes only. Remember to use Python 2.7.6 or lower. You'll need to make changes for Python 3.

Below are the public specs for Bitcoin's curve - the secp256k1

Pcurve = 2256 - 232 - 29 - 28 - 27 - 26 - 2**4 -1 # The proven prime N=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # Number of points in the field Acurve = 0; Bcurve = 7 # These two defines the elliptic curve. y^2 = x^3 + Acurve * x + Bcurve Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240 Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424 GPoint = (Gx,Gy) # This is our generator point. Trillions of dif ones possible

Individual Transaction/Personal Information

privKey = 0xA0DC65FFCA799873CBEA0AC274015B9526505DAAAED385155425F7337704883E #replace with any private key

def modinv(a,n=Pcurve): #Extended Euclidean Algorithm/'division' in elliptic curves lm, hm = 1,0 low, high = a%n,n while low > 1: ratio = high/low nm, new = hm-lmratio, high-lowratio lm, low, hm, high = nm, new, lm, low return lm % n

def ECadd(a,b): # Not true addition, invented for EC. Could have been called anything. LamAdd = ((b[1]-a[1]) * modinv(b[0]-a[0],Pcurve)) % Pcurve x = (LamAddLamAdd-a[0]-b[0]) % Pcurve y = (LamAdd(a[0]-x)-a[1]) % Pcurve return (x,y)

def ECdouble(a): # This is called point doubling, also invented for EC. Lam = ((3*a[0]*a[0]+Acurve) * modinv((2*a[1]),Pcurve)) % Pcurve x = (Lam*Lam-2*a[0]) % Pcurve y = (Lam*(a[0]-x)-a[1]) % Pcurve return (x,y)

def EccMultiply(GenPoint,ScalarHex): #Double & add. Not true multiplication if ScalarHex == 0 or ScalarHex >= N: raise Exception("Invalid Scalar/Private Key") ScalarBin = str(bin(ScalarHex))[2:] Q=GenPoint for i in range (1, len(ScalarBin)): # This is invented EC multiplication. Q=ECdouble(Q); # print "DUB", Q[0]; print if ScalarBin[i] == "1": Q=ECadd(Q,GenPoint); # print "ADD", Q[0]; print return (Q)

print; print "******* Public Key Generation *********"; print PublicKey = EccMultiply(GPoint,privKey) print "the private key:"; print privKey; print print "the uncompressed public key (not address):"; print PublicKey; print print "the uncompressed public key (HEX):"; print "04" + "%064x" % PublicKey[0] + "%064x" % PublicKey[1]; print; print "the official Public Key - compressed:"; if PublicKey[1] % 2 == 1: # If the Y value for the Public Key is odd. print "03"+str(hex(PublicKey[0])[2:-1]).zfill(64) else: # Or else, if the Y value is even. print "02"+str(hex(PublicKey[0])[2:-1]).zfill(64)

$\endgroup$
6
  • 2
    $\begingroup$ "that throws information away when deriving the public key from the private key"; actually, that is not true; no information is thrown away when deriving the public key; the private key is uniquely defined by the public key. The reason the private key is safe is because, even though it is uniquely defined by the public key, we don't know how to recover the private key (that is, without doing a huge amount of computation; far more than what any real adversary can do) $\endgroup$ – poncho Apr 5 '18 at 13:54
  • 1
    $\begingroup$ When a question asks to explain it in layman's terms, I wouldn’t post a wall of code. Instead, it would be better understandable if you would actually explain what’s going on there. Also, you should know that the Python code you posted is incomplete (it misses a few lines at the start… 17 lines to be exact). $\endgroup$ – e-sushi Apr 5 '18 at 14:51
  • $\begingroup$ Thanks for pointing out the missing code. The missing lines of code have been included in an edit of the original post. I included a wall of code because it is a useful working example of how public keys are generated. $\endgroup$ – Donald. Apr 6 '18 at 7:23
  • $\begingroup$ "the private key is uniquely defined by the public key" Is this not the other way around, the public key is uniquely defined by the private key. Also modular arithmetic results in loss of information. For example, if the time on a clock moves from 2AM to 4AM it may be 2hours, 14 hours, 16hours etc of elapsed time. This is a simple modular example of what happens when generating a public key from a private key. Thus information is thrown. $\endgroup$ – Donald. Apr 6 '18 at 7:32
  • $\begingroup$ The code source and explanation is found here youtube.com/watch?v=iB3HcPgm_FI $\endgroup$ – Donald. Apr 6 '18 at 7:46
-5
$\begingroup$

You can absolutely derive the private key from the public key. Just keep subtracting the base point from the public key until you get to the base point. And keep count of how many times you subtracted. You could get extremely lucky on your first try. But that isn't likely. On average, with current computer technologies, it would take thousands of years.

$\endgroup$
3
  • 3
    $\begingroup$ The existence of an infeasible way is no strong indication of the non-existence of a feasible way. $\endgroup$ – fgrieu Feb 13 '20 at 6:25
  • $\begingroup$ Without explaining terms like "negligible" and "computationally hard" and suchlike this answer seems to lack merit. The inclusion of "extremely lucky" and "thousands of years" makes it wrong. And that's besides it making a logically invalid statement, as fgrieu indicates. $\endgroup$ – Maarten Bodewes Feb 13 '20 at 13:37
  • $\begingroup$ I'm not sure what all of you are talking about. Subtracting to get to base point will take millennia, unless you get "extremely lucky". Over the real numbers, you could simply subtract or halve, based on whether the point you are dealing with is even or odd. Over a finite field modulo P, odd vs even goes out the window. So the only option that is SO FAR available is to subtract. And that will take a very long time, unless you get lucky - like "winning five lottery jackpots in a row" lucky. $\endgroup$ – Tom V Feb 14 '20 at 4:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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