RSA算法详解

时间: 2018-08-07阅读: 1385标签: 算法

这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述。首先先来了解下这个算法的历史:


RSA算法的历史

RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

但实际上,在1973年,在英国政府通讯总部工作的数学家克利福德·柯克斯(Clifford Cocks)在一个内部文件中提出了一个相同的算法,但他的发现被列入机密,一直到1997年才被发表。

所以谁是RSA算法的发明人呢?不好说,就好像贝尔并不是第一个发明电话的人但大家都记住的是贝尔一样,这个地方我们作为旁观者倒不用较真,重要的是这个算法的内容:


RSA算法的过程

RSA算法用到的数学知识特别多,所以在中间介绍这个算法生成私钥和公钥的过程中会穿插一些数学知识。生成步骤如下:

1. 寻找两个不相同的质数

随意选择两个大的质数p和q,p不等于q,计算N=p*q;

什么是质数?我想可能会有一部分人已经忘记了,定义如下:

除了1和该数自身外,无法被其他自然数整除的数(也可定义为只有1该数本身两个正因数]的数)。

比如2,3,5,7这些都是质数,9就不是了,因为3*3=9了

2. 根据欧拉函数获取r

r = φ(N) = φ(p)φ(q) = (p-1)(q-1)

这里的数学概念就是什么是欧拉函数了,什么是欧拉函数呢?

欧拉函数的定义:

欧拉函数 φ(n)是小于或等于n的正整数中与n互质的数的数目。

互质的定义:

如果两个或两个以上的整数的最大公约数是 1,则称它们为互质

例如:φ(8) = 4,因为1,3,5,7均和8互质。

推导欧拉函数:

(1)如果n = 1φ(1) = 1;(小于等于1的正整数中唯一和1互质的数就是1本身);

(2)如果n为质数,φ(n) = n - 1;因为质数和每一个比它小的数字都互质。比如5,比它小的正整数1,2,3,4都和他互质;

(3) 如果nak次幂,则 φ(n) = φ(a^k) = a^k - a^(k-1) = (a-1)a^(k-1)

(4) 若m,n互质,则φ(mn) = φ(m)φ(n)

证明:ABC是跟mnmn互质的数的集,据中国剩余定理(经常看数学典故的童鞋应该了解,剩余定理又叫韩信点兵,也叫孙子定理),A*BC可建立双射一一对应)的关系。(或者也可以从初等代数角度给出欧拉函数积性的简单证明) 因此的φ(n)值使用算术基本定理便知。(来自维基百科)

3. 选择一个小于r并与r互质的整数e

选择一个小于r并与r互质的整数e,求得e关于r的模反元素,命名为ded = 1(mod r)模反元素存在,当且仅当e与r互质),e我们通常取65537。

模反元素:

如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。

比如35互质,3关于5的模反元素就可能是2,因为32-1=5可以被5整除。所以很明显模反元素不止一个,2加减5的整数倍都是3关于5的模反元素{…-3, 2,7,12…} 放在公式里就是3*2 = 1 (mod 5)*

上面所提到的欧拉函数用处实际上在于欧拉定理:

欧拉定理:

如果两个正整数an互质,则n的欧拉函数 φ(n) 可以让下面的等式成立:

a^φ(n) = 1(mod n)

由此可得:aφ(n - 1)次方肯定是a关于n的模反元素。

欧拉定理就可以用来证明模反元素必然存在。

由模反元素的定义和欧拉定理我们知道,aφ(n)次方减去1,可以被n整除。比如,3和5互质,而5的欧拉函数φ(5)等于4,所以34次方(81)减去1,可以被5整除(80/5=16)。

小费马定理:

假设正整数a与质数p互质,因为质数p的φ(p)等于p-1,则欧拉定理可以写成

a^(p-1) = 1 (mod p)

这其实是欧拉定理的一个特例。

4. 销毁p和q

此时我们的(N , e)是公钥,(N, d)为私钥,爱丽丝会把公钥(N, e)传给鲍勃,然后将(N, d)自己藏起来。一对公钥和私钥就产生了,然后具体的使用方法呢?请看:SSL协议之数据加密过程详解


