Compute EC_KEY starting from X or Y coordinate only

classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

Compute EC_KEY starting from X or Y coordinate only

Luca Di Mauro

Hello all,

I don't know if it is the correct mailing list to ask this, so I'm  
sorry if it is the wrong palce.

I'm using openssl v1.1, and I'm trying to compute both the X and Y  
coordinates of an elliptic curve point starting from a single  
coordinate (X or Y).

How can i perform that in C/C++ language using libssl? I searched on  
google for a couple of days but i haven't found a solution.

Luca Di Mauro


Reply | Threaded
Open this post in threaded view
|

Re: Compute EC_KEY starting from X or Y coordinate only

Nicola
Hi,

with traditional EC from the x coordinate alone you can't really do that, because there are always 2 possible solutions for y (in R the curve is symmetrical on the x axis). 

The standards define a "compressed point" format in which you can send the coordinate x and an additional bit to select which of the 2 y solutions to pick.

You can read more about it in EC_GROUP_set_point_conversion_form at https://www.openssl.org/docs/man1.1.1/man3/EC_GROUP_copy.html 

and in EC_POINT_set_compressed_coordinates at

Hope this helps, 

Nicola Tuveri


On Fri, Oct 18, 2019, 11:31 Luca Di Mauro <[hidden email]> wrote:

Hello all,

I don't know if it is the correct mailing list to ask this, so I'm 
sorry if it is the wrong palce.

I'm using openssl v1.1, and I'm trying to compute both the X and Y 
coordinates of an elliptic curve point starting from a single 
coordinate (X or Y).

How can i perform that in C/C++ language using libssl? I searched on 
google for a couple of days but i haven't found a solution.

Luca Di Mauro


Reply | Threaded
Open this post in threaded view
|

Re: Compute EC_KEY starting from X or Y coordinate only

Luca Di Mauro
Thank you very much for the reply!
Yes, I have also the additional information about on which of two  
solutions I should take.

I'll check the guides you linked below.

Luca Di Mauro

Nicola Tuveri <[hidden email]> ha scritto:

> Hi,
>
> with traditional EC from the x coordinate alone you can't really do that,
> because there are always 2 possible solutions for y (in R the curve is
> symmetrical on the x axis).
>
> The standards define a "compressed point" format in which you can send the
> coordinate x and an additional bit to select which of the 2 y solutions to
> pick.
>
> You can read more about it in EC_GROUP_set_point_conversion_form at
> https://www.openssl.org/docs/man1.1.1/man3/EC_GROUP_copy.html
>
> and in EC_POINT_set_compressed_coordinates at
> https://www.openssl.org/docs/man1.1.1/man3/EC_POINT_new.html
>
> Hope this helps,
>
> Nicola Tuveri
>
>
> On Fri, Oct 18, 2019, 11:31 Luca Di Mauro <[hidden email]> wrote:
>
>>
>> Hello all,
>>
>> I don't know if it is the correct mailing list to ask this, so I'm
>> sorry if it is the wrong palce.
>>
>> I'm using openssl v1.1, and I'm trying to compute both the X and Y
>> coordinates of an elliptic curve point starting from a single
>> coordinate (X or Y).
>>
>> How can i perform that in C/C++ language using libssl? I searched on
>> google for a couple of days but i haven't found a solution.
>>
>> Luca Di Mauro
>>
>>
>>



Reply | Threaded
Open this post in threaded view
|

Re: Compute EC_KEY starting from X or Y coordinate only

Luca Di Mauro
Hi,
the link you posted below are very useful!

However, after many trials and errors, I created a little program to  
derive a public key from an x-only coordinate but, in the last step,  
it fails, namely in the function  
'EC_POINT_set_compressed_coordinates_GFp' called in the function  
'loadKey_xOnly'.
Here the whole code:


#include <iostream>
#include <string>
#include <cstring>

#include <openssl/ec.h>
#include <openssl/ecdsa.h>
#include <openssl/obj_mac.h>
#include <openssl/err.h>

char *ossl_err_as_string (void)
{ BIO *bio = BIO_new (BIO_s_mem ());
   ERR_print_errors (bio);
   char *buf = NULL;
   size_t len = BIO_get_mem_data (bio, &buf);
   char *ret = (char *) calloc (1, 1 + len);
   if (ret)
     memcpy (ret, buf, len);
   BIO_free (bio);
   return ret;
}


