RSA加密原理:非对称加密鼻祖

栏目: 编程工具 · 发布时间: 4年前

内容简介:加密算法,RSA是绕不开的话题,因为RSA算法是目前最流行的公开密钥算法,既能用于加密,也能用户数字签名。不仅在加密货币领域使用,在传统互联网领域的应用也很广泛。从被提出到现在20多年,经历了各种考验,被普遍认为是目前最优秀的公钥方案之一。比特币所使用的Sha256算法,也是在其基础之上建立的。了解RSA算法,相信你会对区块链有更深的认识。直到1970年代,密码学都是基于

RSA加密原理:非对称加密鼻祖

加密算法,RSA是绕不开的话题,因为RSA算法是目前最流行的公开密钥算法,既能用于加密,也能用户数字签名。不仅在加密货币领域使用,在传统互联网领域的应用也很广泛。从被提出到现在20多年,经历了各种考验,被普遍认为是目前最优秀的公钥方案之一。比特币所使用的Sha256算法,也是在其基础之上建立的。了解RSA算法,相信你会对区块链有更深的认识。

非对称加密

直到1970年代,密码学都是基于 对称密钥 ,也就是发送者使用特定密钥加密信息,而接收者使用相同密钥解密,加密也就是一种来自信息的映射,使用特定密钥来加密信息,要解密密文,需要使用相同密钥,将映射逆转过来。

假设Alice想要和Bob通信,他们必须共享相同的密钥,但如果Alice和Bob不能实际见面,建立共享密钥通常不太可能,或者需要额外的通信开销,比如使用迪菲赫尔曼密钥交换。

另外,如果Alice希望同很多人通信,比如,她开了一家银行,那么她需要同每个人交换不同密钥,她必须管理好所有这些密钥,发送数以千计的信息。于是,密码学家不禁会想,是否有更简单的方式呢?

1970年,英国工程师兼数学家詹姆斯·艾丽斯,试图公开密钥加密,这基于一种简单但聪明的概念,加锁和解锁是互逆操作

为了理解这些,我们用颜色为比喻进行说明,Bob是如何发给Alice一个特定的颜色,而不让监听者截获信息的。

每种颜色都具有互补色,同互补色叠加会得到白光,这能去掉第一种颜色的作用,这里我们假设,混合颜色是一个单向函数,混合颜色输出第三种颜色很容易,但反向过程就难了,Alice首先生成自己的私有密钥,也就是可以随便选择一个颜色,比如红色,下面,假设Alice有一种神秘的颜色机器,能够找到这种红色的互补色,没有其他人能够知道这个,这得到蓝绿色,他将这发给Bob作为公开密钥,假设Bob想发送一种神秘的黄色给Alice。

RSA加密原理:非对称加密鼻祖

他将黄色同公开颜色混合然后得到的混合色发给Alice,此时,Alice能够将自己的私有色叠加到Bob的混合色,这将解除公开色的作用,剩下Bob的秘密颜色,而窃听者无法简单破译Bob的黄色,除非他有Alice的红色。

我们还需要一种数学方法,让这能用于实践。

模幂计算

解决方法由另一位数学家找到——克利福德科克斯,科克斯需要构建一种特殊的单向函数,也就是 陷门单向函数,这种函数从一个方向计算很容易,反过来就难了 ,除非你有关于陷门的特殊信息,为此,他考虑到了 模幂计算。

之前讲的菲迪赫尔曼密钥交换,我曾经介绍过,这里在简单说下,具体方法如下:取一个数字的某次方,除以模数,输出余数,这可以被这样用于加密信息,假设Bob有一段信息被化为数字m,他可以将这个数字自乘e次,其中e是公开指数,然后他可以将结果除以随机数N,并输出除法的余数,这会得到数字c,这个计算很容易完成,但已知c e N,很难求出m是什么,因为我们需要某种试错的过程,这就是可以用于m的单向函数。

正向执行容易,但是反过来难,这就是,我们是数字锁,钥匙就是陷门,这是某种让加密逆过程很容易的信息,我们需要取c的其他次幂,比如d次幂,解除我们原来对m所进行的运算,得到最初的信息m,两个运算合起来也就是m的e次方。然后整个的d次方,也就是m的e乘以d次方,e表示加密,d表示解密。

因此,Alice需要有一种方法构建e和d,导致其他人很难求出d的值。这需要第二个单向函数,用户生成d,为此,他想到了欧几里得。

欧几里得的证明

2000多年前,欧几里得证明了,每个数只有一种质因数分解,这可以考虑为一个密钥,我们知道, 质因数分解是一个非常难的问题 ,我明确一下这里的“难”是什么意思,我将通过介绍所谓事件复杂度来讲解,我们都进行过乘法运算,每个人都有自己的计算加速方法,如果编程,让计算机计算乘法,它能比任何人类算起来快得多。

将这同质因数分解对比,如果有人让你将589质因数分解,你可能会感到问题比较难,无论如何,这都需要采用试错法,直到找到某数能够均分589,经过一系列是错,你会发现其质因数分解是19*31,如果有人让你将437231质因数分解,你可能直接放弃,然后找计算机帮忙,较小的数字这还行得通,但随着数字越来越大,电脑也将开始无法驾驭,随着数字增大,计算步骤增多,需要的时间将大幅增加,大一点的数字计算机可能需要几分钟,再大可能需要数小时,最终,可能需要成千上百年才能分解非常大的数字。

因此,我们说这是一个很难的问题,求解问题所需要的事件会飞速增长,因数分解正是科克斯用于构建陷门的方法。

