常见加密算法：

对称加密算法、非对称加密算法、Hash算法

对称加密：

对称加密分为流加密和分组加密，其特点是加密、解密使用同一种密钥。

• 优点：算法公开、计算量小、加密速度快、加密效率高。
• 缺点：数据传送前，发送方和接收方需要同步保存秘钥，而同步过程发生在共有环境,一旦其中一方密钥泄露，那么加密信息就不安全了。如果窃听者在秘钥同步的过程中，在共有环境劫持到秘钥，就可以通过大量数据穷举出加密法则从而破解密文得到明文。
• 使用场景：本地数据加密解密、https通信、网络传输等。
• 常见算法：AES、DES、3DES、DESX、Blowfish、IDEA、RC4、RC5、RC6。其中IDEA（国际数据加密算法）相比于DES（数据加密标准），加密性更好，而且对计算机性能要求也没那么高。

非对称加密：

非对称加密，即加密、解密使用不同的规则，这两种规则之间存在某种对应关系，从而避免直接传递密钥。

• 优点：相比于对称加密，安全性更好。只需要同步公钥，不需要同步私钥。
• 缺点：加密和解密花费时间长、速度慢，只适合对少量数据进行加密。
• 使用场景：https会话前期、CA数字证书、信息加密、登录认证等。
• 常见算法：RSA、ECC（移动设备用）、Diffie-Hellman、El Gamal、DSA（数字签名用）

Hash算法：

Hash算法是一种单向算法，用户可以通过Hash算法对目标信息生成一段特定长度的唯一的Hash值，却不能通过这个值重新获得目标信息。

• 优点：不可逆、易计算、特征化。
• 缺点：可能存在散列冲突。
• 使用场景：文件或字符串一致性校验、数字签名、鉴权协议
• 常见算法：MD2、MD4、MD5、HAVAL、SHA、SHA-1、HMAC、HMAC-MD5、HMAC-SHA1

RSA算法推导

RSA算法基于一个非常简单的数论事实：

如果将两个大素数相乘，则乘积计算十分容易；但是如果对这个乘积进行质因式分解，却非常困难。

数论基础

1. 质数又称素数，指在一个大于1的自然数中，除了1和本身之外，无法被其他自然数整除的数。
2. 寻找质数的方法-短除法、筛选法
3. 互质关系：如果两个正整数，除了1以外没有其他公因子，我们就称这两个数是互质关系（coprime）。其中：
   • 任意两个质数一定互质
   • 一个数是质数，另一个不是它的倍数，则二者互质
   • 较大的数是质数，则二者互质
   • 相邻两个自然数一定互质
   • 相邻两个奇数一定互质
   • 1和任意数互质
4. 任意一个大于1的正整数，都可以写成一系列质数的积。 $n=p_1^{k_1}p_2^{k_2}...p_r^{k_r}$
5. 欧拉函数的通用计算公式:$\phi(n) = n(1-{1\over p_1})(1-{1\over p_2})...(1-{1\over p_r})$
   $\phi(n)$表示1~n之中与n构成互质关系的正整数的个数
6. 欧拉定理：如果两个正整数a和n互质，则$a^{\phi(n)}-1$ 能整除 n，即 $a^{\phi(n)}-1 = n \times b$ (b为正整数)
7. 模反元素：如果两个正整数a和n互质，那么一定可以找到正整数x，使得ax-1能整除n，此时x就叫做a的模反元素。 $a^{\phi(n)} = a * a^{\phi(n)-1}$ $a^{\phi(n)}-1 = n \times b$ (b为正整数) $a * a^{\phi(n)-1} - 1 = n\times b$

   即$a * a^{\phi(n)-1} - 1$能整除n，则x为$a^{\phi(n)-1}$
   得到结论：如果两个正整数a和n互质，那么a必有一个模反元素是$a^{\phi(n)-1}$

8. 如果x是a对于n的某一个模反元素，那么$x+kn$（k是整数）都是a的模反元素
9. 大整数快速幂算法以及大整数快速幂取模算法

