decompressKey method in ECKey return compressed keys

[GoogleCodeExporter]

decompressKey(...)..getEncoded() return 33 byte long buffer!

changing true to false in the return statements below solve the problem to me!

Is that correct?

 if (beta.toBigInteger().testBit(0) == yBit) {
     return new ECPoint.Fp(curve, x, beta, true); // <= change true to false ?
 } else {
     ECFieldElement.Fp y = new ECFieldElement.Fp(curve.getQ(), curve.getQ().subtract(beta.toBigInteger()));
     return new ECPoint.Fp(curve, x, y, true); // <= change true to false ?
 }

Regards

Original issue reported on code.google.com by yves.cui...@gmail.com on 1 Jul 2013 at 5:28

[GoogleCodeExporter]

That method is private, it's not really a public API. decompressKey is meant to 
give you back a point on the curve. The "compressedness" is just a flag in the 
ECPoint structure, so yes, when you use getEncoded() it will re-compress it. 
The point itself is the uncompressed form. If you want to get the ECPoint with 
the flag set to off, you can modify that function, or you could do:

p = new ECPoint.Fp(curve, q.getX(), q.getY(), false);

yourself.

What are you actually trying to do here?

Original comment by hearn@google.com on 2 Jul 2013 at 8:04

[GoogleCodeExporter]

Thanks for your comment.
May be I don't fully understand your code, but, for example, i have some 
difficulties with the ECKey class.

It seams that the public key could be stored either in compressed or 
uncompressed form (you provide an isCompressed() method to assert that). But 
many methods don't care about the public key form. 

For example the equals method could (incorrectly for me) return false if you 
compare the same key (in the sense of the same private key) but with public key 
in uncompressed and compress form.

    @Override
    public boolean equals(final Object o) {
        if (this == o) {return true;}
        if (o == null || getClass() != o.getClass()) {return false;}

        final ECKey ecKey = (ECKey) o;
                // What if pub is compressed and ecKey.pub is not ?
        return Arrays.equals(pub, ecKey.pub);
    }

So i clone your code and try to simplify it by putting asserts that public keys 
are always stored in uncompressed form (storage is not an issue). So if i 
receive a compressed public key, i need to get the uncompressed bytes.

Regards

Yves

Original comment by yves.cui...@gmail.com on 2 Jul 2013 at 10:29

[GoogleCodeExporter]

It's not been a priority because the form a key takes is supposed to never 
change post-creation. If it did, you would get two different addresses for the 
same key and the rest of the code isn't set up to deal with that.

Your proposed modification is safe, but as I said, decompressKey is not public 
API so it's not really a bug either.

Original comment by hearn@google.com on 2 Jul 2013 at 11:00

[GoogleCodeExporter]

Consider this :
 BigInterger privKey = ...

 ECKey key1 = new ECKey(privKey,null,true);
 ECKey key2 = new ECKey(privKey,null,false);

key1.equals(key2) will respond false! Do you think this is the correct answer ?

Yves

