1.计算机出现以前的密码
这篇文章旨在浅显易懂的介绍标题所述的各个算法概念与应用，文中没有数学公式。在主要概念出现之前，先简谈一下密码发展史的几个重要时期。
计算机出现之前，加密算法主要有“替换加密”，“移位加密”，“维吉尼亚密码”等。
著名的凯撒密码就是最简单的“替换加密”，密文每个字母相对原文向后移动3位，例如：
ATTACK AT THREE AM TOMORROW
加密后就变成了
DWWDFN DW WKUHH DP WRPRUURZ
复杂的替换加密会将26个字母都替换成另一个不同字母。解密时需要知道加密进行的操作，即字母是如何替换的。在这里，字母替换表称为密钥，可能的替换方案越多，密钥空间越大，则越不易被破解，对于26个字母，不重复的替代方案有26! 大约4×1026种！
替换加密尽管有很大的密钥空间，但存在一个致命弱点：一种语言中每个字母出现的频率是固定的。例如英语中e是最常见的字母，如果使用替换加密，那密文里最常见的字母很可能原文就是e！此外，单词首字母频率最高的是t；th，he，in等组合字母出现次数也要比其他字母组合频繁的多。所以当时经验丰富的密码师可以很容易破译这类加密。1587年，苏格兰玛丽女王使用这种方法加密“暗杀英格兰伊丽莎白女王计划”，但不幸内容被破译引来处刑。
二战时期德军著名密码机“谜团”（Enigma）将“替换加密”发展到极致，是计算机出现前最复杂的加密方式。这种机器类似打字机，敲入明文可以直接显示密文（通过亮灯）；反之，如果知道密钥能正确连线和摆放转轮，敲入密文也可以直接还原明文。Enigma的复杂之处在于机器上的3-4个转轮，每输入一个字母，其中一个转轮就会旋转一格，类似汽车里程表。当转动一圈后，第二个转轮会转动一格，第二个转轮转动一圈后，第三个转轮再转动一格。而替换方案由全部转轮的位置来决定。这表示，虽然本质仍是替换加密，但替换方案是变化的。原文中出现第一个e和第二个e加密后不一定相同。但即使是这样，对岸的英国破译小组，在几百个数学家努力下（其中包括计算机之父--艾伦·图灵），仍然破译了大量密码，从而提前结束了战争。
2.编码（Hex，Base64，Urlencode）
这些算法不能算作加密，只能称之为“编码”。因为编码和解码算法都是公开一致的，编码后的文本只是人类不熟悉的计算机语言而已。
计算机出现后，信息保存在磁盘中。由于计算机只能识别二进制0和1，需要制定一套方案用来保存文字信息。ASCII码表，雏形形成于1963年，用7 bit，一共27=128种编码表示数字，英文，和标点符号，随后扩展到8 bit，新增了ä, ö, ü, ß等西欧字符。早期IBM推崇的1字节=8 bit 概念此时已经根深蒂固，因为对大部分欧美国家，1字节就是1个字母或1个标点。
对非英语国家，如中国，在1980颁布GB2312编码规格，用两字节216=65535种编码，表示七千多个简体字和字符。1995年又颁布了GBK，在兼容前者基础上，新增了繁体字和部分日韩文字。
世界上常用的几十种语言，如果每个国家都有一套自己的编码方案，跨国通信是很困难的，这时Unicode出现。Unicode选择4字节 232=4294967296 这么多种编码，足够保存世界上所有语言还绰绰有余。四字节直接保存的结果是UTF-32，名称源于4字节=32 bit。虽然编码统一问题解决了，但这对于大部分英语国家而言是极其浪费空间的。本来人家1个字母1字节就够，现在要扩大到4倍！于是又有了UTF-8，可以理解为UTF-8是Unicode存储时压缩后的“可变长”编码。英语部分不变，UTF-8完全兼容ASCII；非英语字符占2-4个字符，达到了统一与节省的平衡。
二进制01序列为了表示方便，书写时通常选择16进制，即Hex。
以中文为例，“你好”在经过utf-8编码后是，
| 二进制 | 1110 | 0100 | 1011 | 1101 | 1010 | 0000 | 1110 | 0101 | 1010 | 0101 | 1011 | 1101 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Hex | e | 4 | b | d | a | 0 | e | 5 | a | 5 | b | d |
由于图片，文件等格式的二进制文件源码无法转为字符串（ASCII包含了大量不可见字符），直接用Hex与原文件相比又整整多占用一倍空间！因为Hex仅仅用到了数字0到9，字母abcdef（不区分大小写）加起来才16个，浪费了大量可视字符。 Base64编码算的上是“折衷”方案，它模仿ASCII，用到的字符有：全字母大小写52个，数字0到9，外加+和/ 两个符号。
| 二进制 | 111001 | 001011 | 110110 | 100000 | 111001 | 011010 | 010110 | 111101 |
|---|---|---|---|---|---|---|---|---|
| Base64 | 5 | L | 2 | g | 5 | a | W | 9 |
Base64相比Hex，实际只是将二进制流从4 bit分组，变为6 bit分组。26=64，即6 bit选择64个符号来表示，这就是Base64名字的由来，Hex也可以被称为Base16。
1字节= 8 bit，3字节 = 24 bit = 4个Base64字符，这意味着Base64只能对3的整数倍字节数进行编码，如果字节数不是3的倍数，会通过在末尾补一或两个全0字节使其变成3的倍数，并在密文后加同样数量的“=”，解码时侯，末尾有几个“=”，就需要在解码后末尾原文去掉几个全0字节
同样是中文“你好”，在GBK编码规则下：
| 二进制 | 1100 | 0100 | 1110 | 0011 | 1011 | 1010 | 1100 | 0011 |
|---|---|---|---|---|---|---|---|---|
| Hex | c | 4 | e | 3 | b | a | c | 3 |
上面 4 Byte不能被3整除，需要补2个全0字节，即 0 × 16 bit
| 二进制 | 110001 | 001110 | 001110 | 111010 | 110000 | 11 |
||
|---|---|---|---|---|---|---|---|---|
| Base64 | x | O | O | 6 | w | w | = | = |
Base64的出现实现了任何二进制流到可视字符串的转换，进而方便添加进XML，JSON这类数据格式中。对于不需要可视的文件，完全可以直接通过Stream的方式传输。毕竟原来的3字节现在要用4个字符表示，字符传递时仍占一字节，这导致Base64编码后，所占空间将增大4/3倍。
上面也看出，一个汉字在utf8中通常占3字节，在gbk中占2字节，这使得不少中国企业当初选择数据库编码时选择了gbk，但如今硬盘越来越便宜，国际化却越来越重要。由于utf8可以正确处理全球语言，▲ ★ 甚至包括Emoji 🤣 😏 在内的特殊符号，所以越来越多人开始选择utf8！
urlencode 主要用于防止非英文字符在URL地址中破坏其格式，所以只会对非英文字母编码。中文“你好”，urlencode编码后是： %E4%BD%A0%E5%A5%BD，有没有觉得很熟悉？早期URL地址是不允许有中文的，所以urlencode格外有用，地址中的中文和特殊符号都需要经过编码。urlencode另一个重要作用是：不止可以编码字符串，它可以编码JSON对象作为GET参数放入URL中。
3.信息摘要算法（MD5，SHA256，HMAC）
信息摘要（Message Digest），同义词有散列，哈希（Hash），可以理解为特征缩影，例如，这篇文章的摘要可以是：现代加密简介：MD5/AES/RSA/HTTPS。要判断两个东西是否相等，首先应该判断同一算法下的摘要是否相等。如果摘要相等，内容不一定相等；但如果摘要不相等，则内容一定不相等。
信息摘要扮演着十分重要的角色，是许多类型的实现原理，如LinkedList，HashTable，Dictionary，数据库索引，等等。在C#中，如果遇到需要重写Equals()的时候，一定也要重写GetHashCode()，因为比较摘要是否相等总是第一位的。在GetHashCode()相同时，才去继续调用Equals()函数。摘要算法设计的好，比较效率会提高许多。
经典Hash算法有很多，通过加，减，移位，还有诸多以提出者命名的算法。这里仅列举一个移位Hash做例子：
def rotatingHash(message, prime):
hashCode = len(message)
for i in range(len(message)):
hashCode = (hashCode<<4)^(hashCode>>28)^ord(message[i])
return hashCode % prime
摘要算法严格来讲也不能被称为加密，以为其是单向的，没有解密算法，信息无法被还原。这类算法中，目前比较流行的有MD5，和SHA256算法。md5()函数将一切字节大小的数据，映射到128 bit 的结果集，有2128个值。转为HEX后是32位字符串。不同内容在md5运算后碰撞概率发生极低。而SHA256会映射到256 bit 结果集，更大大降低了碰撞概率。
md5('123456') = e10adc3949ba59abbe56e057f20f883e
md5('123457') = f1887d3f9e6ee7a32fe5e76f4ab80d63
可见，字符串123456和123457相比，只差一位数，但密文几乎毫无相干。MD5目前的应用极多，下面举一些例子：
一些下载工具，为了提高下载速度，会将目标文件切割成许多块，每一块都可以独立下载，这样只要记住块相对位置，当所有块下载完成后，在客户端整合在一起形成完整的文件。那如何判断合并后的文件和原文件完全一样？下载工具先计算源文件的MD5值，待你下载好以后会在本地再计算MD5值并进行比较，如果一致，代表下载成功。极少数情况可能下载中间过程出现了漏洞，之后计算的两个MD5是不同的，那就代表下载就失败了。
许多网盘有都有“极速上传”的功能：部分同学会有这样经历：准备在网上分享几个G的资源，本来打算上传好久，意外发现几秒之后就显示上传成功了。原理并不复杂。网盘在上传文件之前会计算文件的MD5值（这个值仅与文件内容有关，文件名，作者，修改日期，权限等等是由操作系统维护），计算MD5会很快，之后先去中心记录寻找这个值之前有没有别人传过，如果存在记录，直接添加一份你对该文件的引用就好了。如果之前没有人传过，才选择上传。不用担心若干日后之前传那个文件的人不需要它并选择删除，如果网盘中心知道你还保留着对这个文件的引用，就并不会真正的删除这个文件，只是删掉了那个人对该文件的引用（引用类型，垃圾回收机制原理）。理论上，网盘也可以比较经过压缩/解压缩后是否还是一份文件。但目前压缩算法繁多，常见的就有rar,zip,7z,tar.gz,iso...二十几种，每次上传一个文件都要逐个计算一遍有时反而是得不偿失的。
在智能手机出现前，早期网游为了保护用户账号安全，会推出一款叫做“将军令”的设备，游戏登陆时不仅需要账号密码，还要输入设备上的六位数字，数字每分钟更换一次，所以大大增加了安全系数。其原理十分简单：只需要内置时钟和一个专门计算散列的硬件即可。对 当前日期时间精确到分 和 绑定的用户账号 作散列运算得到6为数字，服务器上保留一份同样的散列算法，这样登陆时就可以判断两个数字是否相等，而且这个过程不需要网络。将军令的寿命取决于内置时钟的误差精度，如果一年以后这个时间误差超过了一分钟，那这个设备就不能继续使用了。智能手机出现后，类似实现原理被转移到了手机上。由于联网的手机可以实时同步时间，所以寿命是永久的。
散列运算是单向的，被加密的信息无法还原，所以极适合用来保存用户隐私信息。如密码，只需用户本人知道，哪怕系统维护人员也不应该得知。最简单的实现方法就是：用户注册时，数据库保存user_id和md5(password)；用户登陆时，对输入密码做md5运算并和数据库做比较。
尽管无法完全破解，但黑客们如果获取到e10adc3949ba59abbe56e057f20f883e这样的常见散列，也会知道是原密码是123456。如果有人宣称可以解密MD5，那么其原理都是在一张表上记录了大量的原文--密文，数据可以占到几千TB甚至更大空间，称为彩虹表。纯数字和简单如qwerasdf这种密码，是很容易反推的。于是又出现了md5(md5(password))，和md5(sha256(password))这类换汤不换药的混合运算。
真正有效防止彩虹表破译的做法是在MD5散列计算前，对密码“加盐”（英文Salt），不再保存md5(password)，而用salt和md5(password+salt)代替。每个人注册时会产生一个随机字符串，称为盐，和原密码混淆后再进行md5运算，由于每个人的salt是随机的，即使很多用户同时使用123456作为密码，数据库记录的加盐密码散列也是不一样的。想通过salt和md5(password+salt)反推password极其困难。那么password和salt如何混合可以达到最佳反破译效果？和设计MD5和SHA256思想类似，HMAC(message,salt)函数是当前比较流行的算法。
当然，最最重要的还是要保证数据库安全，但如不慎数据库被侵入（如CSDN），上面的办法可以有效二次抵挡窃取用户重要信息
4.对称加密（DES，AES）
对于加密后需要被还原的信息，比如E-mail，加密算法需要尽可能复杂（但也不能过慢，要找到安全性和速度的平衡点）。密文中每个字符出现的频率应该尽可能一致，加密后字符串的相似程度与加密前无关，使窃取到密文的人无法通过分析频率，相似度等手段破译。
1949年，信息论之父--香农严格证明了100%安全加密的条件：
- 密钥的产生是真正随机的。
- 密钥的长度要大于等于明文长度。
- 每个密钥只能使用一次。
遗憾的是，这3个条件都很难满足。首先，一般计算机只能产生伪随机数，伪随机序列足够长以后是有规律可循的。要想足够快的产生真随机序列需要引入量子力学，比如每个时钟周期测量一个随机电子的自旋方向；密钥长度过大，密钥管理和传递就会遇到问题。如果每个密钥使用一次就舍弃，大量的通讯时间将会都浪费在生成密钥上。
好在人类对“安全”的概念上是有容忍的，只要破译足够难，耗时足够久（比如几万年以后），代价足够高，那么这种加密算法就可以被认为是“安全”的。
计算机加密中，最常用的算法是异或，因为任何一个二进制序列，在和另一个序列异或运算两次后是原来本身。我们还用中文“你好”举例，模拟100%安全加密，下面是“你好”的utf8编码：
1110 0100 1011 1101 1010 0000 1110 0101 1010 0101 1011 1101
下面是随机数生成的48位密钥
1110 1010 1101 0011 1010 0010 1101 1001 1111 1101 0110 1010
上下做异或运算后得到密文
0000 1110 0110 1110 0000 0010 0011 1100 0101 1000 1101 0111
这个密文是绝对安全的，只有当密文和密钥再做一次异或运算，才能还原回“你好”。不同的48 bit密钥，可以解密出不同两个汉字的组合，如“祖国”，“我们”，当然也可能是乱码。
1977年代IBM和NSA两家公司提出数据加密标准（Data Encryption Standard），简称DES，DES采用了64 bit长度二进制作为密钥，但其中8 bit是校验位，实际有效位数只有56 bit，即256种不同密钥。以当时的计算机能力，56 bit 也可谓是绝对安全的。但随着CPU（GPU）计算能力越来越强，2000年前后，已经有专门的硬件能在22小时内破解出DES的正确密钥，这意味着DES已经不再安全。
2001年美国开始征集新算法，命名为高级加密标准（Advanced Encryption Standard），简称AES，经过筛选，最终选定了两位比利时密码学家的Rijndael算法。AES可以选三种密钥，分别是128 bit, 192 bit 和256 bit。即使选择最小的128位密钥，其安全系数也是DES的4.72×1021倍，如果这个数字不够形象，可以假设目前有一台机器，破解DES只需要1秒钟，让它来破解AES则需要大约1496468亿年！
不论DES还是AES实现都相当复杂，Wikipedia上有详细原理，这里不做详述。好在绝大多数高级编程语言都内置了Crypto模块，可以方便我们直接调用而不必关心实现原理。另外，这两种加密方式也是对bit位加密的，意味着“你好”在GBK和UTF-8下的密文是不一样的。密文是若干字节的二进制序列，为了阅读，存储和传输方便，常用办法是转为Hex，长度缩减为原来1/4；另一种方法是用上面说过的Base64编码，长度可以缩减到为原来1/6；
5.非对称加密（RSA）
AES加密在今天仍然十分安全，只要密钥够复杂，几乎可以看作不可破解，但却存在一个新的问题：密钥如何传递？
密钥是不可能明文传递的，否则密钥被截获那一切都白费了。如果把密钥加密，用于其加密的密钥又怎么传输呢？对于固定通信的两个单位，可以先私下制定密钥，甚至制定密钥日历，每天更换新的密钥。传统网银U盾，和一些CA的U Key都是这种情况下的产物，但对于节奏飞快的互联网时代来说，这无疑是反人类的。你会为了注册某个账号跑到对方公司去领一个Key吗？
早在1976年，Diffie和Hellman两人发表密钥交换的概念，其支持在不安全的信道上传输密钥，原理如下：
- 在数学中找到单向函数 a + b = c，即知道 a, b 计算 c 很容易，但知道 c 和其中一项，想计算另一项很困难(这里的+号，不是数学相加，仅代表某种运算符)。
- 满足交换率和结合律：(a + b) + c = (c + b) + a
二人很快找到这样的函数 Bx mod M，其中B代表底数(Base)，mod是求模运算（即求余数）M代表模(Modules)。其中 B 和 M 是公开的，假设Bob想和Alice通信，他们可以这样：
- Bob选择x作为私钥，Alice选择y作为私钥：
- Bob发送(Bx mod M) 给Alice，Alice发送(By mod M)发送给Bob，
- Bob收到后，继续计算 (By mod M)x mod M，Alice同样计算(Bx mod M)y mod M，数学上可证两式相等，均为(Bxy mod M)。从而，即使双方均不知道对方的私钥，仍可以计算出一致的结果。
- Bob和Alice使用(Bxy mod M)作为密钥，现在可以用AES加密的方式安全通信了。
- 窃听者得到：B，M，(Bx mod M)，(By mod M)，根据这些是没有能力计算出密钥，从而无法破解之后的加密信息。
试想：27303594784432036767?? mod 39540592690228530645 = 5105659384789281862 想反算秘密指数是多少，几乎是不可能的。
幂模运算存在快速算法，实际并不需要去计算第一个超大的幂指数。
1977年，Rivest, Shamir, Adleman 三人在幂模运算基础上，提出了新型算法，以他们三人命名为RSA。现如今安全型http，即https，目前流行的比特币都是基于此原理。
RSA算法中，存在一对密钥，公钥Public Key和私钥Private Key，私钥由保管者拥有，公钥发布给其他人，信息用公钥加密后，只能通过私钥解密，所以是“非对称”的。同样私钥加密后也可以通过公钥解密，可以证明信息确实由私钥拥有着所发。
BitCoin交易中，收款方会告知对方自己的钱包地址（即公钥），而付款方则会用私钥对商品，金额，对方钱包地址等摘要加密，证明确实存在此次交易。与传统不同的是，BitCoin没有中心服务器，所有交易记录由世界各地的“矿工”们保存，而给“矿工”们的奖励，就是每记录一笔交易会奖励一些BitCoin，奖励逐年减少，直到全球总币数达到一定量后停止。由于去中心化，数据共享，所有交易历史都是不可伪造，不可篡改的。
6.HTTPS
HTTPS基于RSA算法。目前大多数知名互联网公司，都已经选择https，下面的例子可以帮助快速理解这个概念：
Bob开了一家银行，Alice是其客户，在想要联系Bob时，Alice先产生一个足够复杂随机密钥AES-Key，通过Bob的公钥加密后传给Bob，这个信息只能通过Bob的私钥解密还原AES-Key，Bob解密后双方就可以用AES加密实现安全通信了，这是最简单的模型。
有时候Bob会主动联系Alice，例如说自己现在xx产品收益不错建议购买，发送给包括Alice在内的所有客户。由于不是什么隐私话题，这段信息没有加密。（澄清概念：隐私信息千万不要用私钥加密，因为公钥是公开的，所有人都能解密）为了证明这条信息由自己所发，Bob对信息摘要（例如MD5）用私钥加密作为数字签名，附在信息上同时传递。每个Bob的客户都有Bob的公钥，可以解密签名，同时自己计算一遍信息摘要，如果和解密摘要一致，说明信息没有被篡改过（因为只有Bob才有私钥能够加密摘要）。
现在出现了一个黑客，他没有Bob的私钥，但是有自己的一对公钥/私钥，他设法将Bob的公钥替换成了自己的，模仿Bob并发送了类似的消息给Alice，并用自己的私钥签名，Alice用黑客的公钥解密后认为一切正常，误以为信息来自Bob。
“尊敬的Alice您好，我们发现您的账号存在xxx问题，请提供密码，验证码等方便我们进行修复和升级。”
如果以上信息发信人是10086，或着来自某个官网邮件，那能骗到的人绝不会在少数。不幸的是：伪造Http请求的门槛极低。要保证这种情况不会再发生，大家提议，公钥不再由网站直接发出，而是把公钥放到权威机构--数字证书中心（简称CA）作认证，证明Bob的公钥的确属于Bob本人，而黑客则无法认证为Bob。常见的数字证书中心有微软，DigiCert, Symantec, Comodo, GlobalSign等等国外机构和中国的CNNIC。认证不是免费的，根据不同安全级别，年费几百到几千人民币不等。
于是Bob去了一家CA做了认证，CA公司在确认其身份后，对其身份信息和Bob的公钥，用CA的私钥加密，颁发给Bob，这就是Bob的数字证书。从这以后，过程变成了这样：
- Bob此时发送给Alice的内容有：源信息，信息摘要签名，数字证书
- Alice根据该数字证书的颁发机构，去根证书列表查询该CA公钥。
- Alice用CA公钥解密证书，获得Bob的公钥和认证基本信息，确认得到的公钥属于Bob。
- Alice用Bob公钥去解密摘要签名，同时对源信息计算摘要，如果一致，则说明原信息未被篡改，是来自Bob的真实信息。
这时黑客能否故伎重演？尝试用自己的公钥替换CA的公钥，用自己的私钥伪造一份Bob的证书？理论上，如果黑客技术够高，发现了CA公司存在的漏洞，确实可以办到，HTTPS也不是百分百安全的。但上面提到的数字证书中心：Symantec, Comodo 都是世界一流互联网安全公司。不仅如此，操作系统和浏览器在安装时，已经内置了根证书公钥，顶级根证书由操作系统TLS模块负责维护其安全。在多重保险下想替换CA公钥绝不是件容易的事情。
与上面的担心相比，CA中心是否应该被绝对信任，相对更需要关注。早年CNNIC就被指控在用户不知情情况下下载软件，且滥发证书等恶劣行为，导致被谷歌和火狐等部分浏览器吊销其根证书。但即使是形象良好的CA公司，其权限过大也不是大家愿意看到的，区块链技术应景而生，区块链技术不需要中心认证，而比特币则是该技术应用最成功的例子。世界各处矿工们保存着同一个数据库副本，即使某个人篡改了记录，其他大多数人的记录是保持不变的，在同步数据时，与多数不一样的数据就会被认为不正常从而被舍弃。
本文完。与个人博客同步更新
原创文章，如需转载，请注明来源。
如需联系作者：zijian@outlook.de
