写在前面

笔者在下定决心要学习密码学相关知识之前，一直对加密解密感到无力：数学公式也太难了，定理未免也太多了！加上工作中就算不清楚原理，只需要知道对称加密、非对称加密大概是什么；会调用相关的API就可以解决问题了。

折腾这些也是“迫于生计”，笔者从事边缘计算设备近2年，跟一些恶劣的设备打交道，比如内存只有512MB，系统不带且不支持安装openssl；设备最后部署在民用网络下，经常被challenge安全问题。于是，不得不好好补习下这块空白。本文是笔者的学习笔记，也希望对跟笔者一样对密码学懵懵懂懂的初学者有所帮助，本文将不会很深入讨论原理、也不会过多出现公式、推理和证明（笔者自己的数学也是个渣渣）。当然，若文章有表述不正确的地方，非常欢迎指出，交流学习。

本文将讨论：

  • 加密和解密（重点讨论加密）：
    • 加密是什么？目的是什么？从古典密码学如何发展到现代密码学？
    • 加密类型：对称加密和非对称加密分别是什么？底层原理是什么？
    • 常见的加密算法：DES，AES；RSA，DH，ECC。嗯，一堆令人头疼，看了讨厌但是用起来真香的名词。哎，RSA不就是非对称加密吗？那DH和ECC算什么？

0. 加密和解密（Encryption & Decryption）简介

首先来认识”加密“，英文对应是Encryption，翻看其定义，笔者摘录了认为解释得最好的：

Encryption is the method by which information is converted into secret code that hides the information's true meaning. The science of encrypting and decrypting information is called cryptography.
翻译：加密是一项把信息转换为隐藏其真实含义的秘文的方法。加密和解密信息的科学被称为密码学。

从上文可以知道：加密是一种把「可读信息」转换为「不可读信息」的手段。当然，我们自然还希望这种手段能够绝对安全，即只有『合法者』才能读取，而其他人都无法破解读取。

1. 从古典密码学到现代密码学

密码学的起源非常早，不知道这种说法正不正确：人类战争推动密码学的发展（笔者非常痛恶战争，但是回顾历史，人类战争真的是推动技术发展的第一动力，写到这里，心情复杂）。笔者小时候听到过一个很有趣的故事：

在古希腊战争时代（故事起头总是这样的，究竟是不是古希腊就不得而知了），希腊和敌国（也不知道具体是哪个国家）发生了战争。混入敌方的战士窃取了敌方机密，需要把信息传回希腊，但是需要防止信息中间被人截获。于是他首先将布条绕在一根棍子上，然后写下了机密，最后把棍子插在腰间、布条藏在身上，秘密潜回希腊。中间肯定是经历了千难万险，也一定遇到了敌方战士，好在对方并没有破解布条的秘密，所以最后他成功送回消息。回到希腊后，他再次把布条绕道棍子上，希腊军队首领获得了机密。故事最后一定是：多亏了这个机密，希腊大获全胜。

哎，在这个小故事里，『棍子』就是加密/解密手段。我们中国也有很多类似的故事，笔者一时也记不起来了，总之一定有这种故事：

拿到密文后，解密者再从书架上拿出一本很神奇的书，对照密文和书本，逐字翻译，最终得到了可以读懂的原文。

从上种种，可以看到，密码学很早就出现了，比如菩提老祖敲了孙悟空后脑勺三下，被孙悟空正确解密为“半夜三更去学武”。经过几代密码学家们的努力，最终形成了可证伪、科学有序的密码学。

而在密码学领域，前人的『棍子密码』，上文的『书本密码』亦或者是『凯撒密码』（Google自行了解），都被归到了古典密码学范畴：以「置换法」与「替换法」为基础，多应用于军事与情报领域（摘自《从古典到现代密码学，细数密码学发展历程及理论研究》）。

古典密码学在当年，是很有用的。但在计算机发明之后，算力和算法的极大提升，这些方法就显得“太小儿科”了。

那什么是现代密码学呢？知乎上也有一个有趣的问题：现代密码技术和古典密码技术的分水岭是什么?，回答中提到了一个很关键的点：

密码系统的安全由保密算法转向保密密钥。

