avatar

tetsai

原创声明

本文由tetsai原创,转载请注明来源

我觉得这篇文章是我写的最掉头发的文章了,在这之前我看RSA算法那是一头雾水,现在还是,不过我已经大概搞懂了它到底是如何运算的了,现在我们来探索一下RSA的算法到底是怎样的

其实本质上来说,RSA没有所谓的公钥和私钥,只是一对**,你选择公开哪个,被公开的那个就成为公钥,另一个就成了私钥。

所以接下来的讨论我只用密钥A密钥B来表示这一对密钥

注意:虽然用A和B表示,但它们在被选择公开A还是B之前,完全是平等的而且可以互换

密钥的生成

这里引用百度百科的话:

质数(prime number)又称素数,有无限个。质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。

随便想两个质数,而且互质,这个东西小学就学了,可以选择11和3

11不能被3整除,3不能被11整除,这就叫“互质”,再也没有除了1和11本身能把11除成整数的数,所以11的质数,3也一样

我们把11和3相乘,得到33,它是共模因子,听起来很深奥是吧?其实没什么,一句话:密钥A和密钥B都得包含它!

也就是密钥A为(33,[?]),密钥B为(33,[?]

我们现在需要找到,到底有多少个数和77互质

这里就要用到欧拉函数,公式是(p-1)(q-1)=(11-1)(3-1)=20个

接下来我们要计算[?]到底是多少了

随便想一个数,大于1小于20,只要与20互质的数都行(错误示范)这里不能选择15,因为20和15都能被5整除,这里我选择了3(选的数不好,会导致公钥和私钥相同,需要重新选)

这样其中一个密钥就知道了哦,设它是密钥A吧

密钥A就是(33,3)

这还不够,密钥B是多少?其实密钥B已经确定了,密钥B(33,[?])的[?]要求和3(上面选的那个数)相乘,而且要和20(欧拉数)相除,余数必须是1

写成表达式就是[?]×3%20=1,求[?]

看起来像是一个解方程的题,这里我用程序找,打开浏览器,按下F12,选Console

执行:

for(var i=1;i<10;i++){console.log(i,3*i%20)}

输出的内容,其中有一行是7 1

所以7×3%20=1

另一个密钥就出来啦,就是(33,7)

现在我有一对密钥(33,3) 和(33,7)了,你选择公开哪个?一旦公开,它就成为了公钥,另一个就需要严加保密,否则RSA安全体系就失去了意义。

密钥的加密和解密

加密解密比较简单,假如密钥是(33,3)

明文的3次幂除以33取余就是密文

一旦用(33,3)加密,就必须用(33,7) 解开,也就是

密文的7次幂除以33取余就是明文

这里明文有讲究滴,必须小于共模因子,也就是33,否则计算会出错(无法解密),而且要大于等于1(这很好理解,如果是0或1,那么无论几次幂都是一个数,那会造成明文和密文相同的尴尬局面)

假设对方手里有(33,3)和(33,7) ,他选择公开(33,3),于是(33,3)是公钥,(33,7) 是私钥

比如我要加密一个数字24给对方,我只有对方的公钥(33,3),那么我就开始计算啦

24的3次幂再除以33取余数,执行代码Math.pow(24,3)%33 结果=30,30发送给对方

对方收到了我的数据,是30,于是拿出了私钥(33,7) ,开始计算

30的7次幂再除以33取余数,Math.pow(30,7)%33 结果为24

对方就知道我要发的其实是24

就这样完成了通信,中间的监听者因为不知道私钥是多少,我发送的内容是无法监听的。


同样的:

对方如果想对我发送17,拿出了私钥(33,7),同样Math.pow(17,7)%33 是8

对方发送了8给我,我收到了8

我拿出了他上次公开的公钥(33,3),Math.pow(8,3)%33 算出17

事实上因为公钥公开,这次通信可能会被监听,所以一般在上一次秘密通信时就交换了对称**,如AES,这次通信应用AES加密即可。

算法参数:

质数对:3,11
共模因子:33
欧拉数:20
公钥:3
私钥:7

编者注:可能我写的比较抽象,可以百度搜索“RSA算法原理”看看别的大佬怎么说的。。

1 对 “浅谈RSA的算法内容”的想法;

发表评论

电子邮件地址不会被公开。 必填项已用*标注