文章目录

前言
相关介绍
一、变量
二、公式
三、RSA
[1]. 发布公钥（n,e）
[2]. 发布密文（c）
[3]. RSA解密
四、总结

前言

文章首发于CSDN，安全-RSA算法基础
此篇文章的内容是从书本上概况下来的
每轮信息发送时，攻击者、接收者、发送者得到的新信息以高亮的形式体现

相关介绍

yafu大素数分解

一、变量

先介绍一下RSA算法当中可能会出现的变量，顺序从A-Z

二、公式

^表示次方
mod表示取模，即求余数

n = p*q

φ(n) = (p-1)*(q-1)

c = ( m^e ) mod n

d = 1 mod φ(n) / e

m = ( c^d ) mod n

dp = d * (p - 1)

dq = d * (q - 1)

三、RSA

为了方便理解，分成了发布者、接收者、攻击者来模拟现实的情况。

[1]. 发布公钥（n,e）

刚开始时，发布者先广播了一条内容：我有消息需要发给接收者
然后接收者和攻击者都明白了发布者要发布内容。

接收者为了让发布者能更好地隐藏内容，提议使用RSA算法。
然后接收者先确定了两个素数p和q，再确定了一个素数e
通过p和q，由公式计算出了n，接收者就在网络中发布了公钥（n，e）

此时网络中的三人所拥有的信息如下：

用到的公式

n = p*q
φ(n) = (p-1)(q-1)

[2]. 发布密文（c）

当接收到了公钥（n，e）之后，发布者先将需要传输的内容通过hex等方法转换成了数字m
由公式计算出了c，并通过广播发布了（c）

此时网络中的三人所拥有的信息如下：

注：表格高亮处为此步骤中用户新得知的内容

用到的公式

c = ( m^e ) mod n

[3]. RSA解密

接收者接收了c之后，就可以开始解密的步骤了
先由公式计算出中间量d，然后再由公式计算出m
最后将m进行hex的方式进行转码后，得到了明文
私钥即为（n，d）

此时网络中的三人所拥有的信息如下：

用到的公式|

d = 1 mod φ(n) / e

m = ( c^d ) mod n

四、总结

如果公钥（n,e）中的n数值过小时，对应的p和q就容易通过脚本爆破出来
攻击者得到了p和q时，同样能够进行RSA解密的操作
通常来说2048位以上的n是安全的，你可以参考yafu大素数分解来将n分解成p和q