而现代密码学的一个关键人物，是的，大名鼎鼎的香农。嗯，香农对于EE可能就是图灵之于CS，不过最后会发现EE和CS其实是一家。1948 年，克劳德·香农发表了著名的论文《通信的数学理论》（The Mathematical Theory of Communication），开创了一门新的学科：信息论。隔年，香农发表了《加密系统的通信理论》(Communication Theory of Secretary System)，首先使用数学工具对加密系统进行分析。香农的理论使密码学得以成为真正的科学，也标志着现代密码学的开端（摘自《从古典到现代密码学，细数密码学发展历程及理论研究》）。

再接下来，就是1976年Whitfield Diffie 和 Martin E.Hellman 在 IEEE Transactions on Information Theory 上发表了论文《New Directions in Cryptography（密码学的新方向）》，探讨了无需传输密钥的保密通信和签名认证体系问题，正式开创了现代公钥密码学体系的研究（摘自《密码学简史》）。随后，1978年Rivest、Shamir和Adleman基于DH发表的论文，提出了大名鼎鼎的RSA公钥密码体制。

（是不是有个很神奇的问题，从1948年到1976年中间近30年的时间，发生了什么？要知道对称加密算法DES和AES分别制定与1976年和2001年。但是一点可以肯定：这个时期的密码学都是基于密钥体系的。）

2. 对称加密（Symmetric Encryption）

平时我们常说的“对称加密”，一般是指AES算法。但从更广义的分类上来说，对称加密算法可以分为：

  • 序列密码/流密码（Stream Cipher）。维基百科对于它的定义是：
    加密和解密双方使用相同伪随机加密数据流（pseudo-random stream）作为密钥，明文数据每次与密钥数据流顺次对应加密，得到密文数据流。实践中数据通常是一个位（bit）并用异或（xor）操作加密。
    本文不对此做深入讨论，感兴趣的同学推荐阅读《Overview: Stream Ciphers vs. Block Ciphers》。
  • 分组密码/块密码（Block Cipher）。维基百科对于它的定义是：
    将明文分成多个等长的模块（block），使用确定的算法和对称密钥对每组分别加密解密。
    我们平时常见的AES、DES算法都属于分组密码。

接下来，一起来看看常见的AES和DES算法，终于到了AES和DES，激不激动（emm...一点也不激动）！友善提醒：接下来两小节可能会有点晦涩难懂，坚持住呀！


2.1 AES（Advanced Encryption Standard，高级加密标准）

听AES的名字，是不是很奇怪：哎，这不是一个标准吗？我们知道，但凡叫做标准的东西，大多是一个空头文档，没有具体实现的东西。

是的，AES是NIST（美国国家标准与技术研究院）在2001年推出的标准，内容见《ADVANCED ENCRYPTION STANDARD (AES)》。但其实在1997年的时候NIST就公开征集更安全的加密算法，经过3年的时间，Rijndael算法最终入选。也就是说，2001年推出的AES标准，其实就是Rijndael算法（子集）。因此，有时候在网上搜索AES算法，会看见Rijndael这个名词，其实是一个意思：AES=Rijndael算法子集。

Rijndael算法是什么？搜索Rijndael出来的词条，大多是AES，这个算法最初是由比利时学者Joan Daemen和Vincent Rijmen所提出的，算法的名字就由两位作者的名字组合而成。

故事听完，开始介绍AES算法本身了。笔者最早看到很多博客AES算法解析，感觉高深莫测，马上就头疼脑热，看不下去了，直到看到了github-matt-wu/AES。请注意：AES没有数学公式、证明和推理，官方号称是基于代换-置换网络（SPN，Substitution-permutation network）的迭代算法，大白话说，AES就是循环地对矩阵/向量做查表替换、位运算、乘积的过程。所以，相信自己，一步一步follow下来，也能了解AES全貌的。

2.1.1 AES预备知识

  • 预先要知道的AES小知识：
    • 统一名称，对待加密的原文数据，称为明文（plaintext/cleartext）；加密得到的称为密文（ciphertext）；对称密钥简称为密钥（key）。
    • AES的密钥长度支持128/192/256bits。注意：这里指的是AES密钥总长度。
    • AES的组（block）大小只支持128bits，尽管Rijndael支持分组128/192/256bits。注意：这里的组大小是对明文进行分组后的每组的数据长度。

2.1.2 AES概览

先看看AES加密算法全过程的图（图摘自matt-wu/AES）：

AES Overview

