BTC 学习笔记连载(2)——近现代密码学

All in Web3

0xaF56

September 1st, 2022

欢迎交流：twitter.com/songoku_web3

密码学是研究编制、破译密码的技术学科。

研究密码变化的客观规律，应用于编制密码保护信息的的称为编码学；应用于破译密码获取情报的称为破译学，合在一起就是密码学。

加密与破译互为对抗关系，密码学就是在这种不停的对抗中发展起来的。

近代密码学 [ 无线电、亚瑟·谢尔比乌斯、Enigma机]

1901年底意大利工程师 Guglielmo Marconi 成功完成了跨越大西洋的无线电通信实验，宣告无线电通信时代正式到来。

无线电的发明极大提高了人类远程通信能力，在全球范围内引发颠覆性的变革，人们的工作、生活、娱乐...整个时代的发展都深受其影响。

但无线电存在一个天然缺陷，它只管传送而无法限制接收方，要想保护所传递的信息就得采用可靠的加密技术。

对无线电信息进行加密、破解的对抗过程，直接促进了近代密码学&计算机技术的诞生。

一战时期德国外交部长Arthur Zimmermann 勾结墨西哥意图达成抗美军事同盟的电报被英国情报机构40号办公室破译，直接导致了美军参战。

本来在欧洲的战场就开始节节败退了，美军的参战直接导致德军的溃败，1919年11月11日德国代表在巴黎北部的行军火车上签署了停战协定正式宣布投降。

傲慢自大的德国人始终想不通为什么自己会输掉这次战争，直到1923丘吉尔在《世界危机》中透露，早在一战开始没多久英国就破译了德军的情报。

艹，小丑居然是自己！

如梦初醒的德国人这才意识到自己的情报机构有多拉胯，如此的羞辱让德国不得不重新审视自己的加密技术，而直到这个时候德军才想起之前有个愣头青来推销过一台密码机……

记住这个人：亚瑟·谢尔比乌斯

......

当亚瑟仔细给大家阐述了这台密码机的原理后，军方大为赞叹！

文明世界的 Enigma 机诞生了。

就是这台机器达到了古典密码学应用的巅峰！

这是密码学发展史上一个重要的标志性事件。

持续监听德国的几个大国包括英国、法国、美国，甚至波兰对收到来至这个战败国的意义不明的加密信息一筹莫展，传统方法甚至统计学都无法帮助破译。

德军在二战战场上指哪儿打哪儿，一波摧枯拉朽之势几乎将欧洲推平。（后来得知英军从1942年2月到12月都没能解读出德国潜艇发出的信号）

二战中后期爆发了一场关于加密 VS 破译的对抗，20世纪30年代波兰密码学家率先进行了系统性的研究和破译，利用德军电报中前几个字母的重复出现，破解了早期的 Enigma 机，而后辗转法国和英国，计算机理论之父图灵加入研究，通过寻找德国人在密钥选择上的失误，成功夺取德军的部分密码本获得密钥，而图灵机的发明最终成功破解了 Enigma 机，获取了相当多德军高机密情报。

战争虽然残酷但不可否认也极大地推动了科技、学术的发展。Enigma 机的加解密攻防之战，在二战时期绝对是人类智慧的巅峰！

虽然把一众密码学家搞得脑浆迸裂，但Enigma机本质上就是古典密码学的多表替换法。（Enigma机的实现原理这里不展开了，因为太经典了，我后面单独开一篇详细介绍）

另外一个经常在电影里看到的古典密码学替换法的应用能猜到是什么吧？

5秒钟想一下

...

对，就是摩斯电码，也是一组对照表，时通时断的信号代码通过不同的排列顺序表达不同的信息。

近代密码学阶段是指20世纪初期到40年代末的大约50间，这段时间主要是采用机械、机电密码机进行加解密，也可以称为机电密码时代。

现代密码学 [ 香农、理想分组密码、Feistel、DES、AES、公钥密码学 ]

1945年9月1日，香农完成了内部报告《A Mathematical Theory of Cryptography》（密码学的一个数学理论），1949年10月，该报告以《Communication Theory of Secrecy Systems》（保密系统的通信理论）为题在 Bell System Technical Journal（贝尔系统技术期刊）上正式发表。

这篇跨时代的论文首次将密码学和信息论联系到一起，把已有数千年历史的密码学推向了基于信息论的科学轨道，并提出扩散和混淆两大设计原则，为对称密码技术提供了成体系的数学理论基础。

这标志着现代密码学的开启。

这是密码发展史上的第一座里程碑性事件！

编码及破译的攻防被提高到了一个前所未有的高度，现代密码学核心加解密算法分类如下：

散列函数

