1

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

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.

  • It looks like the algorithm you need is published on bitcointalk. Are you asking whether Java has the same capabilities to convert public keys as Python? – Jestin May 9 '16 at 16:49
  • Right! Actually I started doing the code I don't understand how to do the p//4 (floor division) part though since I'm working with biginteger. I also tried doing y=((x^3+7)^1/2)mod p where p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F but it didn't work either. – prof.Zoom May 9 '16 at 17:17
  • If your question is about how to do a specific thing in Java, it might be worthwhile to post the question to StackOverflow. I'm sure there's a few people here who have worked with BigIntegers in Java, but there's certainly more on SO. – Jestin May 9 '16 at 18:08
2

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

  • Thanks! Program looks clean. I'll check and let you know. – prof.Zoom May 10 '16 at 6:31
  • I'm unable to upvote this answer due to low reputation. – prof.Zoom May 10 '16 at 7:18
  • It fails for this compressed key. 022A779D25B43F04C3DD8A27B079FF4C6BECFBDE1419F1CF0B5CDA2AB001517884 could you please check? fails at assert result.pow(2).mod(MODULUS).equals(value); – light_keeper Dec 10 '17 at 21:07
  • @light_keeper Are you sure that your x coordinate of 2A77...7884 actually has a point on the elliptic curve? – Nayuki Dec 10 '17 at 23:54
  • You need to multiply your first temp (x^2+a) by x before adding b and calling sqrtMod. Also for the second assertion to work correctly you must either reduce the argument to sqrtMod modulo p, or have the assertion check congruence rather than equality. – dave_thompson_085 Apr 24 at 22:44
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);
}
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.