X1r0z included in Programming

2018-08-03 2018-08-03 About 1300 words 3 minutes

学习 RSA 算法的相关笔记

先介绍两个概念, 对称加密算法和非对称加密算法.

对称加密算法

使用同一密钥进行加解密. 例如之前介绍的 xor, 也可以算作对称加密算法.

非对称加密算法

使用不同密钥进行加解密, 公开的叫公钥, 不公开的叫私钥, 使用公钥加密, 私钥解密.

RSA 是一种典型的非对称加密算法.

数论

简单介绍一点数学知识.

质数

除了 1 和它本身以外不再有其它因数的自然数.

最大公因数

两个或两个以上的数中最大的共有因数.

最小公倍数

两个或两个以上的数中最小的共有倍数.

互质关系

对于两个数 a b, 如果 a 与 b 的公因数只有 1, 则 a 与 b 互质.

例如 1 和 2 互质, 15 和 23 互质.

欧拉函数

对于一个正整数 n, 在不大于 n 的范围中所有与它互质的数的总个数表示为 φ(n).

φ(n) 叫做 n 的欧拉函数.

例如正整数 4, 在 1,2,3,4 中, 4 与 1 互质, 4 与 3 互质, 则 φ(4) = 2.

计算欧拉函数分很多种情况, 这里就简单介绍两种, 后面进行加密的时候还会用到.

对于质数 a, 则 φ(a) = a - 1.

如果 c 可以分解为两个质数 a b 的乘积, 例如 6 = 2 x 3, 则 φ(c) = φ(ab) = φ(a)φ(b), 又因为 φ(a) = a - 1, φ(b) = b - 1, 所以 φ(c) = (a - 1)(b - 1).

模反元素

对于两个互质的正整数 a b, 总有整数 c, 使 (ab) -1 被 c 整除, 或者说 ab 被 n 除的余数是 1, c 就叫做 a 的模反元素.

例如 3 和 11 互质, 因为 (3 x 4) = 12, (12 - 1) ÷ 11 = 1, 所以 3 的模反元素就为 4.

当然模反元素不止一个, (3 x 15) = 45, (45 - 1) ÷ 11 = 4, 这里 15 也是 3 的模反元素.

生成密钥

生成两个不相等的大质数 p q

举个例子.

p = 23, q = 67

计算 p q 的乘积 n

n = 23 x 67 = 1541

计算 n 的欧拉函数 φ(n)

φ(n) = (p - 1)(q - 1)

φ(n) = 22 x 66 = 1452

这里其实也可以计算出 lcm(p - 1, q - 1), 即 p - 1 和 q - 1 的最小公倍数.

好像只是个范围, 数学系的学姐说这样也能求出 e 和 d 并成功进行信息的加解密.

随机选择一个整数 e, 必须满足 1 < e < φ(n), 且 e 与 φ(n) 互质

e = 5

计算 e 对于 φ(n) 的模反元素 d, 使 ed - 1 能被 φ(n) 整除, 且 1 < d < φ(n)

ed = 1 (mod φ(n))

d = 581

将 n 和 e 封装为公钥, n d 封装为私钥

pub = (n, e) = (1541, 5)

pri = (n, d) = (1541, 581)

信息加密

假设信息为 m , 其中 m 必须为整数, 且 m < n.

m = ord('A') = 65

加密公式

me = c (mod n)

已知 m e n, 求 c

Python

c = (m ** e) % n

计算出 c = 839

信息解密

解密公式

cd = m (mod n)

已经 c d n, 求 m

Python

m = (c ** d) % n

计算出 m = 65 chr(m) = 'A'

实践

Python 实现的简单 RSA

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68


#!/usr/bin/python3
import random
import string
import math

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

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

def prime(n):
    if n == 2 or n == 3:
        return True
    if n % 6 != 1 and n % 6 != 5:
        return False
    t = int(math.sqrt(n))
    for i in range(5,t + 1):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True

def rnd_pq(size):
    while True:
        p = int(''.join(random.sample(string.digits,size)))
        q = int(''.join(random.sample(string.digits,size)))
        if prime(p) and prime(q):
            if p != q:
                return p, q

def rel_e(l):
    for e in range(2, l):
        if gcd(e, l) == 1:
            return e

def mod_d(e, l):
    for d in range(2, l):
        if  (e * d) % l == 1:
            return d

def encrypt(m, pub):
    n = pub[0]
    e = pub[1]
    c = (m ** e) % n
    return c

def decrypt(m, pri):
    n = pri[0]
    d = pri[1]
    m = (c ** d) % n
    return m

p, q = rnd_pq(2)
n = p * q
l = lcm(p - 1, q - 1)
e = rel_e(l)
d = mod_d(e, l)
pub = (n, e)
pri = (n, d)
m = 65
c = encrypt(m, pub)
cm = decrypt(c, pri)
print(m, c, cm)

RSA 算法原理

数论

生成密钥

信息加密

信息解密

实践