古老的加密学

来自互联网
        话说咱们多多少少都听说过加密学，啊，至少也听过各种加密算法，什么AES啊，RSA啊，对称加密算法啊，非对称加密算法啊，会话金钥啊，公钥啊，私钥啊诸如此类的加密学名词。
        不过，听说归听说，这些名词究竟是个什么意思，加密学究竟是一门怎样的学科，恐怕就没多少人清楚了。
那么，就让本幽灵在前面开路，和诸位一起看看加密学的世界吧！
        说起加密学，这可是个老家伙啊。加密学的英文是cryptography，这词起源于两个希腊文词汇：kryptós（对应的英文为hidden,secret）和
graphein（对应的英文为writing），刚好展现了加密学的本质：秘密书写。广义的密码学负责信息的保密认证和防篡改，包括加密算法和散列算法，狭义的密码学只有加密算法。
        A想要传递信息给B，但又不想让路上的C知道，所以就把本来人人都能读懂的信息通过一定的规则转换成没人能读懂的信息，B收到之后再通过对应的规则转换回能读懂的信息。
        其中，“人人都能读懂的信息”被称作明文（plaintext），“没人能读懂的信息”被称作密文（ciphertext），这两个词汇会在我以后的科普中被广泛使用，诸位不要忘了它们的含义哦：）
最早的加密算法出现在古希腊，是一种重组（transposition）算法。举个例子：明文为hello world，密文为elolh drwlo，这就是最典型的重组算法。
        除了重组算法，还有替代（substitution）算法，最有名的替代算法是凯撒密码：明文为attack tonight，加密算法是将每个字母替换为字母表中三位后的字母（例如a替换为d），密文就是dwwdfn wrqljkw。
        很显然凯撒密码非常容易被破解，于是后来有人设计了使用数次重组和替代的算法，例如二战时的英格玛密码机。很长一段时间之内，密码学家们都是在研究字母表：）
这些基于字母表的算法，统称为古典加密算法。加密学在很长一段时间之内，都是军方的宠物，似乎与普通人无关。
        后来，计算机诞生了，人们开始用0和1传递信息。此时，基于复杂数学方法的现代加密算法诞生了：密码学家们不再拿着字母表，而是开始研究数学（尤其是离散数学），研究如何将这些0和1转换成没人能看懂也没人能破译的内容，同时又可以变回明文（这个特性叫做可逆性，加密算法必须具有可逆性；相对的，散列算法要求不可逆）。
        最开始诞生的是对称加密算法（symmetric-key algorithm）：随机生成一个密钥K，然后将这个密钥和明文一起输入到算法中，产生密文，接收方再用同一个密钥K解密得到明文（或者也可以是不同的密钥K1和K2，但是两者可以相互派生，也就是说知道其中一个就可以轻易得知另一个）。
        对称加密算法的代表有DES（Data Encryption Standard，数据加密标准），3DES（DES的改进版本），AES（Advanced Encryption Standard，高级加密标准），RC4（Rivest Cipher 4）等。其中DES已经因为安全性过弱而被弃用，现在AES被广泛使用，迄今为止AES依旧非常安全，被认为实际上无法破解。
        这其中DES和AES都是块密码（Block Cipher），数据以块的形式输入（一块512bits的数据，加密，一块512bits的数据，加密......）；而RC4则是流密码（Stream Cipher），数据以bit流或字节流的形式输入（数据流，加密......）。对称加密算法非常非常非常（！）复杂，这里我就不展开了，在以后的系列里介绍相对简单的吧。
        哈，这里有个词很奇怪：实际上无法破解？事实上，除了属于古典加密算法的“一次性填充（one-time pad）”之外，其他所有加密算法（不管是古典还是现代，不管是对称还是非对称）都是理论上可破解的：brute-force attack，一个个尝试密钥的破解（听起来很像所谓的暴力破解，不过还是有所不同：比起暴力破解，brute-force attack更有技术含量，会采用一些技巧进行辅助破解）。只要攻击者有足够的时间和资源，理论上来说没有加密算法可以挡住brute-force attack。
        我们仔细看一下吧：一次性填充是采用完全随机的一次性密码本的，这导致攻击者完全无从下手，但是其他所有算法都做不到这一点，包括现代加密算法，解密密钥是通过计算机生成的伪随机数而不是随机数，也就是说如果伪随机数生成函数有问题，生成的伪随机数不够随机或者位数过少，那么攻击者很容易尝试出解密密钥；即便算法足够强悍，在理想情况（不考虑时间和计算成本）下还是可以尝试出解密密钥。
        那么，有人大概会想：你说的破解前提建立在攻击者知道加密算法这一点之上，不是吗？那么我们只要把保密工作做好，不让第三方知道我们使用的算法不就可以了？
很不幸，你想得太美了！除了前面提到的brute-force attack，还有一种更常见的密码破解方式：密码学分析（cryptanalysis），通过分析密文或者比对密文和已知明文等手段找出加密算法的漏洞，从而将密码破解。如果一个加密算法有严重缺陷，那么即便再怎么保密，攻击者还是能很轻易的找出这个算法的漏洞并将其破解
（密码学中破解的定义是：找到一种比暴力破解更有效率的获得解密密钥的方法）。
        密码学实践也说明了这一点：很多自创的加密算法虽说对第三方保密，但是在密码学分析面前不堪一击；而像AES这种从一开始就公开了所有细节的算法，反倒是一直极为坚挺，直到现在，密码分析师们无从下手。越公开的算法，经受了越多密码分析师的检验，抗击密码学分析的能力也越强。
        密码学原理一：公开算法的安全性好过保密算法。
        关于密码分析和brute-force attack，还有相当多的内容可以聊，不过考虑到快要失控的篇幅，就此打住吧。
虽然现代加密算法理论上可破解，但如果说你破解一段密文需要10年时间，花上个几百亿美金，你说你会去破解吗？就算破解出来，也早就黄花菜都凉了啊。
这就是实际上不可破解的真正含义！
        前面说了对称加密算法，那么自然还有非对称加密算法（asymmetric-key algorithm）：加密密钥和解密密钥不是同一个，更重要的是无法相互派生，知道其中一个也找不出另外一个。非对称加密算法的加密密钥又被称作公钥，可以随便公开；而解密密钥被称作私钥，由解密者秘密持有。所以很多时候非对称加密算法又被叫做公钥加密算法（public-key algorithm）。
最著名的非对称加密算法非RSA莫属，这名字是三个密码学大牛的姓名开头第一个字母的组合：R，Ronald Rivest；S，Adi Shamir；A，Leonard Adleman。RSA算法诞生于1978年，迄今为止仍然被广泛使用。不过RSA算法并不是第一个非对称加密算法，这当中还有一段很有趣的故事，下次具体聊RSA的时候仔细聊聊吧。