1
p、q

1
n = p * q

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

1
1 < e < φ(n)

1
d * e mod φ(n) = 1

1
KU = (e, n)

1
KR = (d, n)

1
明文 M  加密 M^e mod n = C
2
密文 C  解密 C^d mod n = M

1
p = 3
2
q = 11
3
n = 3 * 11 = 33
4
φ(n) = (3 - 1) * (11 - 1) = 20

1
与 φ(n) 互质的整数 1 < e < φ(n)
2
e = 3

1
e 对于 φ(n) 的模反元素 d
2
d * 3 mod φ(n) = 1
3
d * 3 mod 20 = 1
4
d = 7

1
加密 M = 20
2
KU = (3, 33)
3
密文 C = 20^3 mod 33 = 14

1
解密 C = 14
2
KR = (7, 33)
3
明文 M = 14^7 mod 33 = 20

1
import gmpy2
2

3

4
p = 3
5
q = 11
6
n = p * q
7
phi_n = (p - 1) * (q - 1)  # φ(n)
8
e = 3
9

10
d = gmpy2.invert(e, phi_n)
11
c = 14
12
m = pow(c, d, n)
13
print m      # m = 20

1
欧拉函数φ(n)的定义是小于n的自然数中与n互质的数的个数

1
若n,a为正整数，且n,a互质，则:a^φ(n)≡1 mod n

1
(a + b) % p = (a % p + b % p) % p
2
(a - b) % p = (a % p - b % p) % p
3
(a * b) % p = (a % p * b % p) % p
4
a ^ b % p = ((a % p) ^ b) % p
5
结合律
6
((a + b) % p + c) = (a + (b + c) % p) % p
7
((a * b) % p * c) = (a * (b * c) % p) % p
8
交换律
9
(a + b) % p = (b + a) % p
10
(a * b) % p = (b * a) % p
11
分配律
12
(a + b) % p = (a % p + b % p) % p
13
((a + b) % p * c) % p = ((a * c) % p + (b * c) % p
14
重要定理
15
若 a ≡ b (mod p)，则对于任意的 c，都有(a + c) ≡ (b + c) (mod p)
16
若 a ≡ b (mod p)，则对于任意的 c，都有(a * c) ≡ (b * c) (mod p)
17
若 a ≡ b (mod p)，c ≡ d (mod p)，则
18
(a + c) ≡ (b + d) (mod p)
19
(a - c) ≡ (b - d) (mod p)
20
(a * c) ≡ (b * d) (mod p)
21
(a / c) ≡ (b / d) (mod p)

1
逆元
2
a mod p的逆元便是可以使 a * a' mod p = 1 的最小a'

1
式1：c = m ^ e % N
2
式2：m = c ^ d % N

1
(m ^ e % N) ^ d % N
2

3
=>  (m ^ e) ^ d % N          #模运算 a ^ b % p = ((a % p) ^ b) % p
4

5
m ^ (e * d) % N              #幂的乘方，底数不变，指数相乘

1
=> (m ^ (K * φ(N) + 1)) % N
2

3
=> (m ^ (K * φ(N) * m ^ 1) % N      # 同底数相乘，指数相加
4

5
=> (m ^ (K * φ(N) * m) % N
6

7
=> ((m ^ φ(N) ^ K % N * m) % N      # 幂的乘方，底数不变，指数相乘
8

9
=> ((m ^ φ(N) ^ K % N * m % N) % N           # (a * b) % p = (a % p * b % p) % p
10

11
=> ((m ^ φ(N) % N) ^ K % N * m % N) % N      # a ^ b % p = ((a % p) ^ b) % p
12

13
=> (1 ^ K % N * m % N) % N                   # 根据欧拉定理：a ^ φ(n) ≡ 1 mod n 即 a ^ φ(n) mod n = 1
14

15
=> (m % N) % N                               # 1 ^ K % N = 1
16

17
=> (m % N) % N
18

19
=> (m % N) ^ 1 % N
20

21
=> (m ^ 1) % N                               # a ^ b % p = ((a % p) ^ b) % p
22

23
=> m % N
24

25
m               # 因为 m < N