RSA加密算法六:公私钥对安全性的一点思考

考虑这样一个问题:

扩展欧几里得算法如何确定私钥d的值?公钥(n, e)对应的私钥(n, d)是否唯一?

根据之前编写的扩展欧几里得算法得到一个解

这次使用枚举法得到几组解

这些解的特点非常明显,是差值为fn的等差数列,这个也很容易理解

根据RSA加解密过程

对于同一公钥(n,e)使用不同的私钥(n,d)进行解密

得到的解密密文是相同的都是65,所以我们有一个结论

结论1:

公钥:(n, e) = (3233, 17)对应私钥不止一个:(n, d) = (3233, 2753) or (3233, 5873) or (3233, 8993)

并且每一个私钥都可以正确解密公钥加密的密文。

并且所有私钥值dn满足 dn = d1+k*fn,即所有满足的值d构成公差为fn的等差数列

使用openssl中生成的RSA证书进行研究,观察私钥值d的生成规律

在32bit证书中,根据p q和e的值使用扩展欧几里得算法得到的值d与证书中的值d相同

在64bit证书中,也满足此规律,需要使用hex()转换成16进制

根据以上,有一个结论

结论2:

扩展欧几里得算法计算得到的d值与生成的私钥文件中privateExpontent值相同,并且d的取值应该是取最小正整数值或者说最优值。

根据以上所有实验,发现如下问题:

问题:

(1)公钥(n,e)对应的私钥(n,d)可能不唯一,但不影响加解密结果

(2)如果有两个证书A和B含有相同的公钥(n,e),并且A证书的私钥d泄露,则可以用泄露的A的私钥d解密未泄露的证书B

以上2出现的概率应该很小,但是可以作为一种证书破解思路。

方法:

可以收集已经泄露的证书的公钥(n,e),然后跟现有未泄露的证书比对,如果发现有相同的公钥(n,e),则可以用泄露的私钥解密此证书。

您可能还喜欢...