# RSA学习

## 1.形式

有公钥和私钥

1.单项计算容易，但逆向很难

模运算是单项函数

计算
$$
3^3 mod 7 =6 
$$
很容易

但是知道
$$
3^xmod7=6
$$
计算x很难



## 2.加密

对于一个数
$$
m^e mod N =c
$$
其中e为秘钥,c为密文

## 3.解密

$$
c^d mod N = m
$$



其中d是解密的秘钥



## 4.变换

将两个公式合并，可以得到
$$
m^{ed} \; mod \; N =m
$$
那么可以得到
$$
m^{ed}\; \equiv \; m
$$


### 引入

欧拉函数：
$$
φ(p)=p-1 
$$
其中**p为质数**

如果(p,q)=1,有这个性质
$$
φ(p*q)=φ(p)*φ(q)
$$


不知道为啥

#### 这里解释一下为什么可以这么推

首先有欧拉定理：
$$
m^φ(n)\equiv 1 (mod \; n)
$$
可以在等式的两端同时取k次幂
$$
(m^{φ(n)})^k\equiv 1^k (mod \; n)
$$
然后等式两端同时乘以m
$$
m^{kφ(n)+1} \equiv m \; (mod \; n)
$$
然后模运算变形
$$
m^{kφ(n)+1}  \; mod \; n = m
$$
这个式子和这个类似
$$
m^{ed} \; mod \; n =m
$$
可以得到
$$
ed=kφ(n)+1
$$
然后可以选取`k,n,e`来获得`d`



### 然后

我们可以知道
$$
d = \frac{kφ(n)+1}{e}
$$
此时，如果e=3

取一个p=17,q=23,其中（17,23）=1

那么可以得到
$$
φ(17*23)=φ(391)=352
$$
e=3,k=5
$$
d=\frac{kφ(n)+1}{e}=\frac{5*352+	1}{3}=587
$$
这样

e：公钥

d：私钥

都有啦



然后把 `e:公钥`和`n:`公布

 

### 例子

当前

公钥e=3，私钥d=587，n=391

要加密的数据为97


$$
97^3 \; mod \; 391 = 79
$$
97为加密后的密文



解密：
$$
79^{587} \; mod = 97
$$
还原

用了587这个秘钥



嗯，暂时就这样啦



# 补充

e需要满足：
$$
1<e<φ(n)
$$
且
$$
(e,φ(n))=1
$$
还有这个性质
$$
m^{kφ(n)} \; mod \;n =1
$$
其中`n`为前面欧拉函数的计算结果

