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

[Yann Garcia]

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 :=
'D418760F0CB2DCB856BC3C7217AD3AA36DB6742AE1DB655A3D28DF88CBBF84E1'O;
Public key X := '
*EE9CC7FBD9EDECEA41F7C8BD258E8D2E988E75BD069ADDCA1E5A38E534AC6818*'O;
Publick key Y :=
'5AE3C8D9FE0B1FC7438F29417C240F8BF81C358EC1A4D0C6E98D8EDBCC714017'O;
Public compressed key := '
*03EE9CC7FBD9EDECEA41F7C8BD258E8D2E988E75BD069ADDCA1E5A38E534AC6818*'O;


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= :
00EE9CC7FBD9EDECEA41F7C8BD258E8D2E988E75BD069ADDCA1E5A38E534AC6818


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);
  gcry_mpi_addm (axb, axb, b, p);
  gcry_mpi_addm (y_2, x_3, axb, p);


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

output: y_2:
00E2BC9B1E5CB40472C271A5FAB056FA5D821591027481894A50B1ADEA18A6ABF0


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_add_ui(p_plus_1, p, 1);
    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
Microsoft MCAD.net Certified
**************************************
FSCOM SARL
Le Montespan B2
6,
<https://maps.google.com/?q=6,%C2%A0+Avenue+des+Alpes&entry=gmail&source=g>
Avenue des Alpes
<https://maps.google.com/?q=6,%C2%A0+Avenue+des+Alpes&entry=gmail&source=g>
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
Google+: garcia.yann at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.gnupg.org/pipermail/gcrypt-devel/attachments/20181128/b796e807/attachment-0001.html>