今天我们从对称加密算法开始，讨论：为什么需要非对称加密算法，什么是RAS算法，相关数学证明，以及个人实现。

对称加密算法的缺点

在对称加密解密算法中，加密与解密使用相同的密钥。优点是加密高效，而缺点是信息交换双方都要知道密钥，容易泄露。

假设有三个独立个体：a b c，需要交换信息，并使用相同的加密算法。若（a与b）或（b与a）进行交换记为(a,b)。那么，如果密钥存在重复，就会存在信息安全风险，即秘密不是某对独立个体间的秘密，而是使用了相同密钥独立个体间的共同秘密。为了确保交换的过程中不会泄密，就共需要三个独立的密钥：e(a,b) e(a,c) e(b,c)。

更进一步，假设有n个独立个体进行信息交换，那么我们共需要多少独立的密钥才称得上是安全呢？根据组合知识，我们知道，集体所需的密钥总数等于C(n,2)。而对于每个个体而言，需要管理的密钥总数是n-1。

为了解决这个挑战，前辈们就想，有没有一种方法，可以让加密密钥和解密密钥不同呢？于是，公钥加密算法就诞生了。而其中最流行的当属RSA了，这也是我们今天所要讨论的主题。顺便说一下，基于RSA，每个个体只需要保存一对密钥，就可以支持不同账户的访问了。

公钥加密算法 – RSA

在 RSA中，我们将可以公开以加密的密钥叫公钥，而私有以解密的密钥叫私钥。具体地，以 RSA的 K=(n, d)情形为例，步骤如下：

步骤 参数 方法 约束或说明
1.1 p p = prime.random() 质数
1.2 q q = prime.random() 质数
2.1 n n = p * q 模数
2.2 φ(n) φ(n) = (p-1)(q-1) 欧拉函数
2.3 e e ∈ N+, e < n, (e，φ(n)) = 1 公共指数
2.4 d e*d≡1(mod φ(n)) 模反元素
3.1 (n, e) tuple 公钥
3.2 (n, d) tuple 私钥
4.1 c = RSAEP ((n, e), m) c = m^e mod n 加密
4.2 m = RSADP ((n, d), c) m = c^d mod n 解密
5.1 s = RSASP1 ((n, d), m) s = m^d mod n 签名
5.2 m = RSAVP1 ((n, e), s) m = s^e mod n 认证

举个例子，假设 (p,q) = (5,11)，进而取公共指数 e = 13，那么：

名称 参数 取值
质数 p 5
质数 q 11
模数 n 55
欧拉函数 φ(n) 40
公共指数 e 13
模反元素 d 37
公钥 (n, e) (55, 13)
私钥 (n, d) (55, 37)

即我们获得了一对密钥，公钥：(55, 13)，私钥：(55, 37)。那么，以 1 2 3为例，加密解密计算如下：

明文 加密：c = m^e mod n 解密：m = c^d mod n
1 c = 1^13 mod 55 = 1 m = 1^37 mod 55 = 1
2 c = 2^13 mod 55 = 52 m = 52^37 mod 55 = 2
3 c = 3^13 mod 55 = 38 m = 38^37 mod 55 = 3

数学证明

互质：记作：(a,b) == 1

同余：记作：a≡b(mod m)

φ(n)：{ n ∈ N+, a ∈ [1,n) } && { S = |a|{(a, n)=1} } => φ(n) = |S|

欧拉定理：若： a,m ∈ N+且 (a,m) == 1，则：a^φ(m)≡1(mod m) 。

相关算法

米勒素性检验

定理1：若：p 是质数，(a , n) = 1，则：a^(p-1) = 1 (mod p)。

定理2：若：p 是质数，x ∈ [1, p)，则：x^2≡1(mod p)的解 x ∈ {1, p-1}。

米勒素性检验原理：

假设：P是所有质数的集合。

（1）根据定理1的逆否命题：

    若：对于任一a < n，使 a^(n-1) ≠ 1 (mod n)，则：n ∉ P。

（2）根据定理2的逆否命题：

    若：n ∈ S，x^2≡1(mod n)的解 x ∉ {1, n-1}，则：n ∉ P。

综上：

    对于任一给定的数字n，令：n-1 = m*2^s，其中 m是奇数。为了分解方便，可以将 n-1视为二进制数。

    循环验证定理2的逆否命题，当循环结束时，即相当于同时验证了定理1的逆否命题。

据传：结果是素数的概率至少是：1-(1/4)^p
幂的速乘

原理1：速乘算法的原理

# 计算：v = a^b = a.power(b)
# 假设
#   b = for i in 0..n |+| {  b.bit(i) * bit(i) }
# 那么
#   v = for i in 0..n |*| { a.power(bit(i)).power(b.bit(i)) }
# 令：
#   base = a.power(bit(i))

def pow(a, b):
    result, base = 1, a

    while b:
        if b & 1:
            result *= base
        base *= base
        b >>= 1

    return result

原理2：余数运算的分配率

# 计算：v = a^b%c
#
# (a * b) mod c=((a mod c) * (b mod c)）mod c

def modpow(a, b, c):
    result, base = 1, a

    while a:
        if b & 1:
            result = result * base % c 
        base = base * base % c
        a >>= 1

    return result
欧基里德算法

原理：若 a ≡ r (mod b)，gcd(a,b) = gcd(b,r)

# 证明:
# 假设
#   a > b, d = (a, b) => d|a, d|b
# 那么
#   r = a - kb => r/d = a/d - kb/d => d|r
# 因为
#   (a, b) = (a + kb, b) = (b, a + kb)
# 因而
#   (a, b) = (b, r)

def gcd_org(a, b):
    if a < b:
        a, b = b, a

    if b == 0:
        return a
    else:
        return gcd_org(b, a % b)

def gcd_ext(a, b):
    revs = False
    if a < b:
        a, b = b, a
        revs = True
  
    u,  v,  s,  t = 1, 0, 0, 1
    while b:
        q, r = divmod(a,b)
        a, b = b, r
        u, s = s, u - q*s
        v, t = t, v - q*t

    if revs:
        u, v = v, u

    return (a, u, v)

本人实现

1 2 3 4