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