Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
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. – CodesInChaos Feb 11 '14 at 16:26
@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. – LamonteCristo Feb 11 '14 at 16:34
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. – LamonteCristo Feb 11 '14 at 16:35
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. – CodesInChaos Feb 11 '14 at 16:37
@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. – gmoktop Feb 11 '14 at 18:41

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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