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).

Lammergeier

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");
            }
        }
    }
}

Cleasta

I've used the standard uncompressed point notation. That means that the indicator byte is of course overhead. Furthermore, there is also the compressed point notation, but there are some IP issues with compressed points, I think Bouncy has some support for point compression though. – Cleasta

Uncompressed point is OK, some company has patents related to point compression. You've mentioned that functionality is present in BC itself, could you also add example on how to do it using BC API? – Lammergeier

@Lammergeier Could you have a look yourself? I currently don't use compressed points, so I would basically have to write it myself, and I'm short on time. – Cleasta

Sorry for misunderstanding. I wasn't asking about point compression but public key <-> bytes conversion using BC API :) if I knew how to do it I wouldn't ask main question at all – Lammergeier

OK, but how hard have you looked? It's not like ECPoint.getEncoded() or ECPoint.Fp.getEncoded(boolean compressed) are that hard to find. – Cleasta

Answer 2

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

Ascogonium

Answer 3

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;
}

Housecarl

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.

Eldoraeldorado

Answer 5

A one line BC approach is:

EC5Util.convertPoint(ecPublicKey.getParams(), ecPublicKey.getW()).getEncoded(true);

ecPublicKey is a Java ECPublicKey.

Note: Using compressed points is absolutely fine in 2022. The hilarious patents have expired. See Cryptography StackExchange.

Reclamation

Answer 6

In 2021 just use the Tink library

public static byte[] pointEncode(EllipticCurves.CurveType curveType,
                                 EllipticCurves.PointFormatType format,
                                 ECPoint point)
                          throws GeneralSecurityException

Milda

Link does not work – Dove