RSA加密算法

我就是我 2022-05-09 04:50 173阅读 0赞

# RSA加密算法基于大数因数分解问题 #

--------------------

具体过程：

1.A选取两个大质数P1、P2 并计算出![N= P1\\times P2][N_ P1_times P2]，公开N

2.利用欧拉函数性质：![\\phi \\left ( N \\right )= \\left(P1-1\\right) \\right )\\times \\left (P2-1 \\right )][phi _left _ N _right _ _left_P1-1_right_ _right _times _left _P2-1 _right]

在选取一个E，满足![gcd\\left ( E,\\phi \\left (N \\right ) \\right )=1][gcd_left _ E_phi _left _N _right _ _right _1],即E与![\\phi \\left(N \\right )][phi _left_N _right] 互质

3.利用某一公式：![d=\\frac\{a\\times \\phi \\left ( N \\right) +1\}\{E\}][d_frac_a_times _phi _left _ N _right_ _1_E]  其中可以试a 与 d 的值 保证都是正整数，方便计算，将d作为自己的密钥用于解密。

4.B将自己的密文M转化为数字，然后利用A公开的E，N得到密文![C=M^E mod N][C_M_E mod N]，将C发给A

5.A就可以利用公式：![M=C^d mod N][M_C_d mod N]计算出M 得到B的密文

--------------------

具体过程如图（点击进入全屏）：

![RSA][]

[N_ P1_times P2]: https://private.codecogs.com/gif.latex?N%3D%20P1%5Ctimes%20P2
[phi _left _ N _right _ _left_P1-1_right_ _right _times _left _P2-1 _right]: https://private.codecogs.com/gif.latex?%5Cphi%20%5Cleft%20%28%20N%20%5Cright%20%29%3D%20%5Cleft%28P1-1%5Cright%29%20%5Cright%20%29%5Ctimes%20%5Cleft%20%28P2-1%20%5Cright%20%29
[gcd_left _ E_phi _left _N _right _ _right _1]: https://private.codecogs.com/gif.latex?gcd%5Cleft%20%28%20E%2C%5Cphi%20%5Cleft%20%28N%20%5Cright%20%29%20%5Cright%20%29%3D1
[phi _left_N _right]: https://private.codecogs.com/gif.latex?%5Cphi%20%5Cleft%28N%20%5Cright%20%29
[d_frac_a_times _phi _left _ N _right_ _1_E]: https://private.codecogs.com/gif.latex?%5Cfn_cm%20d%3D%5Cfrac%7Ba%5Ctimes%20%5Cphi%20%5Cleft%20%28%20N%20%5Cright%29%20&plus;1%7D%7BE%7D
[C_M_E mod N]: https://private.codecogs.com/gif.latex?%5Cfn_cm%20C%3DM%5EE%20mod%20N
[M_C_d mod N]: https://private.codecogs.com/gif.latex?%5Cfn_cm%20M%3DC%5Ed%20mod%20N
[RSA]: /images/20220509/9a4c24e9c42e4e6bbbb8a0f5a495b44d.png