是不是完全没有思路（不管你是不是，我肯定是的）？好，一步步来拆解：

  1. 图左侧（蓝色）部分是对明文的处理。首先，D_i是一个明文字节（byte=8bit），图中是4x4=16的矩阵，称为state，换算过来就是16x8=128bits（就是AES的组大小）。其次，每一个round（轮函数）就是一套数据操作，简单理解为“加、减、乘、除”，而每一个round的输入是上一个round的输出，换言之，最初state是明文，round目的就是不停修改state内容。
  2. 图右侧（红色）部分是对密钥的处理。首先，K_i是一个密钥字节（byte=8bit），图中演示的是AES-128，也就是密钥长度128bit的加密算法，平时我们常接触到的是就是AES-128。密钥的结构和state相似，称为roundkey（轮密）。其次，每一个round结束后，roundkey也会被修改，对应的修改算法/过程被称为密钥扩展算法（Key Expansion/Schedule）。

2.1.3 AES 轮函数 - 明文加密过程

先看每一个round的操作，round10+round0 = round1~9，了解了一个完整的round过程，等于了解了基本AES的明文加密过程（图摘自《Symmetric-key cryptography》）：

AES 轮函数

有一点：round只对明文（更严谨地说是对state）进行操作！！！roundkey只是参与者，roundkey的修改是在密钥扩展（Key Expansion）另外操作的。一个完整的round分为4个步骤：

1. SubBytes：逐字节替换。查找一张内置的表格，把state每个字节逐一替换为表格对应的字节
内置的表格叫做S-box（lookup table），是一张16X16的常量表格，加密用的S-box如下（图摘自《Rijndael S-box》）：

AES S-box

之前已经介绍过：state是一张4x4的byte矩阵，每一格是一个byte。一个byte可以拆成4bits+4bits，也就是[0~F]+[0~F]的拼接（4个bit可以表示的数值范围：0~(2^4)-1，表示为十六进制就是0~F），分别代表的是S-box的x轴和y轴。那么查找的过程就是：首先根据state原字节的前4bit和后4bit的数值内容作为S-box的x和y下标查找得到目标byte，接着用这个目标byte去替换掉state原byte。过程示意图如下：

AES 查S-box替换示意图

2. ShiftRows：平移行。state每一行（row）各自进行轮换。
这一步骤也是相对简单易懂的，直接上示意图就明白了（图摘自matt-wu/AES）：

AES ShiftRows

3. MixColumns：列混合，state每一列（column）单独和一个常数矩阵做乘法。
这一步骤官方的说法是以多项式做模为理论基础分析展开的，看的笔者一头雾水。这里，抛开多项式，单单从操作上来看：state每一列单独和一个常数矩阵做乘法（自行回忆矩阵乘法）。实际操作示意图如下：

AES MixColumn

总之最后能够达到“column diffusion（列混淆）”，这个后面会介绍为什么一定要“diffusion”。

4. AddRoundKey：和轮密做XOR（位或）操作。
在一个完整的round中，密钥只参与了这步操作：4x4的state矩阵和4x4的roundkey每一位做XOR操作（图摘自一个超有趣的博客《A Stick Figure Guide to the Advanced Encryption Standard (AES)》）：

AES AddRoundKey

看完这4个步骤，是不是有种：AES也就这么回事儿嘛！但是仍有问题没有解决：roundkey是怎么迭代的？

2.1.4 AES密钥扩展 - 修改密钥过程

roundkey迭代的过程，就是密钥扩展算法（Key Expansion/Schedule），先推荐这方面一篇不错的文章《AES Key Expansion》。下面是整个迭代生成过程的示意图（图摘自《AES Key Expansion》）：

AES 密钥扩展算法

乍一看，很复杂的样子？好，接着一步步拆解，一次roundkey生成的过程可以拆解为4个步骤：

1. RotWord：只对最后一列操作，平移列（类似ShiftRow）。
取出4X4的密钥byte矩阵，每一列被称作一个word（在state矩阵中也是一样，word=column）。这一步取出最后一个word，对这个word进行上移一格，示意图如下：

AES RotWord

2. SubWord：只对最后一列操作，逐字节替换（类似SubBytes）。
这一步的操作就完全是之前的SubBytes的操作：查S-box并进行byte替换。不同的是，对于state而言每一个byte都要查表；而roundkey只需要操作最后一个word即可。

