Retrieve ECDSA public key from only x-compressed coordinate using Crypto++ library

Question

I'm implementing a security daemon on the vehicular communication scope.

I could receive a message with a signature and the compressed X coordinate of a point to verify that signature. The elliptic curve can be either the secp256 or the brainpoolp256r1 and the algorithm is ECDSA.

My question is: how can I recover the ECC Point (and so the public key) given only the compressed X coordinate with the Crypto++ library?

I followed some links which explain it (and many others) https://www.cryptopp.com/wiki/Point_Compression Crypto++ and Compressed EC keys but they don't fit my problem.

I tried to produce code to resolve the problem, but it won't work:

#include <string>
#include <iostream>
#include <cryptopp/cryptlib.h>
#include <cryptopp/ecp.h>
#include <cryptopp/eccrypto.h>
#include <cryptopp/hex.h>
#include <cryptopp/oids.h>
#include <cryptopp/osrng.h>

using namespace CryptoPP;
using std::cout;
using std::endl;
using std::string;

int main() 
{
    string compactPoint = "937120662418500f3ad7c892b1db7e7c2d85ec48c74e99d64dcb7083082bb4f3";

    AutoSeededRandomPool generator;
    ECDSA<ECP, SHA256>::PublicKey pubKey;
    OID curve       = ASN1::secp256r1();


    StringSource ss (compactPoint, true, new CryptoPP::HexDecoder);
    ECP::Point point;

    pubKey.GetGroupParameters().GetCurve().DecodePoint (point, ss, ss.MaxRetrievable());

    std::cout << "Result after decompression X: " << std::hex << point.x << std::endl;
    std::cout << "Result after decompression Y: " << std::hex << point.y << std::endl;

    return 0;
}

Can you help me please?

Answer 1

The easiest solution is probably to prepend "02" oe "03" to the compact representation. Crypto++ will then decode it as a compressed public key.

$ cat test.cxx

#include "cryptlib.h"
#include "eccrypto.h"
#include "ecp.h"
#include "hex.h"
#include "oids.h"

#include <string>
#include <iostream>
#include <iomanip>

int main(int argc, char* argv[])
{
    using namespace CryptoPP;

    ECDSA<ECP, SHA256>::PublicKey pubKey;
    pubKey.AccessGroupParameters().Initialize(ASN1::secp256r1());

    std::string compactPoint = "02" /* compressed */
        "937120662418500f3ad7c892b1db7e7c"
        "2d85ec48c74e99d64dcb7083082bb4f3";

    StringSource ss (compactPoint, true, new HexDecoder);
    ECP::Point point;

    pubKey.GetGroupParameters().GetCurve().DecodePoint (point, ss, ss.MaxRetrievable());

    std::cout << "Result after decompression X: " << std::hex << point.x << std::endl;
    std::cout << "Result after decompression Y: " << std::hex << point.y << std::endl;

    return 0;
}

And then building and running the program. Notice the library solves for the y portion of the coordinate.

cryptopp$ g++ test.cxx ./libcryptopp.a -o test.exe
cryptopp$ ./test.exe
Result after decompression X: 937120662418500f3ad7c892b1db7e7c2d85ec48c74e99d64dcb7083082bb4f3h
Result after decompression Y: cfcaf74eae3ceec5993928f04970cfef343b9a6b22727fa81926bd21f256ec56h

---

And to save you the trouble of looking it up, you can set the public element for publicKey using:

pubKey.SetPublicElement(point);

std::cout << "X: " << std::hex << pubKey.GetPublicElement().x << std::endl;
std::cout << "Y: " << std::hex << pubKey.GetPublicElement().y << std::endl;

Running with the additional code produces the expected result:

$ ./test.exe
Result after decompression X: 937120662418500f3ad7c892b1db7e7c2d85ec48c74e99d64dcb7083082bb4f3h
Result after decompression Y: cfcaf74eae3ceec5993928f04970cfef343b9a6b22727fa81926bd21f256ec56h
X: 937120662418500f3ad7c892b1db7e7c2d85ec48c74e99d64dcb7083082bb4f3h
Y: cfcaf74eae3ceec5993928f04970cfef343b9a6b22727fa81926bd21f256ec56h

---

If interested, here is the code you are using to decode the point from ecp.cpp:

bool ECP::DecodePoint(ECP::Point &P, BufferedTransformation &bt, size_t encodedPointLen) const
{
    byte type;
    if (encodedPointLen < 1 || !bt.Get(type))
        return false;

    switch (type)
    {
    case 0:
        P.identity = true;
        return true;
    case 2:
    case 3:
    {
        if (encodedPointLen != EncodedPointSize(true))
            return false;

        Integer p = FieldSize();

        P.identity = false;
        P.x.Decode(bt, GetField().MaxElementByteLength());
        P.y = ((P.x*P.x+m_a)*P.x+m_b) % p;

        if (Jacobi(P.y, p) !=1)
            return false;

        P.y = ModularSquareRoot(P.y, p);

        if ((type & 1) != P.y.GetBit(0))
            P.y = p-P.y;

        return true;
    }
    case 4:
    {
        if (encodedPointLen != EncodedPointSize(false))
            return false;

        unsigned int len = GetField().MaxElementByteLength();
        P.identity = false;
        P.x.Decode(bt, len);
        P.y.Decode(bt, len);
        return true;
    }
    default:
        return false;
    }
}

I mention it in case you want to solve for the y coordinate yourself, populate the point, and then call SetPublicElement directly.

---

You can also prepend 03 instead of 02. The difference is, the decoding returns either y or p-y. The variability is introduced due to the modular square root shown above. We need to see the generation algorithm to determine what the value should be.

Here is the difference when using 03 instead of 02:

$ ./test.exe
X: 937120662418500f3ad7c892b1db7e7c2d85ec48c74e99d64dcb7083082bb4f3h
Y: 303508b051c3113b66c6d70fb68f3010cbc46595dd8d8057e6d942de0da913a9h

Notice 03 produces the y coordinate 303508b051c3113b66c6d70fb68f3010cbc46595dd8d8057e6d942de0da913a9h instead of 02 and cfcaf74eae3ceec5993928f04970cfef343b9a6b22727fa81926bd21f256ec56h.