RSA密钥生成过程

1. 随机选择两个不相等的质数p和q。实际应用中，这两个质数越大越难破解。
2. 计算p和q的乘积。 $n = p \times q$
   n的长度就是密钥的长度，将n写成二进制有多少位，即密钥就有多少位。实际应用中RSA密钥一般是1024位，重要场合则是2048位。
3. 计算n的欧拉函数$\phi(n)$
   根据$n = p_1^{k_1}p_2^{k_2}…p_r^{k_r} = p \times q$
   得到$\phi(n) = n(1-{1\over p_1})(1-{1\over p_2})…(1-{1\over p_r}) = n(1-{1\over p})(1-{1\over q}) = (p-1)(q-1)$
   即$\phi(n) = (p-1) \times (q-1)$
4. 从1～$\phi(n)$之间随机选择一个正整数e，满足$1<e<\phi(n)$ 且 e与$\phi(n)$互质。实际应用中常常选择65537
5. 计算e对于$\phi(n)$的模反元素d
   即存在一个正整数k使得$ed - 1 = k\phi(n)$ 令d=x, k = -y
   即$ex + \phi(n)y = 1$
   e和$\phi(n)$的值我们已经是知道的了，通过扩展欧几里得算法可以得到上面二元一次函数的某组解，那么可以得到一个模反元素d的值
   再根据如果x是a对于n的某一个模反元素，那么$x+kn$（k是整数）都是a的模反元素，那么通过 $d = d + k\phi(n)$（k是整数）修正d的值，让其最好是正整数方便后续计算。
6. 至此我们已经得到了e和d的值，将n和e封装成公钥（n，e）发布，n和d封装成私钥（n，d）保存。在仅知道n和e的前提下，要想推导出d的值，必须要将n因数分解得到p和q的值才行，可是大整数的因数分解相当困难，所以RSA算法是很可靠的。

RSA加密解密过程

假设我们的原文是m，此时我们已知 n, e, d

m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n

1. 使用公钥(n,e)进行加密，即,使用下面的公式得到密文c: $c=m^e\%n$
2. 使用密钥(n,d)进行解密 $m=c^d\%n$

rsa公式论证

继续上面的例子，要验证rsa算法成立，那么就是验证解密公式$m=c^d\%n$成立： 根据加密公式：

推导出$c=m^e-kn$（k为正整数）
将c代入我们要证明的解密公式得到：

等价于$m=m^{ed}\%n$即$m^{ed}对n取余值为m$

为什么可以这么等价，我们将上面的式子简化为 $(x - kn)^d$对n取余，前面的多项式可以展开为$x^d+n(多项式)$，在对n取余的过程中，除了第一项，后面的都可以消掉。即，$(x - kn)^d$对n取余就是$x^d$对n取余。

再根据前面RSA密钥生成过程中的第5步得到：

将其带入上式可得：

只要验证$m^{k\phi\left(n\right)+1}$对n取余值为m，也就证明了RSA算法的成立。下面需要分两种情况来进行验证：

1. m与n互质 根据欧拉定理我们能得到：

那么：$\left(m^{\phi\left(n\right)}\right)^k=\left(1+nb\right)^k$ (b为正整数)

也就是说，$m^{k\phi\left(n\right)+1}$对n取余 等价于$m\left(1+nb\right)^k$ (b为正整数)对n取余，等价于m对n取余，而整个加密解密的前提条件是 $0<m<n$，所以m对n取余的值就是m，也即：

，证明原式成功！！

1. m与n不互质 那么m与n必然有除1以外的公因子，又因为n等于质数p和质数q的乘积，所以m必然等于hp或者hq
   假设m=kp，那么m与q一定互质，则根据欧拉函数跟欧拉定理我们能得到

然后可以推出：

