在对称密码中，由于加密和解密的密钥是相同的，因此必须向接收者配送密钥。用于解密的密钥必须被配送给接收者，这一问题称为密钥配送问题，如果使用公钥密码，则无需向接收者配送用于解密的密钥，这样就解决了密钥配送问题。可以说公钥密码是密码学历史上最伟大的发明。

密钥配送问题

解决密钥配送问题的方法

• 通过事先共享密钥来解决
• 通过密钥分配中心来解决
• 通过Diffic-Hellman密钥交换来解决
• 通过公钥密码来解决

通过事先共享密钥来解决

在人数很多的情况下，通信所需要的密钥数量会增大，例如：1000名员工中每一个人都可以和另外999个进行通信，则每个人需要999个通信密钥，整个密钥数量：
1000 x 999 ÷ 2 = 499500
很不现实，因此此方法有一定的局限性

通过密钥分配中心来解决

• 密钥分配中心虽然能解决上述密钥数量过多的限制，但是随着员工数量的增多，密钥分配中心的负荷也会随之增加，如果密钥分配中心计算机发生故障，全公司加密通信就会瘫痪，
• 此外主动攻击者也可能针对密钥分配中心下手
  这是密钥分配中心所面临的问题。

通过Diffic-Hellman密钥交换来解决

在Diffic-Hellman密钥交换中，进行加密通信的双方需要交换一些信息，而这些信息即便被窃听者窃听到也没有问题（后续文章会进行详解）。

通过公钥密码来解决

在对称密码中，加密密钥和解密密钥是相同的，但公钥密码中，加密密钥和解密密钥却是不同的。只要拥有加密密钥，任何人都可以加密，但没有解密密钥是无法解密的。

公钥密码

公钥密码中，密钥分为加密密钥（公钥）和解密密钥（私钥）两种。

• 发送者只需要加密密钥
• 接收者知悉要解密密钥
• 解密密钥不可以被窃听者获取
• 加密密钥被窃听者获取也没有问题

公钥和私钥是一一对应的，一对公钥和私钥统称为密钥对，由公钥进行加密的密文，必须使用与该公钥配对的私钥才能够解密。密钥对中的两个密钥之间具有非常密切的关系——数学上的关系——因此公钥和私钥是不能分别单独生成的。

公钥通信的流程

发送者：Alice      接收者：Bob      窃听者：Eve
通信过程是由接收者Bob来启动的

1. • Bob生成密钥对，私钥自己来妥善保管
2. • Bob将自己的公钥发送给Alice。
   • Bob的公钥被Eve截获也没有关系。
   • 公钥发送给Alice，表示Bob请Alice用这个公钥对消息进行加密并发送给他。
3. • Alice用Bob的公钥对消息进行加密。
   • 加密后的消息只有用Bob的私钥才能够解密
   • 虽然Alice拥有Bob的公钥，但是Bob的公钥是无法对密文进行解密的
4. • Alice将密文发给Bob
   • 密文被Eve截获也没关系，Eve可能拥有Bob的公钥，但是无法进行解密

5. • Bob用自己的私钥对密文进行解密

     
     
     image.png

公钥密码无法解决的问题

公钥密码解决了密钥配送的问题，但依然面临着下面的问题

• 判断所得到的公钥是否正确合法，被称为公钥认证问题（后面会通过中间人攻击来探讨这个问题）
• 公钥密码的处理速度只有对称密码的几百分之一。

RSA

什么是RSA

RSA是目前使用最广泛的公钥密码算法，名字是由它的三位开发者，即Ron Rivest、Adi Shamir和Leonard Adleman的姓氏的首字母组成的（Rivest-Shamir-Adleman）。RSA可以被使用公钥密码和数字签名（此文只针对公钥密码进行探讨，数字签名后续文章敬请期待）1983年在美国取得了专利，但现在该专利已经过期。

RSA加密

在RSA中，明文、密钥和密文都是数字，RSA加密过程可以用下列公式来表达

密文 = 明文^E mod N

注意 mod运算讲解在这里

简单的来说，RSA的密文是对代表明文的数字的 E 次方求mod N 的结果，换句话说：将明文和自己做 E 次乘法，然后将结果除以 N 求余数，这个余数就是密文。

从上面公式中可以看出，只要知道 E 和 N 这两个数，任何人都可以完成加密的运算。所以说 E 和 N 是RSA加密的密钥，即 E 和 N 的组合就是公钥 ，一般写成 “公钥是(E,N) ” 或者 “公钥是{E,N}”

RSA解密

RSA解密过程可以用下列公式来表达

明文 = 密文^D mod N
对表示密文的数字的 D 次方求mod N 就可以得到明文，换句话说：将密文和自己做 D 次乘法，在对其结果除以 N 求余数，就可以得到明文
此时使用的数字 N 和加密时使用的数字 N 是相同的，数 D 和数 N 组合起来就是RSA的解密密钥，因此 D 和 N 的组合就是私钥。只要知道 D 和 N 两个数的人才能够完成解密的运算

由于 N 是公钥的一部分，使公开的，因此单独将 D 成为私钥也是可以的

RSA的加密和解密

RSA的加密和解密

生成密钥对

根据加密和解密的公式可以看出，需要用到三个数—— E、D 和 N 求这三个数就是生成密钥对，RSA密钥对的生成步骤如下：

• 求 N
• 求 L (L 是仅在生成密钥对的过程中使用的数)
• 求 E
• 求 D

1、求 N

准备两个很大的质数 p 和 q ，将这两个数相乘，结果就是 N
N = p x q

2、求 L

