python实现RSA算法，对数据进行加密认证

• RSA
• 一、数学原理
• 二、实现代码
• • 1 生成素数
  • 2 生成秘钥
  • 3 对数据进行加密、解密
• 总结

RSA是一种非对称加密体制，由公钥和私钥组成，数学原理是实数域的模余法。在使用私钥对数据进行加密后，可用公钥对数据进行解密。
在RSA算法中，设公钥为（D, N），私钥为（E, N），加密过程可以表示为 明 文 E   m o d   N = 密 文 明文^{E} mod N=密文 明文E mod N=密文
解密算法一致，把E换成Ｄ， 密 文 Ｄ   m o d   N = 明 文 密文^{Ｄ} mod N=明文 密文Ｄ mod N=明文
当然，能这样计算对N、E、D是有要求的。

RSA是目前公认的安全算法，对它进行破解需要进行大数的质数分解，目前除了穷举法没有发现其他方法能计算，而穷举法在足够大的大数面前计算是需要非常漫长的时间的，因此当RSA算法采用的N、E、D足够大时，就认为是安全的。目前来说需要N达到1024bits。

1. 欧拉函数的性质：
   若 n = q p ， p 和 q 是 两 个 质 数 ,   则 φ ( n ) = ( q − 1 ) ( p − 1 ) n = qp，p和q是两个质数, 则{varphi}(n) = (q-1)(p-1) n=qp，p和q是两个质数, 则φ(n)=(q−1)(p−1)

2. 欧拉定理：若a与n互质，即 g c d ( a , n ) = 1 , 则 a φ ( n )   ≡   1 m o d      n gcd(a,n)=1, 则a^{varphi(n)} {equiv} 1mod n gcd(a,n)=1,则aφ(n) ≡ 1mod n
   进一步，若n是质数， a n − 1   ≡   1 m o d    n a^{n-1} {equiv} 1mod n an−1 ≡ 1modn， a n   ≡   a m o d    n a^{n} {equiv} amod n an ≡ amodn

3. 费马小定理：若n是质数，a与n互质，，则 a n − 1   ≡   1 m o d      n a^{n-1} {equiv} 1 mod n an−1 ≡ 1mod n，

4. 逆元：如果 a b   ≡   1 m o d      n , 则 a 和 b 互 为 逆 元 ab {equiv} 1mod n, 则a和b互为逆元 ab ≡ 1mod n,则a和b互为逆元

5. RSA加密的条件：
   · n = p × q n = p{times}q n=p×q
   · L = φ ( n ) = ( p − 1 ) ( q − 1 ) L = {varphi}(n) = (p-1)(q-1) L=φ(n)=(p−1)(q−1)
   · 随机选取 1 < e < L ， 使 得 g c d ( e , L ) = 1 1 ·计算 e d   ≡   1 m o d      L ed {equiv} 1mod L ed ≡ 1mod L
   ·公钥对 =（n, d），私钥对 =（n, e）

   继续设明文 = M，密文 = C，现在来证明可以用上述方法加解密的条件。
   M E   m o d   N = C ,   C D m o d      N = M M^{E} mod N = C, C^{D}mod N = M ME mod N=C, CDmod N=M
   根据模法， C D   −   k N = M C^{D} - kN = M CD − kN=M，代回第一个式子，
   ( C D   −   k N ) E   ≡   1 m o d      N (C^{D} - kN)^{E} {equiv} 1mod N (CD − kN)E ≡ 1mod N C D E   ≡   C m o d      N C^{DE} {equiv} Cmod N CDE ≡ Cmod N由于 E × D ≡ 1 m o d      φ ( N ) Etimes Dequiv 1mod varphi(N) E×D≡1mod φ(N)，也即 E D − k φ ( N ) = 1 ED-kvarphi(N) = 1 ED−kφ(N)=1
   若gcd(C, N) = 1，根据欧拉定理， C φ ( N )   ≡   1 m o d      N C^{{varphi}(N)} {equiv} 1mod N Cφ(N) ≡ 1mod N C k φ ( N ) + 1   ≡   C m o d      N C^{k{varphi}(N)+1} {equiv} Cmod N Ckφ(N)+1 ≡ Cmod N C E D   ≡   C m o d      N C^{ED} {equiv} C mod N CED ≡ Cmod N若C与N不互质，由于N是两个质数的积，所以gcd(C,N)=q or gcd(C,N)=p。设 C = k 1 q   o r   C = k 2 p C= k_{1}q or C=k_{2}p C=k1​q or C=k2​p，假设C = kp，而且gcd(m,q)=1，由欧拉定理和欧拉函数的性质， ( k p ) q − 1   ≡   1 m o d      q (kp)^{q-1} {equiv} 1 mod q (kp)q−1 ≡ 1mod q ( ( k p ) q − 1 ) k 2 ( p − 1 )   ≡   ( k p ) q − 1   ≡   1 m o d      q ((kp)^{q-1})^{k_{2}(p-1)} {equiv} (kp)^{q-1} {equiv} 1 mod q ((kp)q−1)k2​(p−1) ≡ (kp)q−1 ≡ 1mod q ( k p ) k 2 φ ( n )   ≡   1 m o d      q (kp)^{k_{2}{varphi}(n)} {equiv} 1 mod q (kp)k2​φ(n) ≡ 1mod q C k 2 φ ( n ) − a q = 1 C^{k_{2}{varphi}(n)}-aq = 1 Ck2​φ(n)−aq=1两边同时乘上C, C k 2 φ ( n ) + 1 = a C q + C = a k p q + C = a k N + C = k 3 N + C C^{k_{2}{varphi}(n)+1}=aCq+C=akpq+C=akN+C=k_{3}N+C Ck2​φ(n)+1=aCq+C=akpq+C=akN+C=k3​N+C也即 C E D   ≡   C m o d      N C^{ED} {equiv} Cmod N CED ≡ Cmod N，原式得证。

