关闭

RSA 背后的算法

时间: 2019-10-16阅读: 658标签: 算法

这篇文章我本来是想写了放到极客时间上 我写的专栏里面的,但是专栏的内容是需要仔细斟酌的。这篇文章我认为还是偏难,不适合整个专栏的内容和难度的定位,因此我把它稍微加工了一下,放到我这个博客上。

在专栏中的第 36 讲的选修课堂(该讲预计在 12 月初发布)中,我介绍了 Diffie–Hellman 密钥交换这一算法,它可以说是质数在加密技术中的一个应用,并且是通过其中的 “模幂运算” 来实现的。今天,我来介绍质数的另一个应用,RSA 背后的算法。我在互联网上搜索了一下,我发现基本没有能把它背后的实现原理用浅显的中文叙述讲清楚的,但我还是想试一试,看看能不能尽可能避开那些难懂的术语,用尽量形象和易于理解的方式,把 RSA 背后的原理讲清楚。

在专栏的 第 02 讲 ,我们讲了非对称性加密,比如通过公钥加密的数据,能且只能通过私钥来解密,可是这是怎样实现的呢?这就要讲 RSA 加密技术的原理了。现在,假定我们要通过 RSA 来进行安全的通信,于是你要使用我发布的公钥来对数据加密,加密以后发给我,我拿到加密数据以后使用对应的私钥解密,而攻击者截获了这个加密数据并尝试破解。


模幂等式

我们在介绍 Diffie–Hellman 密钥交换的时候讲到了这个模幂等式:

gᵃ mod p = A

从难度上看它具有如下三个特性:

  • 特性 ①:已知 g、a 和 p,求 A 容易;
  • 特性 ②:已知 g、p 和 A,求 a 困难;
  • 特性 ③:已知 a、p 和 A,求 g 也困难。

再看看上面我们介绍的模幂公式关于离散对数求解的三种难易程度不同的情况吧, 我们在 Diffie–Hellman 密钥交换中应用了特性 ① 和特性 ②,而在 RSA 中,我们还要应用特性 ① 和特性 ③。

观察特性 ①,我们可以利用它来设计 RSA 加密,即让 g 代表需要被加密的实际值,而 a、p 可以公开。于是你就求出它的 a 次幂,并取 p 模,得到了 “密文” A,把它发给我。这个过程中,如果 A 被截获,那么根据特性 ③,已知 A、p 和 a,攻击者是很难求解出 g 来的。我们已经说过了,这符合 “ 正向计算简单,逆向求解困难 ” 这一特性,这一点很适合用来加密。

但是和前面的 Diffie–Hellman 密钥交换不同的是,我们并不是要让所有人都求解这个 g 困难,因为密文是发给我的,我得很容易求解这个 g 才行啊,要不然就像是用一把没人拥有钥匙的锁来加密,这把锁就失去意义了。

我们再来观察一下这个模幂等式:

gᵃ mod p = A

藉由 Diffie–Hellman 密钥交换带来的灵感,如果我们构造这样一个和上式形式一致,但变量具有一定对称性的等式:

Aᵈ mod p = g

这其实是什么?这不就是将加密的数据 A,经过模幂运算以后,得到了原始的未加密数据 g 了吗?也就是说, 既然 a 是公钥,那么这里的 d 就是所谓的 “私钥” 啊 。

好,我们把后面这个公式的 A 通过前面那个公式来带入,得到:(gᵃ mod p)ᵈ mod p = g,根据我们前面介绍模幂运算时提到的联等公式,它就可以化简为:

gᵃᵈ mod p = g

因此这个式子,就表示出了公钥、私钥,以及被加密数之间的关系。

接下去,我们来思考怎样生成这个私钥 d。

欧拉函数

为了继续进行后面的分析,我们需要一点知识储备,首先是欧拉函数。 欧拉函数 φ(x) 表示,有多少不大于 x 的正整数中,与 x 互质的数目 (即公因数只有 1)。

举例来说,要计算 φ(4),你看不大于 4 的正整数包括 1、2、3、4,其中:

  • 1 和 4 互质;
  • 2 不和 4 互质,因为它们有公因数 2;
  • 3 和 4 互质;
  • 4 不和 4 互质,因为它们有公因数 4。

所以 φ(4) = 2。

欧拉函数 φ(x) 一般很难计算,但是如果 x 是质数,情况就不同了,因为质数和任何比它小的正整数互质,比如 φ(5) = 4,这四个数分别是 1、2、3、4,因此,在 x 是质数的情况下:

φ(x) = x – 1

同时,如果 x 是一个可以因式分解的合数,比如 x = m*n,欧拉函数还具备这样的特性:

φ(m*n) = φ(m) * φ(n) = (m-1) * (n-1)

这个公式我们后面还会用到。


欧拉定理

有了欧拉函数的知识,我们进一步了解欧拉定理。 欧拉定理 指的是,对于正整数且互质的 g 和 x,有如下性质:

gᵠ⁽ᴾ⁾ ≡ 1 (mod p)

其中的三横线不是表示 “恒等”,而是表示 “同余”,上面的意思是,g 的 φ(p) 次幂,除以 p 所得的余数,和 1 除以 p 所得的余数,二者相同。

举例来说,当 g=3,p=5,根据前面学的欧拉函数有 φ(5)=4,那么 gᵠ⁽ᴾ⁾=81,81 除以 5 余 1;1 除以 5 也余 1,同余关系成立。


