【YoBit官方网站】什么是 RSA 算法
来源:后端技术指南针-指南针氪金入口
1. 数学之美和密码学
前阵子闲来无事看了会儿《数学之美》,其中第 17 章讲述了由电视剧《暗算》展开的密码学背后的一些数学原理。
书中从凯撒密码到二战盟军和日军,讲到密码学中均匀分布 & 统计独立的基础理论,看得我津津有味,但是其中一些细节没有整明白,于是决定搞篇文章。
2. 加密算法的一点历史
我们知道常见的加密算法有:对称加密和非对称加密,非对称加密是我们今天的主角。
非对称加密不是一蹴而就的,它是 1976 年之后才出现的,可以说非对称加密是对称加密的优化。
2.1 对称加密的缺点
所谓对称加密是指:发送方使用一种规则对信息进行处理,接收方需要使用相同的规则对信息进行逆向处理。
对称加密要求通信双方使用相同的规则和密钥进行加解密,这样如何妥善保管密钥和规则就非常重要了。
如果密钥泄露那么再强大的对称加密算法也是徒劳的,所以如何安全地交换对称加密的规则和密钥是短板。
如何安全地交换密钥呢?让人头疼。
2.2 密钥交换算法
1976 年两位美国计算机学家 Whitfield Diffie 和 Martin Hellman,提出了一种崭新构思,可以在不传递密钥的情况下,完成解密,听着很厉害的样子,这难道就是江湖上传说的隔空打牛?
其实这是被称为 Diffie-Hellman 迪菲-赫尔曼密钥交换算法,来看看维基百科上两位大神的简介:
这两位大神是密码学的先驱,为非对称加密算法指出了明路:双方不一定要直接交换密钥。
迪菲-赫尔曼密钥交换算法中通信双方并没有真正交换密钥,而是通过计算生成出一个相同的共享密钥,具体的过程还是比较复杂,在此不展开了。
非对称加密算法 RSA 借鉴了这种思想,使用公钥和私钥来完成加解密,但是又避免了密钥传输,RSA 算法的公钥是公开的,使用公钥加密的信息,必须使用对应的私钥才能解密。
3. RSA 算法
RSA 算法可以说是地球上最重要的算法之一,是数据通信和网络安全的基石。
3.1 算法作者
RSA 是 1977 年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。
当时他们三人都在麻省理工学院工作,RSA 就是他们三人姓氏开头字母拼在一起组成的。
RSA 算法密钥越长越难破解,根据相关文献,目前被破解的最长 RSA 密钥是 768 个二进制位。一般认为,1024 位的 RSA 密钥基本安全,2048 位的密钥极其安全,RSA 算法目前支持 4096 位长度。
密钥长度和加解密的时间是成正比的,因此我们需要根据自己的场景来选择密钥长度,不必追求一味长密钥。
3.2 算法过程
RSA 算法的本质就是数学,公钥和私钥是数学上关联的,无须直接传递。
算法过程包括:密钥生成、密钥加解密。
3.2.1 密钥生成
RSA 算法的密钥是成对的,公钥加密私钥解密,来看下这对密钥是如何被计算出来的。
- 1. 随机选择两个质数 P 和 Q
我们选择 P=61,Q=53,计算 PQ 的乘积 N=PQ=61*53=3233,将 N 转换为二进制 :110010100001,N 的二进制长度是 12,也就是密钥长度为 12。
本文只是阐述算法原理,在实际中密钥长度在 1024 位以上才安全,12 位基本上就是个演示。
- 2. 求 N 的欧拉函数值 M
欧拉函数的定义:任意给定正整数 n,请问在小于等于 n 的正整数之中,有多少个与 n 构成互质关系?
欧拉函数有个通用的计算公式:
要证明欧拉函数需要分为很多种情况,特别地,当 n 是质数时会出现一些特殊的情况。
直接来个结论 :
a. 如果 k 是质数,则φ(k) = k-1;
b. 如果 n = P * Q,P 与 Q 均为质数,则 φ(n) = φ(P * Q)= φ(P)φ(Q) = (P - 1)(Q - 1) 。
P=61、Q=53 则 N=3233,那么 N 的欧拉函数记为 M=(P-1)(N-1) = 6052=3120
-
3. 找一个与 M 互素的整数 E
M 和 E 之间除了 1 以外没有公约数 (互质) 且 E -
4. 找一个整数 D,满足如下关系:
(E*D) mod M = 1,换句话说 E 和 D 的乘积除以 M 的余数为 1,这里有一个术语-模逆元,也就是指有一个整数 d,可以使得 ed 被φ(n) 除的余数为 1。
等价于 如下计算过程:
当 E=17,M=3120,K=1,2,3... 时,
17D - KM = 1,求解这个方程找到一组满足关系的 D 和 K 即可,可证其中一组为 (D,K)=(2753,15)。
综上所述,我们找到了通过随机选择的互质的 P 和 Q 计算得到 N、M、E、D,我们把这些数字分为两组:(E,N) 和 (D,N) 分别为公钥组和私钥组,E 是公钥、D 是私钥。
在本例中公钥组为 (E,N)=(17,3233),私钥组 (D,N)=(2753,3233),接下来我们将使用这对密钥进行加解密。
3.2.1 加密过程
由于 RSA 算法本质是数字的运算,因此我们在对字符串进行加密时需要先将字符串数值化,可以借助 ascii 码、unicode 编码、utf-8 编码等将字符串转换为数字。
需要特别注意转换后的数字 X 需要小于密钥组中的 N,如果字符串转换后的数字大于 N 则需要进行拆分,这可能也是在数据量大时我们使用对称加密算法来加密内容,用非对称加密算法来加密密钥的原因吧。
加密过程满足:
X^E mod N = Y
其中 X 为明文,E 为公钥,N 为大整数,Y 为密文,mod 取余运算。
3.2.3 解密过程
我们获得密文 Y 后,开始解密,过程满足:
Y^D mod N = X
其中 Y 为密文,D 为私钥,N 为大整数,X 为明文,mod 取余运算。
上述的加密和解密过程涉及到了费尔马小定理。
3.2.4 欧拉定理和费尔马小定理
这块有点晦涩,但是确实 RSA 算法的核心部分,简单看下吧:
费尔马小定理给出了素数检测性质,欧拉对其进行了证明,也就是费马-欧拉定理。
3.3 RSA 算法可靠性分析
经过上面的密钥生成、加解密过程,我们难免要问:RSA 算法可靠吗?通过公钥组 (E,N) 能否推导出私钥 D 呢?
来梳理一下:
-
由于 ed≡1 (mod φ(N)),只有知道 e 和φ(N),才能算出 d,e 是公钥匙,所以需要知道φ(N) 就可以。
-
根据欧拉函数 φ(N)=(P-1)(Q-1),只有知道 P 和 Q,才能算出φ(N)。
-
N=pq,只有将 N 进行因数分解,才能算出 P 和 Q。
所以,如果大数 N 可以被因数分解,私钥 D 就可以算出,从而破解密文。
3.5 大整数因数分解
大整数的因数分解是极其困难的,属于 NPC 问题,除了暴力破解没有很好的解决方案,目前人类分解的最大长度的二进制数为 768 位,1024 位的长度目前尚未破解,因此 1024 长度的二进制密钥是安全的。
所以 RSA 算法的安全性取决于大整数分解的难度,目前 RSA 算法可以支持 4096 位密钥长度,分解难度超乎想象,即使借助于量子计算机难度和时间都是非常非常大的。
4. 总结
本文从对称加密算法传递密钥安全性为起点,说到迪菲-赫尔曼算法进行密钥交换协商,该算法为 RSA 算法的公钥和私钥提供了灵感。
麻省理工的三位数学家在欧拉定理 & 费尔马定理等等一些数学定理的基础上创造了伟大的 RSA 非对称加密算法。
RSA 算法的安全性取决于大数质因数分解的难度,目前而言 1024 位二进制长度的密钥人类都没有破解,为了安全性考虑可使用 2048 位长度的 RSA 密钥进行加密。
确实是烧脑的硬核内容啊,不由得感叹素数真是个神奇的东西,段位有限只能抛砖引玉,到此为止啦!
- 免责声明
- 世链财经作为开放的信息发布平台,所有资讯仅代表作者个人观点,与世链财经无关。如文章、图片、音频或视频出现侵权、违规及其他不当言论,请提供相关材料,发送到:2785592653@qq.com。
- 风险提示:本站所提供的资讯不代表任何投资暗示。投资有风险,入市须谨慎。
- 世链粉丝群:提供最新热点新闻,空投糖果、红包等福利,微信:juu3644。