即$m^{k\left(p-1\right)\left(q-1\right)}=\left(1+qb\right)^{k\left(p-1\right)}$ 又因为已知$\phi\left(n\right)=(p-1)(q-1)$ 所以$m^{k\varphi\left(n\right)}=\left(1+qb\right)^{k\left(p-1\right)}$ 通过前面的分析我们可以知道，此时$m^{k\varphi\left(n\right)}$对q取余就等于$\left(1+qb\right)^{k\left(p-1\right)}$对q取余，那么就等于1 即$m^{k\varphi\left(n\right)}=1+qt$(t为正整数) 那么$m^{k\varphi\left(n\right)}\times m=\left(1+qt\right)\times m$(t为正整数)

显然，此时$m^{k\varphi\left(n\right)+1}$对n取余的值即为$m+htn$对n取余，值为m，也即：

，证明原式成功！！ 综上所诉：
通过加密公式$c=m^e\%n$得到密文c，再通过解密公式$m=c^d\%n$重新得到原文m这一过程，是正确的，即RSA算法成立。

短除法

时间复杂度较高

对于任意奇数p，用小于p的平方根的质数去整除p，如果发现p可以被整除，p就不是质数

# 判断是不是质数
def isPrime(p, prims):
    sqrt = math.sqrt(p)
    for prime in prims:
        if prime <= sqrt and p % prime == 0:
            return False
        if prime > sqrt:
            return True


# 取1~n以内所有的质数合集
def shortDivision(n):
    if n < 2:
        return []
    prims = [2] # 质数集合
    for i in range(3, n, 2):
        if isPrime(i, prims) is True:
            prims.append(i)
    return prims

筛选法

空间换时间

将n个数字全部放进数组，并都置为肯定状态，依次遍历数组长度的平方根个数字，如果当前数字处于肯定的状态，则将其倍数的数字状态置为否定。

def screening(n):
    prims_pool = [False, False] + [True] * (n - 1)
    prims = []
    for i in range(2, int(math.sqrt(n)) + 1):
        if prims_pool[i] is True:
            for j in range(i + i, n + 1, i):
                prims_pool[j] = False
    for i in range(2, n):
        if prims_pool[i] is True:
            prims.append(i)
    return prims

大整数快速幂算法

如果我们要计算a的11次方，则按照幂运算的定义，需要执行11次乘法
如果将指数11写成二进制，则\(11=1011B=2^3+2^1+2^0\Rightarrow a^{11}=a^{2^0+2^1+2^3}=a^{2^0}\times a^{2^1}\times a^{2^3}\) 可以看到经过上述变化，计算a的11次方只需要执行3次乘法即可

def poww(a, b):
    res = 1
    while b > 0:
        if b & 1 == 1:
            res *= a
        a *= a
        b >>= 1
    return res

大整数快速幂取模算法

快速幂取模算法基于下面这个取模等价式子
\(\left(a\times b\right)mod\;c=\left(a\;mod\;c\right)\;\times\;\left(b\;mod\;c\right)\;mod\;c\)

def poww_mod(a, b, mod):
    res = 1
    while b != 0:
        if b & 1 == 1:
            res = res * a % mod
        a = a * a % mod
        b >>= 1
    return res

简单代码实现RSA

# -*- coding: UTF-8 -*-
import math
import time

# 筛选法-找到1~n内所有质数
def screening(n):
    prims_pool = [False, False] + [True] * (n - 1)
    prims = []
    for i in range(2, int(math.sqrt(n)) + 1):
        if prims_pool[i] is True:
            for j in range(i + i, n + 1, i):
                prims_pool[j] = False
    for i in range(2, n):
        if prims_pool[i] is True:
            prims.append(i)
    return prims

# 寻找n的所有质因数：每个合数都可以写成几个质数相乘的形式
def find_prims_factor(n):
    prims = screening(n)  # 先找出n以内所有的质数
    prims_factor = []
    for p in prims:
        r = 1
        while p**r <= n:
            if n % p**r == 0:
                prims_factor.append(p)
                break
            r += 1
    return prims_factor

def poww_mod(a, b, mod):
    res = 1
    while b > 0:
        if b & 1 == 1:
            res = res * a % mod
        a = a * a % mod
        b >>= 1
    return res

