密码学杂谈 - 下

经典加密

在数字计算机没有发明之前，加密都是对字符进行加密，一般采用的方法是字母替换，我把它称为 经典加密 。

凯撒密码

简单的字母替换规则可以通过对字母表进行循环移位而来，最早记载的凯撒（Caesar）密码就是采用这种方式。凯撒密码是传说中的凯撒大帝发明，加密时将明文中的每个字母都按照其在字母表中的顺序向后移动固定数目生成密文。例如，当偏移量是右移3(+3)的时候形成下面的字母替换表：

+----+--------------------------+
|明文|ABCDEFGHIJKLMNOPQRSTUVWXYZ|
+----+--------------------------+
|密文|DEFGHIJKLMNOPQRSTUVWXYZABC|
+----+--------------------------+
复制代码

对应我们的明文 GAME404 就变成了密文 JDPH404 。解密时候再把密文在字母表中左移3(-3)得到明文 GAME404。这种情况下凯撒密码的秘钥就是单个数字3。

凯撒密码现在看来是比较小儿科，但是在2000多年前，是了不起的发明，为凯撒部队的保密工作做了贡献。即使是到现在，军事上的信息保密需求，任然是密码学前进的最大动力。

这里数字忽略加密，采用原文传输

ROT13加密

rot13（rotate by 13 places）也是一种简易的替换式密码，是凯撒密码的变种。rot13将明文偏移13位形成密文，因为英文总共26位，所以密文再偏移13位后会循环回到原文，非常巧妙的设计，加密和解密使用同一个方法。这是公式:

rot13(rot13(xxx))=xxx。在python3中默认带rot_13的算法实现, 下面是用例:

➜  ~ echo "game404" | python -m encodings.rot_13
tnzr404
➜  ~ echo "tnzr404" | python -m encodings.rot_13
game404
复制代码

随机单表替换

采用位移形成的字母替换，有明显的规律。加密中最要的一点是 随机 ，所以可以使用随机的方式形成字母替换表:

+----+--------------------------+
|明文|ABCDEFGHIJKLMNOPQRSTUVWXYZ|
+----+--------------------------+
|密文|ZEBRASCDFGHIJKLMNOPQTUVWXY|
+----+--------------------------+
复制代码

这样加密和解密都必须持有 ZEBRASCDFGHIJKLMNOPQTUVWXY 这个完整的密码本，长度为26位，而不是3或者13这样的单位秘钥。

随机单表替换，初看无法得到具体信息。但是一些密码破译专家，也是数学家就可以看到一些统计规律。比如明文 hello game 加密后的密文 daiil czja。因为在英语中字母e是频率最高的字符，根据前面的密文表现，可以初步推断 e->a。如果我们再掌握更多的密文，分析其中的统计规律，使用类似求解数独的方式，破译密码。

维吉尼亚多表替换密码

单表替换容易透露统计规律，自然的改进思路就是使用多表替换，每个字母采用不同的替换规则，让规律不好捉摸。比如下面的维吉尼亚多表:

此密码曾被误以为由布莱斯•德•维吉尼亚所创，所以才叫作维吉尼亚密码，实际上最著名的一种为吉奥万•巴蒂斯塔•贝拉索于1585年推出。它于1863年之前一直未被破解。法国人称它作“不能破译的密码”。

维吉尼亚密码中,表格的第一行只需直接填上26个字母,然后以下每一行的字母都是向左偏移一格，形成对称结构。这叫作表格横移,数学上每一列同余26。

这种密码需要使用一个关键字来作为密钥，关键字按字循环使用。

假设关键字是CAT,明文的第一个字由C加密,第二个字由A加密,第三个则由T加密,然后再回到C加密,一直重复。加密按照上边的密码表,例如明文BALL用CAT作关键字时会得到密文DAEN,同一个字母L会加密成2个不同字母EN。现实中,维吉尼亚密码的关键字非常长，破解难度提高了很多。