void printAndExit (std::string s) {
        std::cerr << "ERROR!\n" << s << std::endl << ossl_err_as_string () <<  
std::endl;
        exit(EXIT_FAILURE);
}


EC_KEY* loadKey_xOnly (std::string& xOnly) {
        EC_GROUP* group = EC_GROUP_new_by_curve_name (NID_secp256k1);
        if (group == NULL)
                printAndExit ("group null");

        EC_GROUP_set_point_conversion_form (group, POINT_CONVERSION_COMPRESSED);
        EC_POINT* pubPoint = EC_POINT_new (group);
        if (pubPoint == NULL)
                printAndExit ("pibpoint == null");

        BN_CTX* bnCtx = BN_CTX_new ();
        BIGNUM* x = BN_new ();
        if (x == NULL)
                printAndExit ("X == NULL");

        if (BN_hex2bn (&x, (const char*) xOnly.c_str()) == 0)
                printAndExit ("hex2bn == 0");

        std::cout << "x_BN:\t" << BN_bn2hex (x) << std::endl;
        std::cout << "x_BA:\t" << xOnly << std::endl;

        if (EC_POINT_set_compressed_coordinates_GFp (group, pubPoint, x, 0,  
bnCtx) == 0)
                printAndExit ("set_compr_coord == 0");
}



int main () {
        std::string xOnlyStr =  
"c16b4ce0532f5dc9d09114fe121d3956ae84f9eb677a0d4bdac1d3af7a91950c";
        EC_KEY* key = loadKey_xOnly (xOnlyStr);

        return 0;
}

The string 'xOnlyStr' contains a real x-only coordinate of a verification key.

Could you help me?

Thank you,

Luca Di Mauro

Luca Di Mauro <[hidden email]> ha scritto:

> Thank you very much for the reply!
> Yes, I have also the additional information about on which of two  
> solutions I should take.
>
> I'll check the guides you linked below.
>
> Luca Di Mauro
>
> Nicola Tuveri <[hidden email]> ha scritto:
>
>> Hi,
>>
>> with traditional EC from the x coordinate alone you can't really do that,
>> because there are always 2 possible solutions for y (in R the curve is
>> symmetrical on the x axis).
>>
>> The standards define a "compressed point" format in which you can send the
>> coordinate x and an additional bit to select which of the 2 y solutions to
>> pick.
>>
>> You can read more about it in EC_GROUP_set_point_conversion_form at
>> https://www.openssl.org/docs/man1.1.1/man3/EC_GROUP_copy.html
>>
>> and in EC_POINT_set_compressed_coordinates at
>> https://www.openssl.org/docs/man1.1.1/man3/EC_POINT_new.html
>>
>> Hope this helps,
>>
>> Nicola Tuveri
>>
>>
>> On Fri, Oct 18, 2019, 11:31 Luca Di Mauro <[hidden email]> wrote:
>>
>>>
>>> Hello all,
>>>
>>> I don't know if it is the correct mailing list to ask this, so I'm
>>> sorry if it is the wrong palce.
>>>
>>> I'm using openssl v1.1, and I'm trying to compute both the X and Y
>>> coordinates of an elliptic curve point starting from a single
>>> coordinate (X or Y).
>>>
>>> How can i perform that in C/C++ language using libssl? I searched on
>>> google for a couple of days but i haven't found a solution.
>>>
>>> Luca Di Mauro
>>>
>>>
>>>



Reply | Threaded
Open this post in threaded view
|

Re: Compute EC_KEY starting from X or Y coordinate only

Billy Brumley
>         EC_GROUP* group         = EC_GROUP_new_by_curve_name (NID_secp256k1);

> "c16b4ce0532f5dc9d09114fe121d3956ae84f9eb677a0d4bdac1d3af7a91950c";

I don't believe there's a point on secp256k1 with that x-coordinate.
If you check the failure reason for
EC_POINT_set_compressed_coordinates_GFp in the debugger, that is
probably what it is telling you.

Where did this curve / x-coord pair come from?

BBB
Reply | Threaded
Open this post in threaded view
|

