Tar*_*ngh 10 encryption cryptography rsa
我有一些想法,这是由于一些复杂的计算,但我想知道究竟发生了什么需要很长时间比相应的加密过程.任何链接到网页或纸张都会有很大帮助.
谢谢
感谢您的回答,再一次怀疑,签名和验证怎么样？这个时间差异是否也适用于签名和验证？防爆.签名需要比验证更多的时间吗？
Tho*_*nin 14
我们分别称为n,d和e RSA模数,私有指数和公共指数.RSA解密速度与(log d)(log n)2成比例(即模数长度的二次方,以及私有指数长度的线性).类似地,RSA加密速度与(log e)(log n)2成比例.私钥持有者也知道n的因子分解,可以用来将私钥操作加速约4倍(使用中国剩余定理).有关所涉及算法的详细信息,请参阅" 应用密码学手册",尤其是第14章("高效实施").
为了保证适当的安全性,私人指数(d)必须很大; 已经表明,如果它小于模数(n)长度的29%,则可以重建私钥.我们不知道避免这种弱点的最小长度是多少,因此在实践中d将具有与n相同的长度.这意味着解密将在n的长度上约为立方.
同样的规定并不适用于公共指数(ē),作为希望的,只要它与RSA规则规定(可为小é必须是相对素R-1的所有主要因素[R的ñ) .因此习惯上选择非常小的e.按惯例,有广泛部署的实现无法处理大型公共指数.例如,如果e不适合32位,则Windows'CryptoAPI(连接到具有RSA服务器证书的HTTPS站点时由Internet Explorer使用的那个)中的RSA实现无法处理RSA公钥.e = 3是最好的,但e = 65537是传统的(这是一种历史性的错误,因为如果使用RSA而没有适当的标准填充,一个非常小的指数可以引起感知的弱点,这是永远不应该做的事情无论如何).65537是17位长整数,而n和d的典型长度是1024位或更多.这使得公钥操作(消息加密,签名验证)比私钥操作(消息解密,签名生成)快得多.
从理论上讲,它不一定是.加密和解密算法基本相同.鉴于:
d = decryption key
e = encryption key
n = modulus (product of primes)
c = encrypted code group
m = plaintext code group
然后:
用于提升功率的常规算法是迭代的,因此所花费的时间取决于指数的大小.在大多数情况下,该对使用解密密钥(通常相当大)比加密密钥大.
但是可以扭转这一点.仅举一个玩具示例,请考虑:
p=17
q=23
n=391
以下是此特定素数对的一些有效加密/解密密钥对的列表:
e = 17, d = 145
e = 19, d = 315
e = 21, d = 285
e = 23, d = 199
e = 25, d = 169
e = 27, d = 339
e = 29, d = 85
e = 31, d = 159
e = 35, d = 171
e = 37, d = 333
e = 39, d = 343
e = 41, d = 249
e = 43, d = 131
e = 45, d = 133
e = 47, d = 15
e = 49, d = 273
e = 51, d = 283
e = 53, d = 93
e = 57, d = 105
e = 59, d = 179
在这20个密钥对中,只有一个具有小于加密密钥的解密密钥.在其他情况下,解密密钥的范围从大到两倍到几乎是大的17倍.当然,当模数很小时,生成大量密钥对会很快捷,所以找到一个小的解密密钥相当容易 - 使用真正的RSA密钥,然而,它并不是那么琐碎,而且我们通常只接受我们找到的第一对.从上面的列表中可以看出,在这种情况下,您最终可能会得到比加密密钥大得多的解密密钥,因此解密最终会比加密慢.当使用~100位数字时,我们必须非常耐心地找到一对解密将与加密一样快(甚至接近)的对.