2

我正在尝试实现 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 坐标是否正确。

这就是我正在做的事情：

 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

有什么我想念的吗？

4

1 回答 1

3

你不能在这里只取普通平方根，你需要取模平方根。换句话说，给定一个整数n和一个素数p，您需要找到整数r使得r 2 ≡ n mod p。

我不知道VB是否提供了模块化平方根函数，它看起来不像。有些语言确实在他们的标准库中提供了它，例如Go。

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

于 2019-07-31T22:17:20.557 回答