RSA非对称加密算法浅析

说起加密算法，大的分类上，常规区分通常会区分为对称加密与非对称加密两种，两种算法都各有优缺点。然而互联网发展到今天，应用更广的还是非对称加密的方式，而非对称加密中，RSA又首当其中，被广泛运用到各类应用中。本人作为一个标准的Javer，一直对RSA细节没有深入探究，本文算是对该算法的一个浅析，其中涉及大量的数据公式推导，当遇到大家耳熟能详的数据公式（例如费马定理）时，便不再展开
一、对称加密

关于对称加密，网络的释义很多，有的博主将其定义为“加密和解密使用同一个秘钥就是对称加密”。这样的定义一般值得都是算法透明，密钥不透明的场景，例如加解密双方使用的都是DES算法，在密文传递的同时，密钥也需要传递过去
其实所谓对称加密，即解密是加密的逆运算；比如将一个宝物装进箱子中，然后将其锁上，经过一段路途的运输，收件人收货后，将锁打开，然后将宝物搬出来，流程是这样进行的：

宝物 --> 放入箱子 --> 上锁 -----运输至目的地------ 解锁 --> 箱子中取出 --> 宝物

可见解密是加密的逆运算，我们便可称之为对称加密。应用到程序中，假如我们现在有这样一段文本：
Attack tomorrow morning
我们将每个字符对应的ASCII都统一加一，对应的密文即变为

1. @Test
2. public void encrypt() {
3.     String str = "Attack tomorrow morning";
4.     char[] chars = str.toCharArray();
5.     for (int i = 0; i < chars.length; i++) {
6.         chars[i] = (char) (chars[i] + 1);
7.     }
8.     System.out.println(new String(chars));  // 结果为 "Buubdl!upnpsspx!npsojoh"
9. }

复制代码

Buubdl!upnpsspx!npsojoh
而将其解密的原理也就显而易见，将值统一减一

1. @Test
2. public void decrypt() {
3.     String str = "Buubdl!upnpsspx!npsojoh";
4.     char[] chars = str.toCharArray();
5.     for (int i = 0; i < chars.length; i++) {
6.         chars[i] = (char) (chars[i] - 1);
7.     }
8.     System.out.println(new String(chars));  // 结果为 "Attack tomorrow morning"
9. }

复制代码

其实在算法公开的背景下，此处“1”便是密钥，发送方将密文发送的同时，需要将“1”也传送出去，这样接收方便可通过这个“1”对密文进行解密

优点	缺点
算法公开、计算量小、加密速度快、加密效率高	秘钥的管理和分发非常困难，不够安全。上文中，我们的密钥其实就是“1”，但在实际应用的场景中，我们需要将密钥同步给使用方，并且每个用户的密钥都需要保证唯一，且一方的密钥一旦泄露，那么数据肯定也就不安全了，而随着用户的增多，这会使得收、发双方所拥有的钥匙数量巨大，密钥管理成为双方的负担

常见的有对称加密算法有DES、AES、3DES等

二、非对称加密-RSA

非对称加密是相对“对称加密”而言的，拿上文从箱子中取出宝物的例子来说，解密流程可能是将箱子的侧面打开，将宝物取出，亦或是直接将箱子砸碎，反正一定不是加密的逆流程
2.1、加密形式

RSA的密钥有2个

• Public Key 即公钥，对外公布的，所有人都可以直接查询到
  
• Private Key 即私钥，只有密钥的提供者拥有，用来将密文解析出明文的关键key
  

一般是服务的提供者将Public Key公布给所有人，或者索性挂在自己的网站上（证书文件），需要连接该服务的客户端，下载证书并与之建立联系。有同学可能会有疑问，Public Key一样的话，信息如果被其他人截获，岂不造成数据泄露？ 其实这个担心是多余的，因为只有拥有了私钥才能解密密文，而私钥是只有服务提供者才会拥有的独一份数据
2.2、加密概述

RSA生成公钥、私钥的流程是这样的

参数	说明
p	大质数
q	大质数
n	n = p * q
z	z = φ(n) = (p-1) * (q-1) 欧拉函数
e	要求(e < n)，且与 z 互质
x	要求 (e * x) % z == 1

此时，公钥、私钥也就生成了

• 公钥 (n, e)
  
• 私钥 (n, x)
  

加密操作（m为明文，c为密文）：

解密操作（m为明文，c为密文）：

