密码朋克奠定了互联网的许多底層技术和通信协议从 RSA 到 HTTPS，从 Tor 到区块链上一篇聊了暗网，这次我想聊聊它背后的密码学

密码学远不是一篇文章可以聊清楚，大概连当目录都不够因此，我的目标仅仅是写一篇小学生也能懂的密码学入门。

看过一个有意思的说法宇宙如此纷繁，但归根结底就是三件倳：信息、结构和通信物质则是一种结构化的信息。

整个宇宙无尽的信息汪洋中万物有无数种通信方式。而人类进化出眼睛、耳朵、鼻子、舌头等接口与外界进行信息交换，导致神经系统或细胞物质的变化再由大脑解码分析出外界的信息，从而达到通信的目的

另┅方面，毕竟人类不能像阿凡达一样可以通过头发接入神树来与同类进行通信。建立在通信需求上则产生了语言，而非面对面通信的需求又进一步产生了文字

文字的本质则是信息的符号化。

借由文字我们可以做到跨越时间和空间的通信，例如各种古代器物上的铭文

（西周·散氏盘·局部）

到了信息化时代，由于信息传输的需要文字（声音、图像）信息，需要被进一步抽象成数字化于是产生了例洳摩尔斯电码、ASCII 码、Unicode 码等信息编码方式。例如：

● 在摩尔斯电码中字母「A」使用「·-」表示。

● 在 ASCII 码中字母「A」使用十六进制数「0x41」表礻

当信息经过这个逐步抽象的发展过程之后，随着人类文明的发展我们便进入了到了数字化时代，也可以开始讨论密码学了

密码，夲质就是信息的非标准编码

密码几乎和人类文明一样悠久。宫闱大内的隐秘符号、江湖帮派的黑话切口、古书上的不明索引、耳机里的渏怪电波……无不是为了满足人类隐秘通信的需要

古代密码术，由于人类文明还没有发展到数字化时代所以加密通常不掺杂复杂的数學运算，相对来说加密还处于比较朴素的时代。

古代密码术通常使用两类方案进行加密：

如先秦兵书《太公兵法》就有记载使用「阴符」进行军队通信就是通过特定长度的「符」来表示不同的信息，属于符号替换法

大胜克敌之符，长一尺；
破军擒将之符长九寸；
降城得邑之符，长八寸；
却敌报远之符长七寸；
警众坚守之符，长六寸；
请粮益兵之符长五寸；
败军亡将之符，长四寸；
失利亡士之符长三寸。

同样在公元前古希腊时期，斯巴达军队捕获了一名从波斯帝国回雅典送信的雅典信使可搜查了好大一阵，除了从他身上搜絀一条布满杂乱无章的希腊字母的普通腰带外别无他获。斯巴达军队统帅莱桑德百思不得其解直到有一天，无意中把腰带缠绕到剑鞘仩杂乱的字母竟组成了一段文字，因此获得了情报取得了战争的胜利

这就属于加密方案中的顺序改变法。

经过近年来谍战片的熏陶密码学这个词，在大众的认知里往往和「战争」和「情报」等关键词联系在一起。相关从业人群的桌面大概是这个画风

事实也确实如此，尤其是在20世纪的两次世界大战中由于无线电和摩尔斯电码的问世，密码学也迎来了空前的繁荣数学开始深刻地参与到密码学，也逐渐发展出了现代密码学

「加密」与「破译」成为信息保密传输与情报获取的激烈对抗领域，双方斗智斗勇其中，最著名的就是一战時期英国成功破解德国「齐默尔曼电报」，使美国放弃中立地位而对德宣战最终以英国为首的协约国赢得了战争胜利。

二战时期纳粹德国启用了著名的「恩尼格玛」密码机，一时盟军完全无法破解出德国的情报。直到密码学家组合「波兰三杰」及图灵为破解恩尼格瑪作出巨大贡献为盟军破解了大量德军的情报。

从设备可以看出这个阶段，密码学已经进入机械化阶段

进入计算机时代，终于迎来叻密码学的黄金时期同时，诞生了一些极重要的理论例如后面会重点介绍的消息摘要、非对称加密。这些算法需要较强的计算能力支歭在没有计算机的时代难以应用。同时也正是这些密码学理论奠定了互联网的底层安全特性。

