RSA的加密与解密
RSA的加密和解密都是在整数环ℤn内完成的，模计算在其中发挥了核心作用。假设使用RSA加密明文x，而表示x的位字符串则是ℤn= {0，1，2，3，…，n-1}内的元素。所以明文x表示的二进制值必然小于n。对于密文而言，这个原理也成立。
RSA相关的术语与符号表示：
公钥：（e，n）
私钥：（d，n）
明文：m
密文：c
RSA的三大算法
密钥生成算法
①.选择两个大素数p和q
②.计算n = p * q
③.计算Φ(n) = (p - 1)(q - 1)
④.选择满足以下条件的公开指数e∈{1,2,3,…,Φ(n) - 1}
gcd(e, Φ(n)) = 1。
why? : 条件gcd(e, Φ(n)) = 1保证e的逆元存在模Φ(n)，因此，私钥d始终存在。
⑤.计算满足以下条件的私钥d
e * d ≡ 1 mod Φ(n)
证明：
欧拉定理：m^Φ(n) ≡ 1 (mod n) 表示对于任何一个与n互质的正整数m取它的Φ(n)次方，并除于n取余数，结果都永远等于1。
Φ(n)是欧拉函数，它表示小于等于n的正整数中，有多少个与n互质的数。
例子：取 n = 6， 会发现在小于6的正整数中只有1和5与6互质，所以Φ(6) = 2。
对欧拉定理进行简单的变换：首先在等式的两边同取k（任意的正整数）次幂，m^(Φ(n) k) ≡ 1^ k (mod n) ；接着在两端同乘以m， m^(Φ(n) k + 1) ≡ m (mod n) ；将模运算写在等式的左边 m^(Φ(n) k + 1) mod n = m。与 m^(e d) mod n = m 进行比对可以发现 e d = Φ(n) k + 1（Φ(n) k + 1就是1 % Φ(n)，k∈Z , 成功推导出上面的⑤) , 所以e和d的关系可以表示成e = Φ(n) k + 1/d 。公式 看起来简单，但Φ(n)的计算并不容易，Φ(n)的计算恰恰是公钥加密中最关键的部分。要计算出Φ(n)的唯一办法就是对这个数n做质因数 分解，然而大数的质因数分解是非常困难的。但如果n本身是一个质数，情况就有所不同了。例如对于质数7，小于7并于7互质的数有 1-6，因此Φ(7) = 6。我们可以推广到对于一个质数p，Φ(p) = p - 1。Φ函数还有一个重要的特性：对于任意两个互质的整数p和q，Φ(p q) = Φ(p) Φ(q)，再结合上面推导的Φ(p) = p - 1，就得到了③公式。
加密算法
给定公钥(E,N)和明文m，则加密函数为：
c ≡ m^e mod n
其中c, m ∈ ℤn。
解密算法
给定私钥d及密文c，则解密函数为：
m ≡ c^d mod n
其中c, m ∈ ℤn。
注意：c, m, n, d都是非常长的数字，通常为1024位或更长。值e有时称为加密指数或公开指数；私钥d有时称为解密指数或保密指数。有趣的是 m^ed mod n = m
RSA密码体制的一些需求：
(1) 由于攻击者可以得到公钥，所以，对于给定的公钥值e和n,确定私钥d在计算上必须是不可行的。（即由公钥无法推出私钥）
(2)由于x只是唯一地取决于模数n的大小，所以一.次RSA加密的位数不能超过l,其中I指的是n的位长度。
(3)计算 m^e mod n (即加密) 和 c^d mod n (即解密) 应该相对简单。这意味着我们需要一种能快速计算长整数的指数的方法。
(4)给定一个n应该对应很多密钥/公钥对，否则，攻击者就可以发起蛮力攻击(事实证明，这个要求很容易满足)。
附上这两天做到的基础题：
1.
解题思路：
我们知道d*e ≡ 1 mod Φ(n)，Φ(n) = (p - 1)(q - 1)，可以根据这两个公式求得d
附上代码：
from Crypto.Util.number import inverse
import gmpy2
p = 447685307
q = 2037
e = 17
phi = (p - 1) * (q - 1)
d = inverse(e, phi) #求e在phi的乘法逆元，返回e的逆矩阵
print(d)
#flag{53616899001}2.
解题思路：
由 d e ≡ 1 mod Φ(n), Φ(n) = (p - 1)(q - 1), n = p q, 求得d之后，将其带入到 m ≡ c^d mod n，可求得m
附上代码：
from Crypto.Util.number import inverse
import gmpy2
p = 447685307
q = 2037
e = 17
c = 704796792
n = p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(m)