维吉尼亚密码的密码本是规则的，所以破解的关键在于找到关键字。具体破解办法还是要从统计规律入手，进行暴力破解。

恩尼格玛密码机

人为制作的密码本是规则且有限，所以聪明的人想出了制作密码机器。恩尼格玛密码机(德語：Enigma)是第二次世界大战时的纳粹德国使用的密码机。关于恩尼格玛密码机和图灵的故事非常精彩和传奇，也有很多文章介绍。这里我只是简单介绍一小小部分。恩尼格玛密码机大概长这样:

看起来和一个机械打字机类似，顶部的转子用来旋转设置秘钥，转子内部自动生成不同的密码表，底部的键盘用来键入明文，每个明文经过机器转换加密后输出到中间的灯泡，记录下灯泡的位置就得到密文。解密的时候设置好相同的转子位置，然后输入密文，就得到了明文。

因为恩尼格玛密码机加密非常复杂，不犯错的情况下人肉难以快速破解。所以后来大神图灵登场，设计了“炸弹机”，用机器来破解机器，从此开启了计算机的新时代。

数字加密

在数字世界里，字符不再是不可分割。经典场景中字符A是原子的，没法拆分成左半个A和右半个A。数字世界0和1才是原子的，字符可以分解成不同的0和1组合，比如:

>>> a = "a"
>>> print(a, ord(a), bin(ord(a)))
a 97 0b1100001
复制代码

字符a的ASCII码是97，对应的二进制是8位001100001。这样我们就可以把a打散成两部分，比如左边6位0011000，右边2位01，再和别的字符重新排列。

base64

所谓Base64，就是说选出64个字符----小写字母a-z、大写字母A-Z、数字0-9、符号"+"、"/"（再加上作为垫字的"="，实际上是65个字符）----作为一个基本字符集。然后，其他所有符号都转换成这个字符集中的字符。这种加密方式因为密码本公开，所以一般只是称为base64 编码，而不叫做base64 加密。

阮一峰老师的Base64笔记介绍的非常好，大家可以通过尾部的参考链接去查看。我偷懒简单整理一下。先是base64的码表:

码值  字符  码值  字符  码值  字符  码值  字符
0 A 16  Q 32  g 48  w
1 B 17  R 33  h 49  x
2 C 18  S 34  i 50  y
3 D 19  T 35  j 51  z
4 E 20  U 36  k 52  0
5 F 21  V 37  l 53  1
6 G 22  W 38  m 54  2
7 H 23  X 39  n 55  3
8 I 24  Y 40  o 56  4
9 J 25  Z 41  p 57  5
10  K 26  a 42  q 58  6
11  L 27  b 43  r 59  7
12  M 28  c 44  s 60  8
13  N 29  d 45  t 61  9
14  O 30  e 46  u 62  +
15  P 31  f 47  v 63  /
复制代码

然后部分ASCII码表:

二进制 十进制 十六进制  图形
...
0100 1101 77  4D  M
...
0110 0001 97  61  a
...
0110 1110 110 6E  n
复制代码

那么base64的编码过程如下:

步骤说明:

1. 得到明文Man的ASCII编码十进制
2. 得到明文Man的ASCII编码二进制，3个字节
3. 最关键的一步是把明文的3个字节，3*8=24位，重新排列成4*6=24, 变成4段
4. 进行密文的补齐，也就是把每段6位补齐成8位，变成完整的4个字节
5. 从二进制还原到十进制得到密文编号
6. 根据base64码表翻译成密文 TWFu

所以base64编码是重组了ascii编码的二进制规则。至于为什么重组成6个一组，是因为63的二进制表示刚好是6位，这样保证编码后不会溢出base64的码表。

XOR异或

XOR异或是逻辑运算的一种，当两个值相同时，返回false，否则返回true:

>>> True ^ False
True
>>> True ^ True
False
>>> False ^ False
False
复制代码

同时XOR运算有一个很奇妙的特点：如果对一个值连续做两次 XOR，会返回这个值本身:

>>> 2^2022
2020
>>> 2020^2022
2
复制代码

第一次使用2和2022进行异或运算，得到2020，第二次使用2020再和2022进行异或运算，又得到2。我们可以把2看做明文，2022看做密码，那么进行一次异或运算，就是加密过程，得到密文2020。密文2020再进行一次异或运算，就是解密过程，得到明文2。

因为异或是逻辑运算，是按位进行的，所以我们可以把它理解成二进制上的字母替换，和经典的字符替换一致。

这里大家可以思考一个小问题，要按位运算需要明文和密码长度一致，如果明文非常非常长应该怎么处理呢?

对称加密算法

我们在数字加密中可以通过XOR(按位替换)和重组(base64)这样两个基本手段工具，设计出更复杂的，也就是更安全的加密算法。最早登场的是DES加密算法，然后是AES算法，下面是2种算法的对比：

DES的算法比较复杂，我简单总结一下大概步骤：

1. 准备64位的明文和64位的密钥
2. 秘钥经过16次调度，形成16个子秘钥
3. 每个子秘钥，通过从秘钥64位摘取56位，分成左右各28位的L端和R端。然后L端和R端各自左移指定轮次的位数，然后拼接L端和R端。这个过程是字节的重组。最后对形成的秘钥在进行一次置换。得到48位的子秘钥。
4. 重复上面的步骤3，直到得到16个48位子秘钥
5. 明文的64位根据置换表进行一次置换，再拆分成L端和R端各32位
6. 循环执行L，R = R，F(L，子秘钥)16次，就是把R端复制给L，然后把32位的L和48位的子秘钥使用f函数进行加密。
7. 最后把L和R拼接后进行再进行一次置换得到密文

可以看到算法中关键点, F函数。 Feistel函数重点是把32位的一半明文和48位的子秘钥，混合得出一个32位的等长秘钥。这个过程依赖一个不透明的预制机制S盒，所以其实不收大家信任，怀疑算法留有后门。这个过程，我们可以把它想象成接水管游戏，不同的输入经过内部管道处理，输出特定的结果:

DES加密的思想，总结起来就是二进制位的重组和替换。DES和AES都是成熟的算法，一般情况下我们不需要实现它。出于安全性考虑，DES已经弃用，现在实际业务中一般直接利用AES的API即可。下面是完整的实现:

from base64 import b64encode, b64decode
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
def ase_cbc():
    data = b"secret"
    key = b"jSOlan6Co5Ac2HiT"
    cipher = AES.new(key, AES.MODE_CBC, iv=key[:AES.block_size])
    ct_bytes = cipher.encrypt(pad(data, AES.block_size))
    ciphertext = b64encode(ct_bytes).decode('utf-8')
    print(ciphertext)
    ct = b64decode(b64encode(ct_bytes).decode())
    cipher = AES.new(key, AES.MODE_CBC, iv=key[:AES.block_size])
    dat = unpad(cipher.decrypt(ct), AES.block_size)
    print(dat)
# svhpgz4vi1AgHDtdt8aaww==
# b'secret'
复制代码

• 明文是6个字节，秘钥是16个字节
• 创建一个ase的算法实现，这使用cbc模式
• 使用pad方法先对明文数据进行补齐
• 对明文进行加密得到密文，密文是二进制
• 因为二进制密文打印会乱码，所以将其使用base64编码转换成ascii字符
• 解密则是加密的逆过程

非对称加密算法

前一篇文章介绍过非对称加密的一些思路，和对称加密不同的是秘钥分成一个秘钥对：私钥+公钥。公钥用于加密，私钥永于解密。在介绍非对称加密的算法实现之前，我们先看看物理世界的非对称加密模拟，有助于我们理解非对称加密的基本逻辑。

上面是我简单画的一个非对称加密信箱，分成上下2个盒子，中间是联通的。上方盒子需要使用四角星的钥匙打开，下方盒子需要使用五角星的的钥匙打开。那么一个信息加密传输过程大概如下:

