专栏首页五分钟学算法图解|什么是RSA算法

图解|什么是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) = 60*52=3120

  • 3.找一个与M互素的整数E M和E之间除了1以外没有公约数(互质)且E<M,我们随机选择E为17。
  • 4.找一个整数D,满足如下关系: (E*D) mod M = 1,换句话说E和D的乘积除以M的余数为1,这里有一个术语-模逆元,也就是指有一个整数d,可以使得ed被φ(n)除的余数为1。 等价于 如下计算过程:

当E=17,M=3120,K=1,2,3...时, 17*D - K*M = 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密钥进行加密。

确实是烧脑的硬核内容啊,不由得感叹素数真是个神奇的东西,段位有限只能抛砖引玉,到此为止啦!

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 「算法与数据结构」从入门到进阶整理推荐书单

    小吴花了几天时间整理了一下学习「数据结构与算法」可以参考的书籍,希望能在学习的道路上帮到你,文末提供收集的PDF版。

    五分钟学算法
  • 这 3 个学数据结构和算法的网站,相信你也会喜欢的!

    而我比较特殊,我的第一印象、第二印象以至第 N 印象都觉得很难,所以为了更好的学习和理解算法,我千金一掷一下买了一堆的算法书,有图为证:

    五分钟学算法
  • 10 大算法

    简单的说,任何定义明确的计算步骤都可称为算法,接受一个或一组值为输入,输出一个或一组值。

    五分钟学算法
  • keyless原理

    ssl协议是基于密码学的基础上,解决通信双方加密信道和身份鉴权的安全问题。ssl协议的算法本身是公开的,但是算法本身的输入参数(key)是由通信双方私自保存。在...

    mariolu
  • 《算法图解》note 10 K近邻算法1.K近邻算法简介2.python实现方式3.K近邻算法的优缺点

    billyang916
  • 平面三节点三角形常应变单元有限元程序算例

    如图所示,平板受集中力作用,划分2个三角形单元,分别用自编程序和ANSYS计算节点位移及单元应力。 ? ANSYS计算结果: ? ? 自编程序计算结果: ? ...

    fem178
  • 一次性密码本-绝对不会被破译的密码

    一次性密码本即Vernam Cipher,是由Gilbert Vernam在1917年, 开发的一种加密算法。

    程序那些事
  • 用一句话总结常用的机器学习算法

    浓缩就是精华。想要把书写厚很容易,想要写薄却非常难。现在已经有这么多经典的机器学习算法,如果能抓住它们的核心本质,无论是对于理解还是对于记忆都有很大的帮助,还能...

    SIGAI学习与实践平台
  • 机器学习在自动驾驶方面的应用

    概要:不同的自动驾驶算法。 来源:雷锋网 将汽车内外传感器的数据进行融合,借此评估驾驶员情况、进行驾驶场景分类,都要用到机器学习。本文中,我们讲解了不同的自动驾...

    IT派
  • 机器学习算法在自动驾驶领域的应用大盘点!

    AI 研习社按:本文原载于 kdnuggets,由林立宏、吴楚编译。 将汽车内外传感器的数据进行融合,借此评估驾驶员情况、进行驾驶场景分类,都要用到机器学习。本...

    AI研习社

扫码关注云+社区

领取腾讯云代金券