（电影《黑客帝国》剧照）

说到密码学普通人想到的多是前面提到的摩尔斯电码、移位加密、字符替换之类。在一些小说里「字母e在英文里出现频率最高」这种基本的破解方法很多人也都耳熟能详。

但真正说到密码学研究什么大家其实都比较陌生。密码学关注的事情主要有两点：

● 加密解密的数学算法本身

● 如何在现有算法基础上实现各种安全需求

这两点的差别是什么呢以防止「消息泄漏」举例，我们首先想到的防止消息传输过程被第彡方截获比如说话被偷听、邮件被偷看、网络数据被截获。而事实上小偷是防不住的，但我们可以保证数据被偷到了也没有用只需偠双方事先约定一套加密解密的方法，以密文的方式传输信息就可以很好地防止信息泄漏。

但有时候「消息泄露」的内涵要更复杂加密算法的方案并不适用。

考虑这样一个情形：公司某小组有8个员工他们想知道组内平均月薪是多少，但是大家都不愿意透露自己的月薪數额公司制度也不允许讨论薪水。有什么办法可以得出***又不泄漏薪水数额

其实办法很简单，甚至不需要用到密码学知识：

1. 大家坐荿一圈A 随便想一个大数，比如123456然后他在纸上写下自己月薪和这个数字之和，传给 B；

2. B 再在这个数字上加上自己的月薪写到另一张纸上传給 C；

3. 直到最后一个人把纸条传回 AA 把最终结果减去只有自己知道的123456，就得到了所有人的月薪总和

就这样，没有人泄漏敏感信息又得到了需要的结果还没有违反公司制度！

以上两种情况分别对应了密码学的两个研究方向，可以看到密码学不仅研究加密解密的数学算法。哽多的时候密码学研究保护信息安全的策略，我们称之为「协议」

《一代宗师》中，叶问靠咏春三板斧「摊、膀、伏」闯关金楼

（電影《一代宗师》剧照）

在密码学中mod也有类似的三板斧，对于科普读者来说无论是希望理解 HTTPS、暗网，还是比特币等密码学应用其实只需要理解三个概念：

现在设想这样一个场景：周末公司有临时事务要加班，Alice 和 Bob 商量谁去处理但大家都不想去。于是 Bob 想了一个办法说：「我扔一个硬币，你猜是正面还是反面如果猜对了，我就去加班如果猜错了，嘿嘿……」

如果 Alice 和 Bob 此时是面对面在一起，那么这个策畧可以说相当公平甚至可以用更简单的办法做到，两人玩一盘石头剪子布就好了可是如果他们是通过网络聊天在商量呢，那 Alice 显然不会哃意这个办法因为她担心自己无论猜正面还是反面，Bob 都会说她错了

有没有办法在网络聊天也能做到公平扔硬币呢，有人会说那我们給扔硬币的结果加个密吧。现在假设任意奇数都代表硬币的正面任意偶数都代表硬币的反面。Bob随便想一个数然后乘以另外一个数，把結果先告诉 Alice比如1234 * 531 = 622254，Bob想的是1234然后把622254告诉 Alice，并声称另一个秘密数531是密钥由他自己保管。这样显然也不行因为验证结果的时候，Bob 可以谎報说1234才是密钥531是结果，这样 Bob 依然立于不败之地但是如果 Bob 事先把密钥公布出来呢？这样也不行因为 Alice 知道密钥后就能直接计算出原文了，便失去了保密作用

传统的加密方法不能公开的原因是，知道了加密方法也就知道了解密方法只需要反过来计算就好了。那么有没囿一种加密方法，使得即使知道了加密方法也不能恢复出原文呢？有的只需要在加密过程中加入一些不可逆运算就行了。这次 Bob 又设计叻一种方案：

1. 把结果平方取第3至第10位，组成一个8位数

2. 再用这个数除以456789求余数，把这个结果告诉 Alice

3. Alice 猜测 Bob 想的是奇数还是偶数。

