验证一个点是否属于secp256r1

Question

我需要确认这个公钥中的点

04 11 95 23 03 f0 f1 f1 45 67 14 98 e4 39 80 ce 25 39 02 6e 72 34 fe 02 38 8a ea cc fb 3a 3d 4d dc d9 6d 3c fe 8b 55 bf ea c3 3a a1 59 13 54 b3 91 79 45 b7 3b 49 d9 0e 96 2a de 79 d3 49 dc 79 ca

在secp256r1。我已经知道了曲线的参数a和b，但是它们很大，而且是十六进制的。我一直想把它传给十进制，但我不明白。我应该用十六进制来计算吗？我也不明白公钥的坐标是什么。我的意思是，公钥应该是具有x坐标的点，也是y坐标中最不重要的部分，因为公钥从04开始，不是吗？我真的很抱歉，但我很困惑如何处理这个问题。

注意:我看到了一些与我的问题基本相同的问题，但数字要小得多。我还需要使用PARI/GP。

编辑:我尝试过使用SageMath，结果是

y = 98344895439910594971593461997930184197459096557735598026509132013917697767882
a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291

然后，我尝试了y^2 == x^3 + a*x + b，它给出了假的，但我事先知道点属于曲线。你能告诉我我做错了什么吗？

Answer 1

在有限域\mathbb F_p上定义的椭圆曲线意味着所有的坐标都是\mathbb F_p的元素，即在仿射坐标系中，设P=(x,y)是点，然后是x,y \in \mathbb F_p。实际上，所有算法都是在\mathbb F_p上完成的。

在编码中

04 11 95 23 03 f0 f1 f1 45 67 14 98 e4 39 80 ce 25 39 02 6e 72 34 fe 02 38 8a ea cc fb 3a 3d 4d dc d9 6d 3c fe 8b 55 bf ea c3 3a a1 59 13 54 b3 91 79 45 b7 3b 49 d9 0e 96 2a de 79 d3 49 dc 79 ca

第一个字节定义压缩。和04意味着没有压缩。因此，去掉04后，前半部分属于x，下半部分属于点的y坐标。

你忘了带走\bmod p了。

具有测试双方相等性的

#Sagemath
x = Integer("0x11952303f0f1f145671498e43980ce2539026e7234fe02388aeaccfb3a3d4ddc")
y = Integer("0xd96d3cfe8b55bfeac33aa1591354b3917945b73b49d90e962ade79d349dc79ca")
a = Integer("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC")
b = Integer("0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B")
p = Integer("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")

print(y^2 % p)
print( (x^3 + a * x + b) % p )
#or test with assert
assert(y^2 % p == (x^3 + a * x + b) % p)

输出

107039974491263683037557989129009082794410266580376414531485756411379666775575
107039974491263683037557989129009082794410266580376414531485756411379666775575

因此，它是曲线上的一个有效点。

在SageMath

上使用曲线

还有另一种方法，而且在SageMath上可能更容易。该方法采用椭圆曲线构造和曲线上定义点的方法。

#secp256r1
a = Integer("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC")
b = Integer("0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B")
p = Integer("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")

K = GF(p)
E = EllipticCurve(K,[a,b])

x = Integer("0x11952303f0f1f145671498e43980ce2539026e7234fe02388aeaccfb3a3d4ddc")
y = Integer("0xd96d3cfe8b55bfeac33aa1591354b3917945b73b49d90e962ade79d349dc79ca")

P = E(x,y) ### try to set the point with the coordinates.

如果P不是曲线上的一个点，您将得到许多错误

进一步注意到

在接下来的步骤中，您可能需要添加/双点。椭圆曲线使用特殊的点相加公式。您可能会发现它们是这里，或者直接使用Sagemath，您只需将加法用于点加法，P+Q和5*P用于标量乘法，通常将其写为[5]P = P + P + P + P +P。

无穷远点的

表示

椭圆曲线上的点与无穷远点\mathcal{O}上的点在点加法下形成阿贝尔群。对于secp256r1；

E(\mathbb{F_p}) := \{ (x, y) \in \mathbb{F}^2_p \mid y^2= x^3 + a\cdot x + b\} \cup \{\mathcal O\}

如我们所见，\mathcal O在仿射坐标上没有表示，我们神奇地将它添加到组定义中。虽然在数学上我们可以处理这个问题，但我们需要以编程的方式来表示它。如果b \neq 0 \bmod p坐标下的(0,0)不满足曲线方程，那么它就不在曲线上，因此它是\mathcal O表示的一个很好的选择，通常采用这种方法。在使用库时，始终检查\mathcal O是如何表示的。