小绿锁背后的RSA算法

如今,我们上网时常能见到一把小绿锁,这便是多数浏览器对于HTTPS连接的标识。即HTTP over SSL,它代表着我们与网站服务器的连接是经过SSL加密的。然而,不论何种加密算法,总是有加密和解密的过程,其中最关键的就是密钥交换过程,如果在交换过程中这个密钥被窃取,之后的加密便毫无意义。那么SSL是如何确保即使我们的网络流量被抓取的情况下也能保证加密信息安全的呢?这就是我们今天要说的密钥交换RSA算法。

RSA算法是1977年由麻省理工学院的Ron Rivest、Adi Shamir、Leonard Adleman三人共同提出的,RSA名字便取自他们三人的姓氏。在RSA算法之前,密钥交换主要采用预共享密钥的方式,例如我们生活中连接WPA2-PSK的Wi-Fi便是采用预共享密钥的方式,它的特点是需要通信双方事先共享密钥才能加密,也称为对称加密。而RSA采用的是非对称加密,需要生成两组密钥,称为公钥(Public Key)和私钥(Private Key),这两组密钥是成对的。使用公钥加密的数据可以被私钥解密,使用私钥加密的数据可以被公钥解密。

在了解这个算法前,你需要了解以下数学知识,我假设读者已经具备初中数学知识。
对于OIer,你如果了解过扩展欧几里得欧拉函数费马小定理,你可以跳过这一段,而且你看这个会很轻松。

0.最大公因数
Greatest Common Divisor,即两个数的因数集合的交集中最大的数,通常我们使用gcd表示。
例如a、b的最大公因数记为gcd(a,b)

1. 互质关系
即a\b的公因数仅有1,我们记为gcd(a,b) = 1

2. 欧拉函数
欧拉函数简写为phi(x),即为小于等于x的数中与x互质的数的个数,特殊地:phi(1) = 1
例如x=6,在[1,5]区间中,1、5与6互质,因此phi(6)=2
例如x=7,在[1,6]区间中,1、2、3、4、5、6与7互质,因此phi(7)=6

对于一个质数,phi(x) = x – 1

3. 乘法逆元
这里简要概括,我们设ax+by=c
我们已知a、b,且a、b为正整数
令c=gcd(a,b)
必然存在一组整数x、y使等式成立,通常x,y有一个是负的。
(证明略)
通过这个我们可以求出同余方程。
这个求解过程我们使用扩展欧几里得算法,即exgcd。

4. 模运算
记为a % b或a mod b,即a / b之后的余数
例如:
5 % 2 = 1
15 % 10 = 5
2 % 8 = 2
9 % 8 = 1
3 % 3 = 0

5. 指数运算
记为a^b,即a的b次方
例如:
a^0=1(a≠0)
a^1=a
a^2=a*a
a^3=a*a*a
以此类推

 

好了,我们开始介绍RSA算法的工作过程。

1. 服务器随机产生两个大质数p、q。

2. 计算N=p*q

3. 计算T=phi(p)*phi(q)
由于p、q都是质数,所以T=(p-1)*(q-1)

4. 之后,选择一个正整数E作为公钥(Public Key),使gcd(E,T)=1,即E、T互质。

5. 通过乘法逆元算出私钥(Private Key),记为D,使(E*D) % T = 1。
(学过exgcd的OIer应该都知道这要怎么算吧,毕竟E和T已经互质了。)

此时,我们便得到了公钥和私钥,公钥为{E,N},私钥为{D,N}。

在HTTPS中,

我们需要扔掉p、q、T以确保安全。

我们定义一个明文M,它对应的密文是C。

加密:C = M^E % N
解密:M = C^D % N

我们来实践一下这个加密算法:

我们选择两个大质数p=37,q=23,那么N=p*q=851,T=(p-1)*(q-1)=36*22=792。
之后,我们选择E=5,便得到了公钥{5,851}。我们通过exgcd算法计算出D=317(这个让人来演算太复杂我就略过了)。
得到私钥{317,851}。
假设我们有个密文M=7,C = 7^5 % 851 = 638
此时我们便完成了加密过程。

那么,如何解密呢?
如前文所述,我们使用私钥进行解密。
M = 638^317 % 851 = 7

此时,便得到了原来的密文M。

这样,只要确保Private Key不被盗取,便只有求N的质因数的方法来求解p、q得到私钥,但当这个N足够长的时候,求质因数算法的时间是成指数增长的,目前数学上尚未找到多项式时间内求质因数的方法。因此,只要这个生成N的p、q足够大,基本是没有可能被破解出来的。

你看,RSA算法是不是很神奇?

 

看到这里你一定会有一个疑问,RSA算法计算起来如此繁琐,那SSL加密得有多慢啊。并且只保证了客户端向服务器发送的数据是加密的,服务器用Private Key加密的数据有Public Key的人都能获取,那加密还有什么用呢?

其实不然,SSL的建立连接过程是这样的:
1. 客户端随机一个加密密钥K(通常不用RSA了)
2. 客户端连接服务器,获得服务器的Public Key
3. 用服务器的Public Key加密密钥K,发送给服务器
4. 服务器通过自己的Private Key解密得到密钥K,之后便使用这个密钥加密的其它加密算法进行通信。

 

除了传输密钥交换之外,RSA算法在数字证书上也有广泛的应用,这里就不展开解释了。

 

感谢POJ 2447,带我复习了扩展欧几里得顺便了解了多年以来感兴趣的RSA算法原理。

发表评论

电子邮件地址不会被公开。 必填项已用*标注