上⼀篇⽂章介绍了RSA涉及的数学知识，本章将应⽤这些知识详解RSA的加密与解密。
密钥的⽣成是RSA算法的核⼼，它的密钥对⽣成过程如下：
1. 选择两个不相等的⼤素数p和q，计算出n=pq，n被称为RSA算法的公共模数；
2. 计算n的欧拉数φ(n)，φ(n)=(p-1)(q-1)；
3. 随机选择⼀个整数e作为公钥加密密钥指数，1< e < φ(n)，且e与φ(n)互质； 4. 利⽤同余⽅程ed≡1 (mod φ(n))计算e对应的私钥解密指数d。由于GCD(e, φ(n))=1，因此同余⽅程有唯⼀解，d就是e对于模φ(n)的乘法逆元；
5. 将(e,n)封装成公钥，(d, n)封装成私钥，同时销毁p和q。
由于n已经被公开出去，剩下的d就成为RSA有效性的关键，如果d被破解，那么密码系统也宣告失效。⾄于能否破解，后续再议，先来看看RSA是的加密和解密算法。 惊蛰水下摄影
RSA的加密和解密算法
现在Bob通过上述过程⽣成了公钥和私钥，并把公钥告知了Alice，如果Alice想和Bob通讯，就需要⽤Bob的公钥PK B对发送的明⽂X进⾏加密，从⽽得到密⽂Y：
在RSA中，E e,n(X)是模幂运算，先计算X的e次⽅，再对其结果⽤n求余：
Bob收到密⽂后，需要对其解密，还原出明⽂X，解密运算也是模幂运算：
所有信息（包括⽂字、语⾳、图像、视频等）在计算机中都是⼆进制数据，因此可以将X和Y视为整数，进⽽使⽤摸幂运算。
加密运算容易理解，解密运算为什能还原出明⽂呢？如果a%n=b，则下⾯的表达是等同的：
因此加密过程在表达上等同于：
将密⽂代⼊解密运算：
继续计算似乎有点困难，不妨先把问题简化，令a=X e：
这⾥有⼀个规律，展开式只有第⼀项不含有kn，这意味着(a-kn)d能否被n整除完全取决于展开式的第
⼀项，因此：
山西商务旅行社 在⽣成密钥的第4步，根据ed≡1 (mod φ(n))计算出了d，这意味着：始祖鸟化石
根据欧拉定理，如果a, n是正整数，且⼆者互质，则：
因此，当X和n互质时：
根据①可知：
根据模运算的性质：
③可进⼀步简化为：
这⾥有两种情况，X>=n或X <n 。当X<n 时，由于已经假设了互质，所以：
当X>=n是，情况变得有些微妙，假设X=37,n=35：
看来只能是 X<n，当X和n 互质时，解密算法有效，可以还原出明⽂。
当X和n不互质时，它们必然有除了1以外的其它公约数；由于n只有p和q两个约数，因此p或q也⼀定是X的约数，也就是说X=kp或
X=kq。假设X=kp，如果X与q不互质，q本⾝⼜是与p互质的素数，因此k⼀定是q的整数倍：
这⾥⽤使了同余的性质，若 a≡b mod m，则：a n≡b n mod m 。
同余符号两侧同时乘以 X：
根据②：
代⼊④中：
因为(kp)ed能够被p整除，所以kp+tq也能被p整除，同时kp也能被p整除，根据整除的性质，tq也能被p整除；由于p和q互质，所以t⼀定是p的倍数：
现在可以把这个结论代⼊①中继续进⾏解密运算：
根据模运算规则：
解密运算进⼀步简化为：
由于RSA规范限制X<n，因此：
现在可以知道，在RSA规范的限制下，RSA的解密确实可以还原出明⽂。
假设Bob选择了两个素数，p=113,q=59，由此计算出n=6667，φ(n)=112*58=6496；之后Bob选择了⼀个与6496互质的⼩质数e=17作为密密钥指数，再使⽤前⾯介绍的扩展欧⼏⾥德算法⽤extEculid(17, 6496)计算出乘法逆元d=3057；最后，Bob把(17, 6667)作为公钥发送给Alice，把(3057，6667)作为私钥留给了⾃⼰。
现在，Alice向Bob发送了⼀个520的数字，经过加密运算后⽣成了密⽂：
Bob收到后⽤⾃⼰的私钥对其解密：姜斌是谁
RSA的安全性
密码体制的安全性依赖于密钥的安全性，现代密码学不追求加密算法的保密性，⽽是追求加密算法的完备，使攻击者在不知道密钥的情况下，没有办法从算法到突破⼝。
RSA算法的密钥⽣成过程中涉及到p,q,n, φ(n),e,d⼏个数字，其中p和q在最后被销毁，还剩下四个：n, φ(n),e,d，在这四个数中，n和e⽤于私钥，对外公开，d⽤于私钥要严格保密，⼀旦d泄露了，就等于加密系统被破解了。现在的问题是，能否通过公钥n和e推算出d？
回顾RSA密钥⽣成的过程，d是由ed≡1 (mod φ(n))计算得出的，只有知道e和φ(n)才能计算出d；φ(n)=(p-1)(q-1)，只有知道p和q才能计算出φ(n)；n=pq，GCD(p,q)=1，只有将n进⾏素因⼦分解才能
计算出p和q，这就回到了RSA的原理——将两个⼤素数相乘很容易，但是想要对它们的乘积进⾏素因⼦分解却及其困难。反过来，如果n可以被素因⼦分解，就可以复原已经被销毁的的p和q，进⽽计算出d，获得私钥。
所谓将⼤整数进⾏素因⼦分解很困难，是指计算上的困难，对⼀极⼤整数做素因⼦分解越困难，RSA算法越可靠。假如有⼈到⼀种快速的素因⼦分解算法，那么⽤RSA加密的可靠性就将会极度下降。到⽬前为⽌，只有短的RSA密钥才可能被解破，⾄今为⽌，⼈们还没有发现⼀个有效的⽅法快速分解⼤整数。为了确保RSA加密系统的安全性，应该随机选择两很⼤的素数进⾏操作，以确保n的⼆进制达到上千位，以防御未来可能出现的素因⼦分解技术的近进步。⽬前能预测2030年之前⾜够安全的RSA密钥长度是2048位。
攻破⼼的壁垒
坚固的城堡往往是从内部被攻克的，再⾼明的加密体制也抵挡不住私钥泄露的危险。
周武王在对主将颁布“阴符”时曾明确告知，谁要是敢泄露“阴符”的暗语就剁了谁：“诸奉使⾏符，稽留者，若符事泄，闻者告者，皆诛之。⼋符者，主将秘闻，所以阴通⾔语不泄，中外相知之术。”然⽽⼀旦被俘，⼜有⼏个⼈能够做到不泄密？因此谍战⽚中很少有⾼端的密码破解技术，更多是严刑拷打，这⽐破译密码有效多了。现代特种部队的“抗审”训练也并⾮是提⾼硬扛的能⼒，⽽是尽最⼤可能拖延
泄密的
灰雀教学实录时间，像挤⽛膏⼀样把信息⼀点⼀点透露出去，因为随着时间的流逝，机密的等级也将变得越来越低。
窃取和平年代的商⽤密码⾃然不能靠严刑拷打了，我们平时接触的密码很多，⽐如最典型的公司门禁密码和业务系统密码。然⽽遗憾的是，绝⼤多数公司都过于注重技术上的安全性，轻视了脆弱的⼈⼼。
“银河集团”最近上线了⽤于管理公司业务和客户信息的“芒砀⼭系统”，这是由⼀个著名的软件公司开发的，号称能够安全运⾏100年。“芒砀⼭系统”在外⽹上公开了注册客户能够使⽤的⼀些功能。“银河集团”特别注重系统的安全性，要求所有有权限登录管理端的员⼯必须使⽤16位以上的密码并定期更换。现在Mallory来了，他想要到系统中游荡⼀番，顺便篡改⼀下数据，他会怎么做呢？
以下是Mallory的⾃述：
我⼀定要⿊进“芒砀⼭系统”，为此我做了⼤量的信息侦查，收集到了“银河集团”⼀些⼈员的姓名和座机电话。
我不知道这个系统还有没有其它名字，所以我⼀开始拨打了⼀个，说⾃⼰的公司也在使⽤
⼀个类似的系统，我说：“我们的系统在公司内部叫芒砀⼭，你们也叫这个名字吗？”上海财务管理进修学院
“我们叫芒砀⼭号。”客服⼩说。
这是个有⽤的信息，能够增加我的信誉度。然后，我给⾏政部门的打了⼀个电话，给了他们在信息侦查时到的客服部经理的名字，说⾃⼰是⼀位刚刚⼊职的员⼯，需要分配⼀个邮箱。接电话的哥们⽴马给我开通了邮箱，并告诉了我邮箱地址和初始密码。
⼀⼩时后，我⼜拨打了⾏政部门的电话，接电话的还是刚才的⼈，我挂掉了电话。
⼜过了⼀会，我再次拨打⾏政部的电话，这次是⼀个叫赵信的⼈接听的。“Hi，我是客务部新⼊职的员⼯，我需要登录芒砀⼭号的客户管理界⾯，能不能为我开通⼀下账号？”“好的，你的邮箱是什么？”我给了他刚刚激活的邮箱。“好的，没问题。你的帐号就是你的邮箱号，初始密码需要你到我这⾥领取。”
我试着问：“可以把密码发到我邮箱⾥吗？”
他回答说：“我们不允许在电话和邮件中给你密码，你的办公室在哪⾥？”
我说：“我马上要去赶飞机。你可以把密码密封在⼀个信封⾥，待会交给琪琳吗？” 琪琳是我从信息侦查环节中发现的客服部秘书的名字。
他说“好的，祝你⼯作顺利。”
过了⼀会，我打电话给琪琳，取回赵信留给我的信封，并读取其中的信息给我，她照办了。我告诉她把字条扔到垃圾桶⾥，因为我不再需要它了。
“芒砀⼭系统”就这样对我敞开了⼤门。
Mallory使⽤了⼀种被称为“社会⼯程学”的知识取得了密码，从⽽“光明正⼤”地⾛进了系统，并不是Mallory的技术⾼深莫测，⽽是Mallory 更懂⼈⼼。
注：Mallory的故事改编⾃世界顶级⿊客凯⽂·⽶特尼克的《线上幽灵》。
来⾃量⼦计算的挑战
RSA加密系统能够确保安全的前提是，没有⼀个计算机能够在可接受的时间内分解⼀个极⼤整数，即使是超级计算机也要花费数年的时间。然⽽，随着量⼦计算机体系结构的发展，过去的超强算⼒似乎也并⾮不可触及。
⼆⼗世纪后期，美国学者提出了基于量⼦计算机的质因数分解算法——Shor算法，从理论上证明，在当前最快的计算机上需要上万年才能完成的计算任务，量⼦计算机瞬间即能完成，严重地威胁到了
基于这类数学难题的公钥密码系统的安全性。紧随其后的Grover量⼦搜索算法，对于密码破译来说，相当于把密钥的长度减少⼀半，种种迹象表明，通⽤量⼦计算机⼀旦实现，对⽬前⼴泛使⽤的RSA、EIGamal、ECC公钥密码和DH密钥协商协议都构成了严重的威胁。
2016年，美国国家安全局建议所有美国政府机构放弃RSA加密算法，⽽改⽤其它技术。随着量⼦技术的不断成熟，实⽤量⼦计算机总会有到来的⼀天，到了那⼀天，密码学，特别是基于NP困难问题的公钥密码系统会何去何从呢？
作者：我是8位的
本⽂以学习、研究和分享为主，如需转载，请联系本⼈，标明作者和出处，⾮商业⽤途！
扫描⼆维码关注“我是8位的”
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议