公钥密码

密钥配送问题：在对称密码中，由于加密和解密的密钥是相同的，因此必须事先向接收者配送密钥。

如果使用公钥密码，则无需向接收者配送用于解密的密钥，这就相当于解决了密钥配送问题。

对称密码通过将明文转换为复杂的形式来保证机密性，公钥密码则是基于数学难题来保证机密性。 例如RSA利用了大整数的质因数分解问题的困难度。

即使已经有了公钥密码，对称密码也不会消失。

公钥密码的运行速度远远低于对称密码，因此一般通信过程中，往往会配合使用这两种密码，即用对称密码提高处理速度，用公钥密码解决密钥配送问题。这样的方式称为混合密码系统。

密钥配送问题

密钥配送问题指的是如何安全地将密钥发送给接收者，用以解密密文。

解决密钥配送问题的方法有以下几种：

事先共享密钥

事先用安全的方式将密钥交给对方，称为密钥的事先共享。（比如当面共享，邮寄等）

密钥分配中心

当需要进行加密通信时，密钥分配中心会生成一个通信密钥，每个人只需要和密钥分配中心事先共享密钥。

通信流程：

1. 密钥分配中心将通信密钥使用通信双方各自的密钥进行加密，并分别发送给通信双方。
2. 通信双方各自使用自己的密钥解密获得通信密钥。
3. 通信双方使用通信密钥进行通信。

缺点：

• 通信方数量很大时，密钥分配中心负荷会剧增。
• 密钥分配中心出现故障，则所有通信中断。

Diffie-Hellman密钥交换

在Diffie-Hellman密钥交换中，进行加密通信的双方需要交换一些信息，而这些信息即便被窃听到也没有问题。

根据所交换的信息，双方可以各自生成相同的密钥，而窃听者却无法生成相同的密钥。

公钥密码

在公钥密码中，加密密钥和解密密钥是不同的。

只要拥有加密密钥，任何人都可以进行加密，但没有解密密钥是无法解密的。因此，公钥密码的一个重要性质是只有拥有解密密钥的人才能够进行解密。

通信流程如下：

1. 接收者事先将加密密钥发送给发送者，该加密密钥即使被窃听也没有关系。
2. 发送者使用加密密钥对通信内容进行进行加密并发送给接收者。
3. 接收者使用解密密钥进行解密。

因此对称密码的密钥配送问题可以使用公钥密码来解决。

公钥密码

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

发送者使用加密密钥对消息进行加密，接收者用解密密钥对密文进行解密。

特点

• 发送者只需要加密密钥。
• 接收者只需要解密密钥。
• 解密密钥不可以被窃取。
• 加密密钥被窃取也没关系。

公钥密码中，加密密钥一般是公开的，因此该密钥被称为公钥。解密密钥是绝对不能公开的，这个密钥只能接收者来使用，称为私钥。

公钥和私钥是一一对应的，一对公钥和私钥统称为密钥对（key pair）。公钥加密的密文，只有配对的私钥才能够解密。

公钥密码的使用者需要生成一个包括公钥和私钥的密钥对，其中公钥发送给别人，私钥仅供自己使用。

历史

通信流程

在公钥密码通信中，通信过程是由接收者来启动的。

问题

数学基础

mod运算

除法求余数的运算即mod，和乘除同级。

模逆元：对于正整数$a$ 和 $m$ ，如果有 $a * x = 1 (\mod m)$，那么把这个同余方程中的 $x$ 的最小整数解称为 $a$ 模 $m$ 的逆元。

RSA

RSA是一种公钥加密算法，它的名字取自其三位开发者，即Ron Rivest、Adi Shamir和Leonard Adleman的姓氏的首字母。

RSA可以被用于公钥密码和数字签名。

RSA加密

在RSA中，明文、密钥和密文都是数字。

加密公式如下：

$$ 密文 = 明文^{E}\mod N$$ 即RSA的密文是对代表明文的数字的 $E$ 次方求 $\mod N$ 的结果，或者是将明文和自己做 $E$ 次乘法，然后用其结果对 $N$ 取余，这个余数就是密文。

因此加密公式中出现的两个数 $E$ 和 $N$ 的组合就是公钥。

RSA解密

解密公式如下：

$$ 明文 = 密文 ^{D} \mod N $$ 即对表示密文的数字的 $D$ 次方求 $\mod N$ 就可以得到明文。