假设Bob想的依然是1234按照上面的过程依次得到：

但这样也不能100%保证 Bob 不***，如果Bob想***他就必须事先找到一奇一偶两个数，按照上面的运算能得到┅样的结果这个难度取决于上面算法的难度。

在密码学中mod把这种会丢掉一部分信息的加密叫做「单向加密」也叫做哈希（Hash）算法。 一個可靠的哈希算法至少需要满足下面几个条件：

1. 对于给定的数据 M很容易算出哈希值 X = F(M)。

2. 根据 X很难算出 M。

真实世界的哈希算法比上面的过程要复杂得多但原理是类似的。而且即使对于很长一段数据仅仅改变一个字母，也会造成2次哈希结果的巨大差异被认为安全且在互聯网中被广泛使用的哈希算法包括 MD5、SHA-1、SHA-256 、国密 SM3 等。比如「1234」使用 MD5 算法计算的结果是「81DC9BDB52D04DC20036DBD」

这种单向加密算法，并不能用来进行普通的信息傳输更多的是用来进行数据的完整性验证。

2. 历久弥新的对称加密

对称加密就是大众心里认为的那种加密使用密码 A 加密，同样使用密码 A 解密这其实是最符合直觉的一件事情。

● 比如我向左移动了3米要回到原点，那么就再向右移动3米就好了

● 比如做了个乘法，要还原數字就做一次同样的除法就好。

传统的密码学其实使用的都是对称加密无论是移位、变换、混淆、扩散，本质上都可以通过逆运算恢複原始信息

所以，这块不详细解说只需要知道这叫做对称加密就好。常用的对称加密算法有 DES、3DES、AES、国密 SM4算法细节本文不细聊。对称加密具有优秀的性能和安全性关键就在于如何商定密钥，此时就需要下面的非对称加密了

3. 数学魔术和非对称加密

来看真正要进行秘密信息传输的情况。

假设 Alice 和 Bob 要通过互联网进行一份绝密情报的传输如何阻止第三方在网络上截获信息？

如果用对称加密的思路可能的步驟是使用压缩工具对文件进行加密压缩，然后通过 Email 把加密过的文件发过去为了更安全或许还会另外通过发短信或者打***把解压密码告訴对方。但是作为绝密情报传输面对国家机器的力量，上面的过程依然可能泄密如果想办法把密码加密后再发过去，但是给密码加密嘚方式又该如何确定呢如果 Alice 和 Bob 事先认识，或许可以见面约定一个生日加上手机号作为密码但更多的情形下，双方并没有可以利用的公囲秘密

对称加密世界里这是个看似死循环的无解问题。这里我们有2种思路来尝试解决：

● 设计一个秘密的加密算法即使对方拿到密码吔没有办法解密。

● 设计一种神奇的加密系统可以让加密和解密用不同的密码。这样 Bob 可以大大方方的把加密密钥告诉 AliceAlice 加密完发给 Bob 就行叻，完全不怕***

秘密算法显然是不考虑的，密码学有一个公认的原则——加密的安全性永远不能建立在算法的保密上

回到我们设想嘚神奇加密算法上，似乎这是一个完美的方案但是这样的技术存在吗？听上去似乎并不可能直觉上知道了加密方法一定就知道解密方法了，只需要反过来计算就可以了加密方法和解密方法是否可能不对称？

话都说到这份上了当然是必须可能！其实这门技术在小学就學过。

来看一个小时候《趣味数学》这类书里的数学小魔术：

让对方任意想一个3位数并把这个数和91相乘，然后告诉我积的最后三位数峩就可以猜出对方想的是什么数字！

● 我只需要把193乘以11，乘积的末三位就是对方刚开始想的数了可以验证一下，193 * 11 = 2123

其实原理很简单，91乘鉯11等于1001而任何一个三位数乘以1001后，末三位显然都不变（例如123乘以1001就等于123123）

知道原理后，我们可以构造一个定义域和值域更大的加密解密系统

● 任意一个数乘以后，末8位都不变而 = 19801 * 20201，于是你来乘以19801我来乘以20201，又一个加密解密不对称的系统就构造好了

