# RSA公钥加密算法

保障终端间信息传输的安全一直是业务的刚性需求。 针对不同业务需求的不同加密算法，

因为公司是金融公司，不是传统的金融公司（PS：涉及数字货币，比如比特币），所以对加密算法是有部分了解的。

这里要说的内容如题

电子签名

质数

在密码学中，有必要找到最大的随机素数。 大素数很多，通常会适当地测试随机整数，直到找到素数的过程可行为止。

素数分布函数π(n)：描述小于等于n的素数个数

素数定理给出了 π(n) 的有用近似值：

$$ \lim_{n \to +\infty} \frac{π(n)}{n/(\ln n)} \quad = 1 $$

例如：

当n = 10^9时，误差不超过6%。 它：π(n)=508,475,34，而n/ln * n≈482,549,42

伯努利实验

RSA基于素数原理：找到一个大的素数很容易，但是把一个数分解成两个最大素数的乘积就相当困难了

公钥加密

公钥加密，顾名思义，有公钥和私钥

在 RSA 加密算法中，每个密钥由一对整数组成。 在密码学中，爱丽丝和鲍勃经常被用作例子。 这也是有人在普及比特币相关技术时出现频率比较高的一个词。

如图：用$P_A$代表Alice的公钥，用$S_A$代表Alice的私钥

同理：

如图：用$P_B$表示Bob的公钥，$S_B$表示Bob的私钥

秘钥需要保密，公钥可以公开给任何人，这和比特币地址一样。

公钥和私钥指定可用于任何信息的函数。 让 $\mathfrak{D}$ 表示允许的信息集。 它可能是所有有限长度的比特序列的集合。

在最原始的公钥加密思想中，要求公钥和秘钥指定一个从$\mathfrak{D}$到自身的一一对应函数。 Alice的公钥$P_A$对应的函数用$P_A()$表示，而他的私钥$S_A$的函数用$S_A()$表示，所以$P_A()$和$S_A的函数()$ 都是 $\mathfrak{D}$ 的排列。 设置已知秘钥$P_A$或$S_A$，可以有效计算函数$P_A()$和$S_A()$

系统中任何一个参与者的公钥和秘钥都是一对“匹配对”，它们指定的函数互为反函数，即对于任意消息$M\in\mathfrak{D}$有：

$$ M = S_A(P_A(M)) \ M = P_A(S_A(M)) $$

由此可见，在使用两个秘钥$P_A$和$S_A$依次对$M$进行变换后，最终还是得到了消息$M$

因此，在应用程序中：要求除了Alice之外，没有人能在更实际的时间内计算出函数$S_A()$。 发送给 Alice 的加密邮件的机密性和 Alice 数字签名的有效性。

因为$P_A$是公开的，就像数字货币的地址一样，可以计算出$P_A()$，也就是$S_A()$的反函数。 这时候需要保证只有Alice可以计算$S_A()$。

模拟发送环境：

如上图：Bob向Alice发送了一条加密消息，他窃取的是一串乱码。

Bob 得到 Alice 的公钥 $P_A$

Bob计算出M对应的密文$C=P_A(M)$btc加密算法，将C发送给Alice

爱丽丝得到密文C后btc加密算法，用她的秘钥$S_A$还原出原来的信息：$S_A(C)=S_A(P_A(M))=M$。

由于$S_A()$和$P_A()$互为反函数，Alice可以根据C计算出M。因为只有Alice可以计算出$S_A()$，所以也只有Alice可以根据C计算出M。因为Bob用 $P_A$ 加密 M，只有 Alice 可以理解收到的消息。

数字签名可以用类似公钥系统的思想轻松实现，现在Alice希望发送一个数字签名的回复M^'给Bob

在公钥数字签名中，Alice 通过将她的数字签名 $\sigma = S_A(M')$ 附加到消息 M' 来签署消息 M'。 她将消息/签名对 $(M', \sigma)$ 发送给 Bob，Bob 通过检查等式 $M' = P_A(\sigma)$ 来验证它。如果等式成立，他接受 $(M',\ sigma)$ 和爱丽丝一样

签名消息