3. KeyXOR - 这一步没有官方名称，第一列、最后一列（第四列）和一个RCON常量列向量做XOR操作。
RCON是一个常数项量，如下：

AES RCON

具体做法其实相对比较简单，下图直接明了：

AES RCON位或操作

这一步结束后，就得到了新的roundkey的第一列向量。

4. KeyXOR - 这一步也没有官方名称，新roundkey的word和旧roundkey的word做XOR操作。
语言描述起来相对复杂，这里使用公式说明会更明晰。先记旧roundkey=K，有K=[w_1, w_2, w_3, w_4]，新roundkey=K'，有K'=[w'_1, w'_2, w'_3, w'_4]。

综上，一次roundkey生成的过程结束了，再回头看整个迭代生成过程的示意图是不是觉得一下子豁然开朗了？（什么？没有？嗯，那你需要细细品品了。）

2.1.5 AES 组间迭代

到这里，我们知道了一组（block）内部128bits是怎么进行加密的，但是一个明文的长度极有可能远大于128bits，各个组之间又是怎么“拼接”的呢？此外，如果明文不能被128整除呢？也就是说很大概率会存在一个组的长度小于128bits，又怎么处理呢？

组间拼接（Cipher Mode）

有一点需要keep in mind：因为AES操作太多了，容易混乱，因此千万不要和round（轮函数）搞混了，它是独立于round之外的。本小节接下来出现的图都来自文章《【密码学】一万字带您走进密码学的世界（上）》，不过笔者推荐更推荐文章《现代分组密码的操作模式》和《Block cipher mode》，文章对于每种“拼接”模式、优缺点都分析得很好了，本文就不赘述了，我们就以EBC和CBC2种模式来感受下：

1. EBC：最直接的拼接方式，每组结束后，直接把最终的state拼接就成了。简单，可并行。

AES EBC

这种方式当然是有问题的，下面是摘自YouTube-Basics of cryptography - 2 TDES, AES, RSA, ECC, DH, ECDH, IES的例子。非常明显，如果明文中正好几个组的内容一样，那么加密得到的密文内容也相同。因此CBC虽然很快，但是安全等级不高。

AES EBC例子

2. CBC：每组的密文数据，还会参与下一组的加密操作。
很直观可以从示意图中看到：在明文被送到round之前，会先与上一组的密文首先进行XOR操作（对于第一组来说，是和初始化向量IV做XOR）。

AES CBC

CBC显然比EBC更安全，但是也带来一个缺点：不可并行。据悉，目前我们常接触的AES的组间“拼接”模式就是CBC。

数据补齐/填充（Padding）

Padding并不复杂，但是需要遵循同一套补齐/填充规则，具体可以参考维基百科Padding(cryptography)，这里介绍2种常用的Padding方式：

原文 01
原文 02 02
原文 03 03 03
原文 04 04 04 04
原文 05 05 05 05 05
原文 06 06 06 06 06 06

细心的你发现了一个问题没有：如果原文正好是block size（AES算法来说是128bits）的倍数，是否不需要填充？如果是，那么解密的时候怎么知道数据是否被填充过？
答案是：无论是否block size的倍数，都需要填充。现在讨论倍数的情况，那么在最后增加一个16byte的block，填充上16个16就可以。这种好处是，在执行逆向过程的时候，只需要根据最后的字节内容，去掉对应的byte就可以了，非常灵活。
至于PKCS#5，直接用维基百科的解释：

PKCS#5 padding is identical to PKCS#7 padding, except that it has only been defined for block ciphers that use a 64-bit (8-byte) block size. In practice the two can be used interchangeably.
PKCS＃5填充与PKCS＃7填充相同，只不过它是为使用64位（8字节）块大小的块密码定义的。 实际上，两者可以互换使用。

嗯，谷歌翻译真香。

2.1.6 AES 扩展

AES-128的加密算法基本介绍结束了。但其实还遗留了1个问题：AES-192和AES-256是怎么做的呢？要知道，在AddRoundKey步骤是state和roundkey进行XOR，而state是128bits（4x4byte矩阵），也就是说，roundkey一定也是128bits。但是192是4X6，这个怎么办呢？AES key expansion for 192-bit也问了同样问题，解答如下：

无论是192bit（4X6）还是256bit（4X8），roundkey仍旧是4X4，而且密钥扩展算法也是一样的，只是我们会发现，这种情况下，一个roundkey只是密钥的子集了。