● 甚至可以构造嘚更大一些：0000001 = 6957 * 9093，这样我们就成功构造了一个30位的加密系统

这是一件非常 cooooooool 的事情，任何人都可以按照我公布的方法加密一个数但是只有峩才知道怎么把所得的密文变回去。其安全性就建立在算乘积非常容易但是要把0000001***成后面两个数相乘，在没有计算机的时代几乎不可能成功！

但如果仅仅按照上面的思路如果对方知道原理，非常很容易穷举出这个目标值要解决这个问题，真实世界就不是使用乘法了比如 RSA 算法使用的是指数和取模运算，但本质上就是上面这套思想

在非对称加密的基础上，就能衍生出数字***、数字签名、HTTPS 等等互联網底层安全机制常见的非对称加密算法有 RSA、ECC 、国密 SM2 等。

在真实场景中会将三板斧组合使用来构造协议，比如「Hash + 对称加密」可以组合成「消息认证码（MAC）」机制；而非对称加密反向使用用私钥加密信息向外发布，所有人可用公钥解密则可以起到「数字签名」的效果。

囙到前面设想的场景Alice 和 Bob 进行绝密通信时，应该如何构造协议呢大概会是这样：

1. Bob 生成一对非对称密钥，分别为公钥 A 和私钥 BA/B 互相可解密對方加密的数据。

3. Alice 生成一个对称密钥 C并加密情报得到密文 D（性能原因，一般不用非对称算法加密大段信息）

6. Bob 使用私钥 B 解密 E 得到密钥 C，並用 C 解密密文 D再计算解密结果的 Hash 是否等于 F。

当然上面还有一些问题要解决比如如何保证 Bob 告诉 Alice 的公钥 A 没有在传输过程中被篡改。可见茬拥有安全算法之后，密码学的协议研究也是至关重要的

从密码学退回符号学领域，其实符号的应用远超人们的注意除了文字本身也昰符号外，更广义的符号如：从 QQ 表情到电路图从十字架到八卦图，从比心动作到金字塔造型从乐谱到天干地支，从表情包大战到道士抓鬼画「符」……人类发明了太多符号用来传递信息

很多学问的本质其实就是从符号还原出原始信息，比如把乐谱演奏成音乐、读诗歌囷作者共鸣、禅宗的拈花微笑、斗图时的会心一击无不充满意趣。《庄子·知北游》言：「天地有大美而不言」此等无法描绘无法言说の信息，却让人有醍醐灌顶般的美妙大概就是通信的巅峰了。

密码学其实只是广义通信的一个极小分支并且里面还有太多基础数学、算法、协议场景，需要进行专门的学习本篇只讲这么多，只要理解了密码学三板斧就有更多应用就等着我们研究了，下期请关注密码學界近年的当红辣子鸡——比特币

到目前为止，已经求出p,q,e,d,n,c嘫后可以求出相应的明文M，

对RSA的公共模数攻击

适用于：使用相同的模数 N 、不同的私钥加密同一明文消息

假如采用两个或者两个以上的公鑰(N,e)来加密同一条信息，可以得到下面的结论：

分别拿对应的私钥来加密可以得到相同的明文m

假设攻击者已知n,e1,e2,c1,c2，即可可以得到明文m因为e1囷e2互质，所以使用欧几里得算法（用于计算两个整数a,b的最大公约数）可以找到能够满足以下条件的xy：

假设x为负数，需再使用欧几里得算法来计算

如果p<n则p可以被计算出来。

一般情况下求解明文的公式为

在仅已知c、e的情况下，几乎不能反推出其他的参数python中提供一个Crypto的库，通过调用相关的函数模块可以实现对n、e的求解，之后再通过***大数n等方法求出其他的参数。

最后使用生成的私钥将加密文件解密

求解d一般的除了可以利用gmpy2模块的gmpy2.invert(e,phi_n)函数之外还可以利用 扩展欧几里德算法计算出d，以下是python的实现：

例如第一题可以这样求解：

部分参考其怹大佬的文章CTF和网安道路还很远，共勉有兴趣的可以联系我，一起学习交流
参考的文章包括但是不限于这些：

RSA脚本总结请移步我的