也就是我们常说的哈希函数、杂凑函数、摘要函数，严格来讲哈希并不属于密码，因为它是单向的并不适合用于加解密。

但是它却有不可忽视的重要作用，BTC共识协议就是构建在哈希函数SHA-256的基础上，甚至可以说哈希是整个Crypto世界的基础，归类到现代密码学的范畴不过分。

这么重要的存在，下一篇单独深入讲解，这里就不展开了。

对称密码体系

对称密码的对称2个字简明扼要地表达了其特点，也就是加密、解密过程用到相同的秘钥。

对称密码主要分为序列密码和分组密码：

序列密码

序列密码也称为流密码，流密码是将信息中的每一个元素（1个字母、1个bit）作为基本的处理单元进行加密，解密的过程就是进行逆运算。

前面讲到的古典密码学涉及到的加解密方式大多都属于序列密码，但在当代实际应用的序列密码就复杂多了，流密码算法的代表有A5和RC4，A5是GSM规定的加密算法，RC4被应用在1999年的安全传输层协议（TLS），现在都已证明不再安全，有兴趣的可以深入了解一下。

通常使用相同的伪随机加密数据流作为密钥，对一个 bit 进行加密操作，由于实际操作相对困难通常用于硬件加密。
分组密码

分组密码是先对明文进行等长的分块，再使用确定的算法和对称密钥对每组分别加密，解密的过程同样是进行逆运算。

细心的读者可能已经注意到了，上一篇古典密码学中讲到的栅栏密码就是属于分组密码。

DES、3DES、AES是现代密码学分组密码的代表，应用于电子邮件加密、银行交易转账加密等软件类加密场景。

对称密码中和我们息息相关的是分组密码，涉及到现代互联网及生活应用场景的方方面面，今天我们着重讨论一下：

前面讲了分组密码的加密过程主要是将一条长信息M分为等长的n个块H，然后逐个对齐进行加密，解密就是其逆过程：

按理想分组密码来讨论，一个n位二进制明文分组一定对应一个n位的二进制密文分组，同理一个n位的二进制密文分组也对应这一个n位二进制明文分组。

为什么？

比如3位二进制明文，要映射到2位二进制密文，那就是8个输入空间要映射到4个输出空间上，就没法一一对应，加解密就无法做到可逆！所以理想的分组密码通常需要密文和明文等长，一般密文比明文长，这时候只需要给明文补位即可。

在等长的情况下，所有可能的明文分组与对应的密文分组组成的一个表称为可逆映射表，这是3位二进制的一个理想分组密码的可逆映射表：

那接着我们再深入一下：

一个n位的二进制数的排列组合是：2^n

一个n位的二进制明文映射到一个n位的二进制制密文可能的情况有：2^n！(这里如果不懂，可以设n为2排列组合来列举一下，就是一个简单的概率问题)

任意一份n位二进制数的明文-密文映射表，将所有密文连一起就形成一份完整的密文，这个密文的长度是：n * 2^n

这里的密文长度取决于分组长度，分组长度太小容易被破解，分组长度过大会导致秘钥长得离谱，比如后面要讲的DES分组长度为64bit，秘钥长度就是64 * 2^64，这是一个天文数字，这在秘钥共享上是不接地气的。

每当这个时候总有神人出现~

这次又是德国人：Horst Feistel (我无法掩饰对德国这个国度的敬仰)

Feistel是一位物理学家兼密码学家，在IBM工作期间完成了一个用于构造分组密码的对称结构 Feistel cipher，也称为 Feistel network，之后的大部分分组密码都是基于该方案，包括后面也会重点讲到的数据加密标准（DES）。

Feistel是一种多轮迭代密码，其内部函数称为轮函数，不知道轮函数是不是Feistel第1个提出的，但多轮是一个在Crypto世界中用烂的手法，包括在BTC的私钥生成公钥、公钥生成地址的过程中，这里先记住轮函数这个概念。

Feistel另一个灵性操作是随手就提出完全没必要使用理想的分组密码，足够安全就可以了。是的，没必要付出巨大的代价干多余的事，够用就行了！

加密解密永远都会在对抗中发展，一个时代有一个时代的应对之道。

那怎样才是足够安全的呢？

那就是香农提出的扩散&混淆：

扩散

就是使明文和密文之间的关系尽可能复杂，无法从明文推导密文。

可以通过让明文中的N位对密文的M位造成影响（N>M or M = 1），从而达到扩散效果。也可以先对明文进行置换，然后使用轮函数多次对其加密，从而达到扩散效果。

后面展开的 Feistel 密码就能让你了解到轮函数的精髓。
混淆

就是使密文和密钥之间的关系尽可能复杂，无法从密文推导密钥。

