密码学幼稚园丨密码朋克的社会实验(二)

Track-SSG   ·   发表于 2019-01-04 11:05:18   ·   漏洞文章

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

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

一、信息和编码

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

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

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

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

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

 密码朋克的社会实验

(西周·散氏盘·局部)

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

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

在 ASCII 码中字母「A」使用十六进制数「0×41」表示。

在 Unicode 码中汉字「山」使用十六进制数「0x5c71」表示。

信息逐步抽象过程(信息逐步抽象过程)

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

二、密码学发展史

密码,本质就是信息的非标准编码。

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

1. 古代密码术

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

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

符号替换法

顺序改变法

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

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

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

 密码朋克的社会实验

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

2. 近代战争时期

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

电报发报机

(电报发报机)

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

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

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

恩尼格玛密码机

(恩尼格玛密码机)

从设电报发报机备可以看出,这个阶段,密码学已经进入机械化阶段。

3. 计算机时代

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

电影《黑客帝国》剧照

(电影《黑客帝国》剧照)

三、密码学研究什么

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

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

加密解密的数学算法本身

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

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

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

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

7.jpg

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

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

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

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

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

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

四、密码学三板斧

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

电影《一代宗师》剧照

(电影《一代宗师》剧照)

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

单向散列(Hash)

对称加密

非对称加密

下面逐一解释:

1. 硬币扔出的 Hash

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

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

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

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

1. Bob 先想一个数,并加上123456。

2. 把结果平方,取第3至第10位,组成一个8位数。

3. 再用这个数除以456789求余数,把这个结果告诉Alice。

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

5. Bob 告诉Alice 原始值,Alice验算确认。

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

1. 1234 + 123456 = 124690

2. 124690 * 124690 = 15547596100

3. 54759610 mod 456789 = 401719

Alice 拿到的结果是401719,既可以验证 Bob 有没有撒谎,同时 Alice 又很难根据401719算回1234

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

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

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

2. 根据 X,很难算出 M。

3. 很难找到 M 和 N,令 F(M) = F(N)。

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

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

2. 历久弥新的对称加密

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

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

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

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

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

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

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

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

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

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

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

设计一种神奇的加密系统,可以让加密和解密用不同的密码。这样 Bob 可以大大方方的把加密密钥告诉 Alice,Alice 加密完发给 Bob 就行了,完全不怕监听。

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

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

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

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

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

比如 A 想的是123,计算出123 * 91 = 11193,并把结果的末三位193告诉我。

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

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

9.jpg

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

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

甚至可以构造得更大一些:4000000000000000000000000000001 =1199481995446957 * 3334772856269093,这样我们就成功构造了一个30位的加密系统。

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

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

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

五、真实世界

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

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

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

2.  Bob 将公钥 A 告诉 Alice。

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

4.  Alice 用公钥 A 加密 C 得到密文 E,并计算情报的 Hash 值 F。

5.  Alice 将 D、E、F 全部发给 Bob。

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

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

六、写在最后

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

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

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

本文作者:karmayu @ 腾讯安全云鼎实验室,转载来自 FreeBuf.COM


打赏我,让我更有动力~

0 条回复   |  直到 2019-1-4 | 1155 次浏览
登录后才可发表内容
返回顶部 投诉反馈

© 2016 - 2024 掌控者 All Rights Reserved.