从零到壹学习密码学第十三讲:RSA加密解密

作者:黎跃春

孔壹学院创始人兼CEO

黎跃春:孔壹学院创始人兼CEO,国内区块链布道先行者,通信和信息技术培养工程区块链高级授课专家。如果您有任何关于区块链的问题,可以加入区块链技术交流QQ群729666975,我们会为您一一解答。

从零到壹学习密码学为一个系列,一共20讲,包括初识密码学、Hash 函数、对称加密算法、数字签名、椭圆曲线加解密、公钥基础设施( PKI )、零知识证明、随机数等,为大家详尽的介绍密码学的学习过程。今天我们将为大家介绍第十三讲:RSA加密解密。话不多说,马上开启我们的密码学学习之旅。

资料获取,添加莉莉微信kongyixueyuan。

孔壹学院

什么是RSA

RSA是一种公钥密码算法,它的名字是由它的三位开发者,即Ron Rivest、Adi Shamir 和 Leonard Adleman的姓氏的首字母组成的( Rivest-Shamir-Adleman )。

RSA可以被用于公钥密码和数字签名。

RSA加密

在RSA中,明文、密钥和密文都是数字。RSA的加密过程可以用下列公式来表达:

密文=明文Emod N(RSA加密)

RSA的密文是对代表明文的数字的E次方求mod N的结果。换句话说,就是将明文和自己做E次乘法,然后将其结果除以N求余数,这个余数就是密文。

加密公式中出现的两个数和 ,到底都是什么数呢? RSA的加密是求明文的次方mod ,因此只要知道E和N这两个数,任何人都可以完成加密的运算。所以说, 和 是RSA加密的密钥,也就是说, 和 的组合就是公钥。

RSA解密

RSA的解密和加密一样简单,可以用下面的公式来表达:

明文=密文Dmod N( RSA解密)

表示密文的数字的D次方求 mod N就可以得到明文。

这里所使用的数字N和加密时使用的数字N是相同的。数 和数 组合起来就是RSA的解密密钥,因此D和N的组合就是私钥。

在RSA中,加密和解密的形式是相同的。加密是求“明文的E次方的 modN",而解密则是求“密文的D次方的 mod N"。

生成密钥对

在RSA中,加密是求“明文的E次方的 modN",而解密则是求“密文的D次方的 mod N"。

由于E和N是公钥,D和N是私钥,因此求E、D和N这三个数就是生成密钥对。RSA密钥对的生成步骤如下:

求N

求L( L是仅在生成密钥对的过程中使用的数)

求E

求D

求N

首先准备两个很大的质数。这两个很大的质数为p和q。p和q太小的话,密码会变得容易破译,但太大的话计算时间又会变得很长。

判断一个数是不是质数并不是看它能不能分解质因数,而是通过数学上的判断方法来完成。

准备好两个很大的质数之后,我们将这两个数相乘,其结果就是数N。也就是说,数 N 可以用下列公式来表达:

求L

这个数在RSA的加密和解密过程中都不出现,它只出现在生成密钥对的过程中。

是 和 的最小公倍数( least common multiple, lcm )。

如果用lcm(X, Y) 来表示 “X和Y的最小公倍数”,则L可以写成下列形式。

求E

E是一个比1大、比L小的数。此外,E和L的最大公约数( greatest common divisor, gcd)必须为1。

如果用gcd(X, Y)来表示X和Y的最大公约数,则E和L之间存在下列关系。

求D

数D是由数E计算得到的。D、E和L之间必须具备下列关系。

举个密钥对生成的例子

求N

首先我们准备两个质数p、q,这里我们选择17和19,它们都是质数。

求L

L是p-1和q- 1的最小公倍数。

求E

E和L的最大公约数必须是1。

满足条件的E有很多,例如下面这些数都可以。

这些数好像都是质数,但其实并不是这样的,比如25就不是质数。这些数称为和 L “互质的数”,也就是相对于L是质数的意思。我们选择5来作为E。

E=5, N=323 就是公钥。

求D

D必须满足下列条件:

D = 29可以满足上面的条件,因为:

我们已经成功生成了密钥对,即:

公钥:私钥:

公钥(E,N)=(5,323)是可以任意公开的,但是私钥(D,N)= (29,323)必须妥善保管。

加密

要加密的明文必须是小于N的数,也就是小于323的数,我们假设要加密的明文是123,加密时使用的是公钥 。

明文Emod N = 1235mod 323 = 255

因此密文就是 255。

解密

我们对密文225进行解密。解密时使用的是私钥D=29、N=323。

密文29mod N = 22529mod 323 = 123

中间人攻击( man-in-the-middle attack )

中间人攻击虽然不能破译RSA,但却是一种针对机密性的有效攻击。所谓中间人攻击,就是主动攻击者Mallory混入发送者和接收者的中间,对发送者伪装成接收者,对接收者伪装成发送者的攻击方式,在这里,Mallory就是“中间人”。

这种攻击不仅针对RSA,而是可以针对任何公钥密码。在这个过程中,公钥密码并没有被破译,所有的密码算法也都正常工作并确保了机密性。然而,所谓的机密性并非在Alice和Bob之间,而是在Alice和Mallory之间,以及Mallory和Bob之间成立的。仅靠公钥密码本身,是无法防御中间人攻击的。

要防御中间人攻击,还需要一种手段来确认所收到的公钥是否真的属于Bob,这种手段称为认证。在这种情况下,我们可以使用公钥的证书。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180614G216WN00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券