Java compact representation of ECC PublicKey

Question

java.security.PublicKey#getEncoded() returns X509 representation of key which in case of ECC adds a lot of overhead compared to raw ECC values.

I'd like to be able to convert PublicKey to byte array (and vice versa) in most compact representation (i.e. as small byte chunk as possible).

KeyType (ECC) and concrete curve type are known in advance so information about them do not need to be encoded.

Solution can use Java API, BouncyCastle or any other custom code/library (as long as license does not imply need to open source proprietary code in which it will be used).

Answer 1

This functionality is also present in Bouncy Castle, but I'll show how to go through this using just Java in case somebody needs it:

import java.math.BigInteger;
import java.security.KeyFactory;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.interfaces.ECPublicKey;
import java.security.spec.ECParameterSpec;
import java.security.spec.ECPoint;
import java.security.spec.ECPublicKeySpec;
import java.util.Arrays;

public class Curvy {

    private static final byte UNCOMPRESSED_POINT_INDICATOR = 0x04;

    public static ECPublicKey fromUncompressedPoint(
            final byte[] uncompressedPoint, final ECParameterSpec params)
            throws Exception {

        int offset = 0;
        if (uncompressedPoint[offset++] != UNCOMPRESSED_POINT_INDICATOR) {
            throw new IllegalArgumentException(
                    "Invalid uncompressedPoint encoding, no uncompressed point indicator");
        }

        int keySizeBytes = (params.getOrder().bitLength() + Byte.SIZE - 1)
                / Byte.SIZE;

        if (uncompressedPoint.length != 1 + 2 * keySizeBytes) {
            throw new IllegalArgumentException(
                    "Invalid uncompressedPoint encoding, not the correct size");
        }

        final BigInteger x = new BigInteger(1, Arrays.copyOfRange(
                uncompressedPoint, offset, offset + keySizeBytes));
        offset += keySizeBytes;
        final BigInteger y = new BigInteger(1, Arrays.copyOfRange(
                uncompressedPoint, offset, offset + keySizeBytes));
        final ECPoint w = new ECPoint(x, y);
        final ECPublicKeySpec ecPublicKeySpec = new ECPublicKeySpec(w, params);
        final KeyFactory keyFactory = KeyFactory.getInstance("EC");
        return (ECPublicKey) keyFactory.generatePublic(ecPublicKeySpec);
    }

    public static byte[] toUncompressedPoint(final ECPublicKey publicKey) {

        int keySizeBytes = (publicKey.getParams().getOrder().bitLength() + Byte.SIZE - 1)
                / Byte.SIZE;

        final byte[] uncompressedPoint = new byte[1 + 2 * keySizeBytes];
        int offset = 0;
        uncompressedPoint[offset++] = 0x04;

        final byte[] x = publicKey.getW().getAffineX().toByteArray();
        if (x.length <= keySizeBytes) {
            System.arraycopy(x, 0, uncompressedPoint, offset + keySizeBytes
                    - x.length, x.length);
        } else if (x.length == keySizeBytes + 1 && x[0] == 0) {
            System.arraycopy(x, 1, uncompressedPoint, offset, keySizeBytes);
        } else {
            throw new IllegalStateException("x value is too large");
        }
        offset += keySizeBytes;

        final byte[] y = publicKey.getW().getAffineY().toByteArray();
        if (y.length <= keySizeBytes) {
            System.arraycopy(y, 0, uncompressedPoint, offset + keySizeBytes
                    - y.length, y.length);
        } else if (y.length == keySizeBytes + 1 && y[0] == 0) {
            System.arraycopy(y, 1, uncompressedPoint, offset, keySizeBytes);
        } else {
            throw new IllegalStateException("y value is too large");
        }

        return uncompressedPoint;
    }

    public static void main(final String[] args) throws Exception {

        // just for testing

        final KeyPairGenerator kpg = KeyPairGenerator.getInstance("EC");
        kpg.initialize(163);

        for (int i = 0; i < 1_000; i++) {
            final KeyPair ecKeyPair = kpg.generateKeyPair();

            final ECPublicKey ecPublicKey = (ECPublicKey) ecKeyPair.getPublic();
            final ECPublicKey retrievedEcPublicKey = fromUncompressedPoint(
                    toUncompressedPoint(ecPublicKey), ecPublicKey.getParams());
            if (!Arrays.equals(retrievedEcPublicKey.getEncoded(),
                    ecPublicKey.getEncoded())) {
                throw new IllegalArgumentException("Whoops");
            }
        }
    }
}

Answer 2

Here is a BouncyCastle approach I've used to unpack the public key:

public static byte[] extractData(final @NonNull PublicKey publicKey) {
    final SubjectPublicKeyInfo subjectPublicKeyInfo =
            SubjectPublicKeyInfo.getInstance(publicKey.getEncoded());
    final byte[] encodedBytes = subjectPublicKeyInfo.getPublicKeyData().getBytes();
    final byte[] publicKeyData = new byte[encodedBytes.length - 1];

    System.arraycopy(encodedBytes, 1, publicKeyData, 0, encodedBytes.length - 1);

    return publicKeyData;
}

Answer 3

Trying to generate an uncompressed representation in java almost killed me! Wish I would have found this (especially Maarten Bodewes' excellent answer) earlier. I'd like to point out an issue in the answer and offer an improvement:

if (x.length <= keySizeBytes) {
        System.arraycopy(x, 0, uncompressedPoint, offset + keySizeBytes
                - x.length, x.length);
    } else if (x.length == keySizeBytes + 1 && x[0] == 0) {
        System.arraycopy(x, 1, uncompressedPoint, offset, keySizeBytes);
    } else {
        throw new IllegalStateException("x value is too large");
    }

This ugly bit is necessary because of the way BigInteger spits out byte array representations: "The array will contain the minimum number of bytes required to represent this BigInteger, including at least one sign bit" (toByteArray javadoc). This means a.) if the highest bit of x or y is set, a 0x00 will be prepended to the array and b.) leading 0x00's will be trimmed. The first branch deals with the trimmed 0x00's and the second one with the prepended 0x00.

The "trimmed leading zero's" lead to an issue in the code determining the expected length of x and y:

int keySizeBytes = (publicKey.getParams().getOrder().bitLength() + Byte.SIZE - 1)
            / Byte.SIZE;

If the order of the curve has a leading 0x00 it gets truncated and is not considered by bitLength. The resulting key length is too short. The incredibly convoluted (but proper?) way to get at the bitlength of p would be:

int keySizeBits = publicKey.getParams().getCurve().getField().getFieldSize();
int keySizeBytes = (keySizeBits + 7) >>> 3;

(The +7 is to compensate for bit lengths which are not powers of 2.)

This issue affects at least one curve delivered with the standard JCA (X9_62_c2tnb431r1) which has an order with a leading zero:

000340340340340 34034034034034034
034034034034034 0340340340323c313
fab50589703b5ec 68d3587fec60d161c
c149c1ad4a91

Answer 4

With BouncyCastle, ECPoint.getEncoded(true) returns a compressed representation of the point. Basically the affine X coordinate with a sign bit for the affine Y.