RSA加密算法

RSA加密算法是一种非对称加密算法，于1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）、伦纳德·阿德曼（Leonard Adleman）一起提出。

RSA优势
对极大整数做因式分解到难度决定了RSA算法的可靠性，对一极大整数做因式分解越困难，RSA算法越可靠

加密由 公钥 私钥 明文 密文 四个部分组成

质数与互质数
一个大于1到自然数，除了1和它本身外，不能被其他自然数整除（除0以外）的数称为质数（素数）；否则称为合数。
例如 15=3×5，所以15不是素数
13除了等于13×1以外，不能表示为其他任何两个整数的乘积，所以13是一个素数
1不是质数，也不是合数
公约数只有1的两个数，叫做互质数

取模运算
取模也就是求余数
例如 10mod3=1（10%3=1）、26mod6=2、28mod2=0
其中 10mod 3 =1 为 10 – (3×n)=1，3n<10

同余定理
“≡”是数论中表示同余的符号，同余的定义如下：
给定一个正整数m，如果两个整数a和b满足 a – b 能被m整除 ：(a -b)mod m = 0，那么就称整数a与b对模m同余，记作a≡b（mod m），同时可成立a mod m =b
同余与模运算是不同的：
（1）若a≡0(mod m)，则m|a；

（2）a≡b(mod m)等价于a与b分别用m去除，余数相同

欧拉函数
任意给定正整数n，计算在小于等于n的正整数之中，有多少个与n构成互质关系？
计算这个值的方法就叫欧拉函数，以φ(n)表示
例如在1到8中，与8形成互质关系的是1、3、5、7所以φ(n)=4
在RSA算法中，欧拉函数对以下定理成立:
（1）如果n可以分解为两个互质的整数之积，即n=p×q，则有：φ(n)=φ(pq)=φ(p)φ(q)；
（2）当p为质数，φ(p)=p-1，所以有φ(n)=(p-1)(q-1)

欧拉定理与模反元素
欧拉函数的用处在于欧拉定理：如果两个正整数a和n互质，则n的欧拉函数φ(n)可以让下面的等式成立；
$$
a^{φ(n)}≡1(mod n)
$$
也就是说，a的φ(n)次方被n除的余数为1
模反元素的推导过程如下：
根据欧拉定理，有：
$$
a^{φ(n)}=a×a^{(φ(n-)-1)}=1(mod n)
$$
令b=a^(φ(n)-1)=1(mod n)得
ab=1(modn)
b就是a的模反元素，所以如果两个正整数a和n互质，那么一定可以找到整数b使得ab-1被n整除，或者说ab被n除的余数是1，所以求私钥d的公式：
$$
de≡1mod[(p-1)(q-1)]
$$
其中{φ(n)=(p-1)(q-1),φ(n)与e互质，k为正整数}
可化为：
$$
d=(kφ(n)+1)/e
$$

推导公式：d*e=1mod φ(n)
可得：(d*e-1)/φ(n)=k;
即：d =(k*φ(n)+1)/e

RSA密钥一般为1024位

由p,q,dp,dq,c求明文的算法

import gmpy2
I =gmpy2.invert(q,p)
mp = pow(c,dp,p)
mq = pow(c,dq,q)            #求冥取模运算

m = (((mp-mq)*I)%p)*q+mq    #求明文公式

print(hex(m))               #转为十六进制

模运算的基本规则

（1）
$$
( a + b ) mod p = ( a mod p + b mod p ) mod p
$$
（2）
$$
( a – b ) mod p = (a mod p – b mod p ) mod p
$$
（3）
$$
(a b ) mod p = (a mod p b mod p ) modp
$$
（4）
$$
a ^b mod p = ( (a mod p ) ^ b ) mod p
$$
结合律
（5）
$$
((a+b)modp +c ) mod p = (a + (b + c)mod p) mod p
$$
（6）
$$
((ab)mod p c) mod p = (a(bc)modp)modp
$$
交换律
（7）
$$
(a+b)modp=(b+a)modp
$$
（8）
$$
(ab)modp=(ba)modp
$$
分配律
（9）
$$
(a+b)modp=(amodp+bmodp)mod p
$$
（10）
$$
((a+b)modpc)modp=((ac)modp+(b*c)modp)modp
$$
（11）》若a≡b(%p)，对任意的C，都有（a+c）≡（b+c）（%p）

（12）》若a≡b(%p)，∀C，有（a×c）≡（b×c）（%p）
（13）》若a≡b(%p)，∀C，有c≡d（%p），则(a+c)≡(b+d)(%p),(a-c)≡(b-d)(%p),
(a×c)≡(b×d)(%p)

RSA已知p,q,dp,dq,c
公式：

（1）
$$
m_1=C^{dp}modp
$$
（2）
$$
m_2=C^{dq}mod q
$$
（3）求明文
$$
m=(((m_1-m_2)I)modp)q+m
$$
I为乘法逆元

已知条件：
c ≡ m^e mod n #加密
m ≡ c^d mod n #解密
φ(n) = (p-1)(q-1) #欧拉定理
d·e ≡ 1 mod φ(n)  #欧拉定理与模反元素
dp ≡ d mod (p-1)
dq ≡ d mod (q-1)

利用中国剩余定理可得：
$$
m_1 ≡ c^d mod p
$$

$$
m_2 ≡ c^d mod q
$$

证明过程
由 
m ≡ c^d mod n
可得
m = c^d + k*n
∵ n = p*q
∴ m = c^d + k*p*q
上述式子同时取余q和p分别得到
m_1=c^d mod p           #m_1 中 _1表示下标 即区分m1和m2
m_2=c^d mod q
> c^d = kp+m
代入m_2 = c^d mod q得
m_2 ≡(kp+m_1)mod q
等式两边同时减去m 得到
(m_2 - m_1)≡ kp mod q
又因为gcd(p,q)=1 求p都逆元
(m_2 - m_1)*p^{-1}≡ k mod q       #{-1}表示指数
>k ≡(m_2 - m_1)*p{-1} mod q
∴k ≡ (m_2 - m_1)*p{-1}mod q && c^d = kp +m_1
>c^d = ((m_2 - m_1)*p^{-1}mod q)*p + m_1
代入m≡c^d mod n
∴m≡(((m_2 - m_1)*p^{-1}mod q)*p + m_1)mod n

现在只要求m1和m2了

因
d ≡ dp mod (p-1)
d ≡ dq mod (q-1)
分别代入m_1,m_2
m_1 ≡ c^{dp mod(p-1)} mod p > m_1 ≡ c^{dp} mod p #1
m_2 ≡ c^{dq mod(q-1)} mod q > m_2 ≡ c^{dq} mod q #2
费马推导gcd(a,b)#求最大公约数，欧几里得算法
假如p是质数，且gcd(k,p)=1,则k^(p-1)≡1 mod p
如果有等式d = dp +k*(p-1)
代入m_1 ≡ c^d mod p
得  m_1 ≡ c^{dp+k*(p-q)} mod p > m_1 ≡ c^{dp}·c^{k*(p-1)} mod p
由费马小定理
c^{k*(p-1)} mod p = (c^{p-1}mod p)^k = 1^k = 1
m_1 ≡ c^{dp} mod p
同理 m_2 ≡ c^{dq} mod q