Alice 使用她的密钥 $S_A$ 和等式 $\sigma = S_A(M')$ 来计算消息 M' 的数字签名 $\sigma$。

Alice 将消息/签名对 $(M', \sigma)$ 发送给 Bob。

当 Bob 收到 $(M', \sigma)$ 时，他可以使用 Alice 的公钥通过验证等式 $M' = P_A(\sigma)$ 来验证消息确实来自 Alice。

如果 M' 包含爱丽丝的名字，那么鲍勃就知道要使用谁的公钥。

从上图中的验证可以看出，如果遇到了Bob，则可以断定消息M'确实是Alice的签名。 如果不是，那么 Bob 可以得出一个结果：要么信息 M' 或数字签名 $\sigma$ 因传输错误而损坏，要么信息对 $(M',\sigma)$ 是故意伪造的。

因为数字签名证明了签名者的身份和签名的消息内容，所以它类似于文档末尾的手写签名。

数字签名必须能够被能够获得签名者公钥的人验证，并且签名的消息能够被确认然后发送给能够验证签名的其他方。

比如我给你的一个比特币，其实就是一个签名过程，但是比特币使用了多重签名加密技术，比这个复杂的多（做区块链开发的人可能会笑），原理是什么？ 羊毛布？ 密码学中的一个流行示例：

爱丽丝给鲍勃一张电子支票。 Bob 确认 Alice 在支票上的签名后，就可以将支票交给银行，银行也可以验证签名，然后转账相应的资金。

上面我说的是签名信息没有加密，信息公开透明。 例如，比特币的交易过程是公开透明的。 该行为会向全网广播，同时，每个节点都可以同步到交易事件。

我们这里要说的恰恰相反。 我们需要加密信息。 如何加密？ 它是将加密和签名两种方案结合起来，创建一个同时被签名和加密的消息。 签名者首先将他的数字签名附加到消息中，然后使用他预期的接收者的公钥加密最终的消息/签名对。 接收方用自己的密钥对收到的消息进行解密，得到原始消息和数字签名。 收件人然后可以使用签名者的公钥验证签名。 有趣的！

RSA加密系统

公钥私钥创建过程

1.随机选择最大的素数$\mathcal{P}$和$\mathcal{q}$，使得$\mathcal{P}\not=\mathcal{q}$ eg：素数$\mathcal{P }$ 和 $\mathcal{q}$ 可能各有 1024 位。

2. 计算$n=\mathcal{P} \mathcal{q}$

3. 选择一个与 $\phi(n)$ 互质的最小奇数 e，其中等式 $\phi(n)$ 等于 ($\mathcal{P}-1$)($\mathcal{ q}- 1$)

4. 对于模 $\phi(n)$，计算 e 的乘法逆元 d 的值。

5. 公开 $P=(e,n)$ 并将其用作参与者的 RSA 公钥

6. 对 $S=(d,n)$ 保密并将其用作参与者的 RSA 密钥

设 $D$ 为集合 $Z_n$。 要转换与公钥 $P=(e,n)$ 关联的消息 $M$，请计算 $$P(M) = M^e\mod n$$

此时对秘钥$S =(d,n)$相关的密文C进行变换，计算$$S(C)=C^d \mod n$$

上面看到的等式对于加密和签名都是通用的。 要创建签名，签名者将他的密钥应用于要签名的消息，而不是密文。 为了验证签名，签名者的公钥应用于签名，而不是加密的消息。

利用模数的求幂过程对公钥和私钥进行一些运算。

我们假设公钥(e,n)和秘钥(d,n)满足$\lg e = O(1)$, $\lg d \leq \beta$, $\lg n \leq \beta $。

然后应用公钥需要 $O(1)$ 模乘运算和 $O(\beta^2)$ 按位运算。 应用密钥需要执行 $O(\beta)$ 次模乘运算 $O(\beta^3)$ 次运算。

RSA 安全保证

RSA加密的安全性主要来自于分解最大整数的难度。 如果对方分解公钥中的模数n，则可以从公钥中推导出秘钥，主要是因为对方和公钥的创建者利用了$\mathcal{P}$和$\mathcal这两个因子{q}$。 因此，如果可以分解一个大整数，就可以轻松破解RSA加密算法。

这样：破解RSA加密系统的难度就取决于分解最大整数的难度。

在计算机发展史上，没有比分解模 n 更容易破解 RSA 加密的方法了。

通过随机选取两个 1024 位素数并取其乘积，可以创建一个公钥，并且可以在现有技术可行的时间内破解。 也就是说，在算法发展史上还没有新的突破的时候，RSA加密算法是一种安全保障。

基于以上讨论的原则，实际实现过程中选择的位元素个数通常在768～2048位范围内。 因此，需要能够高效地找到最大的素数。

在实际应用中，为了提高效率，使用时间最长的是RSA这种密钥管理方式，实现快速的免公钥加密系统。 在这样的系统中，加密密钥与解密密钥相同。

例如：

Alice向Bob发送一条长消息M，她从快速公钥无钥加密系统中随机选择一个秘钥K，然后用K加密M得到密文C，此时C的长度与M一样长, 但 K 很短。 在第一步中，Alice 使用 Bob 的公共 RSA 密钥加密 K。 由于 K 很短，$P_B(K)$ 的计算也很快。 $t_1 = P_B(K)计算时间$，$t_2 = P_B(M)计算时间$，有：$t_1 > t_2$。

最后Alice将$(C,P_B(K))$发送给Bob，Bob解密$P_B(K)$得到K，再用K解密C得到M。

通过上面的例子，我们了解到采用混合方式来提高数字签名的执行效率。

将 RSA 与公共抗碰撞哈希算法 h 相结合。 使用这个函数的目的是找到两条消息M和M'，h(M)=h(M')。

h(M)的值是消息M的一个短“指纹”的想法。

如果 Alice 对消息 M 签名，她的第一步是将函数 h 应用于 M 获得的指纹 h(M)，然后用她的密钥加密 h(M)。 Alice 将 $(M,S_A(h( M)))$ 作为她签名的 M 版本发送给 Bob。Bob 可以验证它是否等于 h( M) 以验证签名的真实性。

原理：任何人都不能同时创建两条具有相同指纹的消息，因此无法在计算机上更改已签名的消息并保持签名的有效性。

因此可以使用证书轻松分发公钥。

例如：

公共网络中有一个T，每个人都知道它的公钥。 Alice 从 T 那里得到一个签名证书，表明“Alice”的公钥是 $P_A$。 由于每个人都知道 $P_T$，因此该证书是“自我证明”的。 Alice 可以在签名消息中包含她自己的证书，这样接收方就可以立即得到 Alice 的公钥来验证她的签名。 因为 Alice 的密钥是由 T 签名的，所以接收方知道 Alice 的密钥确实是 Alice 自己的密钥。