这里所使用的数字 $N$ 和加密时使用的是相同的。 数 $D$ 和数 $N$ 组合起来就是RSA的解密密钥。只有知道 $D$ 和 $N$ 两个数的人才能够完成解密的运算。

生成密钥对

由于 $E$ 和 $N$ 是公钥， $D$ 和 $N$ 是私钥，因此求 $E$、$D$ 、$N$ 这三个数就是生成密钥对。

第一步：求N

1. 准备两个很大的质数为 $p$ 和 $q$。
2. 将两个很大的质数相乘，其结果就是 $N$，即$$N=p * q$$ 。

特点：$p$ 和 $q$ 太小的话，密码容易被破译，太大的话计算时间会变得很长。

判断一个数是否为质数，可以通过费马测试和米勒拉宾测试。

第二步：求L（中间过程使用）

$L$ 是 $p-1$ 和 $q-1$ 的最小公倍数（least common multiple，lcm），即$$L=lcm(p-1,q-1) \tag{L是p-1和q-1的最小公倍数}$$

第三步：求E

$E$ 是一个比 $1$大、比 $L$ 小的数。

$E$ 和 $L$ 的最大公约数（greatest common divisor，gcd）必须为1，即

$$ \begin{align} 1 < E < L \\ gcd(E,L)=1 \tag {E和L互质} \end{align} $$

第四步：求D

数 $D$ 是由数 $E$ 计算得到的。$D$、$E$、$L$ 之间必须具备如下关系：

$$ \begin{align} 1<D<L \tag{1} \\ E * D \mod L=1 \tag{2} \end{align} $$

只要数 $D$ 满足上述条件，则通过 $E$ 和 $N$ 进行加密的密文，就可以通过 $D$ 和 $N$ 进行解密。

要保证存在满足条件的 $D$， 就需要保证 $E$ 和 $L$ 互质。

实践

求N

取$p=17$ 和 $q=19$ ，求 $N=pq=1719=323$

求L

$L=lcm(p-1,q-1)=lcm(16,18)=144$

求E

满足条件： $gcd(E,L)=1$

例如 $5,7,11,13,17,19,23,25,29,31,…$

因此，取$E=5, N=232$ 为公钥。

求D

$D$ 满足条件 $E*D \mod L =1$。

取 $D=29$ 满足 $$ \begin {align} E*D \mod L &= 5 * 29 \mod 144 \\ &= 145 \mod 144 \\ &= 1 \end {align} $$

此时已经生成了密钥对， 即公钥 $E=5,N=323$ 私钥 $D=29,N=323$ 。

加密

要加密的明文必须是小于$N$的数，因为在解密过程中需要求$\mod N$，其结果一定小于$N$。

假设加密的明文是$123$，加密时使用的是公钥$E=5,N=323$，则有

$$ \begin{align} 明文^{E} \mod N &= 123^{5} \mod 323 \\ &= 225 \end{align} $$

解密

对密文$225$进行解密， 解密密钥是$D=29, N=323$，有

$$ \begin{align} 密文^{D} \mod N &= 225^{29} \mod 323 \\ &= (225^{10} * 225^{10} * 225^{9}) \mod 323 \\ &= ((225^{10} \mod 323) * (225^{10} \mod 323) * (225^{9} \mod 323)) \mod 323 \\ &= (16 * 16 * 191) \mod 323 \\ &= 48896 \mod 323 \\ &= 123\\ 225^{10} &= 332525673007965087890625 \\ 225^{9} &= 1477891880035400390625 \end{align} $$

RSA的攻击方式

密码破译者知道的信息：密文、数 $E$ 和 $N$。

通过密文来求明文

$密文=明文^{E} \mod N$ 的求解，等同于求离散对数的问题。

暴力破解

现在RSA中所使用的 $p$ 和 $q$ 都是2048位以上，除非量子计算机出现。

对 $N$ 进行质因数分解攻击

一旦发现了对大整数进行质因数分解的高效算法，RSA就能够在算法层面被破译。

其他公钥密码

Q&A

RSA使用的人原来越多，质数会不会被用光？

512比特能够容纳的质数大约有10的150次方，2048比特则更多。

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

不需要，RSA只有在需要由 $N$ 求 $p$ 和 $q$ 的密码破译过程中才需要对大整数进行质因数分解。