RSA加密原理详解
一、算法介绍
一、RSA加密简介
RSA加密是一种非对称加密。可以在不直接传递密钥的情况下，完成解密。这能够确保信息的安全性，避免了直接传递密钥所造成的被破解的风险。是由一对密钥来进行加解密的过程，分别称为公钥和私钥。两者之间有数学相关，该加密算法的原理就是对一极大整数做因数分解的困难性来保证安全性。通常个人保存私钥，公钥是公开的（可能同时多人持有）。
二、RSA加密、签名区别
加密和签名都是为了安全性考虑，但略有不同。常有人问加密和签名是用私钥还是公钥？其实都是对加密和签名的作用有所混淆。简单的说，加密是为了防止信息被泄露，而签名是为了防止信息被篡改。这里举2个例子说明。
第一个场景：战场上，B要给A传递一条消息，内容为某一指令。
RSA的加密过程如下：
（1）A生成一对密钥（公钥和私钥），私钥不公开，A自己保留。公钥为公开的，任何人可以获取。
（2）A传递自己的公钥给B，B用A的公钥对消息进行加密。
（3）A接收到B加密的消息，利用A自己的私钥对消息进行解密。
在这个过程中，只有2次传递过程，第一次是A传递公钥给B，第二次是B传递加密消息给A，即使都被敌方截获，也没有危险性，因为只有A的私钥才能对消息进行解密，防止了消息内容的泄露。
第二个场景：A收到B发的消息后，需要进行回复“收到”。
RSA签名的过程如下：
（1）A生成一对密钥（公钥和私钥），私钥不公开，A自己保留。公钥为公开的，任何人可以获取。
（2）A用自己的私钥对消息加签，形成签名，并将加签的消息和消息本身一起传递给B。
（3）B收到消息后，在获取A的公钥进行验签，如果验签出来的内容与消息本身一致，证明消息是A回复的。
在这个过程中，只有2次传递过程，第一次是A传递加签的消息和消息本身给B，第二次是B获取A的公钥，即使都被敌方截获，也没有危险性，因为只有A的私钥才能对消息进行签名，即使知道了消息内容，也无法伪造带签名的回复给B，防止了消息内容的篡改。
但是，综合两个场景你会发现，第一个场景虽然被截获的消息没有泄露，但是可以利用截获的公钥，将假指令进行加密，然后传递给A。第二个场景虽然截获的消息不能被篡改，但是消息的内容可以利用公钥验签来获得，并不能防止泄露。所以在实际应用中，要根据情况使用，也可以同时使用加密和签名，比如A和B都有一套自己的公钥和私钥，当A要给B发送消息时，先用B的公钥对消息加密，再对加密的消息使用A的私钥加签名，达到既不泄露也不被篡改，更能保证消息的安全性。
总结：公钥加密、私钥解密、私钥签名、公钥验签。
1. 什么是RSA
RSA算法是现今使用最广泛的公钥密码算法，也是号称地球上最安全的加密算法。在了解RSA算法之前，先熟悉下几个术语
根据密钥的使用方法，可以将密码分为对称密码和公钥密码
对称密码：加密和解密使用同一种密钥的方式
公钥密码：加密和解密使用不同的密码的方式，因此公钥密码通常也称为非对称密码。
1.1 互质关系
如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。
关于互质关系，不难得到以下结论：
1. 任意两个质数构成互质关系，比如13和61。
2. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。
3. 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。
4. 1和任意一个自然数是都是互质关系，比如1和99。
5. p是大于1的整数，则p和p-1构成互质关系，比如57和56。
6. p是大于1的奇数，则p和p-2构成互质关系，比如17和15。
1.2 欧拉函数
请思考以下问题：
任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）
计算这个值的方法就叫做欧拉函数，以φ(n)表示。在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(n) = 4。
φ(n) 的计算方法并不复杂，但是为了得到最后那个公式，需要一步步讨论。
第一种情况
如果n=1，则 φ(1) = 1 。因为1与任何数（包括自身）都构成互质关系。
第二种情况
如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。
第三种情况
如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则
比如 φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4。
这是因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、…、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。
第四种情况
如果n可以分解成两个互质的整数之积，
n = p1 × p2
则
φ(n) = φ(p1p2) = φ(p1)φ(p2)
即积的欧拉函数等于各个因子的欧拉函数之积。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。
这一条的证明要用到“中国剩余定理”，这里就不展开了，只简单说一下思路：如果a与p1互质(a<p1)，b与p2互质(b<p2)，c与p1p2互质(c<p1p2)，则c与数对 (a,b) 是一一对应关系。由于a的值有φ(p1)种可能，b的值有φ(p2)种可能，则数对 (a,b) 有φ(p1)φ(p2)种可能，而c的值有φ(p1p2)种可能，所以φ(p1p2)就等于φ(p1)φ(p2)。
第五种情况
因为任意一个大于1的正整数，都可以写成一系列质数的积。
1.3 欧拉定理
欧拉函数的用处，在于欧拉定理。”欧拉定理”指的是：
如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：
也就是说，a的φ(n)次方被n除的余数为1。或者说，a的φ(n)次方减去1，可以被n整除。比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。
欧拉定理的证明比较复杂，这里就省略了。我们只要记住它的结论就行了。
欧拉定理可以大大简化某些运算。比如，7和10互质，根据欧拉定理，
已知 φ(10) 等于4，所以马上得到7的4倍数次方的个位数肯定是1。
因此，7的任意次方的个位数（例如7的222次方），心算就可以算出来。
欧拉定理有一个特殊情况。
假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成
这就是著名的费马小定理。它是欧拉定理的特例。
欧拉定理是RSA算法的核心。理解了这个定理，就可以理解RSA。
1.4 模反元素
还剩下最后一个概念：
如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。
这时，b就叫做a的“模反元素”。
比如，3和11互质，那么3的模反元素就是4，因为 (3 × 4)-1 可以被11整除。显然，模反元素不止一个， 4加减11的整数倍都是3的模反元素 {…,-18,-7,4,15,26,…}，即如果b是a的模反元素，则 b+kn 都是a的模反元素。
欧拉定理可以用来证明模反元素必然存在。
可以看到，a的 φ(n)-1 次方，就是a的模反元素。
2. RSA加密
RSA的加密过程可以使用一个通式来表达
也就是说RSA加密是对明文的E次方后除以N后求余数的过程。就这么简单？对，就是这么简单。
从通式可知，只要知道E和N任何人都可以进行RSA加密了，所以说E、N是RSA加密的密钥，也就是说E和N的组合就是公钥，我们用(E,N)来表示公钥
不过E和N不并不是随便什么数都可以的，它们都是经过严格的数学计算得出的，关于E和N拥有什么样的要求及其特性后面会讲到。顺便啰嗦一句E是加密（Encryption）的首字母，N是数字（Number）的首字母
3. RSA解密
RSA的解密同样可以使用一个通式来表达
也就是说对密文进行D次方后除以N的余数就是明文，这就是RSA解密过程。知道D和N就能进行解密密文了，所以D和N的组合就是私钥
从上述可以看出RSA的加密方式和解密方式是相同的，加密是求“E次方的mod N”;解密是求“D次方的mod N”
此处D是解密（Decryption）的首字母；N是数字（Number）的首字母。
小结下
| 公钥 | （E，N） |
| 私钥 | （D，N） |
| 密钥对 | （E，D，N） |
此处D是解密（Decryption）的首字母；N是数字（Number）的首字母。
4. 生成密钥对
既然公钥是（E，N），私钥是（D，N）所以密钥对即为（E，D，N）但密钥对是怎样生成的？步骤如下：
- 求N
- 求L（L为中间过程的中间数）
- 求E
- 求D
4.1 求N
准备两个质数p，q。这两个数不能太小，太小则会容易破解，将p乘以q就是N
N = p * q
4.2 求L
L 是 p－1 和 q－1的最小公倍数，可用如下表达式表示
L=lcm（p－1，q－1）
4.3 求E
E必须满足两个条件：E是一个比1大比L小的数，E和L的最大公约数为1
用gcd(X,Y)来表示X，Y的最大公约数则E条件如下：
1 < E < L
gcd（E，L）=1
之所以需要E和L的最大公约数为1是为了保证一定存在解密时需要使用的数D。现在我们已经求出了E和N也就是说我们已经生成了密钥对中的公钥了。
4.4 求D
数D是由数E计算出来的，D与L互质。D、E和L之间必须满足以下关系：
1 < D < L
E＊D mod L ＝ 1
D=gmpy2.invert(E,L)
只要D满足上述2个条件，则通过E和N进行加密的密文就可以用D和N进行解密。
简单地说条件2是为了保证密文解密后的数据就是明文。
现在私钥自然也已经生成了，密钥对也就自然生成了。
小结下：
| 求N | N＝ p ＊ q ；p，q为质数 |
| 求L | L＝lcm（p－1，q－1） ；L为p－1、q－1的最小公倍数 |
| 求E | 1 < E < L，gcd（E，L）=1；E，L最大公约数为1（E和L互质） |
| 求D | 1 < D < L，E＊D mod L ＝ 1 |
4.5 加密
密文＝明文^E mod N
C=M^E mod N
C=pow(M,E,N)
4.6 解密
明文＝密文^D mod N
M=C^D mod N
M=pow(C,D,N)
二，RSA 解密常用库和函数
1. gmpy2 库
1.1 gmpy2.mpz(x)
初始化一个大整数x
1.2 gmpy2.mpfr(x)
初始化一个高精度浮点数x
1.3 C = gmpy2.powmod(M,e,n)
幂取模，结果是 C = (M^e) mod n
1.4 d = gmpy2.invert(e,L)
求逆元，de = 1 mod L（D和L互质，D和E互为逆元）
1.5 gmpy2.is_prime(n)
判断n是不是素数
1.6 gmpy2.gcd(a,b)
欧几里得算法，最大公约数
1.7 gmpy2.gcdext(a,b)
扩展欧几里得算法
1.8 gmpy2.iroot(x,n)
x开n次根
2. libnum 库
2.1 libnum.s2n(s)
字符串转换为数字。
1 | import libnum |
2.2 libnum.s2n(n)
数字转换为字符串。
1 | import libnum |
2.3 libnum.s2b(s)
字符串转换为二进制字符串。
1 | import libnum |
2.4 libnum.b2s(b)
二进制字符串转换为字符串。
1 | import libnum |
2.5 Primes
2.5.1 libnum.primes(n)
返回不大于n的素数列表。
1 | import libnum |
2.5.2 libnum.generate_prime(n)
产生长度为n位的伪素数。
1 | import libnum |
2.6 其它
2.6.1 libnum.factorize(n)
返回n的所有素因子及每个素因子的个数。
1 | import libnum |
2.6.2 libnum.modular.invmod(e,m)
返回e模m的逆元。
1 | import libnum |
其他查看：https://github.com/hellman/libnum
3. Crypto.Util.number 库
3.1 long_to_bytes()
1 | long_to_bytes(0x41424344) |
3.2 bytes_to_long()
1 | bytes_to_long(b'hello') |
3.3 GCD
1 | GCD(a,b) |
3.4 inverse()
1 | inverse(10,5) |
3.5 getRandomRange()
3.6 isPrime()
1 | isPrime(1227) |
3.7 size()
3.8 getStrongPrime()
1 | getStrongPrime(512) |
3.9 ceil_div()
3.10 ceil_shift()
3.11 floor_div()
3.12 exact_div()
3.13 exact_log2()
3.14 getPrime()
1 | getPrime(16) |
https://www.cnblogs.com/pcheng/p/9629621.html
https://blog.csdn.net/qq_42876636/article/details/87559366
https://www.jianshu.com/p/685cfeffe703
套路：https://err0rzz.github.io/2017/11/14/CTF%E4%B8%ADRSA%E5%A5%97%E8%B7%AF/index.html
https://www.anquanke.com/post/id/84632
题型总结：https://blog.csdn.net/vhkjhwbs/article/details/101160822