Re: Compute EC_KEY starting from X or Y coordinate only

Luca Di Mauro
I think it is correct because I extracted the hexadecimal string from  
a packet contained in a pcap.

This compressed point is created following the ETSI TS 103 097 v1.3.1  
standard for secured communications in the vehicular communication  
context  
(https://www.etsi.org/deliver/etsi_ts/103000_103099/103097/01.03.01_60/ts_103097v010301p.pdf).

I notice that the point 'pubPoint' that I created is empty when I try  
to call 'EC_POINT_set_compressed_coordinates_GFp' function. How can I  
put a BIGNUM into an EC_POINT?

Luca

Billy Brumley <[hidden email]> ha scritto:

>>         EC_GROUP* group         = EC_GROUP_new_by_curve_name  
>> (NID_secp256k1);
>
>> "c16b4ce0532f5dc9d09114fe121d3956ae84f9eb677a0d4bdac1d3af7a91950c";
>
> I don't believe there's a point on secp256k1 with that x-coordinate.
> If you check the failure reason for
> EC_POINT_set_compressed_coordinates_GFp in the debugger, that is
> probably what it is telling you.
>
> Where did this curve / x-coord pair come from?
>
> BBB



Reply | Threaded
Open this post in threaded view
|

Re: Compute EC_KEY starting from X or Y coordinate only

Billy Brumley
Don't do that. As I said, the library is trying to tell you that's not a point on the secp256k1 curve.

Quickly browsing the standard, you are likely looking for the prime256v1 curve.

BBB

On Fri, 25 Oct 2019, 9.28 Luca Di Mauro, <[hidden email]> wrote:
I think it is correct because I extracted the hexadecimal string from 
a packet contained in a pcap.

This compressed point is created following the ETSI TS 103 097 v1.3.1 
standard for secured communications in the vehicular communication 
context 
(https://www.etsi.org/deliver/etsi_ts/103000_103099/103097/01.03.01_60/ts_103097v010301p.pdf).

I notice that the point 'pubPoint' that I created is empty when I try 
to call 'EC_POINT_set_compressed_coordinates_GFp' function. How can I 
put a BIGNUM into an EC_POINT?

Luca

Billy Brumley <[hidden email]> ha scritto:

>>         EC_GROUP* group         = EC_GROUP_new_by_curve_name 
>> (NID_secp256k1);
>
>> "c16b4ce0532f5dc9d09114fe121d3956ae84f9eb677a0d4bdac1d3af7a91950c";
>
> I don't believe there's a point on secp256k1 with that x-coordinate.
> If you check the failure reason for
> EC_POINT_set_compressed_coordinates_GFp in the debugger, that is
> probably what it is telling you.
>
> Where did this curve / x-coord pair come from?
>
> BBB



Reply | Threaded
Open this post in threaded view
|

Re: Compute EC_KEY starting from X or Y coordinate only

Luca Di Mauro
Thank you! I thought they were the same.

And given an x-only coordinate, how can I find the y coordinate? I  
don't find the relative functions on the documentation.

Luca

Billy Brumley <[hidden email]> ha scritto:

> Don't do that. As I said, the library is trying to tell you that's not a
> point on the secp256k1 curve.
>
> Quickly browsing the standard, you are likely looking for the prime256v1
> curve.
>
> BBB
>
> On Fri, 25 Oct 2019, 9.28 Luca Di Mauro, <[hidden email]> wrote:
>
>> I think it is correct because I extracted the hexadecimal string from
>> a packet contained in a pcap.
>>
>> This compressed point is created following the ETSI TS 103 097 v1.3.1
>> standard for secured communications in the vehicular communication
>> context
>> (
>> https://www.etsi.org/deliver/etsi_ts/103000_103099/103097/01.03.01_60/ts_103097v010301p.pdf
>> ).
>>
>> I notice that the point 'pubPoint' that I created is empty when I try
>> to call 'EC_POINT_set_compressed_coordinates_GFp' function. How can I
>> put a BIGNUM into an EC_POINT?
>>
>> Luca
>>
>> Billy Brumley <[hidden email]> ha scritto:
>>
>> >>         EC_GROUP* group         = EC_GROUP_new_by_curve_name
>> >> (NID_secp256k1);
>> >
>> >> "c16b4ce0532f5dc9d09114fe121d3956ae84f9eb677a0d4bdac1d3af7a91950c";
>> >
>> > I don't believe there's a point on secp256k1 with that x-coordinate.
>> > If you check the failure reason for
>> > EC_POINT_set_compressed_coordinates_GFp in the debugger, that is
>> > probably what it is telling you.
>> >
>> > Where did this curve / x-coord pair come from?
>> >
>> > BBB
>>
>>
>>
>>



Reply | Threaded
Open this post in threaded view
|

Re: Compute EC_KEY starting from X or Y coordinate only

Billy Brumley
> Thank you! I thought they were the same.
>
> And given an x-only coordinate, how can I find the y coordinate? I
> don't find the relative functions on the documentation.

Well it depends on what you mean. Internally,
EC_POINT_set_compressed_coordinates_GFp will internally automatically
compute the y coordinate based on the y_bit argument.

EC_POINT_set_compressed_coordinates_GFp(group, p, x, 0, ...
EC_POINT_get_affine_coordinates_GFp(group, p, X0, Y0 ...

That will get you one of the points in X0, Y0.

EC_POINT_set_compressed_coordinates_GFp(group, p, x, 1, ...
EC_POINT_get_affine_coordinates_GFp(group, p, X1, Y1 ...

That will get you the other point in X1, Y1. (Where X0 = X1 = x.)

(But you are probably looking to do something cryptographically
interesting between set/get, which is application specific.)

Generally, in addition to the man pages which you seem to have found,
check the "tests" folder if you are looking for examples to get
started.

BBB
Reply | Threaded
Open this post in threaded view
|

Re: Compute EC_KEY starting from X or Y coordinate only

Luca Di Mauro

Mh, maybe I didn't understand.

If I have an x-point which follows this representation  
https://tools.ietf.org/id/draft-jivsov-ecc-compact-05.html (so it is  
composed by 33 byte and first byte is '0x02') and I use  
'EC_POINT_set_compressed_coordinates_GFp' function, it will be  
considered as compressed-y-0 or compressed-y-1? Or it is correctly  
considered as the x coordinate?

Luca

Billy Brumley <[hidden email]> ha scritto:

>> Thank you! I thought they were the same.
>>
>> And given an x-only coordinate, how can I find the y coordinate? I
>> don't find the relative functions on the documentation.
>
> Well it depends on what you mean. Internally,
> EC_POINT_set_compressed_coordinates_GFp will internally automatically
> compute the y coordinate based on the y_bit argument.
>
> EC_POINT_set_compressed_coordinates_GFp(group, p, x, 0, ...
> EC_POINT_get_affine_coordinates_GFp(group, p, X0, Y0 ...
>
> That will get you one of the points in X0, Y0.
>
> EC_POINT_set_compressed_coordinates_GFp(group, p, x, 1, ...
> EC_POINT_get_affine_coordinates_GFp(group, p, X1, Y1 ...
>
> That will get you the other point in X1, Y1. (Where X0 = X1 = x.)
>
> (But you are probably looking to do something cryptographically
> interesting between set/get, which is application specific.)
>
> Generally, in addition to the man pages which you seem to have found,
> check the "tests" folder if you are looking for examples to get
> started.
>
> BBB



Reply | Threaded
Open this post in threaded view
|

Re: Compute EC_KEY starting from X or Y coordinate only

Thulasi Goriparthi
02 indicates y bit is 0
03 indicates y bit is 1


Thanks,
Thulasi.

On Fri, 25 Oct 2019 at 16:50, Luca Di Mauro <[hidden email]> wrote:

Mh, maybe I didn't understand.

If I have an x-point which follows this representation 
https://tools.ietf.org/id/draft-jivsov-ecc-compact-05.html (so it is 
composed by 33 byte and first byte is '0x02') and I use 
'EC_POINT_set_compressed_coordinates_GFp' function, it will be 
considered as compressed-y-0 or compressed-y-1? Or it is correctly 
considered as the x coordinate?

Luca

Billy Brumley <[hidden email]> ha scritto:

>> Thank you! I thought they were the same.
>>
>> And given an x-only coordinate, how can I find the y coordinate? I
>> don't find the relative functions on the documentation.
>
> Well it depends on what you mean. Internally,
> EC_POINT_set_compressed_coordinates_GFp will internally automatically
> compute the y coordinate based on the y_bit argument.
>
> EC_POINT_set_compressed_coordinates_GFp(group, p, x, 0, ...
> EC_POINT_get_affine_coordinates_GFp(group, p, X0, Y0 ...
>
> That will get you one of the points in X0, Y0.
>
> EC_POINT_set_compressed_coordinates_GFp(group, p, x, 1, ...
> EC_POINT_get_affine_coordinates_GFp(group, p, X1, Y1 ...
>
> That will get you the other point in X1, Y1. (Where X0 = X1 = x.)
>
> (But you are probably looking to do something cryptographically
> interesting between set/get, which is application specific.)
>
> Generally, in addition to the man pages which you seem to have found,
> check the "tests" folder if you are looking for examples to get
> started.
>
> BBB



Reply | Threaded
Open this post in threaded view
|

Re: Compute EC_KEY starting from X or Y coordinate only

Luca Di Mauro
But the y bit is indicated by the foutth parameter of  
'EC_POINT_set_compressed_coordinates_GFp' function.
Isn't the representation you linked different by that that I linked  
previously?

Luca

Thulasi Goriparthi <[hidden email]> ha scritto:

> 02 indicates y bit is 0
> 03 indicates y bit is 1
>
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.202.2977&rep=rep1&type=pdf
>
>
> Thanks,
> Thulasi.
>
> On Fri, 25 Oct 2019 at 16:50, Luca Di Mauro <[hidden email]> wrote:
>
>>
>> Mh, maybe I didn't understand.
>>
>> If I have an x-point which follows this representation
>> https://tools.ietf.org/id/draft-jivsov-ecc-compact-05.html (so it is
>> composed by 33 byte and first byte is '0x02') and I use
>> 'EC_POINT_set_compressed_coordinates_GFp' function, it will be
>> considered as compressed-y-0 or compressed-y-1? Or it is correctly
>> considered as the x coordinate?
>>
>> Luca
>>
>> Billy Brumley <[hidden email]> ha scritto:
>>
>> >> Thank you! I thought they were the same.
>> >>
>> >> And given an x-only coordinate, how can I find the y coordinate? I
>> >> don't find the relative functions on the documentation.
>> >
>> > Well it depends on what you mean. Internally,
>> > EC_POINT_set_compressed_coordinates_GFp will internally automatically
>> > compute the y coordinate based on the y_bit argument.
>> >
>> > EC_POINT_set_compressed_coordinates_GFp(group, p, x, 0, ...
>> > EC_POINT_get_affine_coordinates_GFp(group, p, X0, Y0 ...
>> >
>> > That will get you one of the points in X0, Y0.
>> >
>> > EC_POINT_set_compressed_coordinates_GFp(group, p, x, 1, ...
>> > EC_POINT_get_affine_coordinates_GFp(group, p, X1, Y1 ...
>> >
>> > That will get you the other point in X1, Y1. (Where X0 = X1 = x.)
>> >
>> > (But you are probably looking to do something cryptographically
>> > interesting between set/get, which is application specific.)
>> >
>> > Generally, in addition to the man pages which you seem to have found,
>> > check the "tests" folder if you are looking for examples to get
>> > started.
>> >
>> > BBB
>>
>>
>>
>>



Reply | Threaded
Open this post in threaded view
|

Re: Compute EC_KEY starting from X or Y coordinate only

Billy Brumley
In reply to this post by Luca Di Mauro
> If I have an x-point which follows this representation
> https://tools.ietf.org/id/draft-jivsov-ecc-compact-05.html (so it is
> composed by 33 byte and first byte is '0x02') and I use
> 'EC_POINT_set_compressed_coordinates_GFp' function, it will be
> considered as compressed-y-0 or compressed-y-1? Or it is correctly
> considered as the x coordinate?

What you are saying and what you are doing are two different things.

Your code is at a very low level.

Above this there is some encoding of points, depending on any number
of standards. OpenSSL implements some of them, but at a higher level.

The low level API you're talking about provides maximum flexibility to
map that high level encoding in to the API's "x-coord + y-bit"
concept. It's up to you to figure out the details. (Including
determining if the encoding in OpenSSL matches what's expected in your
spec.)

You need to play around a bit with the lib -- you can't expect this
list to interpret the standard for you. Check the "test" folder for
sample code.

BBB
Reply | Threaded
Open this post in threaded view
|

Re: Compute EC_KEY starting from X or Y coordinate only

Luca Di Mauro
I checked the 'test' folder but I didn't found any tests that help me  
in this case.

However the only doubt is how I can use the API offered by openssl library.
I understand how retreive a point (and consequently to assign it to a  
public key) starting from a compressed-y representation (which belongs  
to this standard  
https://tools.ietf.org/id/draft-jivsov-ecc-compact-05.html).

My doubt now is how to obtain a point (x,y) given the coordinate,  
which means resolve the equation y^2= x^3 + ax + b.
Can you give me some tips to found a solution?

Luca

Billy Brumley <[hidden email]> ha scritto:

>> If I have an x-point which follows this representation
>> https://tools.ietf.org/id/draft-jivsov-ecc-compact-05.html (so it is
>> composed by 33 byte and first byte is '0x02') and I use
>> 'EC_POINT_set_compressed_coordinates_GFp' function, it will be
>> considered as compressed-y-0 or compressed-y-1? Or it is correctly
>> considered as the x coordinate?
>
> What you are saying and what you are doing are two different things.
>
> Your code is at a very low level.
>
> Above this there is some encoding of points, depending on any number
> of standards. OpenSSL implements some of them, but at a higher level.
>
> The low level API you're talking about provides maximum flexibility to
> map that high level encoding in to the API's "x-coord + y-bit"
> concept. It's up to you to figure out the details. (Including
> determining if the encoding in OpenSSL matches what's expected in your
> spec.)
>
> You need to play around a bit with the lib -- you can't expect this
> list to interpret the standard for you. Check the "test" folder for
> sample code.
>
> BBB



Reply | Threaded
Open this post in threaded view
|

Re: Compute EC_KEY starting from X or Y coordinate only

Thulasi Goriparthi
Call to EC_POINT_set_compressed_coodinates() with with x-coordinate and y-bit will resolve the curve equation for y and chooses y out of two possible y values based on y-bit input.

You can retrieve the x and y co-ordinates using EC_POINT_get_affine_coordinates as below, where x-cordinate matches with your input x.

EC_POINT_get_affine_coordinates(group, ec_pub_key, bn_x, bn_y, NULL);

Thanks,
Thulasi.

On Sat, 26 Oct 2019 at 13:21, Luca Di Mauro <[hidden email]> wrote:
I checked the 'test' folder but I didn't found any tests that help me 
in this case.

However the only doubt is how I can use the API offered by openssl library.
I understand how retreive a point (and consequently to assign it to a 
public key) starting from a compressed-y representation (which belongs 
to this standard 
https://tools.ietf.org/id/draft-jivsov-ecc-compact-05.html).

My doubt now is how to obtain a point (x,y) given the coordinate, 
which means resolve the equation y^2= x^3 + ax + b.
Can you give me some tips to found a solution?

Luca

Billy Brumley <[hidden email]> ha scritto:

>> If I have an x-point which follows this representation
>> https://tools.ietf.org/id/draft-jivsov-ecc-compact-05.html (so it is
>> composed by 33 byte and first byte is '0x02') and I use
>> 'EC_POINT_set_compressed_coordinates_GFp' function, it will be
>> considered as compressed-y-0 or compressed-y-1? Or it is correctly
>> considered as the x coordinate?
>
> What you are saying and what you are doing are two different things.
>
> Your code is at a very low level.
>
> Above this there is some encoding of points, depending on any number
> of standards. OpenSSL implements some of them, but at a higher level.
>
> The low level API you're talking about provides maximum flexibility to
> map that high level encoding in to the API's "x-coord + y-bit"
> concept. It's up to you to figure out the details. (Including
> determining if the encoding in OpenSSL matches what's expected in your
> spec.)
>
> You need to play around a bit with the lib -- you can't expect this
> list to interpret the standard for you. Check the "test" folder for
> sample code.
>
> BBB