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

关于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加解密的条件

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)

等式得证。

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

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

c++文件：

头文件：

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

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

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

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课