RSA密码的手动算法＋快速幂算法

公钥加密方案（非对称加密算法）

1.为什么要引入公钥加密方案？

密码学中的加密方案分成对称密钥和非对称密钥（也就是我们说的公钥加密，代表加密算法是RSA加密算法）。
而对称加密方法有一个特点，任何通信的两个人都需要共享一个密钥，那么就会产生一个问题：若对一个n个人的团体，就需要n（n-1）/2个不同的密钥才能完成每个人之间的通信。

2.什么是公钥加密算法？

简单来说，就是我们有一个发送方A，一个接收方B。A和B都有属于自己的公钥和私钥。
A和B的公钥都是公开的。如果A想给B发消息，可以用B公开的公钥来加密信息。此时这个消息只有B的私钥能解密。而私钥都是严格保密的。只有B知道，这样就实现了公钥加密。

3.限门单向函数

单向函数（one-way Function）：一个函数容易计算但难于求逆
限门单向函数（Trapdoor one-way function）：如果它是一个单向函数，并在具有特定限门的知识后容易求逆。

举个例子：
n=pq，其中p和q是素数。
单向函数就是：很容易可以得到PQ的结果n，但是如果只有一个n，那么是很难分解出p和q的。

4.RSA密码的手动计算方法

首先我们需要知道一些基础知识：

具体计算方法：

5.什么是快速幂算法？

指数：在乘方a中，其中的a叫做底数，n叫做指数，结果叫幂。
f(x)=a^x ， 随着x单位长度的递增，f(x)会呈“爆炸性”增长。
所以，假如你是求2的100次方，用计算器的话，可能会由于结果数值太大，导致结果无法显示。但是，我们这道题目，其实并不需要得到21的7次方的结果，我们只需要它对187做模运算所得到的结果。所以，这道题目，我们需要使用快速幂算法。

那么快速幂算法是如何计算的呢？首先，我们需要知道下列公式：

(a * b) % p = (a % p * b % p) % p
1

即多个因子连续的乘积取模的结果等于每个因子取模后的乘积再取模的结果
故有下列公式：

(a*b*c)%d=(a%d*b%d*c%d)%d
1

所以对于上面那题，使用快速幂算法的计算过程如下所示：

---

参考博客：快速幂算法