8BTCCI: 15377.41 -0.27% 8BTCVI: 8489.13 -0.23% 24H成交额: ¥3596.09亿 -18.59% 总市值: ¥20187.65亿 -0.42%
学术向 | RSA加密原理:非对称加密鼻祖

学术向 | RSA加密原理:非对称加密鼻祖

猎豹区块链 29793

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


非对称加密


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

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

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

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

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

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


他将黄色同公开颜色混合然后得到的混合色发给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加密


我们现在有了求解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加密强度以来于质因数分解的困难程度,这是质数分布这一深层次问题的结果,这个问题存在了数千年,人类至今人无法解决。

评论(2)
登录 账号发表你的看法,还没有账号?立即免费 注册