举例说明，为了方便计算，我们取较小的n：
[table][tr][td=1,1,119]参数
[/td][td=1,1,250]计算过程
[/td][td=1,1,92]最终取值
[/td][/tr][tr][td=1,1,119]p
[/td][td=1,1,250]-
[/td][td=1,1,92]3
[/td][/tr][tr][td=1,1,119]q
[/td][td=1,1,250]-
[/td][td=1,1,92]5
[/td][/tr][tr][td=1,1,119]n
[/td][td=1,1,250]n = p * q
[/td][td=1,1,92]15
[/td][/tr][tr][td=1,1,119]z
[/td][td=1,1,250]z=φ(n)=(p-1)*(q-1)=2*4=8
[/td][td=1,1,92]8
[/td][/tr][tr][td=1,1,119]e
[/td][td=1,1,250]
e 加密后的密文： 7解密计算的中间值：4747561509943=======================================> 解密后的明文： 13[/code]我们为13加密，加密后的密文为7，可以成功解密并还原13；但是为了给13加解密，需要计算的代价可见一斑，其中解密的中间值达到了13位数4747561509943

注：这里需要注意一点，明文的长度，一定不能超过n，因为加密的过程是明文阶乘后对n取模，如果长度超过n，那就可能存在多个不同的明文对应一个密文，此时解密算法一定出现问题；另外还有个小细节，即明文、密文的长度是一个量级的，因为它们都是通过对n取模后得到，这样使得破解难度进一步提高

2.3、原理推导

RSA加密虽然名字简单，但是却用到了很多经典的数学定理，接下来我们一步步推导一下
2.3.1、基础定理

设定两个大质数 p、q
n = p * q
因为n比较特殊，它是两个质数的乘积，因此根据欧拉函数，可以很快的计算φ(n)

注：欧拉函数指的是某个整数A，在所有 加密后的密文： 4132881878846003477553871672250开始解密解密完成=======================================> 解密后的10进制数： 117815745854514889615880240=======================================> 解密后的字符串为： attack 9:00[/code]上文中，我们随便选取了两个相对大的质数

• p = 1125899839733759
  
• q = 18014398241046527
  

其本质是需要保证p*q后的值，大于"attack 9:00"所代表的数字
因为p、q已经指定，那么n、z也就固定了

• n = 20282408092494394779761211604993
  
• z = 20282408092494375639463130824708
  

e需要小于n，且与z互质，简单起见，我们直接通过e = z - 1来选择e

• e = z - 1 = 20282408092494375639463130824707
  

在需要满足等式 e*x - z*y = 1 的前提下，我们随便选取一个x满足等式即可

• x = 40564816184988751278926261649415
  

其实通过JDK所带的KeyPairGenerator来生成RSA的公私密钥对儿时，也是上述的思路，不过生成的n值比较大，常见的有1024、2048、4097位。我们这个例子中的n值，不过也就100位左右，当然位数越多越安全，越难被破解
可见加密的代价是巨大的，一个简单的"attack 9:00"字符串后，是大量的cpu功耗
2.5、为什么难破解

现在我们把自己想象成一个网络黑客，拿2.4举例来说，对外暴露的公钥是

• (n=20282408092494394779761211604993, e=20282408092494375639463130824707)
  

假如我们现在拿到了这样一段密文

• 密文c = 4132881878846003477553871672250
  

我们只要进行如下运算就可以获取明文

其中，n我们已经知道了，只需要拿到x就能直接破解，而x是通过公式“e*x - z*y = 1”推导出来的，其中

• z = φ(n)
  
• e < n，且与z互质
  

而e作为公钥中的一个属性，已经完全对外暴露，我们现在只需要知道z(φ(n))的值，再套入公式“e*x - z*y = 1”中便可取得x的值，因为如果e、z、n都已经知道，那么满足这个等式的(x, y)是可穷举的，也就成功破解RSA算法了

因此现在的矛盾直接指向了φ(n)，因为不知道p、q的具体内容，因此直接使用欧拉函数φ(n) = (p-1)(q-1)，但我们知道n，现在需要对其进行因数分解

• 也就是对 (n=20282408092494394779761211604993) 因数分解
  

对于这个问题可以先来个简单的，比如：请尝试求φ(77)，我们如果不知道它是由两个质数相乘得到的话，只能从1开始逐一尝试，这个破解难度可想而知。φ(77)={1,2,3,4,5,6,8,9,10,12,13,15,16,17,18,19,20,21,23,24,25,26,27,30,31,32,34,36,37,38,39,40,41,43,45,46,47,48,50,51,52,53,54,58,57,59,60,61,62,64,65,67,68,69,71,72,73,74,75,76}=60，如果知道77=11*7，即2个质数相乘的话，就很容易得到φ(77)=(11-1)*(7-1)=10*6=60

因此事实是，这个工作是灾难性的，迄今为止，没有一个高效的方法对一个大数进行因式分解，只能通过暴力搜索的方式。我们这个例子中，n的值只取了100位，看上去就很难破解了，而实际应用中，通常都是2048位或4096位，短时间内可以说无法破解

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！