Retrieve public key from x-compressed point

[luca.d...@cnit.it]

Hello,

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?

I followed some links which explain it (and many others)

https://www.cryptopp.com/wiki/Point_Compression

https://stackoverflow.com/questions/16576434/crypto-and-compressed-ec-keys

but they don't fit my problem.

 I tried to produce code to resolve the problem (https://pastebin.com/JFLxuW1X) but it doesn't work.

Can you help me please?

[Jeffrey Walton]

Please show how this value is constructed:

    string compactPoint = "937120662418500f3ad7c892b1db7e7c2d85ec48c74e99d64dcb7083082bb4f3";

Jeff

[Luca Di Mauro]

Hello Jeff,

that value is constructed following this standard
https://tools.ietf.org/id/draft-jivsov-ecc-compact-00.xml#NIST-SP800-133 , but
unfortunately I cannot assume any other assumptions.

Luca


Jeffrey Walton <nolo...@gmail.com> ha scritto:

> On Tuesday, February 5, 2019 at 9:56:44 AM UTC-5, luca.d...@cnit.it wrote:
>>
>> Hello,
>>
>> 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?
>> I followed some links which explain it (and many others)
>> https://www.cryptopp.com/wiki/Point_Compression
>> https://stackoverflow.com/questions/16576434/crypto-and-compressed-ec-keys
>> but they don't fit my problem.
>>
>> I tried to produce code to resolve the problem (
>> https://pastebin.com/JFLxuW1X

>> <https://www.google.com/url?q=https%3A%2F%2Fpastebin.com%2FJFLxuW1X&sa=D&sntz=1&usg=AFQjCNEfB2oA3V5N9_a0HktwAWpAGiQVJw>)

>> but it doesn't work.
>>
>
> Please show how this value is constructed:
>
> string compactPoint =
> "937120662418500f3ad7c892b1db7e7c2d85ec48c74e99d64dcb7083082bb4f3";
>
> Jeff
>

> --
> You received this message because you are subscribed to "Crypto++
> Users". More information about Crypto++ and this group is available
> at http://www.cryptopp.com and
> http://groups.google.com/forum/#!forum/cryptopp-users.
> ---
> You received this message because you are subscribed to the Google
> Groups "Crypto++ Users" group.
> To unsubscribe from this group and stop receiving emails from it,
> send an email to cryptopp-user...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Jeffrey Walton]

On Wed, Feb 6, 2019 at 4:42 AM Luca Di Mauro <luca.d...@cnit.it> wrote:
>
> that value is constructed following this standard
> https://tools.ietf.org/id/draft-jivsov-ecc-compact-00.xml#NIST-SP800-133 , but
> unfortunately I cannot assume any other assumptions.

This may work for you.

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

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

int main()
{
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 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;
}

And then:

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

Jeff

[luca.d...@cnit.it]

It seems to work: the public key is correctly generated and verified, but the verification of a signed message fails and I don't know if it depends on key decoding or on the verification procedure.

Should I create new post or I can write this problem in this post?

Thank you for your support (as well as in stackoverflow!)

[Jeffrey Walton]

On Wed, Feb 6, 2019 at 5:55 AM <luca.d...@cnit.it> wrote:
>
> It seems to work: the public key is correctly generated and verified, but the verification of a signed message fails and I don't know if it depends on key decoding or on the verification procedure.
> Should I create new post or I can write this problem in this post?

I'm hazarding a guess... you probably need to call:

pubKey.SetPublicElement(point);

after decoding. Decoding does not set the public element automatically.

Or maybe you need to decode with "03" instead of "02". The prefix
affects whether y or p-y is returned from the modular square toot that
solves for y.

Jeff

[luca.d...@cnit.it]

I called the method SetPublicElement and I performed trials with both "02" and "03", but the verification stil return error.

Code is:

int main () {

    using namespace CryptoPP;

    AutoSeededRandomPool rnd;

ECDSA<ECP, SHA256>::PublicKey pubKey;

    HexDecoder decoder;

    string compactPoint;

    string message  = "4003805520500000003101001400ba749705a41d251799c60000000000000000000000000000000007d1000001029705"

                     "a41d99c6405d693a403ad274803ffffffc23b7743e40e11fdffffe3fe9ed073753085fffa0000000004001240000006d251a3fe2";

    string signature = "26413d411d233adc8baf8d4401036ffd511ed996d862ce4e106275d9851339d7";

    compactPoint = "02" "937120662418500f3ad7c892b1db7e7c2d85ec48c74e99d64dcb7083082bb4f3";

    //compactPoint = "03" "937120662418500f3ad7c892b1db7e7c2d85ec48c74e99d64dcb7083082bb4f3";

pubKey.AccessGroupParameters().Initialize(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;

    pubKey.SetPublicElement (point);

    cout << "Is valid? " << pubKey.Validate (rnd, 3) << std::endl;

    cout << "\n\n==================================================\n==================================================\n";

    ECDSA<ECP,SHA256>::Verifier verifier(pubKey);

    bool result;

    StringSource ss1( signature+message, true, new SignatureVerificationFilter (verifier,new ArraySink( (byte*)&result, sizeof(result))));

    // Verification failure?

    if (!result)

        cout << "Error on verify: " << result << endl << endl;

    else

        cout << "Success on verify: " << result << endl << endl;

return 0;

}

What do you suggest?

[Jeffrey Walton]

Sorry, no idea.

We need to see what the code that is producing the signature is doing.
Otherwise, it is knob turning like you are doing.

Jeff

[Jeffrey Walton]

This may be helpful:
https://www.codeproject.com/articles/25590/cryptographic-interoperability-digital-signatures

It is an old article but it still applies.

Jeff

[luca.d...@cnit.it]

Ok, thank you very much!

[Jeffrey Walton]

On Wed, Feb 6, 2019 at 6:24 AM <luca.d...@cnit.it> wrote:
>

You need to HexDecode the signature and message Something like:

std::string m, s;
StringSource(message, true, new HexDecoder(new StringSink(m)));
StringSource(signature, true, new HexDecoder(new StringSink(s)));

Then use something like:

StringSource ss( s+m, true, new SignatureVerificationFilter (...));

But the signature length looks wrong to me. secp256 and SHA256 should
be producing 64-byte signatures, not 32-byte signatures:

$ echo -n 26413d411d233adc8baf8d4401036ffd511ed996d862ce4e106275d9851339d7
| wc -c
64

Because it is hex encoded, 64/2 = 32 bytes.

You need to get the specs from the folks who are providing the keys,
message and signature.

Jeff

[luca.d...@cnit.it]

It's correct! Tomorrow I'll take more information, but the encryption was done following the IEEE1609.2 standard and I have only a set of pcap files analyzed by wireshark.

However tomorrow (Ihope) I'll let you know more information.

[Jeffrey Walton]

On Wed, Feb 6, 2019 at 9:49 AM <luca.d...@cnit.it> wrote:
>
> It's correct! Tomorrow I'll take more information, but the encryption was done following the IEEE1609.2 standard and I have only a set of pcap files analyzed by wireshark.
> However tomorrow (Ihope) I'll let you know more information.

OK. But keep this in mind when you are turning the knobs. The test
program below shows r || s is 64-bytes for secp256r1.

$ ./test.exe
Private key: 3041020100301306072A8648CE3D020106082A8648CE3D030107042730250201010420D62F849A0C0B4D4E7C8BCAE0AF88C71040FD194F1D2420E076B393EF0C769CEA

Public key: 3059301306072A8648CE3D020106082A8648CE3D03010703420004B327AB1E9192FAA3AB411E9DF0D2282D8640169FF819977A78BF51E475C010DB462070A75FF5F4ADFFD9CD39211FE9795C838A5872CFFB10D9966936109ADED8

Signature: C8EC7C709F9DC7DDC0BF5AE13262CA5D9DF79A5AE65DB23E763B8D31747A1986D2C5FD636946EC4A41294D87BD78C8F4C7355605524EBA3F52E5B00DCDF788C1

Success on verify: 1

And:

$ echo -n C8EC7C709F9DC7DDC0BF5AE13262CA5D9DF79A5AE65DB23E763B8D31747A1986D2C5FD636946EC4A41294D87BD78C8F4C7355605524EBA3F52E5B00DCDF788C1
| wc -c
128

And:

$ cat test.cxx
#include "cryptlib.h"
#include "eccrypto.h"
#include "hex.h"
#include "ecp.h"
#include "oids.h"
#include "files.h"
#include "filters.h"

#include "osrng.h"

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

int main (int argc, char* argv[])
{
using namespace CryptoPP;
AutoSeededRandomPool prng;
HexEncoder encoder(new FileSink(std::cout));

ECDSA<ECP, SHA256>::PrivateKey privKey;
privKey.Initialize(prng, ASN1::secp256r1());

ECDSA<ECP, SHA256>::PublicKey pubKey;

privKey.MakePublicKey(pubKey);

std::cout << "Private key: ";
privKey.Save(encoder);
std::cout << "\n" << std::endl;

std::cout << "Public key: ";
pubKey.Save(encoder);
std::cout << "\n" << std::endl;

std::string m, message =
"4003805520500000003101001400ba749705a41d251799c60000000000000000"
"000000000000000007d1000001029705a41d99c6405d693a403ad274803fffff"
"fc23b7743e40e11fdffffe3fe9ed073753085fffa0000000004001240000006d"
"251a3fe2";
std::string s, signature;

// Decode to binary

StringSource(message, true, new HexDecoder(new StringSink(m)));

ECDSA<ECP, SHA256>::Signer signer(privKey);
StringSource(m, true, new SignerFilter(prng, signer,
new HexEncoder(new StringSink(signature))));

// Not really needed, but we hex encoded in the signing pipeline

StringSource(signature, true, new HexDecoder(new StringSink(s)));

std::cout << "Signature: ";
StringSource(s, true, new Redirector(encoder));
std::cout << "\n" << std::endl;

bool result;
ECDSA<ECP, SHA256>::Verifier verifier(pubKey);
StringSource ss1( s+m, true, new SignatureVerificationFilter (verifier,

new ArraySink( (byte*)&result, sizeof(result))));

// Verification failure?
if (!result)

std::cout << "Error on verify: " << result << "\n" << std::endl;
else
std::cout << "Success on verify: " << result << "\n" << std::endl;

return 0;
}

[Jeffrey Walton]

On Tue, Feb 5, 2019 at 9:56 AM <luca.d...@cnit.it> wrote:
>
> 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.

By the way, ed25519 is available in Crypto++ 8.0 and above.

ed25519 signatures are about 30 times faster then secp256 signatures.

Jeff

[luca.d...@cnit.it]

Unfortunatly I have to use a specific set of elliptic curve.

However the file containing the standard can be found here https://wiki.plugtests.net/ITS-CMS6/images/4/4a/1609.2-consolidated-v4-d8-clean.pdf and the interesting part for our scope should be the paragraph 5.3 starting at page 45.

Talking with my colleagues I discovered taht the correct signature key is contcatenation of "r" and "s" values contained in received packets.

Looking at the standard in the section I said you, could you write a skeleton of source coude as a starting point? My knowledge in cryptography is very few.