# 欧几里得算法
def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a

# 扩展欧几里得算法：求二元一次方程的通解：mx + ny = gcd(m, n)
def exgcd(m, n):
    if n == 0:
        x = 1
        y = 0
        return x, y
    x, y = exgcd(n, m%n)
    temp = x
    x = y
    y = temp - math.floor(m / n) * y
    return x, y

# 拓展欧几里得非递归算法：求二元一次方程的通解：ax + by = gcd(a, b)
def ex_gcd(a, b):
    if b == 0:
        return 1, 0
    x1, y = 1, 1
    x, y1 = 0, 0
    c, d = a, b
    q = int(c / d)
    r = c % d
    while r != 0:
        c = Decimal(d)
        d = r
        x1, x = x, x1 - x * q
        y1, y = y, y1 - y * q
        q = int(c / d)
        r = int(c) % d
    return x, y

# 修正模反元素d
def amendd(d, phi_n):
    if d < 0:
        return d + phi_n * math.ceil(-d/phi_n)
    return d

# 欧拉函数通式：求小于等于n的正整数中与n互质的个数：φ(n) = n(1-1/p1)(1-1/p2)…(1-1/pr)
def Euler_func(n):
    prims_factor = find_prims_factor(n=n)
    s = 1.0
    for factor in prims_factor:
        s *= (1 - 1 / factor)
    return int(n * s)

# 欧拉定理：若a,b为正整数，且a,b互质 => a**m mod b = 1，其中：m = Euler_func(b)
def Euler_theorem(a, b):
    return a**Euler_func(b) % b
    
# 模拟接收者
class Receiver:
    def __init__(self):
        self.createKey()
    
    def createKey(self):
        # 随机选取两个不相等的质数p和q。一般1024位
        p, q = 9973, 9941
        # 计算乘积
        n = p * q
        # 计算n的欧拉函数
        phi_n = (p - 1) * (q - 1)
        # 随机选择一个整数e：1 < e < phi_n and e和phi_n互质
        e = 65537
        # 计算e对于phi_n的模反元素d
        x, y = exgcd(phi_n, e)
        # 修正为正整数
        d = amendd(y, phi_n)
        # 得到公钥和私钥
        self.pub_key, self.pri_key = (n, e), (n, d)

    def get_pub_key(self):
        return self.pub_key

    # 对密文c进行解密，得到明文m
    def decode_c(self, c):
        n, d = self.pri_key
        m = poww_mod(c, d, n) # m = c^d % n
        return m

# 模拟发送者
class Sender:
    def __init__(self, pub_key):
        self.pub_key = pub_key

    # 用receiver同步过来的公钥对明文m进行加密，得到密文c
    def encode_m(self, m):
        n, e = self.pub_key
        if m >= n:
            return None
        c = poww_mod(m, e, n)  # c = m^e % n
        return c

# 模拟窃听者
class Hacker:
    def __init__(self):
        pass
    def crack(self, pub_key, c):
        n, e = pub_key
        p, q = find_prims_factor(n=n)  # 质因数分解合数n(非常困难)
        phi_n = (p - 1) * (q - 1)
        x, y = exgcd(phi_n, e)
        d = amendd(y, phi_n)
        m = poww_mod(c, d, n)
        return m

if __name__ == '__main__':
    start = time.time()
    receiver = Receiver()  # 接收方
    pub_key = receiver.get_pub_key()  # 获取接收方生成的公钥
    sender = Sender(pub_key)  # 同步给发送方
    c = sender.encode_m(123456)  # 发送方将明文m进行加密，得到密文c
    m = receiver.decode_c(c)  # 接收者将密文c进行解密，得到明文m
    print("密文:", c)
    print("明文:", m)
    print("加密解密的时间：", time.time() - start)

    # 破解密文c
    start = time.time()
    hacker = Hacker()  # 窃听者
    m2 = hacker.crack(pub_key, c)
    print("破解后的明文：", m2)
    print("破解时间：", time.time() - start)