密钥生成

由于 1ᵏ ≡ 1 (mod p),我们可以给指数上的欧拉函数赋予正整数系数 k,gᵏᵠ⁽ᴾ⁾ ≡ 1 (mod p),我们再给两边乘以 g,得到 gᵏᵠ⁽ᴾ⁾⁺¹ ≡ g (mod p)。当 g 小于 p 的时候,g 除以 p 的余数就是 g,因此这个同余式可以写成:

gᵏᵠ⁽ᴾ⁾⁺¹ mod p = g

再联想前面的:

gᵃᵈ mod p = g

你看,这两个式子的形式是一样的,这就意味着,kφ(p)+1 = ad。因此,这个私钥就是:

d = (kφ(p)+1)/a

这意味着什么?这意味着如果能够求得 φ(p) 的值,那么这个私钥就求解出来了。但是,怎样求解 φ(p) 呢?这里,我希望:

  • 密钥是我生成的,因此我求解这个 φ(p) 要非常容易,这样我就可以很容易计算出密钥来;
  • p 是公开的,攻击者仅仅知道 p,求解 φ(p) 要非常困难才行,那样才能保证加密的安全性。

你看,这是不是又一个需要 “ 正向计算简单,逆向求解困难 ” 特性的问题?

回想一下前面我们学习欧拉函数的时候,我讲到了,如果 m、n 是质数,那么欧拉函数可以这样求得:

φ(m*n) = φ(m) * φ(n) = (m-1) * (n-1)

这正是我需要的!

你想,如果我选取两个非常非常大的质数 m 和 n,选择 p 的时候,就让它等于 m 和 n 的乘积,那么 φ(p) = φ(m*n) = (m-1) * (n-1),这个正向计算是很简单的,也就是说,因为我知道 m、n,密钥的生成是很容易的一件事情。

可是,攻击者拿不到 m、n,就只能硬生生地尝试去给 p 因式分解才能得到 m、n,而对于一个超大质数的因式分解,这个过程是极其困难的。纵观整个 RSA 的原理,其中涉及到了两个和质数相关的 “正向计算简单,逆向求解困难” 的特性:

  • 一个是前面介绍的模幂等式逆向求底数;
  • 另一个就是这里介绍的超大质数的因式分解。

这也就是 RSA 安全性的基本原理。

当然,随着科技发展,计算能力越来越强,特别是量子计算的兴起,我们对超大质数的位数要求也越来越高,512 bit 的 RSA 已经被破解,而 1024 bit 也已经摇摇欲坠,现阶段 2048 bit 长度还是安全的,可是未来,谁又知道呢?

原文:https://www.raychase.net/5698

站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

链接: http://www.fly63.com/article/detial/6458

js实现生成任意长度的随机字符串

js生成任意长度的随机字符串,包含:数字,字母,特殊字符。实现原理:可以手动指定字符库及随机字符长度,利用Math.round()和Math.random()两个方法实现获取随机字符

Js全排列的六种算法具体实现

六种算法有些是对位置进行排列,例如回溯、排序等,因为这样可以适应各种类型的元素,而非要求待排列元素一定是数字或字母等

js字典对象_js实现字典Dictionary类操作

字典(Dictionary)是一种以 键-值对 形式存储数据的数据结构 ,其实对于javascript来说,字典类(Dictionary)的基础是Array类,js中的Array既是一个数组,同时也是一个字典。字典(Dictionary)类的基础是 Array 类。同之前的我们所看到的数据结构一样,字典类也应该有添加、删除、清空等操作。

js数组的常用算法解析

不改变原数组,返回新数组(字符串);改变原数组;遍历方法;ES6语法Map键值对转化为数组;两个升序的数组合并成一个升序数组;数组重复问题;两个数组的交集;找出一个数组中只出现一次的数字

原生js实现冒泡排序算法,javascript冒泡排序

javascript冒泡排序的实现,冒泡排序是一个非常常见的排序算法,对于一个数组,每趟排序时依次比较两个相邻的数,如果他们的顺序错误就交换两数位置。

Leetcode 242 有效的字母异位词的三种解法

题目描述:给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。这个题目比较简单,属于一眼看过去就有思路的那种。我用了三种解法,你也尝试一些别的方法, 拓宽思路。

Js七种排序算法

冒泡排序的思路:遍历数组,然后将最大数沉到最底部;<br/>时间复杂度:O(N^2);<br/>空间复杂度:O(1);选择排序的实现思路:遍历数组,把最小数放在头部;

js实现将一个正整数分解质因数

js 把一个正整数分解成若干个质数因子的过程称为分解质因数,在计算机方面,我们可以用一个哈希表来存储这个结果。首先,你需要一个判断是否为质数的方法,然后,利用短除法来分解。

js实现:在字符串中找出第一个只出现一次的字符

在给出一个字符串,找出第一个只出现一次的字符。思路分析:可以用对象保存字符出现的次数。将值删除,用 indexOf 查找还有没有相同字符,并查找之前删过的字符,indexOf 的第二个参数,从当前值往后搜索,并查找之前已经查过的字符

Js集合的实现与应用

与数学中的集合概念类似,集合由一组无序的元素组成,且集合中的每个元素都是唯一存在的。可以回顾一下中学数学中集合的概念,我们这里所要定义的集合也具有空集(即集合的内容为空)、交集、并集、差集、子集的特性

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!