【密码学】RSA公钥加密算法

RSA定义

• RSA是一种公钥密码算法
• 他的名字由他的三位开发者的形式首字母组成

RSA加密与解密

加密

• 密文 = 明文^EmodN

• 在RSA只能够，明文、密钥和密文都是数字，具体加密过程可由上式来表达，RSA的密文就是对代表明文的数字的E次方求modN的结果

• E和N的组合就是密钥，一般可写成“密钥是（E, N）”

解密

• 明文 = 密文^DmodN
• 对表示密文 数字的D次方求modN就可以得到明文
• D和N的组合就是私钥，一般可写成“私钥是（D, N）”，这里所使用的数字N和加密时使用的数字N是相同的

生成密钥对

• 公钥是（E, N），私钥是（D, N），因此求E, D, N这三个数的过程就是生成密钥对的过程，即为RSA密钥对的生成过程

1. 求N
   • 首先准备两个很大的质数p, q
   • 若p和q过小的话，密码会变得容易破译；但若p和q过大的话计算时间又会变得很长
   • N为两质数的乘积
   • N = p*q
2. 求L
   • L是(p-1)和(q-1)的最小公倍数(least common multiple)，用lcm(X, Y)来表示“X和Y的最小公倍数”
   • L = lcm(p-1, q-1)
3. 求E
   • E是一个比1大、比L小的数
   • E和L的最大公约数(greatest common divisor)必须是1，用gcd(X, Y)来表示X和Y的最大公约数
   • 1 < E < L, gcd(E, L) = 1
   • 要找到满足要求的数，要使用伪随机数生成器，通过伪随机数生成器在1 < E < L的范围内生成E的候选数，然后再判断其是否满足gcd(E, L) = 1这个条件
4. 求D
   • 1 < D < L, E * D mod L = 1
   • 只要数D满足上述条件，则通过E和N进行加密的密文，就可以通过D和N进行解密

一个例子

密钥对生成

1. 求N
   • p = 17, q = 19
   • N = p * q = 17 * 19 = 323
2. 求L
   • L = lcm(p-1, q-1) = lcm(16, 18) = 144
3. 求E
   • gcd(E, L) = 1
   • E = 5、7、11、13、17…
   • 选取E = 5，N = 323
4. 求D
   • E * D mod L = 1
   • 将D = 29代入上式即满足
   • E * D mod L = 5 * 29 mod 144 = 145 mo 144 = 1

• 得公钥(E, N) = (5, 323)，私钥(D, N) = (29, 323)
• 公钥是可以任意公开的，但私钥必须妥善保管

加密

• 要加密的明文必须是小于N的数，即此处必须是小于323的数，因为在加密过程中有mod N操作
• 假设需要加密的数是123，公钥(E, N) = (5, 323)
• 密文 = 明文^Emod N = 123⁵mod 323 = 225

解密

• 收到密文是225，私钥(D, N) = (29, 323)
• 明文 = 密文^Dmod N = 225²⁹mod 323 = 123

对RSA的攻击

• 密码破译者知道的信息
  • 密文：可以通过窃听来获取
  • 公钥(E, N)：公钥是公开信息
• 密码破译者不知道的信息
  • 明文：需要破译的内容
  • 私钥中的D：私钥中的D是不知道的
  • 其他：密码破译者不知道生成密钥对时所使用的p、q、L

通过密文来求得明文

• 若在加密过程中，没有mod N的操作，通过密文求解明文的难度并不大，因为可以看作是一个求对数的问题
• 但是，加上mod N后，求明文就变成了求离散对数的问题，这种操作非常困难，目前还没有发现求解离散对数的高效算法

通过暴力破解来找出D

