RSA加密算法（改编）

一，简介

RSA加密算法又称“非对称加密算法”，大致流程为：

（1）乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。

（2）甲方获取乙方的公钥，然后用它对信息加密。

（3）乙方得到加密后的信息，用私钥解密。

在以太坊系统中，公钥由私钥通过椭圆曲线加密(ECC)得到，选取的曲线为secp256k1。

二，互质关系

任意两个质数构成互质关系。(13,61)
一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系。(3,10)
两个数中较大的是质数，两者构成互质关系。(97,57)
1和任意一个自然数都是互质关系。(1,99)
p是大于一的整数，则p和p-1构成互质关系。(57,56)
p是大于一的奇数，则p和p-2构成互质关系。(17,15)

三，欧拉函数

欧拉函数用来计算在小于n的任意整数中，有多少个与n构成互质关系。比如φ(8) = 4,(1,2,5,7与8构成互质关系)

如果n等于1，则
$φ(1)=1。$
如果n是质数，则
$φ(n)=n-1$
如果n是质数的某一个次方，即n=p^k(p为质数，k为大于等于1的整数)，则
$\phi(p^{k})=p^{k}-p^{k-1}$
比如：φ(8)=φ(2^3)=2^3-2^2
如果n可以分解为两个质数的乘积之积
$n = p_{1}*p_{2}$
则
$\phi({n}) = \phi({p_{1}p_{2}}) = \phi(p_{1})\phi(p_{2})$
比如：φ(56)=φ(8*7)=φ(8)*φ(7)=4*6=24
任意大于1的整数，都可以写成一些列质数的积
$n = p^{k_{1}}_{1}p^{k_{2}}_{2}\cdots p^{k_{r}}_{r}$
根据第4条结论，得到
$\phi(n) = \phi(p^{k_{1}}_{1})\phi(p^{k_{2}}_{2})\cdots\phi(p^{k_{r}}_{r})$
再根据第3条结论，得到
$\phi(n) = p^{k_{1}}_{1}p^{k_{2}}_2\cdots p^{k_{r}}_{r}(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})\cdots(1-\frac{1}{p_{r}})$
也就等于
$\phi(n) = n(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})\cdots(1-\frac{1}{p_{r}})$
这就是欧拉函数的通用计算公式。

比如：φ(1323)=φ(3^3*7^2)=1323(1-1/3)(1-1/7)=756

四，欧拉定理

如果两个正整数a和n互质，则n的欧拉函数φ(n)可以让下面的等式成立：
$a^{\phi(n)}\equiv1(\mathit{mod\ n})$
也就是说，a的φ(n)次方被n除的余数为1。或者说，a的φ(n)次方减去1，可以被n整除。

比如：[3^(φ(7))-1]/7=[3^6-1]/7=104

五，模反元素

如果两个正整数a和n互质，那么一定可以找到正整数b，使得ab-1被n整除，或者说ab被n整除的余数是1。
$ab\equiv1(\mathit{mod\ n})$
这时b就叫a的模反元素。

比如：3*4=1(mod 11)

显然，模反元素不止一个，如果b是a的模反元素，那么b+kn都是a的模反元素。

六，密钥生成步骤

1，随机选择两个不相等的质数p和q

比如：选择61和53。（质数越大越安全）

2，计算p和q的乘积n

比如：n = 61*53 = 3233

3，计算n的欧拉函数φ(n)

比如：φ(3233) = φ(61)φ(53) = 60*52 = 3120

4，随机选一个整数e，条件是1<e<φ(n),且e与φ(n)互质

比如：随机选择17

5，计算e对于φ(n)的模反元素d

$ed\equiv1(mod\ \phi(n))$

这个式子等价于求
$ex +\phi(n)y=1$
的解，已知e=17，φ(n)=3120
$17x+3120y=1$
算出一组整数解为(x,y)=(2753,-15)

所以d=2753

6，将n和e封装成公钥，n和d封装成私钥

比如：n=3233, e=17, d=2753, 所以公钥就是(3233,17),私钥就是(3233,2753)

七，RSA算法的可靠性

已知n和e，若要算出d，等价于解出下面这个方程
$ed\equiv1(mod\ \phi(n))$
所以需要计算φ(n)
$\phi(n)=(p-1)(q-1)$
所以需要知道p和q，但是大整数的因式分解是一件十分困难的事，目前除了暴力破解别无他法。(p，q算出φ(n)后立即销毁)

八，加密解密

乙向甲发送原始信息m，首先，用公钥(n,e)对m进行加密。所谓加密，就是算出如下式的c：
$m^e\equiv c(mod\ n)$
比如：m是65
$65^{17} \equiv 2790 (mod\ 3233)$
所以c等于2790。

解密用私钥(n,d)
$c^d\equiv m(mod\ n)$

$2790^{2753}\equiv65(mod\ 3233)$

计算得原文就是65。

对于比n大的整数，可以把信息分为若干段或者先用对称加密的算法加密信息然后再用RSA。

九，解密证明

$m^{e\cdot d}\equiv c^{d}(mod\ n)$