Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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
1  
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 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. –  makerofthings7 Feb 11 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. –  makerofthings7 Feb 11 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 at 16:37
1  
@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 at 18:41
show 1 more comment

1 Answer 1

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
add comment

Your Answer

 
discard

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.