← 返回文章档案

RSA学习日志

更新于 2021.09.20下载原始 Markdown ↓

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为前面欧拉函数的计算结果