加密算法之RSA(二)

张彤 2021年10月31日 183次浏览

上一篇介绍了RSA加密算法的一些历史常识及数学知识


这篇文章将通过经典的密码学狗男女Alice和Bob,来介绍RSA加密算法的具体实现办法。

  • 如果Alice要给Bob发送信息,又不想直接把加密规则告诉Bob,那么需要怎么做呢?

一,选择两个质数

这里Alice选择了两个质数~

71 和 89

实际中,这两个数字不会这么小的,质数数值越大,破解的难度也就越大

二,计算两个质数的乘积

#这里为了方便公式化,有如下假设
#p = 17, q = 19, n = p*q
17 * 19 = 323

n的长度(二进制)就是密钥长度,323 的密钥长度就是101000011的长度,9位。
实际应用中,RSA的密钥长度为1024,如果安全级别更高则是2048。

第三步,计算n的欧拉函数φ(n)

依据欧拉函数

φ(n) = (p-1)(q-1)

φ(323)=16*18 = 288

第四步,随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质。

我随机选择了 23 ,在规定区间内,且与288互质

第五步,计算e对于φ(n)的模反元素d。

e * d ≡ 1 (mod φ(n))

转换后得到

e * d - 1 = kφ(n)

相当于 求二元一次方程的x,y 解

ex + φ(n)y = 1

将已知量带入,准备求解

23 * x + 288 * y = 1

求解的办法可以参考欧几里得扩展算法,这里不多复述。
python 实现欧几里得扩展

def ext_euclid(a, b):
    old_s,s=1,0
    old_t,t=0,1
    old_r,r=a,b
    if b == 0:
        return 1, 0, a
    else:
        while(r!=0):
            q=old_r//r
            old_r,r=r,old_r-q*r
            old_s,s=s,old_s-q*s
            old_t,t=t,old_t-q*t
    return old_s, old_t, old_r

x = 551, y = -44 是其中的一组解,即 ** d = 551 **
所有计算至此结束

六,封装,将n和e封装成公钥,n和d封装成私钥。

那么Alice 将(n,e)即(323,23) 封装成公钥,(n,d)即(323,551)封装成私钥
实际工程中,公钥和私钥的数据都采用ASN.1格式表达

七,RSA算法安全性的保证依赖于极大整数的分解是非常困难的事情

计算中用到的变量如下:

  p -- 质数1
  q -- 质数2
  n -- 两质数积
  φ(n) --欧拉函数值
  e -- 随机取值
  d -- 模反元素

公钥中用到了(n,e) 其余的四个元素(p,q,d,φ(n))是不公开的。
最关键的是d,如果d泄露,相当于私钥(n,d)泄露。

那么有无可能在知道公钥(n,e)的情况下推导出d呢?

  (1)ed≡1 (mod φ(n))。只有知道e和φ(n),才能算出d。

  (2)φ(n)=(p-1)(q-1)。只有知道p和q,才能算出φ(n)。

  (3)n=pq。只有将n因数分解,才能算出p和q。

如果n可以被因数分解,d就可以算出,也就意味着私钥被破解.
但是,但是,大整数因数分解到目前为止,人类的历史记录是:232个十进制位,768个二进制位

就这么说把,1024位的破解还早着呢~

八、加密和解密

有了密钥,就可以进行加密解密了,那么如何实现对密文的非对称加密呢?

1,加密公钥(n,e)

假设bob要向alice发送加密信息m,
他就要用爱丽丝的公钥 (n,e) 对m进行加密。
这里需要注意,m必须是整数(字符串可以取ascii值或unicode值),
且m必须小于n。
所谓加密就是算出下列式子的c

m^e ≡ c (mod n)

alice 的公钥是 (323,23),Bob的m假设是92,
那么可以有以下等式

92 ** 23 ≡ c (mod 323)

于是 c = 92^23%323 =80
bob 将92加密后得到80,发送给了alice

2,解密要用私钥(n,d)

alice 持有私钥,在接到密文32后,使用私钥(323,551)进行解密。
可以证明,下面的等式一定成立。

c**d ≡ m (mod n)

结合密文和公钥可以得出

80 ** (551) = m (mod 323) 

通过以上,得到原文明文

80 ^ (551) % 323 = 92

至此加密解密已经完成。为了演示方便,这里采用了较小的两个质数,
在实际生产中通常都是两个大质数相乘。
有疑问是,如果消息m的大于两质数的积n,那么要怎么办呢?通常有两种办法
①一种是把长信息分割成若干段短消息,每段分别加密
②另一种是先选择一种"对称性加密算法"(比如DES),用这种算法的密钥加密信息,再用RSA公钥加密DES密钥。
最后的最后,献上可汗学院的古典密码学和现代密码学,我也是看了这个视频开始接触密码学的。

古典密码学

现代密码学