RSA算法的安全性

我们知道像RSA这种非对称加密算法很安全,那么到底为啥子安全呢?
我们来看看上面这几个过程产生的几个数字:

  • p,q:我们随机挑选的两个大质数;
  • N:是由两个大质数pq相乘得到的。N = p \ q*;
  • r:由欧拉函数得到的N的值,r = φ(N) = φ(p)φ(q) = (p-1)(q-1)
  • e:随机选择和和r互质的数字,实际中通常选择65537;
  • d: d是以欧拉定理为基础求得的e关于r的模反元素,ed = 1 (mod r)

Ne我们都会公开使用,最为重要的就是私钥中的dd一旦泄露,加密也就失去了意义。那么得到d的过程是如何的呢?如下:

  1. 比如知道e和r,因为d是e关于r的模反元素;r是φ(N) 的值
  2. φ(N)=(p-1)(q-1),所以知道p和q我们就能得到d;
  3. N = pq,从公开的数据中我们只知道N和e,所以问题的关键就是对N做因式分解能不能得出p和q

所以得出了在上篇博客说到的结论,非对称加密的原理:

将a和b相乘得出乘积c很容易,但要是想要通过乘积c推导出a和b极难。即对一个大数进行因式分解极难

目前公开破译的位数是768位,实际使用一般是1024位或是2048位,所以理论上特别的安全。


后记

RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。

原文博客地址:RSA算法详解
知乎专栏&&简书专题:前端进击者(知乎)&&前端进击者(简书)
博主博客地址:Damonare的个人博客


站长推荐

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

2.广告联盟: 整理了目前主流的广告联盟平台,如果你有流量,可以作为参考选择适合你的平台点击进入

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

关闭

js二叉树的遍历算法

二叉树是非常重要的数据结构,其中一棵树最上面的点称为根节点,如果一个节点下面连接多个节点,那么该节点称为父节点,下面的节点称为子节点,二叉树的每一个节点最多有2个子节点,一个节点子节点的个数称为度,二叉树每个节点的度只能是0,1,2中的一个,度为0的节点称为叶节点。

用 JavaScript 学习算法复杂度

在后面的例子中,我将引用这两个数组,一个包含 5 个元素,另一个包含 50 个元素。我还会用到 JavaScript 中方便的 performance API 来衡量执行时间的差异

JS排序算法:记数排序

计数排序是一个非基于比较的[排序算法],该算法于1954年由 Harold H. Seward 提出。 它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围), 快于任何比较排序算法。

js求水仙花数_JavaScript可自定义范围打印水仙花数

水仙花数是指一个 n 位正整数 ( n≥3 ),它的每个位上的数字的 n 次幂之和等于它本身(例如:1^3 + 5^3+ 3^3 = 153)。这篇文章主要介绍js实现生成自定义范围内的水仙花数。

JS常见算法题目

JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题

从js讲解时间复杂度和空间复杂度

今天有同事在检查代码的时候,由于函数写的性能不是很好,被打回去重构了,细思极恐,今天和大家分享一篇用js讲解的时间复杂度和空间复杂度的博客;复杂度的表示方式之前有看过的,你可能会看到这么一串东西

JavaScript 面试中常见算法问题详解

所谓提升,顾名思义即是 JavaScript 会将所有的声明提升到当前作用域的顶部。这也就意味着我们可以在某个变量声明前就使用该变量,不过虽然 JavaScript 会将声明提升到顶部,但是并不会执行真的初始化过程。

js数组的常用算法解析

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

简单理解梯度下降算法及js实现

看了很多文章,梯度下降算法描述都比较艰涩难懂,比如说: 目标函数f(θ)关于参数θ的梯度将是损失函数(loss function)上升最快的方向。然后会推导出下面这个公式。

js二分查找算法

二分查找高效的前提是数据结构是有序的。就好比猜1~100之间的数,先猜50,如果太大了就猜25,如果太小了就猜75.每一次都猜最大值和最小值的中间点.

点击更多...

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