CIPT基础知识-非对称加密与RSA算法

2022-09-05 本文已影响0人遥望潇湘

非对称加密基础

对称加密因为加密和解密都需要使用相同的密钥，所以它不适合在数据传输场景中使用，因为需要将密钥从发送方传输到接收方，无法实现密钥在传输过程的保密性，也就无法保证密文消息不被第三方利用密钥解密。

非对称性加密算法的思路是，消息加密和解密使用不同的密钥，所以只需传输加密密钥，第三方截获了加密密钥后也无法解密消息。

图1 - 非对称加密

RSA和ECC（椭圆曲线加密）是两种目前使用较为广泛的非对称加密算法，我们今天介绍RSA算法

RSA算法基础

RSA使用的是离散对数计算进行加密，算法的加密公式为 c = mᵉ(mod N), 解密公式为 m = cᵈ(mod N)。

结合如上的示意图，我们可以看到发送方要得到e和N才能完成加密，而接收方要有d和N才能实现密文数据的解密。为了实现数据传输的保密性，这个算法要能满足如下几点

#1 第三方获得了c，e和N之后，并不能破解初d；

#2 用密钥e加密的数据，用d是可以完成解密

必备数学知识

首先我们需要理解质数和互质的概念。质数(也称为素数)指的是满足同时满足如下两个条件：一它是大于1的自然数；二它只能被1和它自身整除。比如7就是一个质数，它只能被1和7整除。

而互质指的是两个整数之间只有一个公约数1，比如说 18和49就是互质的，因为它们只有一个公约数1. 请注意两个质数一定互质，但不是质数的两个数也可以形成互质关系，比如前面18和49的例子。

第二个需要理解的是欧拉公式，当n是正整数， φ(n)用来计算小于n的正整数中与n互质的整数的数量。在欧拉公式中，有三个知识我们要用到

如果n是质数，那么φ(n) = n-1.

如果m和n互质，那么φ(mn)=φ(n)*φ(n)

欧拉定理：如果两个正整数a和n互质，则 aᵠ⁽ⁿ⁾(mod n) = 1

第三个是模反元素

如果两个正整数e和N互质，那么一定可以找到整数d，满足e*d(mod(N)) = 1

上面的几个定理和公式如果希望看到证明过程，请见参考文章。

RSA密钥生成过程

在数据进行传输前，需要先利用如下步骤完整公钥和密钥的生成

1）找出两个足够大的质数p和q；

2）利用p和q，求出N，公式为N=p*q；

3）求出r =φ(N) ，公式为φ(N)= (p-1)*(q-1);

4）找出一个与r互质的正整数e，且要满足 1<e<r；

5）找出e针对N的模反元素 d，满足e*d(mod N) = 1, 公式为d = (k*φ(N)+1)/e；其中k为正整数，代入不同的正整数，找到满足要求的d（d也为正整数）

6）将（N，e）作为公钥传输给对方；

7）将（N，d）作为私钥进行保存；

我们回到上文提到的要满足的两个条件，看看这个算法是否达到了

#1 第三方获得了c，e和N之后，并不能破解出d；

因为 d = (k*φ(N)+1)/e，而获得φ(N)就需要将N分解为一系列质数的积，大整数的因式分解已经被证明只能用暴力破解，目前被分解的最大整数只有768个二进制位，即RSA密钥超过768位就被证明足够安全。

#2用密钥e加密的数据，一定有d可以支持完成解密；

因为e和N是互质的，所以作为d作为e对模数的模反元素是一定存在的，而使用d一定可以将c解密回m的过程，我们就不做数学公式推导了。可以利用网上的大数计算器做一个快速验证。

有 p = 13， q=11，得到N=143， r=120。选择 e=7，求得d=103

对明文 17 进行加密： 17的7次方，对143取模得到密文： 30

对密文30进行解密： 30的103次方，对143取模得到密文：17

公钥加密的数据，通过私钥正确的解密成功

RSA的优劣势分析

RSA利用分开的公钥和私钥，解决了密钥传输问题，公钥因只用于数据加密，无法解密数据也就不会出现秘密数据泄漏。同时RSA算法还可以支持数字签名场景进行身份验证。

RSA也有显著的缺点，一是它的计算效率低，算法计算复杂度是对称加密算法的几百上千倍，不适合大量数据的加密传输。同时它无法抵御中间人攻击，如下图所示，恶意中间人可以通过将通信双方的公钥替换为自有公钥，即可在双方不知情的情况下的数据窃取和篡改。

图2-RSA加密信息交互

参考资料：

1. 知乎 - RSA算法原理 - 作者Sylarxx。作者在该文章中做了比较完整的数学公式推导，有兴趣的朋友推荐一读；

2. 知乎 - 隐私计算加密技术基础系列（上）-作者秃顶的码农

3. CIPT官方教程 - 《An Introduction to Privacy for Technology Professionals》