基础知识

RSA 非对称加密算法的原理

欧拉函数

欧拉函数用来计算对于给定的正整数 $n$ ，在小于等于 $n$ 的元素之中有多少个元素与其互质。其解析式如下：
$\phi(p^k) = p^k - p^{k - 1}$
如果 $n$ 为质数，则 $\phi(n) = n - 1$ ；
如果 $n$ 可以分解为两个互质的整数 $p$ 和 $q$ 之积，则 $\phi(n) = \phi(p)\phi(q)$ 。

欧拉定理

如果两个正整数 $a$ 和 $n$ 互质，则 $n$ 的欧拉函数可以让如下等式成立：
$a^{\phi(n)} \equiv 1(mod\ n)$

模反元素

如果 $a$ 和 $n$ 互质，则一定存在元素 $b$ ，使得如下等式成立：
$\equiv 1(mod\ n)$
称 $b$ 为 $a$ 的模反元素。

RSA密钥生成过程

选取两个不相等的质数 $p$ 和 $q$ ；
计算 $n = p q$ 的欧拉函数 $\phi(n) = \phi(pq)=\phi(p)\phi(q) = (p - 1)(q-1)$
随机选择一个整数 $e$ ，并计算其对于 $\phi(n)$ 的模反元素 $d$ ，则 $(n, e)$ 作为公钥， $(n, d)$ 作为私钥，其他数字 $p,q,n,\phi(n)$ 不公开。
如果一个攻击者在得知公钥的情况下获取私钥，需要根据 $n, e$ 计算出 $d$ 。
因为 $d$ 是 $e$ 关于 $\phi(n)$ 的模反元素，因而计算 $d$ 需要知道 $\phi(n)$ ，而计算 $\phi(n)$ 则需要找到两个质数 $p$ 和 $q$ ，因为 $\phi(n) = (p-1)(q-1)$ 。而对于大整数的因数分解过程是非常耗时的，只有暴力一种解法。因而RSA算法被认为是安全的。

DH密钥交换算法的原理

DH秘钥交换算法涉及到离散对数的知识。选取两个大数 $p$ 和 $g$ 并公开，其中 $p$ 是一个质数， $g$ 是 $p$ 的模 $p$ 本原单位根，则DH密钥交换算法的流程为：

Alice随机选择一个整数 $a$ ，计算 $Ka=a^g\ mod\ p$ 并将其发送给Bob；
Bob随机算则一个证书 $b$ ，计算 $Kb=b^g\ mod\ p$ 并将其发送给Alice；
Allice和Bob开始通过已知的信息计算密钥。Alice计算密钥 $key=a\times Kb\ mod\ p=a\times b^g\ mod p = (ab)^g\ mod\ p$ ，Bob计算密钥 $key=b\times Ka\ mod\ p= b\times a^g\ mod\ p = (ba) ^ g\ mod\ p = (ab) ^g\ mod\ p$ ，所以Alice和Bob计算出的密钥相同。

基于以下原因：

已知 $a$ ，计算 $b = a^g\ mod\ p$ 容易，但是在已知 $b, g, p$ 的情况下计算a很难（很难的意思是计算出结果需要很长很长时间）。函数 $f(x)=x^g\ mod\ p$ 在密码学中被称为陷门函数，因为已知 $x$ 算 $f (x)$ 简单，但是已知 $f (x)$ 算 $x$ 很难。

假设有一个中间人Eve通过窃听得到了 $p, g, K a, K b$ ，要想求得Alice和Bob协商得到的密钥 $k e y$ ，其必须求得 $a$ 或 $b$ 才能算出密钥，因而 $k e y$ 被认为是安全的，除了Alice和Bob外没人能知道。

RSA握手过程

客户端服务端 client hello {支持的TLS版本、加密和压缩算法、随机数C} server hello {支持的TLS版本、选择的加密和压缩算法、随机数S} 服务端证书其他 server hello done 验证证书 pre_master随机数，使用server的公钥加密 change Cipher spec：使用协商的加密算法和秘钥加密信息握手结束通知，使用协商的密钥和加密算法发送之前发送所有信息的哈希值。使用pre_master、C和S生成密钥，解密哈希值验证消息。 change cipher spec：使用协商的加密算法和秘钥加密信息。握手结束通知，发送加密的所有之前发送信息的哈希值客户端服务端

DH握手过程

客户端服务端 client hello {支持的TLS版本、加密和压缩算法、随机数C} 使用私钥加密DH参数、客户端和服务端生成的随机数生成数字签名 server hello {支持的TLS版本、选择的加密和压缩算法、随机数S、数字签名} 验证数字签名确认数字签名 { 客户端DH参数 } 计算会话密钥计算会话密钥 change Cipher spec：通知后续使用协商的加密算法和秘钥加密信息握手结束通知，使用协商的密钥和加密算法发送之前发送所有信息的哈希值。 change cipher spec：通知后续使用协商的加密算法和秘钥加密信息。握手结束通知，发送加密的所有之前发送信息的哈希值客户端服务端

素性检验：如何生成一个大质数

**方法1：**筛法。判断整数 $n$ 是否为素数的方法是 $n\ mod\ i = 0, i \in [2, \sqrt{n})$ ，即从2开始遍历直到 $\sqrt{n}$ ，如果没有整数能被 $n$ 整除则认为 $n$ 是素数。
**方法2：**利用费马小定理。费马小定理的内容为：

假设 $a$ 是整数， $n$ 是一个质数，则有如下条件成立：
$a^{n-1} \equiv 1(mod\ n)$

费马小定理是判断一个数是否为质数的充分条件，即存在合数满足费马小定理，这些合数被称为迈克尔数。最小的迈克尔数为561。
利用费马小定理检验素数的方法被称为费马素性检验。费马素性检验是指通过多选择几个整数，如果满足费马小定理则 $n$ 是素数的可能性会很大。费马素性检验是概率性算法。
米勒—拉宾算法和AKS算法利用费马小定理进行素性检验。其中米勒—拉宾算法是概率性算法，在实际生活中应用较多，而AKS算法是确定性算法。两者都是多项式时间复杂度。