经常看到各位大佬挥毫泼墨，就算法和密码问题各抒己见，小弟今天斗胆也来上一课。

关于RSA的数学原理和实现，本文根据数论中的知识给出了证明，然后是自己手撸的64位RSA算法。

1.基础知识

辗转相除法：

$a=bx+c,(a,b)=(b,c)$若a=bx+c,则(a,b)=(b,c)

证明略。

欧拉函数：

$\varphi \left(n\right)=n\ast (-/p)(-/q)=(p-)\ast (q-)$ϕ(n)=n∗(1−1/p)(1−1/q)=(p−1)∗(q−1)

证明自行百度。

2. RSA加解密的条件

1. p和q是两个大素数，欧拉函数值$\varphi \left(n\right)=n(-)(-)=(p-)(q-)$ϕ(n)=n(1−p1​)(1−q1​)=(p−1)(q−1)
2. w与$\varphi \left(n\right)$ϕ(n)互素，d是w的模欧拉值逆,即dw=1(mod n)

3. 加解密过程

加密：$c=E\left(m\right)=m^{w}modn$c=E(m)=mwmodn

解密：$m=D\left(c\right)=c^{d}modn$m=D(c)=cdmodn

4. 证明过程：

$(m^{w}modn{)}^{d}modn=m^{wd}modn[m^w=an+b,(m^{w}modn{)}^{d}modn=b^{d}modn{m}^{wd}modn=(an+b{)}^{d}modn=(an{)}^n+C_d^{n-}(an{)}^{n-}b+...+b^{d}modn=b^{d}modn]$(mwmodn)dmodn=mwdmodn[证明：假设mw=an+b,则(mwmodn)dmodn=bdmodn而mwdmodn=(an+b)dmodn=(an)n+Cdn−1​(an)n−1b+...+bdmodn=bdmodn]

所以，要证明加解密过程的正确性，即证明：
$m^{wd}modn=m$mwdmodn=m
因为：
$wd\equiv \left(mod\varphi \right(n\left)\right)$wd≡1(modϕ(n))
所以
$wd=A\varphi \left(n\right)+$wd=Aϕ(n)+1

(1). 若m与n互素
根据欧拉定理可得：
$m^{\varphi \left(n\right)}\equiv \left(modn\right)m^{k\varphi \left(n\right)+}\equiv m\left(modn\right)$mϕ(n)≡1(modn)mkϕ(n)+1≡m(modn)

(2). 若m与n不互素
因为m是合数，n=pq, 根据算数基本定理，m必包含p或者q，假设m包含q,则根据fermat定理可得，
$m^{p-}\equiv \left(modp\right)$mp−1≡1(modp)

等式得证。

屈婉玲等几位老师的《离散数学》证明如下：

例子程序(仅支持64位以内的密钥长度）

代码是自己根据数学公式一行一行写的，因为对照公式可以很容易识别各个函数的用途，所以没写注释，请大家见谅。
只是为了学习验证，可能有所缺陷，敬请批评指正。

c++文件：

头文件：

调用方式是在main函数中执行那个如下代码，main函数就先省略了：）

问题和注意事项：

1.pow_i函数中为什么要取余数？为了防止溢出？数学知识不扎实。

2.加密之前与解密之后的bit位数应该长度相同，加密之后的bit数与解密之前的bit位长度应该相同。

[培训]《安卓高级研修班(网课)》月薪三万计划，掌 握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法