Nist P256: How to calculate Y public key when knowing X and the LSB bit of Y public key

Yann Garcia garcia.yann at gmail.com
Fri Nov 9 09:02:34 CET 2018


Dear All,

I was requested to write a dissector for Wireshark where I need to decrypt
data. I have the ephemeral X public key provided in compressed format.
This means:

compressed_y_1 :=
'CF2A7D7467F217A6B7AEF4C34452A4C62FEDA99C1E1EDEB740F662841B84D394'O
compressed_y_1 means that the LSB bit of Y in 1.

I know I have t use Nist P256 (or Brainpool P256 r1).

My problem is to calculate Y based on previous information.
First I calculated Y^2:
    /* y^2=x^3+a*x+b */
    three = gcry_mpi_set_ui (NULL, 3);
    x_3   = gcry_mpi_new (0);
    axb   = gcry_mpi_new (0);
    y_2   = gcry_mpi_new (0);
    gcry_mpi_powm (x_3, x, three, p); // w = b^e \bmod m.
    gcry_mpi_mulm (axb, a, x, p);
    gcry_mpi_addm (axb, axb, b, p);
    gcry_mpi_addm (y_2, x_3, axb, p);
    show_mpi("y_2", "", y_2);
Where a, b, p are parameters from the Nist P-256 elliptic curve.

My concerns now is how to get the two possible values of y? In other words,
how can I calculate sqrt(y^2).

I did some research on the Internet, but what I found is too much
Mathematical oriented and I was lost. I need something close than an
algorithm I can implement with libgcrypt MIP library.

Please can anyone provide me to some hints?

Many thanks in advance for your help,


Best regards,

Yann Garcia
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.gnupg.org/pipermail/gcrypt-devel/attachments/20181109/6157e953/attachment.html>


More information about the Gcrypt-devel mailing list