RSA概述

RSA是一种非对称加密算法，在公开密钥加密和电子商业中RSA被广泛使用。公钥（Public Key）与私钥（Private Key）是通过一种算法得到的一个密钥对（即一个公钥和一个私钥），公钥是密钥对中公开的部分，私钥则是非公开的部分。公钥通常用于加密会话密钥、验证数字签名，或加密可以用相应的私钥解密的数据。

预备知识

模运算 mod

在正整数范围内选取a，b，分别对另一个正整数n进行取余运算，得到，，如果，则称a与b关于n同余，记作

模逆运算

如果正整数a，b，n满足，则称a与b互为模n的逆元，记作

python实现：

from gmpy2 import *
a = 114514
n = 1919810
b = invert(a,n)
#b即为a关于n的逆元

其余模运算基本原理可以参照这篇文章：https://blog.sengxian.com/algorithms/mod-world

欧拉函数 phi

的值表示小于等于n的正整数之中，有多少个数与n构成互质关系。

1.若，则，因为1与任何数都构成互质关系

2.若为质数，则，因为任何一个质数与小于它的所有数都构成互质关系

3.若，其中p为质数，则

4.若可以分解成两个互质的整数之积，即n，则。

欧拉定理

若两个正整数a和n互质，则n的欧拉函数 可以让下面的等式成立：当n为质数时，欧拉定理可以化为： 这就是费马小定理，它是欧拉定理的特例。

---

How to ENCRYPT?

1.首先，我们选取两个不相同的大素数p和q，并计算

2.计算

3.选取一个小于，且与互质的不太小的正整数e

4.计算e在模n下的逆元d，即

5.(n, e)封装为公钥，(p, q, d)封装为私钥

6.将密文转码为十六进制数据m

7.，c即为可以传输的密文

至此RSA加密完成

---

How to DECRYPT?

最简单的情况：已知p，q，e，c

1.计算

2.计算逆元

3.

即可得到明文

---

解密算法证明

分两种情况证明，与

m与n互质

$$\begin{align} c^d&=m^{ed}\\ &=m^{k\phi(n)+1}&(mod\ n)\\ \because ed&=1&(mod\ \phi(n))\\ \therefore c^d&=[m(m^{\phi(n)}\ (mod\ n))^k]\\ &=m&(mod\ n)\\ &=m\\ \end{align}$$

m与n不互质

由于m与n不互质，所以m与n必定有一个大于1的公因子，而由于，且p与q均为质数，所以，

由于

$$\begin{align} m^{ed}&=m^{k\phi(n)+1}\\ &=m^{k(p-1)(q-1)+1}\\ &=m(m^{q-1}\ (mod\ q))^{k(p-1)}\\ &=m&(mod\ q)\\ \end{align}$$

即

假设，则有

$$\begin{align} m^{ed}&={(cp)}^{ed}\\ &=0&(mod\ p)\\ \because m\ mod\ p&=0\\ \therefore tq\ mod\ p&=0\\ \because gcd(p,q)&=1\\ \therefore t&=rp&(t\in N^{*})\\ \end{align}$$

由此可以得到

$$\begin{align} m^{ed}&=(m+tq)\\ &=(m+rpq)\\ &=(m+rn)&(mod\ n)\\ &=m\\ \end{align}$$

至此证明完毕