社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
上期(RSA简介及基础数论知识)为大家介绍了:互质、欧拉函数、欧拉定理、模反元素 这四个数论的知识点,而这四个知识点是理解RSA加密算法的基石,忘了的同学可以快速的回顾一遍。
一、目前常见加密算法简介
二、RSA算法介绍及数论知识介绍
三、RSA加解密过程及公式论证
今天的内容主要分为三个部分:
大家都知道rsa加密算法是一种非对称加密算法,也就意味着加密和解密是使用不同的密钥,而这不同的密钥是如何生成的呢?下面我们来模拟下小红是如何生成公钥和私钥的。
六步生成密钥:
小红随机选择选择了61和53。(实际应用中,这两个质数越大,就越难破解)
n = 61×53 = 3233
n的长度就是密钥长度,3233写成二进制是110010100001,一共有12位,所以这个密钥就是12位。实际应用中,RSA密钥一般是1024位,重要场合则为2048位。
这里利用我们上篇讲到的欧拉函数求解的第四种情况:
如果n可以分解成两个互质的整数之积,即:n = p1 × p2,则φ(n) = φ(p1p2) = φ(p1)φ(p2),所以φ(3233) = φ(61x53) = φ(61)φ(53)
又因为61和53都是质数,所以可以根据欧拉函数求解的第二种情况:
如果n是质数,则 φ(n)=n-1,所以φ(3233) = φ(61x53) = φ(61)φ(53)=60x52=3120
所以 φ(n)=3120
小红就在1到3120之间,随机选择了17。(实际应用中,常常选择65537)
让我们来回顾一下什么是模反元素:
所谓“模反元素”就是指有一个整数d,可以使得ed除以φ(n)的余数为1,公式表示:
ed≡1(modφ(n))
这个公式等价于
ed–kφ(n)=1
将e=17、φ(n)=3120代入得:
17d–3120k=1
设x=d、y=-k,得
17x+3120y=1
所以我们要求的模反元素d就是对上面的二元一次方程求解
根据扩展欧几里得算法(辗转相除法)求解:
上图我们使用扩展欧几里得求得x=-367,所以d=x=-367,但通常我们习惯取正整数,这样方便计算,还记得我们上节讲过的模反元素的特性吗:
3和11互质,那么3的模反元素就是4,因为 (3 × 4)-1 可以被11整除。显然,模反元素不止一个, 4加减11的整数倍都是3的模反元素 {…,-18,-7,4,15,26,…},即如果b是a的模反元素,则 b+kn 都是a的模反元素。
所以我们取d=d+kφ(n)=-367+1x3120=2753,到这里所有的计算已经全部完毕!
让我们来回顾一下我们一共出现的6个数字:
在这个例子中n=3233,e=17,d=2753,所以公钥就是 (n,e)=(3233,17),私钥就是**(n,d)=(3233, 2753)**,这样小红就将公钥公布出去,自己保存好私钥就可以啦!
至此我们公钥、私钥就生成完毕,是不是觉得并不是很难呢?是不是有点怀疑私钥会不会被人破解呢?下面我们来看看如何才能暴力破解私钥。
回顾我们一共生成了六个数字:p q n φ(n) e d
,这六个数字之中,公钥用到了两个(n和e),其余四个数字都是不公开的。其中最关键的是d,因为n和d组成了私钥,一旦d泄漏,就等于私钥泄漏。
那么,有无可能在已知n和e的情况下,推导出d?
结论:如果n可以被因数分解,d就可以算出,也就意味着私钥被破解。
看到这里有同学可能会惊呼:原来破解RSA算法的方法这个简单???
可是,大整数的因数分解,是一件非常困难的事情。也许你可以对3233进行因数分解(61×53),但是你没办法对下面的大整数分解:
123018668453011775513049495838496272077285356959533479219732245215172640050726
365751874520219978646938995647494277406384592519255732630345373154826850791702
6122142913461670429214311602221240479274737794080665351419597459856902143413
它等于两个质素的乘积:
33478071698956898786044169
84821269081770479498371376
85689124313889828837938780
02287614711652531743087737
814467999489
×
36746043666799590428244633
79962795263227915816434308
76426760322838157396665112
79233373417143396810270092
798736308917
这也是目前维基百科记录的人类分解的最大整数(232个十进制位,768个二进制位),除了暴力破解,还没有发现别的有效方法。所以限制人类分解大整数的是计算机的计算能力,相信如果有一天真正的量子计算机问世后,又会引发一轮安全加密竞赛!
小红有了公钥和私钥这样就可以进行加解密了,于是小红拉着小明一起来测试一下!
假设小明先测试性的给小红发一个字母m=“A”,我们都知道在通信传输中只能传输0和1,所以我们先将“A”转ascii码为65,所以m=65,m必须是整数(字符串可以取ascii值或unicode值),且m必须小于n。
所谓”加密”,就是使用下面的加密公式算出下式的密文c:
me≡c(modn)
小明得到的公钥是(n,e)=(3233, 17),m=65,那么得到下面的等式:
6517≡c(mod3233)
小明通过计算器一算c=2790,所以他就把2790发给小红了。
小红拿到小明发过来的密文c=2790,就用下面的公式进行解密出明文m:
cd≡m(modn)
而小红的私钥为:(n,d) = (3233,2753),所以得到下面的等式:
27902753≡m(mod3233)
小红通过计算器一算,得m=65,然后小红对照着ascii码表得出65对应得字母为A。
至此,整个加解密过程就演示完了,我们来总结一下:
我们可以看到,其实RSA加密算法最核心的就是用公式来加解密,那么我们会有个疑问?为什么解密公式一定可以得到明文m呢?也就是说这个公式是怎么推导出来的?公式一定成立吗?
感兴趣的同学我们可以来一起证明一下解密公式,这也是整个RSA加密算法的最后最核心的一个知识点了。这里我会一步一步的推理,尽可能通俗易懂;
首先让我们再来回顾一下我们一共出现的8个数字
验证rsa算法成立,主要就是验证解密公式成立:
解密公式:cd≡m(modn)
根据加密公式:
加密公式:me≡c(modn)→c=me–kn
将c代入要我们要证明的那个解密公式:
(me–kn)d≡m(modn)
上式等同于下面的公式,原因如下
med≡m(modn)
原因:我们都知道下面的二元一次方程分解,只有第一项不包含n,而所有包含n的项在对n 取余 的操作中都可以消掉。因此得出了上面那个结论
(2–2n)2=4−8n+4n2
又因为生成密钥的第五步中我们取e并求了他对φ(n)的模反元素d:
ed≡1(modφ(n))→ed=hφ(n)+1
所以将ed代入上式得
mhφ(n)+1≡m(modn)
所以,我们只要证明这个公式成立,就证明解密公式的成立,也就证明了RSA算法的成立。
下面我们分两种情况来验证上面的例子
根据欧拉定理:如果两个正整数a和n互质,则n的欧拉函数 φ(n) 可以让下面的等式成立:
aφ(n)≡1(modn)
证明:因为m与n互质,得
mφ(n)≡1(modn)→mφ(n)=1+kn→(mφ(n))h=(1+kn)h
而(1 + kn)^h对n取模为1,因为对(1 + kn)^h拆分只有第一项1不含有n,所以有
(mφ(n))h=(1+kn)h≡1(modn)
同理
(mφ(n))h≡1(modn)→(mφ(n))h=1+kn→(mφ(n))h∗m=(1+kn)∗m
而 (1 + kn)*m对n取模为m,因为前面说过0 < m < n,所以有
(mφ(n))h∗m=(1+kn)∗m≡m(modn)→mhφ(n)+1≡m(modn)
当m与n互质时,证明原式成功!!!
此时m与n不互质,所以m与n必定有除1以外的公因子,而又因为n等于质数p和质数q的乘积,所以m必然等于kp或kq。
以 m = kp为例,考虑到这时m与质数q必然互质,则根据欧拉定理和欧拉函数(第二种:当q为质数,则φ(q)=q-1)使下面的式子成立:
(kp)φ(q)≡1(modq)→(kp)q−1≡1(modq)
同上(m与n互质中)证明原理可得:
[(kp)q−1] 版权声明:本文来源CSDN,感谢博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/u014044812/article/details/80866759
站方申明:本站部分内容来自社区用户分享,若涉及侵权,请联系站方删除。
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!