AES-192 例子

在matt-wu/AES中也说明了，192和256的round也需要有相应的调整，对应关系如下表（AES取N_b为4）：

AES 密钥长度和round次数关系表


综上，终于把AES写完了。通过文字把一个算法写清楚不容易，看到这里的你更加不容易（捂脸）。如果文中仍有交代不清楚、不正确的，非常欢迎留言、私信交流讨论。


2.2 DES（Data Encryption Standard，数据加密标准）

DES是AES的前身，1977年被NIST推出，但是在1999年该算法被破解，于是当年美国政府公开征集新的更安全、灵活的加密算法，然后就有了AES。

现在DES基本已经被弃用了，因此本文也就不讨论DES算法。此外，再提一句，在DES基础上，还有一个3DES，也有称为TDES（Triple DES），可以简单认为是做3次DES。

3. 非对称加密（Asymmetric Encryption）

非对称加密的出现，可以说是整个密码学中的又一个重要里程碑：非对称加密算法是公开密钥密码体系的坚实基础，可以这么说，没有非对称加密，就没有我们现在的整个数据安全系统，特别是网络安全体系。因为，仅有对称加密，我们就不得不为了传输一把至关重要、不可泄露的密钥而绞尽脑汁。实际上，到目前为止，除了非对称加密，确实也没有更安全、优雅的方法。

非对称加密算法最早是1976年由Diffie和Hellman发表的文章中提出的，论文一经发表，很快就引起了学术和工业界的轰动。当时在MIT工作的Rivest、Shamir和Adleman正是受到了这篇论文的启发，折腾一年多之后，在1977年推出了RSA算法，RSA推出后不久就名声大噪，被一直广泛使用到现在。再之后，也有很多学者围绕非对称加密展开了各式研究，推出了不少优秀的算法，如：Elgamal、Robin等算法，值得一提的是1985年被提出的ECC算法，ECC算法被证明在相同密钥长度下，是现有非对称加密算法中最安全的。

笔者是个数学渣，而现有的非对称加密体系主要就是围绕各种数论、定理展开的。本章的介绍仅仅停留在浅层的数学表达上，仅供娱乐。（嗯，一定会努力提高姿势水平的）

3.1 DH

DH算法是Diffie–Hellman名字的组成，该算法过程如下：

DH算法

3.2 RSA

RSA是3个共同推出该算法的名字的组成， Ron Rivest、Adi Shamir 和 Leonard Adleman，关于RSA的故事，非常推荐阅读localhost-8080（matrix67的妹纸，现在年轻一辈都不知道matrix67了，我还记得本科第一次读到matrix67的博客，看的热泪盈眶）的博客《RSA 算法是如何诞生的》，其数学推导过程如下：

RSA算法

3.3 ECC

ECC，全称Elliptic curve cryptography（椭圆曲线加密算法），由 Koblitz 和 Miller 两人于 1985 年提出。ECC也逐渐衍生出各种相关算法，比如ECDH，ECDSA，它们都是ECC的不同实现。虽然RSA更耳熟能详，但实际上，ECC正有逐渐取代RSA的趋势，比如前阵子很火的比特币、区块链中使用到的非对称加密技术用的就是ECC。

笔者现在还处于高中圆锥曲线的恐怖阴影之下，因此对于ECC还是敬而远之。对于这块有兴趣的同学，请自己网上搜索其他博客了解，本文也没有推荐。（嗯，真的是一点都没了解）

写在后面

  1. 对于不少人吐槽：文章跟Golang一点关系都没，挂在开头干什么？

回答：这个是笔者自己学习的历程，现在确实跟Golang没有什么关系，但是很快就会基于这些理论退出Golang的源码阅读、实际应用解析的文章。真不是搞噱头，要搞噱头的话，直接写一个什么“一文读懂加密”之类的不是更好？

2. 学习AES具体流程有什么用？会调用API不就好了？

回答：笔者最早的时候也是这么想的，密码学这块领域更多是数学家发挥的空间，对于数学渣的我来说，能够跟上思路都不见得是很容易的事情。而且，openssl等加密库都已经帮忙做好封装了，直接用用就成了呗。但是吧，最近觉得自己不能再继续水下去了。而且真的老老实实学习下来会发现：加密真的挺有趣的！（不骗你，逃）