NIST p256 点减压：寻找基点的 Y 坐标

Question

我正在尝试实施 NIST P256 点压缩和解压缩，但在求解 y = sqrt(x^3 + ax + b) 时，我总是得到错误的 y 坐标。

我想一个很好的减压测试是采用 NIST 定义的基点 G（https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf，第 D.1.2.3 节）并使用它的 x 坐标来验证 y 坐标 I '计算是正确的。

这是我正在做的事情：

 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

我正在获得可能的积分

110978579505207128328462658488647051134659543018045598806500827547749176924776
4813509705149120434234788460760522395426600397244715389032803761117920929175

两者都不是

的预期基准y点

36134250956749795798585127919587881956611106672985015071877198253568414405109

有没有我遗漏的东西？

Answer 1

这里不能只取普通平方根，需要取modular平方根。也就是说，给定一个整数n和一个素数p，你需要找到整数r这样 r² ≡ n mod p.

不知道VB有没有提供mod平方根函数，好像没有。某些语言确实在其标准库中提供了它，例如Go.

假设它没有，您将需要找到一个或创建您自己的。首先是研究 Tonelli-Shanks.

NIST p256 点减压：寻找基点的 Y 坐标

NIST p256 Point Decompression: Finding Y-Coordinate For Base Point

vb.net

cryptography

elliptic-curve

ecdsa

ecdh