后面会讲到的AES就混合使用了每轮4个步骤（字节替换、行位移、列混淆、轮秘钥加）达到扩散和混淆的效果。

扩散和混淆简明扼要地抓住了现代分组密码设计的最核心的本质。

Feistel密码包含16轮迭代和一次左右置换：

加密过程

如下图，左侧为加密过程。

首先将明文分为左右等长的两部分，分别记为 LE0 和 RE0 ；
然后使用轮函数 F(K1,RE0) 对RE0 进行运算，其结果结果再与 LE0 异或，其结果成为下一轮的 RE1 ；
同时直接将 RE0 挪到下一轮 LE1 的位置上；
每一轮的输出都作为下一轮的输入，一直进行16轮迭代；
最后交换 LE16 和 RE16 ，形成密文；
这里使用到的密钥 K1—K16 是由密钥 K （长度为k的二进制数）扩展生成的，秘钥扩展可以自行google理解一下。

这种方式本质上所需的密码长度为2^k，相较于理想分组密码的 2^n！ 就小很多了。

解密过程

如下图，右侧为解密过程。

由于加密使用的是异或，所以解密过程就是一个顺序翻转方法一致的过程；

在Feistel的基础上，DES（Data Encryption Standard）美国数据加密标准算法诞生了，DES是现代密码学分组密码的经典。

这是密码学发展史上的第二个里程碑性事件！

也是现代密码学的重要标志！

DES最早可以追溯到1970年初，但直到1976年11月才被NBS（国家标准局，现在的NIST）确定为联邦标准，并在1977年1月作为联邦资料处理标准 FIPS PUB 46发布，并授权在非机密级政府通信中使用，随后该算法在国际上广泛流传开来。

70年代初美国政府对其计算机安全问题日益担忧，1972年NBS开始征集用于加密政府内非机密敏感信息的加密标准，1973年5月在咨询了美国国家安全局（NSA）之后，NBS向公众征集可以满足严格设计标准的加密算法，然而没有一个提案可以满足要求。次年8月NBS开始了第二次征集，这一次IBM提交了一份算法提案，这份提案被有限度的接受，这种算法就是基于 Fiestel 提出的。

DES算法明文按64位进行分组，密钥长度也为64位（实际是56位参与运算），本质上还是基于Fiestel的，只是每一轮的轮函数及秘钥K派生算法更复杂了：

首先64位明文右侧的32位经过置换变成了48位；
然后通过置换压缩将56位秘钥变为48位秘钥；
然后48位的明文和48位秘钥进行异或运算；
异或运算后的48位二进制数被分为8组6位二进制数，通过8组S盒的置换得到32位；（8个S盒的替换方式这里就不细讲了，有兴趣的自行google）
剩下的就是和Fiestel一致了；

DES在最初预期作为一个标准只能使用10-15年，但在实际使用中并没有受到严重的威胁，其寿命比预期要长得多。被采用后每隔5年会进行一次评审，最后一次评审在1999年1月，DES成了当时最主流的对称加密算法。

随着计算机计算能力的飞速发展，DES密钥过短的问题成为了DES算法安全的隐患。1998年RSA数据安全公司发起的DES挑战赛试图证明DES的安全性问题，最终由一个称为**电子边境基金(EFF)**的组织在56小时成功破译，非常具有节目效果的是破译后得到的信息居然是："It's time for those 128-, 192-, and 256-bit keys"。

6个月后的1999年1月，电子前哨基金会和distributed.net团队合作参加了RSA安全公司举办的第三届挑战赛，并破译了另一则DES加密的消息，整个过程耗时仅22小时15分，这次挑战动用了互联网上的100000台计算机。

......

最终NIST于1997年发布公告，征集新的数据加密标准作为联邦信息处理标准以代替DES。

......

2002年5月AES（高级加密标准）正式取代了DES成为了新的联邦政府标准。

不同于DES，AES不仅将密钥长度提升至128位、192位、256位，还改进了轮函数算法大幅提升了计算速度，AES同样基于多轮，除了最后一轮其他轮都是由四个步骤组成，字节代替、行移位、列混淆、轮密钥加：

无论秘钥长度是多少，AES明文都是被分组为128位的，即16字节；

并且都以一个4x4的矩阵表示；
然后每一轮基于这个4x4的矩阵进行字节代替、行移位、列混淆、轮密钥加；

这里的字节代替很简单，就是基于一个16x16的S盒替换；

行位移也很简单，就是第2、3、4行分别移动1、2、3个字节形成新的举证；

列混淆用到了矩阵乘法，相对复杂一点；

轮秘钥加就是进行异或运算；
AES的秘钥派生是比较值得研究的，感兴趣的可以自行google；