1. 发送方甲用自己的锁把上方盒子用四角星锁锁住，然后把信箱传递给接收方乙。
2. 接收方乙收到信箱后把下方盒子用五角星锁锁住，然后把信息回传给发送方甲。
3. 甲用四角星钥匙打开上方盒子，塞入信件，然后把信箱和信件一起传递给乙。
4. 乙用五角星钥匙打开下方盒子，取出信件。完成一次信息加密传输。

在这个信息传递过程中，甲乙的钥匙都分别自己保管，没有经过运输。甲用四角星钥匙加锁，乙用五角星钥匙解锁，而且信件都在信箱中。这样保证了信息传递是安全的。

1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法，现在是非对称加密的标准。算法主要采用的是质数因式分解这样一个"盒子"比如下面一个等式:

n = 61×53 = 3233
复制代码

61和53的乘积，大家口算或者笔算有可能可以计算出来，但是反过来求3233是那两个质数的乘积却非常难。在非对称加密情况下，我们选择一个随机数，比如17。使用(3233，17)这样的信息组成公钥，然后使用类似(3233,17*61/17*65)这样的信息组成私钥。公钥只是私钥的一部分信息，这样公钥加密的信息，逻辑上私钥肯定可以解密。而且通过公钥的3233，很难推断出私钥中的61*53。当然非对称加密的数学验证比这个举例要严谨和复杂的多，我这里只是尝试举例，帮助理解。

加密示例:

def rsa_enc():
    from Crypto.PublicKey import RSA
    from Crypto.Random import get_random_bytes
    from Crypto.Cipher import AES, PKCS1_OAEP
    data = "I met aliens in UFO. Here is the map.".encode("utf-8")
    file_out = open("encrypted_data.bin", "wb")
    recipient_key = RSA.import_key(open("public.pem").read())
    session_key = get_random_bytes(16)
    # Encrypt the session key with the public RSA key
    cipher_rsa = PKCS1_OAEP.new(recipient_key)
    enc_session_key = cipher_rsa.encrypt(session_key)
    # Encrypt the data with the AES session key
    cipher_aes = AES.new(session_key, AES.MODE_EAX)
    ciphertext, tag = cipher_aes.encrypt_and_digest(data)
    [file_out.write(x) for x in (enc_session_key, cipher_aes.nonce, tag, ciphertext)]
    file_out.close()
复制代码

• 秘钥可以使用代码生成，也可以使用OpenSSL工具生成，这里我使用上一篇文章中的秘钥
• 导入rsa公钥
• 随机一个AES秘钥，然后使用rsa公钥加密这个秘钥
• 使用AES加密信息
• 将AES秘钥密文，AES的随机数，iv和密文写入结果

解密示例:

from Crypto.PublicKey import RSA
from Crypto.Cipher import AES, PKCS1_OAEP
file_in = open("encrypted_data.bin", "rb")
private_key = RSA.import_key(open("private.pem").read())
enc_session_key, nonce, tag, ciphertext = \
   [ file_in.read(x) for x in (private_key.size_in_bytes(), 16, 16, -1) ]
# Decrypt the session key with the private RSA key
cipher_rsa = PKCS1_OAEP.new(private_key)
session_key = cipher_rsa.decrypt(enc_session_key)
# Decrypt the data with the AES session key
cipher_aes = AES.new(session_key, AES.MODE_EAX, nonce)
data = cipher_aes.decrypt_and_verify(ciphertext, tag)
print(data.decode("utf-8"))
复制代码

• 导入rsa私钥
• 读取结果，并按位从中解析出aes私钥密文，随机数，iv和剩下的密文信息
• 使用rsa私钥从aes秘钥的密文中解析出aes密钥明文
• 使用aes秘钥解密密文信息

这一对过程的重点是，rsa仅仅加密aes的私钥，私钥的密文进行传输 。encrypted_data.bin是二进制的，直接使用文本方式查看会是乱码，我们可以转换为base64方式查看:

