<div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div>Hello,</div><div><br></div><div>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:</div></div></div></div></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><div><div><div><div>(02||X public key), 02 indicating that the Y key is even</div></div></div></div></div><div><div><div><div><div>(03||X public key), 02 indicating that the Y key is odd</div></div></div></div></div></blockquote><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><br></div><div>I tried my code with this NIST P-256 public keys pair generated also using libgcrypt:</div></div></div></div></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><div><div><div><div><div>Private key := 'D418760F0CB2DCB856BC3C7217AD3AA36DB6742AE1DB655A3D28DF88CBBF84E1'O;</div></div></div></div></div></div><div><div><div><div><div><div>Public key X := '<b>EE9CC7FBD9EDECEA41F7C8BD258E8D2E988E75BD069ADDCA1E5A38E534AC6818</b>'O;</div></div></div></div></div></div><div><div><div><div><div><div>Publick key Y := '5AE3C8D9FE0B1FC7438F29417C240F8BF81C358EC1A4D0C6E98D8EDBCC714017'O;</div></div></div></div></div></div><div><div><div><div><div><div>Public compressed key := '<b><font color="#0000ff">03</font>EE9CC7FBD9EDECEA41F7C8BD258E8D2E988E75BD069ADDCA1E5A38E534AC6818</b>'O;</div></div></div></div></div></div></blockquote><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><br></div><div>My issue is that the Y keys I calculated is not correct. I did a mistake somewhere but I cannot find it :(</div><div>Many thanks to you to take a time to verify my code?</div><div><br></div><div>Here is my code, based on <a href="https://en.wikipedia.org/wiki/Quadratic_residue">https://en.wikipedia.org/wiki/Quadratic_residue</a>:</div><div>1) I convert the x_buffer (containing the public key X) into x, a gcry_mpi_t value</div></div></div></div></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><div><div><div><div> if ((rc = gcry_sexp_build(&e_key, NULL, "(e-key(x %b))", buffer_size, x_buffer)) != 0) {</div></div></div></div></div><div><div><div><div><div>...</div></div></div></div></div><div><div><div><div><div><div> }</div></div></div></div></div></div><div><div><div><div><div><div> if ((x = gcry_sexp_nth_mpi(gcry_sexp_find_token(e_key, "x", 0), 1, GCRYMPI_FMT_USG)) == NULL) {</div></div></div></div></div></div><div><div><div><div><div><div>...</div></div></div></div></div></div><div><div><div><div><div><div> }</div></div></div></div></div></div></blockquote><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><div><br></div><div>2) Here, x really contains my public key:</div></div></div></div></div></div></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><div>output: x= : 00EE9CC7FBD9EDECEA41F7C8BD258E8D2E988E75BD069ADDCA1E5A38E534AC6818</div></div></div></div></div></div></div></blockquote><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><br></div><div>3) The Ecc curve equation is: y^2=x^3+a*x+b, with a and b specific to NIST P-256 elliptic curve</div><div>I want to calculate y^2:</div></div></div></div></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><div><div><div><div><div> two = gcry_mpi_set_ui (NULL, 2);</div></div></div></div></div></div><div><div><div><div><div><div> three = gcry_mpi_set_ui (NULL, 3);</div></div></div></div></div></div><div><div><div><div><div><div> four = gcry_mpi_set_ui (NULL, 4);</div></div></div></div></div></div><div><div><div><div><div><div> x_3 = gcry_mpi_new (0);</div></div></div></div></div></div><div><div><div><div><div><div> axb = gcry_mpi_new (0);</div></div></div></div></div></div><div><div><div><div><div><div> y_2 = gcry_mpi_new (0);</div></div></div></div></div></div><div><div><div><div><div><div> gcry_mpi_powm (x_3, x, three, p); // w = b^e \bmod m.</div></div></div></div></div></div><div><div><div><div><div><div> gcry_mpi_mulm (axb, a, x, p);</div></div></div></div></div></div><div><div><div><div><div><div> gcry_mpi_addm (axb, axb, b, p);</div></div></div></div></div></div><div><div><div><div><div><div> gcry_mpi_addm (y_2, x_3, axb, p);</div></div></div></div></div></div></blockquote><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><div><br></div><div>4) Here y_2 contains the result of x^3+a*x+b</div></div></div></div></div></div></div></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><div>output: y_2: 00E2BC9B1E5CB40472C271A5FAB056FA5D821591027481894A50B1ADEA18A6ABF0</div></div></div></div></div></div></div></div></blockquote><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><br></div><div>5) I'm going to calculate sqrt(y^2): two solutions :
y = p + 1 / 4 or y = p - 3 / 4 */</div></div></div></div></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><div><div><div><div><div> q = gcry_mpi_new (0);</div></div></div></div></div></div><div><div><div><div><div><div> r = gcry_mpi_new (0);</div></div></div></div></div></div><div><div><div><div><div><div> y = gcry_mpi_new (0);</div></div></div></div></div></div><div><div><div><div><div><div> if (p_comp_mode == 0x02) { // Y key is even</div></div></div></div></div></div><div><div><div><div><div><div> /* Solution one: y = p + 1 / 4 */</div></div></div></div></div></div><div><div><div><div><div><div> p_plus_1 = gcry_mpi_new (0);</div></div></div></div></div></div><div><div><div><div><div><div> gcry_mpi_add_ui(p_plus_1, p, 1);</div></div></div></div></div></div><div><div><div><div><div><div> gcry_mpi_div(q, r, p_plus_1, four, 0);</div></div></div></div></div></div><div><div><div><div><div><div> gcry_mpi_release(p_plus_1);</div></div></div></div></div></div><div><div><div><div><div><div> } else { // Y key is odd</div></div></div></div></div></div><div><div><div><div><div><div> /* Solution two: p - 3 / 4 */</div></div></div></div></div></div><div><div><div><div><div><div> p_minus_3 = gcry_mpi_new (0);</div></div></div></div></div></div><div><div><div><div><div><div> gcry_mpi_sub_ui(p_minus_3, p, 3);</div></div></div></div></div></div><div><div><div><div><div><div> gcry_mpi_div(q, r, p_minus_3, four, 0);</div></div></div></div></div></div><div><div><div><div><div><div> gcry_mpi_release(p_minus_3);</div></div></div></div></div></div><div><div><div><div><div><div> }</div></div></div></div></div></div><div><div><div><div><div><div><div> gcry_mpi_powm(y, y_2, q, p);</div></div></div></div></div></div></div><div><div><div><div><div><div><div> show_mpi("y", "", y);</div></div></div></div></div></div></div></blockquote><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><div><br></div><div>6) Here Y contain the Y public key:</div></div></div></div></div></div></div></div></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div>output: y: 3ED29A0C723BDE987C0D4DE143FB7781F476AA385D71E42C66BF5F019F850F3E</div></div></div></div></div></div></div></div></blockquote><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><br></div><div>7) This is not what I was expected for, it should be: '5AE3C8D9FE0B1FC7438F29417C240F8BF81C358EC1A4D0C6E98D8EDBCC714017'O;</div><div><br></div><div><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr">Best regards,<br><br>Yann Garcia<br><span style="color:rgb(0,0,0);white-space:pre-wrap">Senior Software Engineer</span><div><span style="font-size:small">Microsoft MCAD.net Certified</span><br>**************************************<br><span style="font-size:small">FSCOM SARL</span><br style="font-size:small"><span style="font-size:small">Le Montespan B2</span><br style="font-size:small"><span style="color:navy;font-family:Arial,sans-serif;font-size:10pt"><a href="https://maps.google.com/?q=6,%C2%A0+Avenue+des+Alpes&entry=gmail&source=g" target="_blank">6,</a> <a href="https://maps.google.com/?q=6,%C2%A0+Avenue+des+Alpes&entry=gmail&source=g" target="_blank">Avenue des Alpes</a></span><span style="color:navy"> </span><br style="font-size:small"><span style="font-size:small">F-06600 Antibes, FRANCE</span><br>************************************************<br>Tel: +33 (0)4 92 94 49 08<br>Mobile: +33 (0)7 61 00 77 05<br>Email: <a href="mailto:yann.garcia@fscom.fr" target="_blank"><b>yann.garcia@fscom.fr</b></a></div><div> <span style="font-size:12.8px;white-space:nowrap"><a href="mailto:Yann.Garcia_EXT@etsi.org" target="_blank">Yann.Garcia_EXT@etsi.org</a></span><br>Skype: yann.garcia<br>Google+: <a href="mailto:garcia.yann@gmail.com" target="_blank">garcia.yann@gmail.com</a><br></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>