区块链的故事 - 9 - RSA 算法

RSA 

迪菲与赫尔曼完美地解决了密钥分发的难题，从此，交换密钥就很简单了，爱丽丝与鲍勃完全可以可以在村头大喇叭里喊话，就能够交换出一个密钥。但加密的方式，依然是对称加密的。

DH 协议交换密钥虽然方便，但依然有一些不尽人意的麻烦处，爱丽丝还是要与鲍勃对着嚷嚷半天，二人才能生成密钥。当爱丽丝想要交换密钥的时候，若是鲍勃正在睡觉，那爱丽丝的情书，还是送不出去。

迪菲与赫尔曼在他们的论文中，为未来的加密方法指出了方向。 通过单向函数，设计出非对称加密，才是终极解决方案。 所谓非对称加密，就是一把钥匙用来合上锁，另一把钥匙用来开锁，两把钥匙不同。锁死的钥匙，不能开锁。开锁的钥匙，不能合锁。

麻省理工的三位科学家，他们是罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman），他们读了迪菲与赫尔曼的论文，深感返冲旁尘兴趣，便开始研究。迪菲与赫尔曼未能搞定的算法，自他们三人之手，诞生了。

2002 年，这三位大师因为 RSA 的发明，获得了图灵奖。 但不要以为 RSA 就是他们的全部，这三位是真正的大师，每一位的学术生涯都是硕果累累。让我们用仰视的目光探索大师漏启歼们的高度。

李维斯特还发明了 RC2, RC4, RC 5, RC 6 算法，以及著名的 MD2, MD3, MD4, MD5 算法。他还写了一本书，叫 《算法导论》，程序员们都曾经在这本书上磨损了无数的脑细胞。

萨莫尔发明了 Feige-Fiat-Shamir 认证协议，还发现了微分密码分析法。

阿德曼则更加传奇，他开创了 DNA 计算学说，用 DNA 计算机解决了 “旅行推销员” 问题。 他的学生 Cohen 发明了计算机病毒，所以他算是计算机病毒的爷爷了。他还是爱滋病免疫学大师级专家，在数学、计算机科学、分子生物学、爱滋病研究等每一个方面都作出的卓越贡献。

1976 年，这三位都在麻省理工的计算机科学实验室工作，他们构成的小组堪称完美。李维斯特和萨莫尔两位是计算机学家，他们俩不断提出新的思路来，而阿德曼是极其高明的数学家，总能给李维斯特和萨莫尔挑出毛病来。

一年过后，1977 年，李维斯特在一次聚会后，躺在沙发上醒酒，他辗转反侧，无法入睡。在半睡半醒、将吐未吐之间，突然一道闪电在脑中劈下，他找到了方法。一整夜时间，他就写出了论文来。次晨，他把论文交给阿德曼，阿德曼这次再也找不到错误来了。

在论文的名字上，这三位还着实君子谦让了一番。 李维斯特将其命名为 Adleman-Rivest-Shamir，而伟大的阿德曼则要求将自己的名字去掉，因为这是李维斯特的发明。 最终争议的结果是，阿德曼名字列在第三，于是这个算法成了 RSA。

RSA 算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但想要对其乘积进行因式分解却极其困难，因此可以将乘积公开，用作加密密钥。

例如，选择两个质数，一个是 17159，另一个是 10247，则两数乘积为 175828273。 乘积 175828273 就是加密公钥，而 （17159，10247）则是解密的私钥。

公钥 175828273 人人都可获取，但若要破解密文，则需要将 175828273 分解出 17159 和 10247，这是非常困难的。

1977 年 RSA 公布的时候，数学家、科普作家马丁加德纳在 《科学美国人》 杂志上公布了一个公钥：

114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541 

马丁悬赏读者对这个公钥进行破解。漫长的 17 年后，1994 年 4 月 26 日，一个 600 人组成的爱好者小组才宣称找到了私钥。私钥是：

p：3 490 529 510 847 650 949 147 849 619 903 898 133 417 764 638 493 387 843 990 820 577

q：32 769 132 993 266 709 549 961 988 190 834 461 413 177 642 967 992 942 539 798 288 533

这个耗时 17 年的破解，针对的只是 129 位的公钥，今天 RSA 已经使用 2048 位的公钥，这几乎要用上全世界计算机的算力，并耗费上几十亿年才能破解。

RSA 的安全性依赖于大数分解，但其破解难度是否等同于大数分解，则一直未能得到理论上的证明，因为未曾证明过破解 RSA 就一定需要作大数分解。

RSA 依然存在弱点，由于进行的都是大数计算，使得 RSA 最快的情况也比普通的对称加密慢上多倍，无论是软件还是硬件实现。速度一直是 RSA 的缺陷。一般来说只用于少量数据加密。 

RSA 还有一个弱点，这个在下文中还会提及。