✗ base64 encrypted_data.bin 
w+ii4VVphO1ulHjrUy4fcc7CuLxaxJTQuzTtgIqvoot3ivBcRWwxV/1rNqIA2fsddYq8AIRo7jV9xoxbUK9ll8LQdM5S0N9eBakM6wzEwnN9PFrJEKN7VdmTqxnzC7go5tS2qNR173xcJKTX3UXKBTLbKXkafj9k2Bk9g93hRh19Uka/S5AqD43dFjIyI2ogxZNkN0v5E6uAyINlhGO8jCHAN0yhu4S5zz0ph7mFAVfXQkNDuotcdmsRfPpEi641BI/fEGE=
复制代码

散列算法

散列函数（Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或hashes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表，用来表示信息完整性。

散列函数数学逻辑并不难，首先需要一个奇函数，保证每一个输入可以得到一个唯一的输出:

然后我们再从输出结果中进行信息摘取部分，这样来保证摘要比原文要短，因为摘要比原文长，那就没有价值。我们可以自己随便设想一个哈希算法:

1. 函数取值 y=2f(x)+3
2. 将结果转换为二进制后循环左移3位
3. 将二进制结果拆分成左右两段并还原成2个十进制数
4. 使用2个十进制数相乘
5. 结果再转换为二进制数据，取其前8位转换成16进制得到哈希值

根据抽屉原理，9个苹果放到8个箱子，一定有一个箱子会有2个苹果。信息摘要算法一定会有冲突，只是好的算法信息冲突的概率会非常非常低。我们上面的设想的哈希算法，仅仅8位，冲突的概率非常高。好的散列函数在输入域中很少出现散列冲突，知名的算法有MD5和SHA。

MD5信息摘要演算法5（MD5 Message-Digest Algorithm 5）是散列算法的一种，可以产生出一個128位（16个字节(BYTES)）的散列值（hash value），一般表示为32位十六进制数字。

SHA安全散列算法（Secure Hash Algorithm ）也是一个系列的散列算法。最早SHA-1，正式发布的第一代算法可以生成一个被称为消息摘要的160位（20字节）散列值，散列值通常的呈现形式为40个十六进制数。

这两种算法都被我国的 王小云 教授破解了，所以这2种算法都被认为安全性不足，不再建议使用，目前较多使用sha256算法。

sha256是sha-2算法的变种，输出是256位(32字节)的摘要值，同属sha-2的还有SHA-224，SHA-512等。2015年还推出了sha算法的第3个版本，即sha3。

下面是md5和sha256的示例:

def hash_sample():
    import hashlib
    plaintext = "game404"
    result = hashlib.md5(plaintext.encode())
    md5 = result.hexdigest()
    print(md5, len(md5))
    result = hashlib.sha256(plaintext.encode())
    s256 = result.hexdigest()
    print(s256, len(s256))
#e935208860777d1584d3586a9e93e160 32
#c56afda14db3e8b61eb83f17540401ec983e91e92375826d2842e29c8a4db437 64
复制代码

license实现

了解完所有算法的模型后，license的实现就非常简单了。我们先设置license信息:

{
    "name":"game404"，
    "expiryDate": 20220220
}
复制代码

然后我们将其dump成字符后使用ras签名, 完整代码如下:

def rsa_sign():
    from Crypto.PublicKey import RSA
    from Crypto.Cipher import AES
    from Crypto.Signature import PKCS1_v1_5
    from Crypto.Hash import SHA256
    import json
    license_object = {
        "name": "game404",
        "expiryDate": 20220220
    }
    plaintext = json.dumps(license_object)
    file_out = open("encrypted_license.bin", "wb")
    private_key = RSA.import_key(open("private.pem").read())
    # rsa签名
    cipher_rsa = PKCS1_v1_5.new(private_key)
    digest = SHA256.new()
    digest.update(plaintext.encode("utf-8"))
    signature = cipher_rsa.sign(digest)
    # aes加密
    session_key = get_random_bytes(16)
    cipher_aes = AES.new(session_key, AES.MODE_EAX)
    ciphertext, tag = cipher_aes.encrypt_and_digest(plaintext.encode("utf-8"))
    # 写license
    file_out.write(b"".join([session_key, cipher_aes.nonce, tag, signature, ciphertext]))
    file_out.close()
