title: NIST p256 Point Decompression: Finding Y-Coordinate For Base Point
body: <p>I'm trying to implement NIST P256 point compression and decompression and I keep getting the wrong y coordinate when I solve y = sqrt(x^3 + ax + b). </p>
  
  <p>I figured a good test of the decompression would be to take the base point G defined by NIST(<a href="https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf" rel="nofollow noreferrer">https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf</a>, Section D.1.2.3) and use it's x coordinate to verify that the y coordinates I'm calculating are correct. </p>
  
  <p>Here's what I'm doing:</p>
  
  <pre><code> Public Shared Sub TestBasePoint()
      'Parameters for the curve as defined by NIST: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf D.1.2.3
      Dim p As BigInteger = BigInteger.Pow(New BigInteger(2), 256) - BigInteger.Pow(New BigInteger(2), 224) + BigInteger.Pow(New BigInteger(2), 192) + BigInteger.Pow(New BigInteger(2), 96) - 1
      Dim a As BigInteger = BigInteger.Parse("3")
      Dim b As BigInteger = BigInteger.Parse("41058363725152142129326129780047268409114441015993725554835256314039467401291")
  
      'The base point 
      Dim Gx As BigInteger = BigInteger.Parse("48439561293906451759052585252797914202762949526041747995844080717082404635286") 'Gx = 6b17d1f2 e12c4247 f8bce6e5 63a440f2 77037d81 2deb33a0 f4a13945 d898c296
      Dim Gy As BigInteger = BigInteger.Parse("36134250956749795798585127919587881956611106672985015071877198253568414405109") 'Gy = 4fe342e2 fe1a7f9b 8ee7eb4a 7c0f9e16 2bce3357 6b315ece cbb64068 37bf51f5
  
      'Compute Sqrt(x^3+ax+b) to get possible values
      Dim x3 As BigInteger = BigInteger.Pow(Gx, 3) Mod p
      Dim ax As BigInteger = (a * Gx) Mod p
      Dim x3ax As BigInteger = (x3 - ax) Mod p
      Dim alpha As BigInteger = (x3ax + b) Mod p
      Dim y_solution1 As BigInteger = Sqrt(alpha) Mod p '110978579505207128328462658488647051134659543018045598806500827547749176924776
      Dim y_solution2 As BigInteger = (p - y_solution1) '4813509705149120434234788460760522395426600397244715389032803761117920929175
  
  End Sub
  </code></pre>
  
  <p>I'm getting possible points </p>
  
  <ul>
  <li><p><strong>110978579505207128328462658488647051134659543018045598806500827547749176924776</strong></p></li>
  <li><p><strong>4813509705149120434234788460760522395426600397244715389032803761117920929175</strong></p></li>
  </ul>
  
  <p>neither of which are the expected base y point of</p>
  
  <ul>
  <li><strong>36134250956749795798585127919587881956611106672985015071877198253568414405109</strong></li>
  </ul>
  
  <p>Is there something I'm missing?</p>