RSA 复习—阮一峰日志学习笔记
1. RSA算法产生的背景:
1976年以前，所有的加密方法都是同一种模式：
对称加密算法
（1）甲方选择某一种加密规则，对信息进行加密；
（2）乙方使用同一种规则，对信息进行解密。
弱点：
甲方必须把加密规则告诉乙方，否则无法解密。
传递密钥的安全性无法保证，一旦传递过程中，加密规则被截获就失去了加密的意义。
这时，新的加密方法便应运而生：
非对称加密算法
（1）乙方生成两把密钥（公钥和私钥）。
公钥是公开的，任何人都可以获得，私钥则是保密的。
（2）甲方获取乙方的公钥，然后用它对信息加密。
（3）乙方得到加密后的信息，用私钥解密。
此时，乙方只要公布他的公钥，甲方就可以通过公钥对发送的信息进行加密然后将密文给到乙方。奇妙的地方在于，以世界目前算力，只有乙方用手上的私钥才能解密获得明文，而解密的钥匙没有经过传递，安全性得到了保障。
RSA算法属于非对称密码。
2. 数学知识储备
·互质关系
如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。
比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。
互质结论:
- 任意两个质数构成互质关系，比如13和61。
- 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。
- 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。
- 1和任意一个自然数是都是互质关系，比如1和99。
- p是大于1的整数，则p和p-1构成互质关系，比如57和56。
- p是大于1的奇数，则p和p-2构成互质关系，比如17和15。
以上看过一遍，理解就好，不需要刻意记忆。
以下要求理解记忆，越熟练越好！
·欧拉函数
引入：
任意给定正整数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 = pk (p为质数，k为大于等于1的整数)，则:
比如 φ(8) = φ(23) =23 - 22 = 8 -4 = 4。
这是因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有pk-1个，即1×p、2×p、3×p、…、pk-1×p，把它们去除，剩下的就是与n互质的数。
上面的式子还可以写成下面的形式：
可以看出，上面的第2种情况是 k=1 时的特例。
如果n可以分解成两个互质的整数之积，n = p1 × p2，则：
φ(n) = φ(p1p2) = φ(p1)φ(p2)
即积的欧拉函数等于各个因子的欧拉函数之积。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。
这一条的证明要用到“中国剩余定理”，这里就不展开了
因为任意一个大于1的正整数，都可以写成一系列质数的积。
根据第4条的结论，得到:
再根据第3条的结论，得到:
也就等于
这就是**欧拉函数的通用计算公式**
比如，1323的欧拉函数，计算过程如下：
·欧拉定理
定义
如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：
注：补充知识—同余
同余可理解为，a的phi(n)次方除n的余数 = 1除n的余数（就是1）
也就是说，a的φ(n)次方被n除的余数为1。或者说，a的φ(n)次方减去1，可以被n整除。比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。
欧拉定理特殊情况
假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成
这就是著名的费马小定理。它是欧拉定理的特例。
·模反元素
定义
如果两个正整数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的模反元素。
3. RSA加解密
·密钥生成的步骤
第一步，随机选择两个不相等的质数p和q。
·比如乙方选择了61和53。第二步，计算p和q的乘积n。
·n = 61×53 = 3233第三步，计算n的欧拉函数φ(n)。
·φ(n) = (p-1)(q-1)
·φ(3233) = 60×52 = 3120第四步，随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
·乙方从1到3120选择了 17（实际应用中，常选65537）第五步，计算e对于φ(n)的模反元素d。
·所谓“模反元素”就是指有一个整数d，可以使得ed被φ(n)除的余数为1
·ed ≡ 1 (mod φ(n)) 等价于 ed - 1 = kφ(n) 等价于 ex + φ(n)y = 1 等价于 17x + 3120y = 1
·用“扩展欧几里得算法”求解*（具体代码看RSA WriteUP），得：(x,y)=(2753,-15)，即 d=2753。第六步，n和e为公钥，n和d为私钥。
· 知道n,e为公钥（公布出去）,n和d为私钥（自己藏着）。
·加密和解密
（1）加密要用公钥 (n,e)
·甲方拿到n,e 。要将明文65加密成密文（m为明文，c为密文）
·利用公式（mod（n）是除于n取余数的意思）
·得：c = 2790
（2）解密要用私钥(n,d)
·乙方收到密文m，自己手里有公钥，当然也有密钥n，d
·利用公式
·得：m = 65 ，则RSA算法加解密原理到此结束
4. CTF中RSA算法题
·需要安装的第三方库
解题一般用python，这里需要安装两个库pycryptodome、gmpy2
在pycharm的下方Terminal中分别输入：
1 | pip install pycryptodome |