复制代码

证书我们可以base64后发送出去:

F4IBtZOODAE5XSdluFynrk8e01gSKwVftivMg+eucfD7j5nCdMZhIcjGyLjQ5miV4Y6mAOooajNypWVL+GTVleXoLUQzqf0hLG02ytuIZ3QlCbGXVn3sofePq+IhwDBH5x2CECwHofzuNH0LbQLlW7LbwXxOl8xvGOw1gCvUgGo8Uuqli0cgrijqKO+n72Rb4Is0KW8EMjvPvaaLodbEhUc2iCLDiDDLXpBvcWsMZeW+AVgfpr6jKR9ICyELg4XQ2s84gs3d+EcFjaFjAzwygBuLYdqa40pR4G/e
复制代码

本地验证证书:

def rsa_verify():
    from Crypto.PublicKey import RSA
    from Crypto.Cipher import AES
    from Crypto.Signature import PKCS1_v1_5
    from Crypto.Hash import SHA256
    file_in = open("encrypted_license.bin", "rb")
    public_key = RSA.import_key(open("public.pem").read())
    # 读取license
    session_key, nonce, tag, signature, ciphertext = [file_in.read(x) for x in (16, 16, 16, 128, -1)]
    # aes解密
    cipher_aes = AES.new(session_key, AES.MODE_EAX, nonce)
    data = cipher_aes.decrypt_and_verify(ciphertext, tag)
    print(data.decode("utf-8"))
    cipher_rsa = PKCS1_v1_5.new(public_key)
    digest = SHA256.new()
    digest.update(data)
    try:
        # 验证签名
        cipher_rsa.verify(digest, signature)
    except ValueError:
        pass
复制代码

证书实际上不需要保密，只需要验证来源的合法性和完整性。所以我们可以看到aes的秘钥是写入到证书文件中的，合法性和完整性使用rsa算法和sha256算法结合来保证。

小结

本文我们一起回顾了经典加密和数字加密的演化过程，学习了使用 随机 ，变换 和 重组 等方式构建加密算法。重点了解了aes对称加密算法，rsa非对称加密算法以及sha256摘要算法，并利用它实现了一个商业license的制作。

数字加密的尽头，可能是量子计算。首先是量子通讯的不可观测性让量子加密具有巨大优势，如果通讯被偷听会导致量子叠加的坍缩，这样还可以主动识别是否被偷听。这个主动防窃听就非常厉害了，是上面的经典计算机的加密算法都无法实现的。其次量子计算机，在并行计算上也有巨大优势，经典计算机无法快速破解的算法，对量子计算机可能秒破。保密和破解这一矛和盾，又将迎来新的一轮变更。

最后，最重要的是我国在量子领域处于第一梯队，起步不晚，发展迅速。从md5的破解，再到量子通讯/计算，中国科学家逐渐登场，以后一定会看到更多 中国名字 和 中国标准 。

参考链接

• DES算法原理及实现 www.ruanx.net/des/
• 什么是DES加密 www.cxyxiaowu.com/1478.html
• 费斯妥密码 zh.wikipedia.org/wiki/%E8%B4…
• Feistel Cipher kysonlok.gitbook.io/blog/crypto…
• Difference between AES and DES ciphers www.geeksforgeeks.org/difference-…
• 维吉尼亚多表替换加密术 sca.gov.cn/sca/zxfw/20…
• zh.wikipedia.org/wiki/%E6%81…
• Base64笔记 www.ruanyifeng.com/blog/2008/0…
• XOR 加密简介 www.ruanyifeng.com/blog/2017/0…
• pycryptodome.readthedocs.io/en/latest/s…