在密码学上，美国的学者们忙的不亦乐乎，成果一个接一个。但老牌帝国英国在密码学上，也并不是全无建树，毕竟那是图灵的故乡，是图灵带领密码学者们在布莱切里公园战胜德国英格玛加密机的国度。

英国人也发明了 RSA，只是被埋没了。

60 年代，英国军方也在为密码分发问题感到苦恼。1969 年，密码学家詹姆斯埃利斯正在为军方工作，他接到了这个密钥分发的课题。他想到了一个主意，用单向函数实现非对称加密，但是他找不到这个函数。政府通讯总部的很多天才们，加入进来，一起寻找单向函数。但三年过去了，这些聪明的脑袋，并没有什么收获，大家都有些沮丧，这样一个单项函数，是否存在？

往往这个时候，就需要初生牛犊来救场了。科克斯就是一头勇猛的牛犊，他是位年轻的数学家，非常纯粹，立志献身缪斯女神的那种。 虽然年轻，但他有一个巨大优势，当时他对此单向函数难题一无所知，压根儿不知道老师们三年来一无所获。于是懵懵懂懂的闯进了地雷阵。

面对如此凶险的地雷阵，科克斯近乎一跃而过。只用了半个小时，就解决了这个问题，然后他下班回家了，并没有把这个太当回事，领导交代的一个工作而已，无非端茶倒水扫地解数学题，早点干完，回家路上还能买到新出炉的面包。他完全不知道自己创造了历史。科克斯是如此纯粹的数学家，后来他听闻同事们送上的赞誉，还对此感到有些不好意思。在他眼里，数学应该如哈代所说，是无用的学问，而他用数学解决了具体的问题，这是令人羞愧的。

可惜的是，科克斯的发明太早了，当时的计算机算力太弱，并不能实现非对称的加解密。所以，军方没有应用非对称加密算法。詹姆斯与科克斯把非对称加密的理论发展到完善，但是他们不能说出去，军方要求所有的工作内容都必须保密，他们甚至不能申请专利。

军方虽然对工作成果的保密要求非常严格，但对工作成果本身却不很在意。后来，英国通讯总部发现了美国人的 RSA 算法，觉得好棒棒哦。他们压根就忘记了詹姆斯与科克斯的 RSA。通讯总部赞叹之余，扒拉了一下自己的知识库，才发现自己的员工科克斯早已发明了 RSA 类似的算法。 官僚机构真是人类的好朋友，总能给人们制造各种笑料，虽然其本意是要制造威权的。

科克斯对此并不介怀，他甚至是这样说的：“埋没就埋没吧，我又不想当网红，要粉丝干嘛？那些粉丝能吃？” 原话不是这样的，但表达的意思基本如此。

迪菲在 1982 年专程去英国见詹姆斯，两人惺惺相惜，真是英雄相见恨晚。可惜詹姆斯依然不能透漏他们对 RSA 的研究，他只告诉了迪菲：“你们做的比我们要好。” 全球各国的科学家们，可以比出谁更好，但全球各国的官僚们，却很难比出谁更颟顸，他们不分高下。

区块链的故事 - 1

区块链的故事 - 2

区块链的故事 - 3

区块链的故事- 4

区块链的故事 - 5

区块链的故事 - 6

区块链的故事 - 7

区块链的故事 - 8

公开密钥算法是在1976年由当时在美国斯坦福大学的迪菲（Diffie）和赫尔曼(Hellman)两人首先发明的（论文New Direction in Cryptography）。但目前最流行的RSA是1977年由MIT教授Ronald L.Rivest,Adi Shamir和Leonard M.Adleman共同开发的,分别取自三名数学家的名字的第一个字母来构成的。

1976年提出的公开密钥密码体制思想不同于传统的对称密钥密码体制，它要求密钥成对出现，一个为加密密钥(e)，另一个为解密密钥(d)，且不可能从其中一个推导出另一个。自1976年以来，已经提出了多种公开密钥密码算法，其中许多是不安全的， 一些认为是安全的算法又有许多是不实用的，它们要么是密钥太大，要么密文扩展十分严重。多数密码算法的安全基础是基于一些数学难题， 这些难题专家们认为在短期内不可能得到解决。因为一些问题(如因子分解问题)至今已有数千年的历史了。

公钥加密算法也称非对称密钥算法，用两对密钥：一个公共密钥和一个专用密钥。用户要保障专用密钥的安全；公共密钥则可以发布出去。公共密钥与专用密钥是有紧密关系的，用公共密钥加密的信息只能用专用密钥解密，反之亦然。由于公钥算法不需要联机密钥服务器，密钥分配协议简单，所以极大简化了密钥管理。除加密功能外，公钥系统还可以提供数字签名。

