ECDSA签名生成和验证延迟

Question

我正在执行一些P256 ecdsa签名生成和验证延迟的度量，我原以为签名验证将比签名生成更快，但事实并非如此。是什么使签名生成更快？在签名验证中，计算开销最大的操作是什么？

Answer 1

我原以为签名验证比签名生成更快。

因为在RSA中签名验证更快？正如您所看到的，RSA != ECDSA；签名和验证所涉及的操作完全不同。

是什么使签名生成更快？

因为签名生成只需要一个点乘(加上一个模逆运算；比较便宜，但代价不小)，而签名验证则涉及两点乘法。

当然，如果您深入到教科书定义的下面，那么双方都有可用的优化：

在签名方：

• 点乘k \times G (我将在维基百科页面上使用表示法)使用一个固定的点(由椭圆曲线定义定义)；有许多方法可以通过基于G的预计算来大大加快速度。
• 此外，与签名操作相关的昂贵操作不依赖于正在签名的消息。因此，如果您的实现有一些空闲时间，它可以预生成k和r值；当它获得消息时，它可以使用这些值以相当低的延迟对消息进行签名。
• 另外，还有一个警告:如果您考虑使用相同的k, r值来签名多条消息，请不要这样做--这会泄露您的私密签名密钥。您确实需要为每个签名的消息随机选择一个新的k值。

在验证方面，昂贵的操作是计算u_1 \times G + u_2 \times Q_A。

• 人们可以使用预先计算的表来快速计算u_1 \times G；这意味着计算u_2 \times Q_A的时间是大部分时间(如果您知道需要多次使用特定的公钥Q_A进行验证，那么您可以基于此预先计算表--我还没有听说过有谁会这么做，因为您需要验证来自该公钥的数千个签名才有价值)。
• 或者，还有Shamir的技巧，这是一种计算a \times P + b \times Q的方法，它的计算时间不超过计算单点乘法所需的时间。但是，您会从预先计算的表中丢失速度。

但是，这两种想法都不会产生与使用预先计算的表进行签名一样快的验证方法。

Answer 2

使用符号那里，ECDSA签名生成需要一个椭圆曲线点乘法，k\times G。而朴素签名验证使用两种方法，即在添加u_1\times G和u_2\times Q_A之前先计算它们。点乘通常是签名生成/验证中最慢的操作，可能是散列(签名生成和验证中常见的)。这可以解释观测到的时间差异。

然而，情况远非如此，还有其他原因可以逆转或至少减轻这种情况：

• 各种技术，如沙米尔诡计或交织的wNAFs允许计算u_1\times G+u_2\times Q_A必须少于两点乘法。在一些CPU上，可以进行并行化。
• k的随机生成仅是生成所必需的，而且在某些平台上可能比较慢。
• 在生成过程中有秘密数据被操纵，而不是验证，这可以激发减缓事物的对策(并且可能需要更多的随机性)。特别是，一种常见的安全实践是先验证生成的签名，然后再暴露它，这样就会产生相反的情况。