6. 素数检验（Miller-Rabbin算法）
   涉及到两个定理：
   5.1 费马小定理：参见3，但是费马小定理的逆定理不一定成立
   5.2 二次探测定理：如果 p是一个素数， 0 < x < p 0 算法内容：
   · 设一个数为x，分解为 2 s t   =   x − 1 2^{s}t = x-1 2st = x−1，t为x不断除以2得到的最大奇数
   · 随机取a， a = a t a=a^{t} a=at，对a进行s次平方（也即计算 b = a 2 m o d    x , a = b b = a^{2}mod x,a = b b=a2modx,a=b），如果其中有次平方的结果为b=1而且此时a不为1或x-1，则不满足二次探测定理
   · 如果 a x − 1 m o d    x ≠ 1 a^{x-1}mod x {neq}1 ax−1modx​=1，则不满足费马小定理
   如果可以，a取小于x的足够多的质数或者随机选取a进行多次检测。Miller-Rabbin算法只能保证x大概率是一个素数，不过这个概率已经足够大了。

7. 快速幂
   计算 a x m o d    n = ? a^xmod n=? axmodn=?，当a和x很大的时候，中间结果超出存储容量又或者数字太大计算复杂，此时需要快速计算这个指数模余值，可以如下进行：
   对x分解为二进制形式，则有 a x m o d   n = a 2 b k + 2 b k − 1 + ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ + 2 b 0 m o d   n = ( ( a 2 b k m o d   n ) ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ( a 2 b 0 m o d   n ) ) m o d   n a^{x}mod n= a^{2^{b_{k}}+2^{b_{k-1}}+······+2^{b_0}}mod n =((a^{2^{b_k}} mod n)······(a^{2^{b_0}} mod n))mod n axmod n=a2bk​+2bk−1​+⋅⋅⋅⋅⋅⋅+2b0​mod n=((a2bk​mod n)⋅⋅⋅⋅⋅⋅(a2b0​mod n))mod n

重新看下RSA算法的流程，
· n = p × q n = p{times}q n=p×q
· L = φ ( n ) = ( p − 1 ) ( q − 1 ) L = {varphi}(n) = (p-1)(q-1) L=φ(n)=(p−1)(q−1)
· 随机选取 1 < e < L ， 使 得 g c d ( e , L ) = 1 1 ·计算 e d   ≡   1 m o d      L ed {equiv} 1mod L ed ≡ 1mod L
·公钥对 =（n, d），私钥对 =（n, e）