L 是 p-1 和 q-1 的最小公倍数，如果用lcm( X , Y )来表示 “X 和 Y 的最小公倍数” 则L可以写成下列形式
L = lcm ( p - 1，q - 1)

3、求 E

E 是一个比1大、比 L 小的数。 E 和 L的最大公约数必须为1，如果用gcd(X , Y)来表示 X 和 Y 的最大公约数，则 E 和 L之间存在下列关系：
1 < E < L
gcd(E , L) = 1 （是为了保证一定存在解密时需要使用的数 D ）

4、求 D

1 < D < L
E x D mod L = 1

RSA中密钥对的生成

RSA密钥对

来个具体的例子

密钥对生成

1、求 N

p = 17
q = 19
N = p x q = 17 x 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，19，23，25，29，31...
这里选择5来作为E,到这里我们已经知道E = 5    N = 323 这就是公钥

4、求 D

E x D mod L = 1
D = 29 可以满足上面的条件，因此：
公钥：E = 5     N = 323
私钥：D = 29    N = 323

5、加密

要加密的明文必须是小于 N 的数，这是因为在加密运算中需要求 mod N 假设加密的明文是123
明文^E mod N = 123⁵ mod 323 = 225（密文）

6、解密

对密文225进行解密
密文^D mod N = 225²⁹ mod 323 = 225¹⁰ x 225¹⁰ x 225⁹ mod 323 = (225¹⁰ mod 323) x (225¹⁰ mod 323) x (225⁹ mod 323) = 16 x 16 x 191 mod 323 = 48896 mod 323 = 123（明文）

对RSA的攻击

1、通过密文来求得明文

如果没有mod N 的话，即：

明文 = 密文^D mod N

通过密文求明文的难度不大，因为这可以看作是一个求对数的问题。
但是，加上mod N 之后，求明文就变成了求离散对数的问题，这是非常困难的，因为人类还没有发现求离散对数的高效算法。

2、通过暴力破解来找出 D

只要知道 D，就能够对密文进行解密，逐一尝试 D 来暴力破译RSA，暴力破解的难度会随着D的长度增加而加大，当 D 足够长时，就不能再现实的时间内通过暴力破解找出数 D

目前，RSA中所使用的 p 和 q 的长度都是1024比特以上，N 的长度为2048比特以上，由于 E 和 D 的长度可以和N差不多，因此要找出 D ，就需要进行2048比特以上的暴力破解。这样的长度下暴力破解找出 D 是极其困难的

3、通过 E 和 N 求出 D

E x D mod L = 1           L = lcm ( p - 1，q - 1)
由 E 计算 D 需要使用 p 和 q ，但是密码破译者并不知道 p 和 q

对于RSA来说，有一点非常重要，那就是质数 p 和 q 不能被密码破译这知道。把 p 和 q 交给密码破译者与把私钥交给密码破译者是等价的。

p 和 q 不能被密码破译者知道，但是 N = p x q 而且 N 是公开的， p 和 q 都是质数，因此由 N 求 p 和 q 只能通过将 N 进行质因数分解，所以说：
一旦发现了对大整数进行质因数分解的高效算法，RSA就能够被破译

4、中间人攻击

这种方法虽然不能破译RSA，但却是一种针对机密性的有效攻击。

所谓中间人攻击，就是主动攻击者Mallory混入发送者和接收者的中间，对发送者伪装成接收者，对接收者伪装成发送者的攻击，在这里，Mallory就是“中间人”

中间人攻击

注意：在这个过程中，Alice所持有的公钥并非是Bob的，而是Mallory的，所以发送的内容被Mallory拦截以后，Mallory可以通过自己的私钥解密，而Mallory还持有Bob的公钥，所以可以篡改信息，然后发送给Bob。

这种攻击不仅针对RSA，而是可以针对任何公钥密码。在这个过程中，公钥密码并没有被破译，所有的密码算法也都正常工作并确保了机密性。然而，所谓的机密性并非在Alice和Bob之间，而是在Alice和Mallory之间，以及Mallory和Bob之间成立的。仅靠公钥密码本身，是无法防御中间人攻击的。

要防御中间人攻击，还需要一种手段来确认所收到的公钥是否真的属于Bob，这种手段称为认证。在这种情况下，我们可以使用公钥的证书(后面会陆续更新文章来进行探讨)

5、选择密文攻击

网络上很多服务器在收到格式不正确的数据时都会向通信对象返回错误消息，并提示“这里的数据有问题”，然而，这种看似很贴心的设计却会让攻击者有机可乘。攻击者可以向服务器反复发送自己生成的伪造密文，然后分析返回的错误消息和响应时间获得一些关于密钥和明文的信息。

为了抵御这种攻击，可以对密文进行“认证”，RSA-OAEP(最优非对称加密填充)正是基于这种思路设计的一种RSA改良算法。

RSA-OAEP在加密时会在明文前面填充一些认证信息，包括明文的散列值以及一定数量的0，然后用RSA进行加密，在解密的过程中，如果解密后的数据的开头没有找到正确的认证信息，则可以判定有问题，并返回固定的错误消息（重点是，不能将具体的错误内容告知开发者）
RSA-OAEP在实际应用中，还会通过随机数使得每次生成的密文呈现不同的排列方式，从而进一步提高安全性。

随着计算机技术的进步等，以前被认为是安全的密码会被破译，这一现象称为密码劣化，针对这一点：

• 1024比特的RSA不应被用于新的用途
• 2048比特的RSA可在2030年之前被用于新的用途
• 4096比特的RSA在2031年之后仍可被用于新的用途