# BTC 学习笔记连载(4)——公钥密码学：D-H & RSA

**Published by:** [Crypto 吊车尾](https://paragraph.com/@imsongoku/)
**Published on:** 2022-09-10
**URL:** https://paragraph.com/@imsongoku/btc-4-d-h-rsa

## Content

欢迎交流：twitter.com/songoku_web3 上一篇讲到了哈希， 接下来就是签名了， 签名要用到非对称加密， 属于公钥密码学。 第一次听到秘钥这个词的时候，我想到的是我们平常用的钥匙。 小时候生活在农村，外婆家院子外有一道铁门，门上有一个老式把锁，每次外出都需要用钥匙把锁打开再锁上，回来的时候用同样的钥匙开锁。 类似这种锁，但比这个更老式 这就是对称加密的原型： 离开时用一把钥匙将房屋锁住保护起来，回来时用相同的钥匙打开； 传输信息前用一个秘钥将信息加密，收到信息时用同一个秘钥解密查看信息； 由于加密和解密都使用同样的秘钥，顾名思义就叫对称加密。 这个过程就如同，传输信息前先用一个保险箱将信息锁起来，收到保险箱后接收方用相同的钥匙打开保险箱获取里面的信息。 在公钥密码学诞生之前，全世界的密码学家设计的加密算法都是基于这个模型的。 对称加密一个最大的问题就是： 通信双方如何共享秘钥？ 这是让全世界密码学家都脑浆迸裂的问题。 之前在近现代密码学一篇中我们讲到过二战时德国使用的Enigma机，德军的办法就是设立通信兵，每个月集结一次并下发下个月的Enigma机秘钥信息： 德军当时使用的秘钥表—转子排列顺序、初始位置、字母对换插接板等信息 这是极不安全的，谁能保障秘钥不被截获？ 能否有一种方法解决秘钥共享的问题呢？ 又或是能够设计出一种加密算法，加密的时候只需要使用一个公开秘钥，接受方接收到加密信息后用自己的另一个秘钥就可以解密呢？ 1976年之前这种想法就是天方夜谭。 但，在人类不会停下发展的脚步， 神人也总会出现...... Merkle、Diffie、Hellman & 公钥密码学 记住这个人：Ralph C. Merkle 一个为公钥密码学做出了杰出贡献的天才密码学家！ Merkle 1952年生于美国加州，1970年进入加州大学伯克利分校主修计算机科学并获得学士和硕士学位，在所有密码学专家都还在深入研究对称密码机制时，Merkle 就提出了公钥密码学的思想： 是否可以在不安全的通信信道中建立安全的通信机制？ 这是公钥密码学思想的源头！ 然而在当时却受到了伯克利大学老师的强烈质疑，Merkle在撰写博士研究计划时提出了两个项目，第1个就是基于公钥密码学的思想，得到的导师评论却是： 第二个项目看起来要好一些，因为你所描述的第一个项目实在太烂了： 手写体部分即为老师的评论 所有伟大的思想，在诞生之初都很难被理解！ 不光是伯克利的导师，当时世界上几乎所有的密码学家都不认可这个思想，1975年Merkle以论文 Secure Communication over Insecure Channels 投稿著名国际期刊 Communication of the ACM，最终也被无情拒绝： 更让Merkle感到绝望的是，伯克利分校的答辩无法通过，甚至不能取得博士学位！ 但优秀的人总能够聚到一起， 另外两位公钥密码学史上的重量级人物该出场了。 Merkle了解到Stanford的两位博士生导师 Bailey Whitfield Diffie、Martin Edward Hellman 也在筹划公钥密码学的研究，于是来到了Stanford，如愿以偿的是导师正是Hellman，而且还能和Diffie一起合作践行公钥密码学思想。 merkle、hellman & deffie 1976年信息论著名期刊 IEEE Transaction on Information Theory 向Diffie、Hellman发出邀请，希望两位能发表一篇论文介绍一下密码学最新研究进展，Merkle当时还是Hellman的博士生。跨时代论文 New Directions in Cryptography (密码学的新方向) 发表了，论文中Diffie、Hellman首次提出了一种通信双方通过不可信的通信信道安全分享秘钥的方法，因此成为了第一个公开提出公钥密码学思想的学者，并正式开创了现代公钥密码学的研究，这就是大名鼎鼎的： Diffie-Hellman 秘钥协商协议 这是密码学发展史上又一个重要里程碑事件！ 30年后的2015年，Diffie、Hellman因这一杰出贡献获得图灵奖！ 遗憾的是没有Merkle！ ...... 大神是不需要剽窃别人的！ 2002年Hellman建议将该算法称为 Diffie–Hellman–Merkle密钥交换协议，从而表彰Ralph Merkle对发明公钥密码学的贡献： 虽然该系统最初是由Diffie和我在一篇论文中描述的，但它是一个公钥分发系统，这是由Merkle最先提出来的概念，因此如果要与它相关联的话，应该被称为“Diffie-hellman-Merkle密钥交换”。我希望这个小讲坛能够帮助人们认识到默克尔对公钥加密技术的同样贡献。 ——Martin Edward Hellman (2002) 1978年Communication of the ACM 弥补了3年前的错误，正式接收了Merkle的论文： Secure Communication over Insecure Channels 1979年Merkle在Stanford获得电机工程博士学位，博士论文主题为：Secrecy, authentication and public key systems（加密，授权与公钥系统） 而牛逼的人在什么领域都能闪闪发光， 我们后面会讲到的 Merkle Tree 就是以 Ralph C. Merkle 来命名的，这是在BTC实现中一个极其重要的数据结构，在BTC的数据结构一篇中我会详细讲解。 模算数、高斯、同余、Diffie-hellman-Merkle密钥交换 德国数学家高斯于1798年写了的一本数论教材，在1801年他24岁时首次出版，这就是在数学界影响深远的《Disquisitiones Arithmeticae》(算术研究)，这本书中整理汇集了费马、欧拉、拉格朗日和勒让德等数学家在数论方面的研究成果，并加入了许多高斯的重要研究。 模算术最早就出现在这本书中！ 什么是模算术？ 其实我们每个人每天都在进行模算术，我们的时钟、手表都是将1天分为2个12小时进行展示的，如果现在是10点，那么5个小时后就是3点，拿数学的语言讲就是10+5 对12取模后得到余数3（对应为12进制问题） 可以表示为：（10+5） mod 12 =3 如果有两个整数a、b，它们mod一个正整数m会得到相同的余数，则称a、b 模m同余。 可以表示为：a ≡ b（mod m） 高斯首次在《Disquisitiones Arithmeticae》中定义了同余符号“≡”及同余表达方式，这在数论和密码学里意义非凡， 这将在所有基于大数质因数分解难题、离散对数问题的加密算法中频繁出现。 同余关系又满足以下四则运算定律： 如果a ≡ b (mod n)，p ≡ q (mod n)，c为任何正整数： a + c ≡ b + c (mod n) a - c ≡ b - c (mod n) a * c ≡ b * c (mod n) a ^ c ≡ b ^ c (mod n) a + p ≡ b + q (mod n) a * p ≡ b * q (mod n) Diffie-hellman-Merkle密钥交换本质上就是基于模运算的： 黄色：保密信息；绿色：公开信息；蓝色：共享秘钥K 如图，Alice、Bob之间要进行通信： g、p：公开信息； a：Alice的保密信息； b：Bob的保密信息； g：原根，通常取2、5即可； p：大质数； K：最终双方计算得到的秘钥； 注意这里面 a, b 和 g^ab ≡ g^ba（mod p）是需要保密的，其它的 g、p、g^a（mod p）、g^b（mod p）都是可以公开传输的，而双方计算出来的K就可以用作对称加密的秘钥，以进行双方通信的信息加密。 Alice不知道b，但可以通过B计算出K； Bob不知道a，但可以通过A计算出K； 而双方计算出的K刚好相等，这就是模算术的精妙之处，证明的方法很简单： K = A^b mod p =（g^a mod p）^b mod p = g^ab mod p =（g^b mod p）^a mod p = B^a mod p 带入一组数值验证一下： 设p = 23、g = 5 a = 6，A = 5^6 mod 23 = 8； Alice将8发送给Bob b = 15，B = 5^15 mod 23 = 19；Bob将19发送给Alice Alice计算出K = 19^6 mod 23 = 2 Bob计算出K = 8^15 mod 23 = 2 至此，Alice和Bob基于不可信的通信信道完成了秘钥的共享(K = 2)，而这只有通信双方知道。 这里我们只是为了举例，p取了一个很小的质数，通常这是不安全的，因为即便a、b再大我们都知道它最多22个可能取值，但如果p是一个500位的质数，a、b至少100位，那么即使用全人类所有的计算资源和当今最好的算法也不可能从g, p和g^a mod p 中计算出 a，这是世界难题离散对数问题。 Rivest、Shamir、Adleman、RSA & 非对称加密 Diffie-hellman-Merkle密钥交换协议非常经典，但有个严重缺陷： 它只是利用公钥密码学的思想实现了一个秘钥的安全共享，而不是用这个协议对信息直接加密。这个问题一直困扰Deffie、Hellman和Merkle，但这一跨越一直没能实现，直到1985年才由另一位密码学家EIGamal改进了D-H，实现对信息的加密。 EIGamal 算法迈出了巨大的一步，但依然有一个缺陷： 它只能用公钥加密、私钥解密，而不能反过来。 这有什么问题？ 我们简单来捋一下非对称加密的2个重要应用：加密、数字签名 （1）加密 Alice要给Bob发送信息，首先用Bob的公钥对信息加密； Bob收到密文后用自己的私钥解密即可获得明文信息； 反之同理，双方都用对方的公钥对信息进行加密，只有自己的私钥才能解密，在一个不可信的通信信道内传输信息是绝对安全的。 （2）数字签名 如图的数据可以理解为一笔交易 签名就是身份证明，只有证明了身份才能在Crypto的世界里调动对应的资产。 Alice要想给Bob发送1个BTC，这是一笔交易信息 Transaction：Alice—>Bob 1BTC Alice 必须要给全网证明自己拥有这1个BTC的所有权，所以需要用自己的私钥对这笔交易进行签名，然后将交易、签名、公钥一起广播出去。 Bob以及全网的节点需要用Alice的公钥进行验证，只有验证通过的Transaction才会被其它节点接受为合法的交易，然后才能广播给其它的节点......最终被写入区块。 所以这相对于加密是一个逆过程，你用你自己的私钥签名，别人用你的公钥来验证。 看到这里的大兄弟应该已经get到了 EIGamal 算法有什么问题？ 它没法实现数字签名！ ...... 直到另外3位大神的横空出世，事情才有了本质进展： 1976年，来自MIT的3位年轻密码学家Ron Rivest、Adi Shamir、Leonard Adleman提出了一种算法彻底实现了非对称加密，这就是闻名世界的RSA，这个算法由他门3个名字的首字母组成。 在讲RSA之前，我们还得了解一点知识： 费马小定理、费马-欧拉定理 费马大家知道吧，业余数学界的顶流。 最有名的就是费马大定理： X^n + Y^n = Z^n，当n > 2的时候没有正整数解。 1637年，费马在阅读丢番图《算术》拉丁文译本时，曾在第11卷第8命题旁写道： ” 将一个立方数分成两个立方数之和，或一个四次幂分成两个四次幂之和，或者一般地将一个高于二次的幂分成两个同次幂之和，这是不可能的。关于此，我确信我发现一种美妙的证法，可惜这里的空白处太小，写不下 “ 就是这么贱贱的一句注解，搞了整个数学界各种数学家300多年，直到1995年才由英国数学家怀尔斯及其学生泰勒证明。 而费马的美妙的证法只能永久尘封在那句注解中了， ...... 但我们今天不是来讲费马大定理的，今天的重点是费马小定理，如下： a：一个整数； p：一个素数； 那么，a^p - a 就一定是p的倍数，也可以写成： a^p ≡ a (mod p) a^(p-1) ≡ 1 (mod p) 这就是费马小定理，费马一贯的尿性就是反正我证明了，但是空白处写不下了，你们需要的话自己证明咯。 WTF ....... 1736年大神欧拉证明了这个定理（欧拉在数学界是神挡杀神、佛挡杀佛的存在，另一位是高斯）。 欧拉觉得虽然这个定理是对的，但不够通用化，于是就优化了一下。 首先了解一下φ(n)，也叫欧拉φ函数，即在<=n 的整数中与n互素的数的个数。 不难理解如果n是一个素数，那么φ(n) = n-1 φ函数是一个积性函数，也就是： 如果 m⊥n（m和n互素），那么φ(m*n) = φ(m) * φ(n) 欧拉升级之后的定理是这样的： a：一个整数； n：一个整数； 其中 a⊥n； 那么，a^φ(n) - 1 就一定是n的倍数，也可以写成： a^(φ(n)) ≡ 1 (mod n) 我们将n换成素数p的时候，就正好能转换成 a^(p-1) ≡ 1 (mod p)，这就是费马小定理呀，欧拉是不是神一般的存在？ 数论中称这个改进后的定理为费马-欧拉定理。 准备工作差不多了，我们可以来讲RSA了~ RSA算法由3个核心步骤组成，秘钥生成、加密、解密，最关键的是秘钥生成： P、Q：2个大质数 N = P * Q，φ(N) = (P-1) * (Q-1) E：整数，E < φ(N) 且 E ⊥ φ(N) —> 公钥：(N，E) D：和E互为模逆元，E * D ≡ 1 mod (φ(N)) —> 私钥：(N，D) 如图Bob生成了自己的公钥、私钥之后，就可以开始秘密通信了： Bob将公钥(N，E)发送给Alice Alice对消息m加密生成C m^E mod (N) = C Bob接收到C后，使用私钥(N，D)进行解密得到消息m C^D mod (N) = m 其证明过程是这样的： C^D mod (N) = (m ^ E mod(N)) ^ D mod(N) = m ^ E*D mod (N) ∵ E * D ≡ 1 mod (φ(N)) ∴ E * D 可以写成 kφ(N)+1 所以上面那个等式可以继续写成： = m ^ (kφ(N)+1) mod (N) = m * m ^ (kφ(N)) mod (N) ∵ m ^ (kφ(N)) mod (N) = (m ^ φ(N)) ^ k mod (N) = 1^k mod (N) =1 ∴ m*m^(kφ(N)) mod (N) = m 注：明文m必须和大数N互质 m和N不互质了，那m基本就是P或Q的倍数了，也就意味着大数质因数分解问题被破解了！ P、Q、N 都是超大的数，明文m一般都不会那么大，如果m太大需要拆解成比较小的部分进行加密！ Bob最终得到了密文m，因为E、D互为模逆元，所以这个过程是可以反过来的，Bob也可以直接用(N，D)进行加密，Alice用(N，E)进行解密。 至此，RSA完美实现了非对称加密的2个重要应用场景。 攻击者无法通过N求得φ(N)，如果N是一个素数这很简单，但N不是素数，这就变成了一个大数质因数分解问题（找到质因数P、Q），是一个数学家、密码学家前仆后继几十年都无法解决的问题，所以也就无法求得D。 但大数质因数分解问题也有弊端，我指的不是量子计算机，而是经验积累问题。 当越来越多的大数被分解后，就会构成一些列映射表，你就需要用更长位数RSA才能保障安全性。 有没有其它的办法呢？下一篇我们讨论一下非对称加密的另一个经典： 椭圆曲线加密！

## Publication Information

- [Crypto 吊车尾](https://paragraph.com/@imsongoku/): Publication homepage
- [All Posts](https://paragraph.com/@imsongoku/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@imsongoku): Subscribe to updates
- [Twitter](https://twitter.com/songoku_web3): Follow on Twitter