Get uncompressed public key from compressed form

Question

A similar question has an answer in Python which links to the bitcointalk forum:

• How can I get the uncompressed public key from the compressed public key in openssl?
• https://bitcointalk.org/index.php?topic=644919.msg7205689#msg7205689

But I'd like to know how a Java program can be written for the same conversion? I noticed that Java uses the byte data type and I'm unable to understand how to operate on values.

Answer 1

Yes, you can convert a 33-byte compressed public key into a 65-byte uncompressed public key in Java.

Here is the code to perform the operation. It is correct, robust, and only requires Java SE classes (no other libraries) - but I apologize for the implementation length.

import java.math.BigInteger;
import java.util.Arrays;

static final BigInteger MODULUS =
    new BigInteger("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16);
static final BigInteger CURVE_A = new BigInteger("0");
static final BigInteger CURVE_B = new BigInteger("7");


// Given a 33-byte compressed public key, this returns a 65-byte uncompressed key.
byte[] decompressPubkey(byte[] compKey) {
    // Check array length and type indicator byte
    if (compKey.length != 33 || compKey[0] != 2 && compKey[0] != 3)
        throw new IllegalArgumentException();

    final byte[] xCoordBytes = Arrays.copyOfRange(compKey, 1, compKey.length);
    final BigInteger xCoord = new BigInteger(1, xCoordBytes);  // Range [0, 2^256)

    BigInteger temp = xCoord.pow(2).add(CURVE_A);
    temp = sqrtMod(temp.add(CURVE_B));
    boolean tempIsOdd = temp.testBit(0);
    boolean yShouldBeOdd = compKey[0] == 3;
    if (tempIsOdd != yShouldBeOdd)
        temp = temp.negate().mod(MODULUS);
    final BigInteger yCoord = temp;

    // Copy the x coordinate into the new
    // uncompressed key, and change the type byte
    byte[] result = Arrays.copyOf(compKey, 65);
    result[0] = 4;

    // Carefully copy the y coordinate into uncompressed key
    final byte[] yCoordBytes = yCoord.toByteArray();
    for (int i = 0; i < 32 && i < yCoordBytes.length; i++)
        result[result.length - 1 - i] = yCoordBytes[yCoordBytes.length - 1 - i];

    return result;
}


// Given x, this returns a value y such that y^2 % MODULUS == x.
BigInteger sqrtMod(BigInteger value) {
    assert (MODULUS.intValue() & 3) == 3;
    BigInteger pow = MODULUS.add(BigInteger.ONE).shiftRight(2);
    BigInteger result = value.modPow(pow, MODULUS);
    assert result.pow(2).mod(MODULUS).equals(value);
    return result;
}

My Bitcoin cryptography library does implement the modulo-prime field arithmetic, but it should add the functionality to decompress public keys as well...

Answer 2

You can use bouncycastle ECPoint to do this conversion:

static ECParameterSpec SPEC = ECNamedCurveTable.getParameterSpec("secp256k1");

static byte[] compressedToUncompressed(byte[] compKey) {
    ECPoint point = SPEC.getCurve().decodePoint(compKey);
    byte[] x = point.getXCoord().getEncoded();
    byte[] y = point.getYCoord().getEncoded();
    // concat 0x04, x, and y, make sure x and y has 32-bytes:
    return concat(new byte[] {0x04}, x, y);
}

Answer 3

In openssl, you can use the EC_POINT_point2oct and EC_POINT_oct2point functions to convert between compressed and uncompressed.

Check if the first octet contains POINT_CONVERSION_UNCOMPRESSED, if you want to know whether it's compressed.