第一步,假设Alice随机生成一个超过150位的质数,记作p1,然后随机生成位数相当的第二个质数,记作p2,然后将两个质数相乘,得到合数N,乘法需要的事件不到一秒,用浏览器就能轻松计算,然后,她将N的分解P1乘P2隐藏起来,而将N告诉所有人,其他人想要计算机计算,可能需要几年时间,

第二步,科克斯需要找到一个函数,依赖于知道N的因数分解,为此,他回头考虑了1765年瑞士数学家莱昂哈德欧拉的函数。

欧拉函数

欧拉继续研究了质数分布的性质,他定义了一个重要的函数,叫 phi函数,它平衡的是数的可分性,对于给定数字N,函数的输出是,有多少小于等于N的整数,不同N具有任何公因数,我以phi(8)为例讲解一下。

我们考虑从1到8的整数,然后数有多少整数,同8没有大于1的公因数,比如6就不算,因为6和8有公因数2,而1357都算,这些同8只有公因数1,因此(8)=4。

对于任意质数P都有(P)=P-1,比如质数7,(7),需要算进小于7的所有整数,这些数同7都没有公因数,所以(7)=6,如果要求质数21377的phi函数值,只需要减1,就能得到答案是,21376,任意质数的phi函数值都好算,这就引出了一个有趣的结果,基于phi的乘法性质phi(A·B)=phi(A)·phi(B),如果知道数字N,是两质数P1和P2的乘积。那么phi(N)就等于两个质数分别phi值的乘积。也就是(P1-1)·(P2-1)。

RSA加密原理:非对称加密鼻祖

RSA加密

我们现在有了求解phi的陷门,如果你知道N如何因数分解,那么求解phi(N)就很容易,比如77的质因数分解是7×11,那么phi(77)=6×10=60。

第三步,如果 将phi函数和模幂运算联系起来, 为此,他想到了欧拉定理,也就是phi函数和模幂运算之间的入下关系,m的phi(n)次方=1mod n,这意味着你可以选择任何2个数字,让他们没有公因数,假设是m和n,这里令m=5,n=8,取m的phi(n)次方,也就是4次方,然后除以n,将总余下1,下面只需使用两条简单规则处理这个等式。

首先,1的任意次方,记作1的k次方,他总是等于1,同理,我们可以将指数phi(n)乘以任意数k,结果任然是1,然后1乘以任何数m结果总是m,同理,左侧可以乘以m,右侧也得到m,这可以化简为m的k·phi(n)+1次方,突破就在这里。

现在我们有了求e乘以d 的等式,这依赖于phi(n),因此,只有当n的因数分解已知时,计算d才容易,这里d可以作为Alice的密钥,这是一扇陷门,让她能够解除e的作用,我用个例子简单讲一下:

假设Bob有一条信息,他使用某种填充方案将其转化为数字,假设这里是m,然后Alice按入下方式生成她的公开和私有私钥,首先,她生成2个大小类似的随机质数,将这两者相乘得到n,假设n是3127,然后很容易计算出phi(n),因为她知道n如何因数分解,这里phi(n)=3016,然后她选取一个小的公开指数e,前天是这个e必须是奇数,而且不同phi(n)具有公因数,这里选择e=3,最后她求出私有指数d 的值,这里也就是(2·phi(n)+1)/3,也就是2011。

他将这些都隐藏起来,只留下n和e的值,因为n和e组成她的公开密钥,这可以考虑为开着的锁,她把这些发给Bob,让Bob能够上锁自己的信息,Bob上锁是通过计算m的e吃饭mod n,记作c这是他的加密信息,他将这个发回给Alice,最后,Alice使用她的私钥d解密这个信息,通过陷门来访问,c的d次方mod n,等于Bob的原始信息m,任何知道c n e 的人,想知道计算指数d,智能通过计算phi(n),这要求他们知道n 的质因数分解。

当n足够时,Alice能够确保哪怕最先进的计算机网络,想计算出这个也需要数百年时间,该技术发布后,立刻被当做国家机密,不过1977年,该技术被独立地在发现,发现者是罗纳德·里维斯特,阿迪·萨莫尔,伦纳德·阿德曼,该加密于是以他们人人姓氏首字母RSA命名,RSA是使用最广泛的公开密钥算法,也是历史上使用最多的加密算法。

目前, 世界上互联网使用者几乎都在使用RSA,或者某种相关的版本, 不管他们意识到没有,RSA加密强度以来于质因数分解的困难程度,这是质数分布这一深层次问题的结果,这个问题存在了数千年,人类至今人无法解决。

猎豹区块链安全以金山毒霸的技术为依托,结合人工智能、nlp等技术,为区块链用户提供合约审计、情感分析等生态安全服务,旗下产品Ratingtoken是专注于区块链项目评级的机构。


以上所述就是小编给大家介绍的《RSA加密原理:非对称加密鼻祖》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

ES6 标准入门(第2版)

ES6 标准入门(第2版)

阮一峰 / 电子工业出版社 / 2016-1 / 69.00元

ES6(又名 ES2105)是 JavaScript 语言的新标准,2015 年 6 月正式发布后,得到了迅速推广,是目前业界超级活跃的计算机语言。《ES6标准入门(第2版)》是国内仅有的一本 ES6 教程,在前版基础上增补了大量内容——对标准进行了彻底的解读,所有新增的语法知识(包括即将发布的 ES7)都给予了详细介绍,并且紧扣业界开发实践,给出了大量简洁易懂、可以即学即用的示例代码。 《......一起来看看 《ES6 标准入门(第2版)》 这本书的介绍吧!

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

html转js在线工具
html转js在线工具

html转js在线工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换