P03.RSA算法简介及原理
P03.RSA简介及原理
rsa算法简介
RSA公开 密钥 密码体制。所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。
选择两个大素数p和q，计算出模数N = p * q
计算φ(N) = (p−1) * (q−1) 即N的欧拉函数，然后选择一个e (1<e<φ(N))，且e和φN互素
取e的模反数为d(逆元)，计算方法: e * d ≡ 1 (mod φ(N))
对明文m进行加密：c=m^e%N
c = pow(m, e, N)，得到的c即为密文
对密文c进行解密:m=c^d%N
m = pow(c, d, N)，得到的m即为明文
p 和 q ：大整数N的两个因子（factor）
N：大整数N，我们称之为模数（modulus）
e 和 d：互为模反数的两个指数（exponent）
c 和 m：分别是密文和明文，这里一般指的是一个十进制的数
rsa算法原理
欧拉函数φ(n)
欧拉函数φ(n)的定义是小于n的自然数中与n互质的数的个数
欧拉定理
若n,a为正整数，且n,a互质，则:a^φ(n)≡1 mod n
费马小定理
费马小定理: :
模运算
运算规则
模运算与基本四则运算有些相似，但是除法除外。其规则如下：
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
a ^ b % p = ((a % p) ^ b) % p
结合律
((a + b) % p + c)%p = (a + (b + c) % p) % p
((a * b) % p * c) %p= (a * (b * c) % p) % p
交换律
(a + b) % p = (b + a) % p
(a * b) % p = (b * a) % p
分配律
(a + b) % p = (a % p + b % p) % p
((a + b) % p * c) % p = ((a * c) % p + (b * c) % p
重要定理
若 a ≡ b (mod p)，则对于正整数 c，都有(a**c) ≡ (b**c) (mod p)
若 a ≡ b (mod p)，则对于任意的 c，都有(a + c) ≡ (b + c) (mod p)
若 a ≡ b (mod p)，则对于任意的 c，都有(a * c) ≡ (b * c) (mod p)
如果ac≡bc (mod m)，且c和m互质，则a≡b (mod m）。
[理解：当且仅当c和m互质,c^-1存在,等式左右可同乘模逆。]
如果a≡b (mod m),a≡b (mod n)，且n和m互质，则a≡b (mod mn）
若 a ≡ b (mod p)，c ≡ d (mod p)，则
(a + c) ≡ (b + d) (mod p)
(a - c) ≡ (b - d) (mod p)
(a * c) ≡ (b * d) (mod p)
(a / c) ≡ (b / d) (mod p)
除法规则：
在模n意义下，a/b不再仅仅代表这两个数相除，⽽是指 a+k1*n 和 b+k2*n这两个组数中任意两个相除，使商为整数
因此也就可以理解，除以⼀个数等价于乘以它的逆
a/b ≡ c(mod n) <=> a ≡ c*(b^-1) (mod n)，其中b模n的逆记作b的负⼀次⽅。
推导过程
将式1带入式2 得 m = (m ^ e % N ) ^ d % N需要证明：m == ( m ^ e % N ) ^ d % N
将 e * d ≡ 1 (mod φ(N)) 即 e * d = K * φ(N) + 1，K为任意正整数，代入得：=> (m^(K*φ(N)+1))%N
=> (m^(K*φ(N)*m^1)%N # 同底数相乘，指数相加
=> (m^(K*φ(N)*m)%N
=> ((m^φ(N)^K%N*m)%N # 幂的乘方，底数不变，指数相乘
=> ((m^φ(N)^K%N*m%N)%N # (a * b) % p = (a % p * b % p) % p
=> ((m^φ(N)%N)^K%N*m%N)%N # a ^ b % p = ((a % p) ^ b) % p
=> (1^K%N*m%N)%N # 根据欧拉定理：a^φ(n)≡1 mod n 即 a^φ(n) mod n = 1
=> (m%N)%N # 1^K%N=1
=> (m%N)%N
=> (m%N)^1%N
=> (m^1)%N # a ^ b % p = ((a % p) ^ b) % p
=> m%N
m #因为 m < N