ECDSA压缩的公钥点回到未压缩的公钥点

P = 1175846487558108474218546536054752289210804601041

X = 583857549063195252150226340830731484791130788759
Y = 1195037839477751118658084226553581900533276838164

02583857549063195252150226340830731484791130788759

#1 楼

根据定义，椭圆曲线上的所有点都会验证曲线方程，通常用$ Y ^ 2 = X ^ 3 + aX + b $表示，其中有两个给定的$ a $和$ b $参数（这两个参数实际上定义了曲线）。因此，如果您知道$ X $，则可以使用曲线方程式重新计算$ Y ^ 2 $。平方根提取将产生$ Y $或$ -Y $。压缩点格式在第一个字节中包含$ Y $的最低有效位（第一个字节为0x02或0x03，具体取决于该位）：该位足以知道您是否获得了$ Y $或$ -Y $

上面的所有计算都是在基字段中完成的，即（通常）整数以质数为模。请参阅此以求素数为模的平方根提取。


编辑：对于二进制曲线，情况有些相似。我们在$ GF（2 ^ m）$字段中工作，所以加法是XOR；曲线方程为$ Y ^ 2 + XY = X ^ 3 + aX ^ 2 + b $（非超奇异曲线的通用方程）。当点$ P =（X，Y）$时，相反的点是$ -P =（X，Y + X）$。我们假设我们正在编码和解码的点的坐标为$ X \ neq 0 $，因为这样的坐标$ X = 0 $的点等于它的对角，即顺序为$ 2 $。在实践中，当我们处理这样的曲线时，实际上使用的是$ r $质数阶的子组（通常，我们将完整的曲线阶设置为等于$ 2r $或$ 4r $）。 >
由于$ X \ neq 0 $，我们可以定义$ Z = Y / X $，然后将曲线方程除以$ X ^ 2 $。这样得出：
$$ Z ^ 2 + Z = X + a + \ frac {b} {X ^ 2} $$
因此，给定$ X $，我们可以计算$ Z ^ 2 + Z $。根据该值，我们可以计算两个解决方案，分别是$ Z $和$ Z + 1 $（请参见下文）。由于$ Y = XZ $，这将产生$ Y $和$ Y + X $，从而得到点$ P $和$ -P $。

这为我们提供了二进制字段中曲线的压缩方法：从$（X，Y）$计算$ Z = Y / X $;然后，压缩点包含$（X，z_0）$，其中$ z_0 $是$ Z $的最低有效位。解压缩时，可以使用上面的公式重新计算$ Z ^ 2 + Z $，然后重新计算$ Z $（$ z_0 $的知识告诉您两个解决方案中的哪一个是正确的$ Z $），然后$ Y = XZ $ 。

要了解如何求解$ Z $，我们需要定义迹线和半迹线。我们在$ GF（2 ^ m）$中；值$ x $的踪迹为：
$$ \ mathrm {Tr}（x）= \ sum_ {i = 0} ^ {m-1} x ^ {2 ^ i} $$
我们处于特征为$ 2 $的字段中，这意味着平方是自同构的：$（uv）^ 2 = u ^ 2v ^ 2 $和$（u + v）^ 2 = u ^ 2 + v ^ 2 $对于所有$ u $和$ v $（这称为Frobenius自同构）。此外，对于所有$ u $，$ u ^ {2 ^ m} = u $（这类似于费马小定理，因为$ GF（2 ^ m）$的非零元素是阶为$ 2的乘法组^ m-1 $）。这意味着跟踪的两个重要特征：


跟踪是线性的：对于所有$ u $和$ v $，$ \ mathrm {Tr}（u + v）= \ mathrm {Tr}（u）+ \ mathrm {Tr}（v）$。
任何$ u $的踪迹为$ 0 $或$ 1 $。实际上，对于所有$ u $，$ \ mathrm {Tr}（u ^ 2）= \ mathrm {Tr}（u）^ 2 $（根据Frobenius自同构）以及$ \ mathrm {Tr}（u ^ 2 ）= \ mathrm {Tr}（u）$（在定义轨迹的方程式中尝试）。因此，对于所有$ u $，$ \ mathrm {Tr}（u）^ 2 = \ mathrm {Tr}（u）$。方程$ x ^ 2 = x $是度数$ 2 $的多项式方程，因此它在一个字段中最多只能有$ 2 $个解，而$ 0 $和$ 1 $是解。因此，$ \ mathrm {Tr}（u）$只能是$ 0 $或$ 1 $。

现在定义半迹。现在，我假设$ m $是奇数（这是二进制椭圆曲线的正常情况，例如NIST曲线B-233在$ GF（2 ^ {233}）$中定义）。对于任何值$ x $，$ x $的一半轨迹为：
$$ H（x）= \ sum_ {i = 0} ^ {（m-1）/ 2} x ^ {2 ^ {2i}} $$
，即，我们采用跟踪方程式，但只将一半的操作数保留在总和中。

像迹线一样，半迹线也是线性的。此外，对于任何$ x $，我们可以看到：
$$ H（x）^ 2 + H（x）= \ mathrm {Tr}（x）+ x ^ {2 ^ m} = \ mathrm {Tr}（x）+ x $$

让我们回到方程$ Z ^ 2 + Z = \ beta $其中$ \ beta = X + a +（b / X ^ 2）$ 。由于迹线是线性的，并且由于$ Z $和$ Z ^ 2 $具有相同的迹线，因此$ \ mathrm {Tr}（\ beta）= \ mathrm {Tr}（Z ^ 2 + Z）= \ mathrm {Tr}（Z ^ 2）+ \ mathrm {Tr}（Z）= 0 $（请记住，加法运算是$ GF（2 ^ m）$中的XOR）。因此，仅当$ \ mathrm {Tr}（\ beta）= 0 $时，方程才可以有解。然后，我们有$ H（\ beta）^ 2 + H（\ beta）= \ beta $，因此$ Z $的解是$ H（\ beta）$和$ H（\ beta）+ 1 $。 br />
如果$ m $是偶数（在二进制曲线上使用配对通常会发生这种情况，尽管这可能不是一个好主意，因为二进制字段中的离散对数比以前预期的要容易得多），那么上面的大部分内容成立，尽管我们需要为半迹线定义另一个定义。基本上，我们需要一个常量元素$ w $，这样$ \ mathrm {Tr}（w）= 1 $，我们可以将半迹定义为：
$$ H（x）= \ sum_ {i = 0} ^ {m-1} \ left（\ sum_ {j = 0} ^ {i} x ^ {2 ^ j} \ right）w ^ {2 ^ i} $$

在两种情况下（$ m $奇数和$ m $偶数），半迹线都是线性的，因此可以将其计算为某些等于源$ 1 $位的预计算值的XOR。这是相当便宜的。跟踪甚至更容易：它只是一些输入位的XOR，实际上，通常是这些位中很少的XOR。