这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述。首先先来了解下这个算法的历史:
RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
但实际上,在1973年,在英国政府通讯总部工作的数学家克利福德·柯克斯(Clifford Cocks)在一个内部文件中提出了一个相同的算法,但他的发现被列入机密,一直到1997年才被发表。
所以谁是RSA算法的发明人呢?不好说,就好像贝尔并不是第一个发明电话的人但大家都记住的是贝尔一样,这个地方我们作为旁观者倒不用较真,重要的是这个算法的内容:
RSA算法用到的数学知识特别多,所以在中间介绍这个算法生成私钥和公钥的过程中会穿插一些数学知识。生成步骤如下:
随意选择两个大的质数p和q,p不等于q,计算N=p*q;
什么是质数?我想可能会有一部分人已经忘记了,定义如下:
除了1和该数自身外,无法被其他自然数整除的数(也可定义为只有1该数本身两个正因数]的数)。
比如2,3,5,7这些都是质数,9就不是了,因为3*3=9了
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) 如果n是a的k次幂,则 φ(n) = φ(a^k) = a^k - a^(k-1) = (a-1)a^(k-1);
(4) 若m,n互质,则φ(mn) = φ(m)φ(n)
证明:设A, B, C是跟m, n, mn互质的数的集,据中国剩余定理(经常看数学典故的童鞋应该了解,剩余定理又叫韩信点兵,也叫孙子定理),A*B和C可建立双射一一对应)的关系。(或者也可以从初等代数角度给出欧拉函数积性的简单证明) 因此的φ(n)值使用算术基本定理便知。(来自维基百科)
选择一个小于r并与r互质的整数e,求得e关于r的模反元素,命名为d(ed = 1(mod r)模反元素存在,当且仅当e与r互质),e我们通常取65537。
模反元素:
如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。
比如3和5互质,3关于5的模反元素就可能是2,因为32-1=5可以被5整除。所以很明显模反元素不止一个,2加减5的整数倍都是3关于5的模反元素{…-3, 2,7,12…} 放在公式里就是3*2 = 1 (mod 5)*
上面所提到的欧拉函数用处实际上在于欧拉定理:
欧拉定理:
如果两个正整数a和n互质,则n的欧拉函数 φ(n) 可以让下面的等式成立:
a^φ(n) = 1(mod n)
由此可得:a的φ(n - 1)次方肯定是a关于n的模反元素。
欧拉定理就可以用来证明模反元素必然存在。
由模反元素的定义和欧拉定理我们知道,a的φ(n)次方减去1,可以被n整除。比如,3和5互质,而5的欧拉函数φ(5)等于4,所以3的4次方(81)减去1,可以被5整除(80/5=16)。
小费马定理:
假设正整数a与质数p互质,因为质数p的φ(p)等于p-1,则欧拉定理可以写成
a^(p-1) = 1 (mod p)
这其实是欧拉定理的一个特例。
此时我们的(N , e)是公钥,(N, d)为私钥,爱丽丝会把公钥(N, e)传给鲍勃,然后将(N, d)自己藏起来。一对公钥和私钥就产生了,然后具体的使用方法呢?请看:SSL协议之数据加密过程详解
我们知道像RSA这种非对称加密算法很安全,那么到底为啥子安全呢?
我们来看看上面这几个过程产生的几个数字:
N和e我们都会公开使用,最为重要的就是私钥中的d,d一旦泄露,加密也就失去了意义。那么得到d的过程是如何的呢?如下:
所以得出了在上篇博客说到的结论,非对称加密的原理:
将a和b相乘得出乘积c很容易,但要是想要通过乘积c推导出a和b极难。即对一个大数进行因式分解极难
目前公开破译的位数是768位,实际使用一般是1024位或是2048位,所以理论上特别的安全。
RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。
原文博客地址:RSA算法详解
知乎专栏&&简书专题:前端进击者(知乎)&&前端进击者(简书)
博主博客地址:Damonare的个人博客
给定一个数组,找出数组中出现次数最多的元素。给定数组 nums = [3,1,2,1,3,4,3,5,3,6,3], 函数应该返回: 次数最多的元素为:3, 次数为:5
在后面的例子中,我将引用这两个数组,一个包含 5 个元素,另一个包含 50 个元素。我还会用到 JavaScript 中方便的 performance API 来衡量执行时间的差异
算法和程序设计技术的先驱者。Oh,God!一些国外网站这样评价他。一般说来,不知道此人的程序员是不可原谅的。其经典著作《计算机程序设计艺术》更是被誉为算法中“真正”的圣经
字典(Dictionary)是一种以 键-值对 形式存储数据的数据结构 ,其实对于javascript来说,字典类(Dictionary)的基础是Array类,js中的Array既是一个数组,同时也是一个字典。字典(Dictionary)类的基础是 Array 类。同之前的我们所看到的数据结构一样,字典类也应该有添加、删除、清空等操作。
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息
js 把一个正整数分解成若干个质数因子的过程称为分解质因数,在计算机方面,我们可以用一个哈希表来存储这个结果。首先,你需要一个判断是否为质数的方法,然后,利用短除法来分解。
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数
在本文中,我们学习 Merge Sort 背后的逻辑,并用 JavaScript 实现。最后,在空间和时间复杂度方面将归并排序与其他算法进行比较。
设计一种方法,通过给重复字符计数来进行基本的字符串压缩。例如,字符串 aabcccccaaa 可压缩为 a2b1c5a3 。而如果压缩后的字符数不小于原始的字符数,则返回原始的字符串。 可以假设字符串仅包括a-z的字母
斐波那契指的是这样一个数列:1、1、2、3、5、8、13、21、34......在数学上,斐波纳契数列以如下被以递归的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*);随着数列项数的增加,前一项与后一项之比越来越逼近黄金分割的数值0.6180339887..…
内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!