公钥加密算法中使用最广的是RSA。RSA使用两个密钥，一个公共密钥，一个专用密钥。如用其中一个加密，则可用另一个解密，密钥长度从40到2048bit可变，加密时也把明文分成块，块的大小可变，但不能超过密钥的长度，RSA算法把每一块明文转化为与密钥长度相同的密文块。密钥越长，加密效果越好，但加密解密的开销也大，所以要在安全与性能之间折衷考虑穗纳，一般64位是较合适的。RSA的一个比较知名的应用是SSL，在美国和加拿大SSL用128位RSA算法，由于出口限制，在其它地区（包括中国）通用的则是40位版本。

RSA算法研制的最初理念与目标是努力使互联网安全可靠，旨在解决DES算法秘密密钥的利用公开信道传输分发的难题。而实际结果不但很好地解决了这个难题；还可利用RSA来完成对电文的数字签名以抗对电文的否认与抵赖；同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完性。 公用密钥的优点就在于，也许你并不认识某一实体，但只要你的服务器认为该实体的CA是可靠的，就可以进行安全通信，而这正是Web商务这样的业务所要求的。例如xyk购物。服务方对自己的资源可根据客升族首户CA的发行机构的可靠程度来授权。目前国内外尚没有可以被广泛信赖的CA。美国Natescape公司的产品支持公用密钥，但把Natescape公司作为CA。由外国公司充当CA在我国是一件不可想象的事情。

公共密钥方案较保密密钥方案处理速度慢，因此，通常把公共密钥与专用密钥技术结合起来实现最佳性能。即用公共密钥技术在通吵数信双方之间传送专用密钥，而用专用密钥来对实际传输的数据加密解密。另外，公钥加密也用来对专用密钥进行加密。

在这些安全实用的算法中，有些适用于密钥分配，有些可作为加密算法，还有些仅用于数字签名。多数算法需要大数运算，所以实现速度很慢，不能用于快的数据加密。以下将介绍典型的公开密钥密码算法-RSA。

RSA算法很好的完成对电文的数字签名以抗对数据的否认与抵赖；利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完整性。目前为止，很多种加密技术采用了RSA算法，比如PGP（PrettyGoodPrivacy）加密系统，它是一个工具软件，向认证中心注册后就可以用它对文件进行加解密或数字签名，PGP所采用的就是RSA算法。由此可以看出RSA有很好的应用。

这个几句话说不清禅肆楚，我也不想打字，到百度百科给你复制个....

RSA

开放分类： 网络、电脑、计算机、安全、算法

RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和 *** 携谈作。 RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是 NPC问题。RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要 600 bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技辩袭碰术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。

这种算法1978年就出现了，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和 *** 作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。

RSA的安全性依赖于大数分解。公钥和私钥都是两个大素数（ 大于 100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。

密钥对的产生。选择两个大素数，p 和q 。计算：

n = p * q

然后随机选择加密密钥e，要求 e 和 ( p - 1 ) * ( q - 1 ) 互质。最后，利用Euclid 算法计算解密密钥d, 满足

e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )

其中n和d也要互质。数e和n是公钥，d是私钥。两个素数p和q不再需要，应该丢弃，不要让任何人知道。

加密信息 m（二进制表示）时，首先把m分成等长数据块 m1 ,m2,..., mi ，块长s，其中 2^s <= n, s 尽可能的大。对应的密文是：

ci = mi^e ( mod n ) ( a )

解密时作如下计算：

mi = ci^d ( mod n ) ( b )

RSA 可用于数字签名，方案是用 ( a ) 式签名， ( b )式验证。具体 *** 作时考虑到安全性和 m信息量较大等因素，一般是先作 HASH 运算。

RSA 的安全性。

RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前， RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解140多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。

RSA的速度。

由于进行的都是大数计算，使得RSA最快的情况也比DES慢上100倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。

RSA的选择密文攻击。

RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装(Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：

( XM )^d = X^d *M^d mod n

前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用 One-Way Hash Function对文档作HASH处理，或同时使用不同的签名算法。在中提到了几种不同类型的攻击方法。

RSA的公共模数攻击。

若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险的。最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那末该信息无需私钥就可得到恢复。设P为信息明文，两个加密密钥为e1和e2，公共模数是n，则：

C1 = P^e1 mod n

C2 = P^e2 mod n

密码分析者知道n、e1、e2、C1和C2，就能得到P。

因为e1和e2互质，故用Euclidean算法能找到r和s，满足：

r * e1 + s * e2 = 1

假设r为负数，需再用Euclidean算法计算C1^(-1)，则

( C1^(-1) )^(-r) * C2^s = P mod n

另外，还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数的一对e和d，一是有利于攻击者分解模数，一是有利于攻击者计算出其它成对的e’和d’，而无需分解模数。解决办法只有一个，那就是不要共享模数n。

RSA的小指数攻击。 有一种提高RSA速度的建议是使公钥e取较小的值，这样会使加密变得易于实现，速度有所提高。但这样作是不安全的，对付办法就是e和d都取较大的值。

---