For your information, i modify the signature of the signature of your private 
compress and decompress methods and i think this could be a public API

    /**
     * @param uncompressed
     *            uncompressed public key
     * @return the compressed bytes for the compressed form of the given public
     *         key
     */
    @NonNull
    public static byte[] compressPublicKey(@NonNull final byte[] uncompressed) {
        if (uncompressed.length != 65) {
            throw new IllegalArgumentException(
                    "Uncompressed public keys must be 65 bytes long"); //$NON-NLS-1$
        }
        if (uncompressed[0] != 0x04)
            throw new IllegalArgumentException(
                    "Uncompressed public keys prefix must be 0x04"); //$NON-NLS-1$
        byte[] buf = new byte[32];
        System.arraycopy(uncompressed, 1, buf, 0, 32);
        final BigInteger xBN = new BigInteger(1, buf);
        System.arraycopy(uncompressed, 33, buf, 0, 32);
        final BigInteger yBN = new BigInteger(1, buf);

        final ECCurve.Fp curve = (ECCurve.Fp) ecParams.getCurve();
        final ECFieldElement x = new ECFieldElement.Fp(curve.getQ(), xBN);
        final ECFieldElement y = new ECFieldElement.Fp(curve.getQ(), yBN);
        return new ECPoint.Fp(curve, x, y, true).getEncoded();
    }

    /**
     * Decompress a compressed public key
     * 
     * @param compressed
     *            the compressed public key. This must be a 33 bytes buffer
     *            starting with a 0x02 or 0x03 byte.
     */
    @NonNull
    public static byte[] decompressPublicKey(@NonNull final byte[] compressed) {
        if (compressed.length != 33) {
            throw new IllegalArgumentException(
                    "Compressed public keys must be 33 bytes long"); //$NON-NLS-1$
        }
        if (compressed[0] != 0x02 && compressed[0] != 0x03)
            throw new IllegalArgumentException(
                    "Compressed public keys prefix must be 0x02 or 0x03"); //$NON-NLS-1$

        // Get X value
        byte[] bufX = new byte[32];
        System.arraycopy(compressed, 1, bufX, 0, 32);
        final BigInteger xBN = new BigInteger(1, bufX);

        // Is y odd ?
        final boolean yOdd = compressed[0] == 0x03;

        // This code is adapted from Bouncy Castle ECCurve.Fp.decodePoint(), but
        // it wasn't easily re-used.
        final ECCurve.Fp curve = (ECCurve.Fp) ecParams.getCurve();
        final ECFieldElement x = new ECFieldElement.Fp(curve.getQ(), xBN);
        final ECFieldElement alpha = x.multiply(x.square().add(curve.getA()))
                .add(curve.getB());
        final ECFieldElement beta = alpha.sqrt();
        // If we can't find a sqrt we haven't got a point on the curve - invalid
        // inputs.
        if (beta == null) {
            throw new IllegalArgumentException("Invalid point compression"); //$NON-NLS-1$
        }
        if (beta.toBigInteger().testBit(0) == yOdd) {
            return new ECPoint.Fp(curve, x, beta, false).getEncoded();
        }
        final ECFieldElement.Fp y = new ECFieldElement.Fp(curve.getQ(), curve
                .getQ().subtract(beta.toBigInteger()));
        return new ECPoint.Fp(curve, x, y, false).getEncoded();
    }

Original comment by yves.cui...@gmail.com on 2 Jul 2013 at 12:12

[GoogleCodeExporter]

I know it's unintuitive but yes, !equals would be the correct answer. If you 
treat compressed and uncompressed keys as equal then all kinds of assumptions 
get messed up. In particular, the wallet will only include one version into the 
Bloom filters it creates, thus you could risk missing transactions if they were 
sent to you with the other form.

I'll ask again - what are you actually trying to do here? Because whatever it 
is, I'm pretty sure that the changes you're making are not the right way to 
solve the problem.

I'll make the original change you proposed because it's a very minor semantic 
improvement (which makes no difference to any existing code), however, as I 
said, that does NOT mean compressed and uncompressed keys can be treated 
equivalently. It's much safer to treat the compression as if it were a part of 
the private key - something chosen once at creation time and then never changed 
again.

Original comment by hearn@google.com on 2 Jul 2013 at 1:38

[GoogleCodeExporter]

Sure it is unintuitive. I have not reach sufficient knowledge of the code and 
the bitcoin protocol to understand all the subtilities beyong all that.
For know, i don't see why, uniformally forcing all public keys to be 
uncompressed, will put me in trouble (may be just waste some CPU power). 
Your argument could probably be reserse saying that missing a particular form 
of the public key in the Bloom filter could miss some transaction (just joking 
;-p )
To answer you question, i am trying to get a very fine understanding and 
knowledge of the bitcoin protocol. I could have study the original Bitcoin-QT 
client, but i am not so familiar with C. Your code is an unvaluable source for 
me.
Regards
Yves

Original comment by yves.cui...@gmail.com on 2 Jul 2013 at 4:01

[GoogleCodeExporter]

I see. OK, then these are all reasonable questions. I was worried you were 
going to build an app based on these changes. The mailing list is a better 
place for discussion than the bug tracker though.

You could force all keys you create to be uncompressed - it'd be inefficient 
and there's no point, but it can be done by changing the line:

 pub = compressed.getEncoded();

to

 pub = uncompressed;

in the ECKey c'tor. The ECKey remembers which form it was created with so it 
should always give you back a decompressed key.

Original comment by hearn@google.com on 2 Jul 2013 at 4:09

[GoogleCodeExporter]

Original comment by mh.in.en...@gmail.com on 24 Nov 2013 at 11:14

• Changed state: Invalid