RSA非对称加密算法浅析
说起加密算法，大的分类上，常规区分通常会区分为对称加密与非对称加密两种，两种算法都各有优缺点。然而互联网发展到今天，应用更广的还是非对称加密的方式，而非对称加密中，RSA又首当其中，被广泛运用到各类应用中。本人作为一个标准的Javer，一直对RSA细节没有深入探究，本文算是对该算法的一个浅析，其中涉及大量的数据公式推导，当遇到大家耳熟能详的数据公式（例如费马定理）时，便不再展开
一、对称加密
关于对称加密，网络的释义很多，有的博主将其定义为“加密和解密使用同一个秘钥就是对称加密”。这样的定义一般值得都是算法透明，密钥不透明的场景，例如加解密双方使用的都是DES算法，在密文传递的同时，密钥也需要传递过去
其实所谓对称加密，即解密是加密的逆运算；比如将一个宝物装进箱子中，然后将其锁上，经过一段路途的运输，收件人收货后，将锁打开，然后将宝物搬出来，流程是这样进行的：
宝物 --> 放入箱子 --> 上锁 -----运输至目的地------ 解锁 --> 箱子中取出 --> 宝物
可见解密是加密的逆运算，我们便可称之为对称加密。应用到程序中，假如我们现在有这样一段文本：
Attack tomorrow morning
我们将每个字符对应的ASCII都统一加一，对应的密文即变为
@Test
public void encrypt() {
String str = "Attack tomorrow morning";
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
chars[i] = (char) (chars[i] + 1);
}
System.out.println(new String(chars)); // 结果为 "Buubdl!upnpsspx!npsojoh"
}Buubdl!upnpsspx!npsojoh
而将其解密的原理也就显而易见，将值统一减一
@Test
public void decrypt() {
String str = "Buubdl!upnpsspx!npsojoh";
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
chars[i] = (char) (chars[i] - 1);
}
System.out.println(new String(chars)); // 结果为 "Attack tomorrow morning"
}其实在算法公开的背景下，此处“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：
|
参数 |
计算过程 |
最终取值 |
|
p |
- |
3 |
|
q |
- |
5 |
|
n |
n = p * q |
15 |
|
z |
z=φ(n)=(p-1)*(q-1)=2*4=8 |
8 |
|
e |
e |
7 |
|
x |
要求 (e * x) % z == 1 |
15 |
因此
公钥为：(15, 7)
私钥为：(15, 15)
根据上述信息跑一下单测
@Test
public void en() {
int p = 3;
int q = 5;
int n = p * q;
int z = (p - 1) * (q -1);
int e = 7;
int d = 15;
int source = 13;
System.out.println("原明文是： (" + source + ")");
double pow = Math.pow(source, e);
long result = (long) Math.abs(pow);
System.out.println("加密计算的中间值：" + result);
result = result % n;
System.out.println("=======================================> 加密后的密文： " + result);
// 以下开始解密
double pow2 = Math.pow(result, d);
long result2 = (long) Math.abs(pow2);
System.out.println("解密计算的中间值：" + result2);
result2 = result2 % n;
System.out.println("=======================================> 解密后的明文： " + result2);
}
原明文是： (13)
加密计算的中间值：62748517
=======================================> 加密后的密文： 7
解密计算的中间值：4747561509943
=======================================> 解密后的明文： 13我们为13加密，加密后的密文为7，可以成功解密并还原13；但是为了给13加解密，需要计算的代价可见一斑，其中解密的中间值达到了13位数4747561509943
注：这里需要注意一点，明文的长度，一定不能超过n，因为加密的过程是明文阶乘后对n取模，如果长度超过n，那就可能存在多个不同的明文对应一个密文，此时解密算法一定出现问题；另外还有个小细节，即明文、密文的长度是一个量级的，因为它们都是通过对n取模后得到，这样使得破解难度进一步提高
2.3、原理推导
RSA加密虽然名字简单，但是却用到了很多经典的数学定理，接下来我们一步步推导一下
2.3.1、基础定理
设定两个大质数 p、q
n = p * q
因为n比较特殊，它是两个质数的乘积，因此根据欧拉函数，可以很快的计算φ(n)
注：欧拉函数指的是某个整数A，在所有<=A 的整数集合中，与A互质（即两个数除了1之外，没有公因子）的数的数量，比如φ(6) = {1, 5} = 2；
z = φ(n) = (p - 1) * (q - 1)
这里是欧拉函数中的一种情况，如果p、q均为质数，且n = p * q的话，那么φ(n) = (p - 1) * (q - 1)；举例来说，φ(15) = (3 - 1) * (5 - 1) = 2 * 4 = 8；而φ(15) = {1, 2, 4, 7, 8, 11, 13, 14}。正好等于8，与欧拉函数符合。欧拉函数证明略
e 找到一个整数e，满足如下条件
- e < n
- e 与 z 互质
由于e与z互质，根据贝祖等式，一定可以找到整数x、y，使得如下等式成立
e * x - z * y = 1
其实贝祖等式这里提供的理论支持，也就是任意两个互质的整数，我们都可以找到N多对儿的x、y，使得上述等式成立，举个简单例子，假如 e = 11, z = 10，那么此时(x=1, y=1)，就可以使得等式成立，或者 (x=11, y=12)，即11 * 11 - 10 * 12 = 1，同样使得等式成立
因此由于z = φ(n) = (p - 1) * (q - 1)，所以上述等式可以变形为
e * x = 1 + z * y = 1 + (p - 1) * (q - 1) * y
此时公钥、私钥也就诞生了
- 公钥：(n, e)
- 私钥：(n, x)
2.3.2、推导
有上文得知，加解密的公式如下：
将加密公式带入解密公式后，我们其实是得到了这样一个新公式：
接下来就是推导这个等式是否成立了，如果这个公式成立，那么我们也就推导出了RSA
由上2.3.1章节，我们已经推导出 ex = 1 + φ(n)*y，因此上述公式可变形为
进而变形为
因为任何两个数的乘积取模，都等于分别取模后相乘，因此可继续变形
再简单变一下形
这里m是我们需要加密的明文，它的大小远小于n，而n则是两个大质数的乘积，即n=p*q。因此可以保证m^y与n互质，此处就要用到费马-欧拉定理了，即若n，a为正整数，且n，a互质，则: a^φ(n) ≡ 1 (mod n)
因此，上述公式马上就可简化
m为密文，因为我们加密的时候，对明文都是采取分段加密的方式，因此m都是小于n的，所以最终推导出
因此公式得证
2.4、加密实践
"attack 9:00"
我们对上述明文进行加密；因为计算机底层所有的存储都是二进制的，因此将上述明文解析后可以得到一个byte数组，拿到了byte数组也即将其转换为了二进制数字
@Test
public void enBig() {
BigInteger p = new BigInteger("1125899839733759");
BigInteger q = new BigInteger("18014398241046527");
BigInteger n = p.multiply(q);
BigInteger z = p.subtract(BigInteger.valueOf(1)).multiply(q.subtract(BigInteger.valueOf(1)));
BigInteger e = z.subtract(BigInteger.valueOf(1));
BigInteger x = new BigInteger("20282408092494375639463130824708").add(new BigInteger("20282408092494375639463130824707"));
System.out.println("p = " + p.toString());
System.out.println("q = " + q.toString());
System.out.println("n = " + n.toString());
System.out.println("e = " + e.toString());
System.out.println("z = " + z.toString());
System.out.println("x = " + x.toString());
String str = "attack 9:00";
byte[] bytes = str.getBytes();
BigInteger source = new BigInteger(1, bytes);
System.out.println("原明文字符串是： " + str);
System.out.println("原明文转换为10进制后的数字为： " + source.toString());
BigInteger c = source.modPow(e, n);
System.out.println("=======================================> 加密后的密文： " + c);
System.out.println("开始解密");
BigInteger newSource = c.modPow(x, n);
System.out.println("解密完成");
String newSourceStr = new String(newSource.toByteArray(), StandardCharsets.UTF_8);
System.out.println("=======================================> 解密后的10进制数： " + newSource);
System.out.println("=======================================> 解密后的字符串为： " + newSourceStr);
}
p = 1125899839733759
q = 18014398241046527
n = 20282408092494394779761211604993
e = 20282408092494375639463130824707
z = 20282408092494375639463130824708
x = 40564816184988751278926261649415
原明文字符串是： attack 9:00
原明文转换为10进制后的数字为： 117815745854514889615880240
=======================================> 加密后的密文： 4132881878846003477553871672250
开始解密
解密完成
=======================================> 解密后的10进制数： 117815745854514889615880240
=======================================> 解密后的字符串为： attack 9:00上文中，我们随便选取了两个相对大的质数
- 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位，短时间内可以说无法破解