RSA公钥指数的选取

1：什么是RSA公钥指数。

首先了解一下RSA密钥的建立流程。如下图所示：

& o$ J' {  j& Y3 Z

(1)选择两个不同的大素数p和q；

(2)计算公共模数（n=pq）和欧拉数（eular=(p-1)(q-1)）；

(3)选择公钥指数e；

(4)计算inverse（d）；

(5)生成公钥、私钥；

上述流程中出现的e就是公钥指数。

2：公钥指数的选取。

公钥指数是可以随意选取的，但是为了提高RSA的加密速度实际使用中公钥指数最长用的三个值是3、17、65537(=2^16+1，65537的二进制表示中只有两个1，所以需要17次乘法来实现指数运算)。PEM建议用3。PKCS#1建议用3或65537。X.509建议用65537。这样选取主要是为了提高加密或签名验证的性能，因为3、17或65537分别只需要2或17次模乘运算，而一个随机选择的e(假设n是1024-bit)则大约需要1000次模乘运算。这种方法刻意把公钥指数选的小一点，其对应私钥指数就会很大，这么做的目的是节约公钥运算的时间。因为正常使用中都是用公钥加密，所以需要节约大部分人的时间。而极少部分人也会选用私钥解密，那么就只能少数服从多数了。

在选用公钥指数时，人们普遍会认为3和17没有65537安全。然而这种想法并没有合理的依据。实际上采用这三个值中的任何一个都不存在安全问题。前提是使用正确的填充方案。