今天我们从对称加密算法开始，讨论：为什么需要非对称加密算法，什么是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)情形为例，步骤如下：

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

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

数学证明

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

同余：记作：$a≡b\pmod m$

欧拉函数：[ φ(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_k}) ] 欧拉定理：[ 若：a,m ∈ N+ \quad and \quad (a,m) = 1 \quad 则：a^{φ(m)}≡{1} \pmod {m} ]

证明：欧拉定理

假设： [ B = { \quad b_i ∈ [1, m) \quad and \quad (b_i, m) = 1 \quad } ]

如果： [ a_i = a * b_i ]

那么： [ A = { \quad a_i ∈ [1, m) \quad and \quad (a_i, m) = 1 \quad } ]

因此： [ a^{φ(m)} \prod_{i=1}^{φ(m)}{b_i} ≡ \prod_{i=1}^{φ(m)}{a*b_i} ≡ \prod_{i=1}^{φ(m)}{a_i} ≡ \prod_{i=1}^{φ(m)}{b_i} \pmod {m} ]

故： [ m | a^{φ(m)} \prod_{i=1}^{φ(m)}{b_i} - \prod_{i=1}^{φ(m)}{b_i} ]

即： [ m | (a^{φ(m)} - 1) \prod_{i=1}^{φ(m)}{b_i} ]

又： [ (m,\prod_{i=1}^{φ(m)}{b_i}) = 1 ]

故： [ m | (a^{φ(m)} - 1) ]

即： [ a^{φ(m)}≡{1} \pmod {m} ]

结束：欧拉定理

证明：加密解密

已知： [ c ≡ m^{e} \pmod {n} ]

欲证： [ m ≡ c^{d} \pmod {n} ]

即证： [ m ≡ {(m^{e} \pmod {n})}^{d} \pmod {n} ]

即证： [ m ≡ m^{ed} \pmod{n} ]

因为： [ e*d ≡ {1} \pmod {φ(n)} ]

假设： [ e*d = 1 + kφ(n) ]

那么： [ m^{ed} = m^{1 + kφ(n)} = m \cdot (m^{φ(n)})^k ]

根据欧拉定理： [ m^{ed} ≡ m \pmod{n} ]

可证： [ m ≡ m^{ed} \pmod{n} ]

结束：加密解密

相关算法

米勒素性检验

定理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)

本人实现

• pkcs#1