为什么验证比签名快得多？

Question

我试图通过运行以下命令来衡量 rsa 算法的性能：

$:openssl speed rsa

输出：

                sign    verify    sign/s verify/s
rsa  512 bits 0.000048s 0.000003s  20923.5 355236.0
rsa 1024 bits 0.000102s 0.000007s   9757.6 152852.6
rsa 2048 bits 0.000676s 0.000022s   1479.2  46028.3
rsa 3072 bits 0.002385s 0.000041s    419.3  24407.0
rsa 4096 bits 0.005083s 0.000069s    196.7  14392.3
rsa 7680 bits 0.041772s 0.000234s     23.9   4281.9
rsa 15360 bits 0.231628s 0.000960s      4.3   1041.6

正如我们从该命令的输出中看到的那样，验证操作花费的时间比签名操作花费的时间少谁能解释一下为什么验证比签名快得多？提前致谢！

Answer 1

我这里只讲RSA签名。

首先，RSA public 密钥是一对 (n,e)，其中 n 是模数，e 称为 public 指数。

常见的 RSA public 指数是 {3、5、17、257 或 65537}。原因很简单；验证成本可以控制在最低限度。例如，如果您 select 3 那么它将需要 1 次乘法和 1 次平方，并且速度很快 moduluar squaring algorithm。如果你 select 65537 = 2^16+1 那么这将需要 16 次平方和 1 次乘法。

现在，一旦您 select 您的 public 密钥，私有指数 d 是一个随机整数 e *d = 1 mod φ(n)，出于安全考虑，我们希望采用这种方式.我们不想要 small d 因为它不安全。在本文 Twenty Years of Attacks on the RSA Cryptosystem.

中阅读有关攻击的更多信息

由于 d 是随机的，如果我们使用 Euler's totient function φ 则平均需要 φ(n)=(p-1)(q-1) 平方和 φ(n)/2 乘法。这就是验证和签名成本差异的核心原因。

RSA 必须在没有适当填充的情况下使用，对于签名，它必须与 RSA-PSS 一起使用（对于加密 OAEP 或 PKCS#5v.5 填充也类似）

备注;

我们实际用的是Carmichael function instead of Euler's function since it always produces the smallest d.
RSA可以使用CRT将私钥运算速度提高4倍，OpenSSL就是这样使用的
RSA 签名不是解密，如上所述，安全 RSA（不是教科书 RSA）必须使用适当的填充。
是的，首先我们selectpublic键然后确保GCD(φ(n), e ) =1，如果不是select新素数p和q 其中 n=p * q

为什么验证比签名快得多？

Why verify is quite faster than sign?

verification

openssl

cryptography

signing

rsa

输出：