• 只要能知道D，就能对密文进行解密。因此可以逐一尝试有可能作为D的数字来破译RSA，即暴力破解法
• 暴力破解法的难度会随着D的长度增大而增大，当D足够长时，就不可能在现实的时间内通过暴力破解找出D
• 现在RSA所使用的p和q的长度都是1024比特以上的，N的长度为2048比特以上的，由于E和D的长度可以和N差不多，因此要找出D，就需要进行2048比特以上的暴力破解

通过E和N求出D

对N进行质因数分解

• p和q是不能被密码破译者知道的，因为N = p * q，而且N是公开的，p和q都是质数，因此由N求p和q只能通过将N进行质因数分解来完成
• 一旦发现了对大整数进行质因数分解的高效算法，RSA就能够被破译
• 然而，现在还没有发现对大整数进行质因数分解的高效算法，而且也尚未证明质因数分解是否真的是非常困难的问题，甚至不知道是否存在一种分解质因数的简单方法

通过推测p和q进行攻击

• 由于p和q是通过伪随机数生成器产生的，如果伪随机数生成器的算法很差，密码破译者就有可能推测出来p和q，因此使用能够被推测出来的随机数是非常危险的

中间人攻击

• man-in-the-middle attack
• 这种方法虽不能破译RSA，但却是一种针对机密性的有效攻击
• 中间人攻击就是主动攻击者M混入发送者和接收者中间，对发送者伪装成接收者，对接收者伪装成发送者的攻击方式，此时M就是“中间人”

1. 消息发送者A向B发送邮件索取公钥
2. 攻击人M通过窃听发现A在向B索取公钥
3. B看到A的邮件，并将自己的公钥发送给A
4. M拦截B的邮件，使其无法发送给A，然后将B的公钥保存起来
5. M伪装成B，将M自己的公钥发送给A
6. A将自己的消息用B的公钥（此时其实是M的公钥）进行加密
7. A将加密后的消息发送给B
   • 但A所持有的并非B的公钥，而是M的公钥，因此A是用M的公钥对邮件进行加密
8. M拦截A的加密邮件
   • 这封加密邮件是用M的公钥进行加密的，因此M能够对其进行解密
9. M伪装成A写一封假的邮件，并用4中保存下来的B的公钥对邮件进行加密，再发送给B

• 上述过程可以反复多次，B向A发送加密邮件也可能受到同样的攻击
• 中间人攻击可以针对任何公钥密码，攻击过程中，公钥密码并没有被破译，所有的密码算法也都正常工作并确保了机密性，然而所谓的机密性并不存在在A与B之间，而成立在A与M之间与M与B之间
• 仅靠公钥密码本身，是无法防御中间人攻击的，这种情况，可以使用公钥的证书

一些思考

公钥密码比对称密码的机密性更高？

• 不一定
• 机密性的高低是根据密钥长度而变化的

对称密码会消失？

• 不会
• 虽然有了公钥密码，但对称密码也不会消失
• 一般来说，在采用具备同等机密性的密钥长度的情况下，公钥密码的处理速度只有对称密码的几百分之一，因此公钥密码并不适合用来对很长的消息内容进行加密
• 根据目的的不同，还可能会配合使用对称密码和公钥密码

RSA使用过程中，质数对会不会被用光？

• 不会
• 512比特能够容纳的质数数量约为10的150次方，假设世界上有100亿人，每人每秒生成100亿个密钥对，那么在经过100亿年后会生成：100亿人 * 100亿个 * （366 * 24 * 60 * 60）秒 * 100亿年 = 316224 * 10³² < 10³⁹ << 10¹⁵⁰

RSA加密过程中需要对大整数进行质因数分解？

• 不需要
• RSA加密和解密的过程都无需对大整数进行质因数分解操作
• 只有在需要有数N求p和q的密码破译过程中才需要对大整数进行质因数分解，RSA的设计是将质因数分解的难题留给密码破译者

N达到多少比特可以抵御质因数分解？

• 不能抵御
• N无论有多长，总有一天能被质因数分解，因此问题是能否在现实的时间内对N进行质因数分解