# 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
Wed Nov 28 11:17:49 CET 2018

```Hello,

I wrote some code to generate an ECDSA S-exp (X, Y) public keys based of an
existing compressed key. This compressed key formatted like this:

(02||X public key), 02 indicating that the Y key is even
(03||X public key), 02 indicating that the Y key is odd

I tried my code with this NIST P-256 public keys pair generated also using
libgcrypt:

Private key :=
Public key X := '
Publick key Y :=
'5AE3C8D9FE0B1FC7438F29417C240F8BF81C358EC1A4D0C6E98D8EDBCC714017'O;
Public compressed key := '

My issue is that the Y keys I calculated is not correct. I did a mistake
somewhere but I cannot find it :(
Many thanks to you to take a time to verify my code?

Here is my code, based on https://en.wikipedia.org/wiki/Quadratic_residue:
1) I convert the x_buffer (containing the public key X) into x,
a gcry_mpi_t value

if ((rc = gcry_sexp_build(&e_key, NULL, "(e-key(x %b))", buffer_size,
x_buffer)) != 0) {
...
}
if ((x = gcry_sexp_nth_mpi(gcry_sexp_find_token(e_key, "x", 0), 1,
GCRYMPI_FMT_USG)) == NULL) {
...
}

2) Here, x really contains my public key:

output: x= :

3) The Ecc curve equation is: y^2=x^3+a*x+b, with a and b specific to NIST
P-256 elliptic curve
I want to calculate y^2:

two   = gcry_mpi_set_ui (NULL, 2);
three = gcry_mpi_set_ui (NULL, 3);
four = gcry_mpi_set_ui (NULL, 4);
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);

4) Here y_2 contains the result of x^3+a*x+b

output: y_2:

5) I'm going to calculate sqrt(y^2): two solutions : y = p + 1 / 4 or y = p
- 3 / 4  */

q     = gcry_mpi_new (0);
r     = gcry_mpi_new (0);
y     = gcry_mpi_new (0);
if (p_comp_mode == 0x02) { // Y key is even
/* Solution one: y = p + 1 / 4 */
p_plus_1   = gcry_mpi_new (0);
gcry_mpi_div(q, r, p_plus_1, four, 0);
gcry_mpi_release(p_plus_1);
} else { // Y key is odd
/* Solution two: p - 3 / 4 */
p_minus_3  = gcry_mpi_new (0);
gcry_mpi_sub_ui(p_minus_3, p, 3);
gcry_mpi_div(q, r, p_minus_3, four, 0);
gcry_mpi_release(p_minus_3);
}
gcry_mpi_powm(y, y_2, q, p);
show_mpi("y", "", y);

6) Here Y contain the Y public key:

output: y: 3ED29A0C723BDE987C0D4DE143FB7781F476AA385D71E42C66BF5F019F850F3E

7) This is not what I was expected for, it should be:
'5AE3C8D9FE0B1FC7438F29417C240F8BF81C358EC1A4D0C6E98D8EDBCC714017'O;

Best regards,

Yann Garcia
Senior Software Engineer
**************************************
FSCOM SARL
Le Montespan B2
6,
Avenue des Alpes
F-06600 Antibes, FRANCE
************************************************
Tel: +33 (0)4 92 94 49 08
Mobile: +33 (0)7 61 00 77 05
Email: *yann.garcia at fscom.fr* <yann.garcia at fscom.fr>
Yann.Garcia_EXT at etsi.org
Skype: yann.garcia