由于RSA的安全性取决于n的大小，所以生成的p和q越大越好，那么需要

1. 生成大素数p和q
2. 计算L = (p-1)*(q-1)
3. 随机选取与L互质的e，2
4. 计算e对L的逆元d
5. 销毁p、q，保存n,e,d

用基础算法列出1-1000的素数，从2到 x sqrt x x ​求x是非能被1和他自身外的其他数整除。

def createPrime():
    ret = []
    for i in range(1000):
        for j in range(2,ceil(sqrt(i))+1):
            if i % j == 0:
                break
            if j == ceil(sqrt(i)):
                ret.append(i)
    return ret

先实现快速幂算法，再用Miller-Rabbin算法生成一个大的素数，这个大有多大看需求。

# 1000以内的质数
prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
              107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
              227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347,
              349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
              467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
              613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,
              751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883,
              887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

def quickPowerMod(a,x,n):
    # 计算a**x % n
    c = b = 1
    binary = bin(x)[2:]
    binary = reversed(binary)
    for it in binary:
        if it == '0':
            # 结果不动，乘子指数加一
            a = (a ** 2) % n
        else:
            # 结果乘上当前权重，乘子指数加一
            b = (a * b) % n
            a = (a ** 2) % n
    return b

def MillerRabin(num):
    # 偶数
    if num & 1 == 0:
        return False
    # 将num分解为 (2**s)*t = num-1
    s = 1
    # 这时t必定是偶数，将其分解到为奇数
    t = num - 1
    while t & 1 == 0:
        s += 1
        t = t // 2
    for it in prime_list:
        if it >= num:
            break
        a = quickPowerMod(it,t,num)
        # 二次探测定理
        for i in range(s):
            b = a * a % num
            if b == 1 and a != 1 and a != num-1:
                return False
            a = b
        if a != 1:
            # (it**t) 同余 1 mod num, 费马小定理
            return False
    return True

def createBigPrime():
    pMin = 10 ** 54
    pMax = 10 ** 64
    a = random.randint(pMin,pMax)
    while  not MillerRabin(a):
        a = random.randint(pMin, pMax)
    return a

接下来编写函数生成公钥私钥对，求逆元的时候有几种算法，由于明文和N关系未知，选取扩展欧几里得算法，又需要求最大公因子和最小公倍数的函数，这两个很简单，直接上代码。

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

def lcm(a,b):
    c = gcd(a, b)
    return a * b // c

def inverseGCD(a,b):
    # 递推求扩展欧几里得算法
    if b == 0:
        return 1, 0
    else:
        k = a // b
        x2, y2 = inverseGCD(b, a % b)
        x1, y1 = y2, x2 - k * y2
    # 注意x1可能为负，在外面再求一次模
    return x1, y1

def createKeys():
    q = createBigPrime()
    p = createBigPrime()
    n = q * p
    # n的欧拉函数
    L = (p - 1) * (q - 1)
    e = random.randint(2,L)
    while gcd(e,L) != 1:
        e = random.randint(2,L)
    # 计算e * d 同余 1 mod L
    # 扩展欧几里得算法求逆元
    d, _ = inverseGCD(e,L)
    d = d % L
    #d = e**(L-2)
    with open('e.txt', 'w') as f:
        f.write(str(e))
    with open('d.txt', 'w') as f:
        f.write(str(d))
    with open('n.txt', 'w') as f:
        f.write(str(n))
    return n, e, d

有了私钥对，加密只是进行一个求快速幂的过程。

m = 8916534261681675
n,e,d = createKeys()
print('私钥对：n',n,e)
print('公钥对：n',n,d)
en = quickPowerMod(m,e,n)
print('原消息: ', m)
print('加密后：', en)
de = quickPowerMod(en,d,n)
print('解密后：', de)

看下结果

已经完成正确的加解密！

RSA算法用到数论、离散数学的基础，加密速度慢，而且每次加密过程中消息大小M不能大于N。但RSA算法是公认非常安全的算法。
如果想对大小超出N的消息加密，一般需要先用DES、SHA等对原消息计算成一定长度的摘要，再对摘要进行RSA加密。