RSA 算法是1978 年由R. Rivest、 A. Shamir 和L. Adleman 提出的一种用数论构造的公钥密码体制， 是迄今理论上最成熟完善的公钥密码体制， 已得到广泛应用。

1. RSA 算法描述

1) 密钥产生

(1) 选两个保密的大素数p 和q。

(2) 计算n， n=p×q， φ(n) =(p-1)(q-1)， 其中φ(n) 是n 的欧拉函数值。

(3) 选一整数e， 满足1 ＜e ＜φ(n)， 且gcd(φ(n)，e) =1。

(4) 计算d， 满足d·e≡1 mod φ(n)， 即d 是e 在模φ(n) 下的乘法逆元， 因e 与φ(n) 互素， 由模运算可知， 它的乘法逆元一定存在。

(5) 以{e，n} 为公钥， 以{d，n} 为私钥。

2) 加密

加密时， 首先将明文比特串分组， 使每个分组对应的十进制数小于n， 即分组长度小于log2n； 然后对每个明文分组m 做加密运算: c≡me mod n。

3) 解密

对密文分组的解密运算:

m≡cd mod n

下面证明RSA 算法中解密过程的正确性。

证明: 由加密过程知， c≡me mod n， 所以

分两种情况:

①m 与n 互素， 则由欧拉定理得

mφ(n)≡1 mod n， mk φ(n)≡1 mod n， mk φ(n) +1≡m mod n， 即cdmod n≡m。

②gcd(m，n)≠1，mkφ(n) +1≡m mod n， 所以cd mod n≡m。

2. RSA 算法举例

(1) 选择素数: p=17， q=11。

(2) 计算: n=pq=17 ×11 =187， φ(n) =(p-1)(q-1) =16 ×10 =160。

(3) 选择e: gcd(e，160) =1， 因此选择e=7。

(4) 确定d: de≡1 mod 160 且d ＜160， 所以d=23。 这是因为， 23×7=161=1×160+1

(5) 公钥KU={7，187}， 私钥KR={23，187}

RSA 的加密、 解密如下:

给定消息: M=88 (88 ＜187)

加密: C=887mod 187 =11

解密: M=1123mod 187 =88

3. RSA 算法的安全性分析(www.daowen.com)

RSA 算法的安全性是基于分解大整数的困难性假定， 之所以能这样假定， 是因为至今还未能证明分解大整数就是NP 完全问题， 也许有尚未发现的多项式时间分解算法。 如果RSA 算法的模数n 被成功地分解为p ×q， 则立即获得φ(n) =(p -1)(q -1)，就能够确定e mod φ(n) 的乘法逆元d， 即d≡e -1 mod φ(n)， 因此攻击成功。 若使RSA算法安全， 则p 与q 必为足够大的素数， 从而使分析者没有办法在多项式时间内将n 分解出来。

随着人类计算能力的不断提高， 原来被认为不可能分解的大整数已被成功分解。 例如，RSA-129 (即n 为129 位十进制数， 约428 位) 已于1994 年被成功分解， RSA-130 已于1996 年被成功分解。

对于大整数的威胁， 除了人类的计算能力外， 还来自分解算法的进一步改进。 使用RSA算法时， 对其密钥的选取要特别注意其大小。 估计在未来一段比较长的时期， 密钥长度为1024 ～2048 位的RSA 算法是安全的。

由于RSA 算法的计算速度远远逊色于DES 算法， 因此RSA 算法用于加密会话密钥、 数字签名和认证。

4. RSA 算法实现中的问题

1) 如何计算ab mod n

RSA 算法的加密、 解密过程都为先求一个整数的整数次幂， 再取模。 如果按其含义直接计算， 则中间结果非常大， 有可能超出计算机所允许的整数取值范围。 然而， 用模运算的性质， 即

可减小中间结果。

因此， 应考虑如何提高加密、 解密运算中指数运算的有效性。 例如， 求x16， 若直接计算， 则需做15 次乘法。 然而如果重复对每个部分结果做平方运算， 即求x、 x2、 x4、 x8、x16， 则只需做4 次乘法。

由此可知， 求am可按以下进行(a、 m 为正整数): 将m 表示为二进制形式bk bk-1…b0，即

因此，

2) 密钥产生

在公钥密码体制的密钥产生过程中， 关于“如何找到足够大的素数p 和q” 和“选择e或d， 然后计算另外一个” 都是比较难解决的问题。

(1) 素数选取。

为了防止攻击方通过穷举攻击发现p 和q， 这些素数必须从足够大的集合中选取。 目前还没有产生任意大素数的有用技术， 通常随机选取一个所需数量级的奇数并检验这个数是否为素数。

(2) e 和d 的选取。

先选择e， 使gcd(φ(n)，e) =1， 然后计算d =e -1mod φ(n)。 Euclid 推广算法可以计算两个整数的最大公约数， 并且在gcd 为1 的情况下， 计算一个整数模另一个整数的逆元。

5. RSA 算法可能遭受的攻击

对RSA 算法的具体实现存在一些攻击方法， 但不是针对基本算法的， 而是针对协议的。

1) RSA 算法的选择密文攻击

E (攻击者) 监听A 的通信， 收集由A 的公开密钥e 加密的密文c， E 想知道消息的明文m， 使m=cd mod n。 E 首先选择随机数r， 使r ＜n。 然后用A 的公开密钥e 进行以下计算:

现在E 让A 对y 签名， 即解密y， A 向E 发送u=yd mod n。

由x=re mod n， 得出r=xd mod n。

E 计算tu mod n= (r -1yd) mod n=r -1xdcd mod n=cd mod n=m。

2) 对RSA 算法的攻击——共模攻击

在实现RSA 算法时， 为方便起见， 可能给每位用户相同的模数n， 虽然加解密密钥不同， 然而这样做是不行的。

设两个用户的公开钥分别为e1 和e2， 且e1 和e2 互素(一般情况都成立)， 明文消息是m， 密文分别是c1≡me1(mod n)、 c2≡me2(mod n)。

攻击者截获c1和c2后， 可采用以下方法来恢复m: 首先， 用Euclid 推广算法求出满足re1 +se2 =1 的两个整数r 和s， 其中一个为负， 设为r； 然后， 用Euclid 推广算法求出c -1

1 ，由此得