目錄
前言
由於硕士课程里接触到关於 Cryptography (密码学) 的课题，突然对 Encryption (加密) 和 Decryption (解密) 的东西产生了兴趣，所以写下这篇文章，以防刚学完的东西转眼又忘掉了。所谓 Encryption 就是把原有的文字讯息，转换成一些没意义的 Cipher (暗号)。而收到暗号的人把讯息还原，就是 Decryption。
Caesar cipher 凯撒密码
早於古罗马时代，已经出现加密技术。相传凯撒大帝在行军时，下达君令会把讯息加密。被加密的讯息到达将领手中就会进行解密。而加密的方法就是以特定方式把原有字母用其他字母取代，由於将领知道取代的方法，很容易就可把讯息解密，以下是一个例子：
| 原文 | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 加密 | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C |
於是，如果原有讯息是：try to decrypt this message
加密後就会变成：wub wr ghfubsw wklv phvvdjh
所以如果你知道原文和加密讯息的替换方法，很容易就可以解密。以上的例子是把原文字母向右移动三格作为加密，又称作 Key = 3。Key 就是发讯者与收讯者共同协议的加密解密钥匙。
又由於加密和解密都是用同一条 Key，这条 Key 就称为 Symmetric Key，而这种 Encryption 亦称为 Symmetric Encryption。
不过 Caesar Cipher 这个加密方法有个严重的缺陷，就是只有 25 个替换的选择，亦即是只有 25 条 Key，如果加密讯息被敌人截获，只需把 25 条 Key 逐一尝试，很快便能破解加密讯息。
既然问题在於 Key 的数量不足，怎样可解决这个问题呢？後来就有人想到，不要顺序把字母编码，取而代之的是随机地把字母换成其他字母，例如：
| 原文 | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 加密 | I | G | W | V | A | H | U | J | T | S | B | R | K | Q | C | P | L | Y | O | E | N | X | M | D | Z | F |
像这样随机加密，Key 的数目就会等於 26! = 400,000,000,000,000,000,000,000,000 条 Key 可以使用，这就解决了敌方逐一尝试的可能性。可是，针对这种加密方法的破解技术出现了！就是 Frequency Analysis (频率分析)。
大家有没有想过，在一篇文章中，不同字母出现的机率并非完全相同的，例如：a,e,i 等字母出现的较多，q, x, z 则较少。再加上，我们知道单个英文字母出现的话肯定是 I 或者 a，两个英文字母多数是：of, to, in, it, is, be 等等，如果字母重覆出现，就很可能是 ss, ee, tt, ff 等等。利用这些特点，只要密文够长的话，就能有机会分析到密文所对应的字母。
你有张良计，我有过墙梯。要防止 Frequency Analysis 的攻击，加密者可以使用以下几个方法：
- 字与字之间不使用分隔
- 故意串错字
- 加入一些没意义的字母
- 把特定字换成其他字，例如：把 is 换成 ztp，把 the 换成 kagg 等
可是这些方法都会增加解密的难度，而且，只要时间充足的话，攻击者一样可以把密文分析出来。
Vigenère Cipher 维吉尼亚密码
到了十六世纪，加密法有了新的突破！法国人维吉尼亚用了一个以其名命的加密方法。首先加密者准备一份维吉尼亚表格，这表格其实就是凯撒密码的变体，只不过是把所有 Key 列出来。
发讯者与收讯者先协商好一条 Key，而 Key 是任何一组英文字，在以下的例子，我们使用 WHITE 来做 Key。原文为 divert troops to eastridge，加密的方法是使用对应 KEY 的一行维吉尼亚表格来置换字母。
| Key | W | H | I | T | E | W | H | I | T | E | W | H | I | T | E | W | H | I | T | E | W | H | I |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 原文 | d | i | v | e | r | t | t | r | o | o | p | s | t | o | e | a | s | t | r | i | d | g | e |
| 加密 | Z | P | D | X | V | P | A | Z | H | S | L | Z | B | H | I | W | Z | B | K | M | Z | N | M |
维吉尼亚密码最妙的地方是就算同一个原文字母会被加密成不同的加密字母，有效地抵抗 Frequency Analysis 的攻击。
可惜，道高一呎，魔高一丈！过了不久，就有人想到破解方法。试看看以下一组维吉尼亚密码：
| Key | K | I | N | G | K | I | N | G | K | I | N | G | K | I | N | G | K | I | N | G | K | I | N | G |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 原文 | t | h | e | s | u | n | a | n | d | t | h | e | m | a | n | i | n | t | h | e | m | o | o | n |
| 加密 | D | P | R | Y | E | V | N | T | N | B | U | K | W | I | A | O | X | B | U | K | W | W | B | T |
留意 BUK 曾经两度出现，这种巧合让攻击者想到 Key 可能在这里循环了两次。攻击者这时会尝试代入三个英文字母的字词来尝试找出 key。这种重覆性就是攻击者破解的关键，如果原文够长的话，攻击者就可以利用这点拆解出原文。
到此刻为止，在密码学的战争中，攻击者似乎大获全胜……
奇谜密码机 (Enigma)
就这样过了一段很漫长的岁月，故事来到 20 世纪初，发生了一件重大事件，让密码学的渴求更加激烈，就是无线电的发明！由於无线电透过大气电波传送，人人都有机会接收得到，因此秘密讯息如果想透过无线电传播必需加密。无线电用於军事上，然而人们开始意识到透过人手加密解密讯息，速度慢之馀，也限制了加密和解密演算的复杂程度。为了发展出更难破解的加密，密码学进入了机械化的时代。
到了第一次世界大战，德军引进了奇迷密码机。此款密码机内置了大量齿轮组件，使用者输入讯息时就会同时产生加密讯息，只要收发双方知道 Key 的设定，就能彼此交换密码讯息。这使加密者和破解者的战争进入白热化的阶段。
One-time Pad Encryption 一次性密码本加密
终於，加密的历史进入了电脑时代。由於数位处理只有 1 和 0，因此，电脑的加密是建构在 1 和 0 之间的转换。比较常用的为 XOR (Exclusive or) 来作转基楚。例如：明文讯息是 HELLO，密匙是 APPLE，把明文和密匙都转换成 ASCII 再用 XOR 加密起来。
| Key | A 01000001 |
P 01010000 |
P 01010000 |
L 01001100 |
E 01000101 |
|---|---|---|---|---|---|
| 原文 | H 01001000 |
E 01000101 |
L 01001100 |
L 01001100 |
O 01001111 |
| 加密 | 00001001 | 00010101 | 00011100 | 00000000 | 00001010 |
如果想解密，只要将密文与 KEY 做一次 XOR 就能得到原文了。One-time Pad Encryption 做法简单，而且很难攻破，唯一缺点是 Key 的长度必需和原文一样长。
Stream Ciphers 资料流加密
与 One-time Pad 相近的是 Stream Ciphers，当中所不同的是加密所用的 Key 不需与明文一样长，Stream Ciphers 会把 Key 通过 Generator 延伸成无限长的 Keystream ，用来加密讯息。由於 Stream Ciphers 是把明文讯息逐个 Bit 转换成 密文，特别适合串流讯息使用，例如：视像讯息，Voice 等等。较有名的 Stream Ciphers 是 RC4。
Block Ciphers 资料区段加密
ECB (Electronic Code Book)
另一种加密方式是 Block Ciphers。透过 Block Ciphers，明文讯息被斩开成一个个 Block，每一个 Block 被独立地进行加密，最後把所有已加密的 Block 再组合起来，就是成为了密文，这个方法也称之为 ECB (Electronic Code Book)。不过今次做 Encrypt 的演算法就不是用 XOR 这麽简单。而是经过非常繁复的演算法 (algorithm) 产生出密文，例如：AES 和 DES 等，让攻击者无法反向猜到明文。
P = Plain Text, C= Cipher, K=Key
| Encryption: | Decryption: |
| C0 = Enc(K, P0) | P0 = Dec(K,C0) |
| C1 = Enc(K, P1) | P1 = Dec(K,C1) |
| . | . |
| . | . |
| . | . |
| Cn = Enc(K,Pn) | Pn = Dec(K,Cn) |
然而，ECB产生了一个问题，就是如果某些 Blocks 的内容一样，所产生出来的密文必然相同，这就存在了保安问题，攻击者有机会拆解出密文背後的秘密，最经典的例子是加密点阵图 (Bitmap) 的问题。
假设我们用 ECB 把下方左图加密，由於点阵图档案里相同颜色的 Block 资料是一样的，而相同颜色会产生出相同的密文讯息，因此图片经加密後仍然隐约看到图片的内容。
 |
 |
CBC (Cipher Block Chaining)
我们可以把 Block Ciphers 改良，解决这个问题，例如使用 CBC (Cipher Block Chaining)。CBC Mode 的重点是每一个 Block 的明文都会先和上一个 Block 的密文做一次 XOR，然後才进行 Encryption，因此就算明文是相同的，都会产生出不同的加密结果，如此一来，就解决了 ECB 所遇到的问题了。(Initial Vector 是一个任意起始值)
|
 |
| Encryption: | Decryption: |
| C0 = Enc(K, P0⊕IV) | P0 = Dec(K,C0)⊕IV |
| C1 = Enc(K, P1⊕C0) | P1 = Dec(K,C1)⊕C0 |
| . | . |
| . | . |
| . | . |
| Cn = Enc(K,Pn⊕Pn-1) | Pn = Dec(K,Cn)⊕Cn-1 |
不过，由於在 CBC 中每一个加密讯息都需倚赖前一个加密讯息运算出来，因此，如果一个加密讯息 Block 有损毁，就会影响连续两个加密讯息出现问题而无法解密。
CTR (Counter Mode)
另一种 Block Cipher 称为 CTR (Counter Mode)，加密流程如下图：
| Encryption: | Decryption: |
| C0 = P0⊕Enc(K, IV) | P0 = C0⊕Enc(K, IV) |
| C1 = P1⊕Enc(K, IV + 1) | P1 = C1⊕Enc(K, IV + 1) |
| . | . |
| . | . |
| . | . |
| Cn = Pn⊕Enc(K, IV + n) | Pn = Cn⊕Enc(K, IV + n) |
CTR 最妙的地方是在 Decryption 时不需要使用 Decryption Function，而是使用 Encryption Function 来进行解密。这在速度上有优势，特别适合需要不断读写的资料。但 CTR 最大的问题是一旦 IV 出了问题，或中途 IV 因为某些原因出错了，所有之後的讯息就再也不能解密出来了！
CFB (Cipher Feedback Mode)
最後要介绍的是 CFB mode，与 CTR 相同的是，只需使用 Encryption Function 即可进行解密，不过比 CTR 的好的是 IV 的失误只会导致第一个 Block 出问题。不过如果任何一个 Cn 出错，仍然会导致连续两个解密出错，情况就和 CBC 一样。
| Encryption: | Decryption: |
| C0 = P0⊕Enc(K, IV) | P0 = C0⊕Enc(K, IV) |
| C1 = P1⊕Enc(K, C0) | P1 = C1⊕Enc(K, C0) |
| . | . |
| . | . |
| . | . |
| Cn = Pn⊕Enc(K, Cn-1) | Pn = Cn⊕Enc(K, Cn-1) |
Symmetric Encryption 对称式加密
到现在为止，以上所说的加密方法全部是 Symmetric Encryption，原因很简单，因为加密与解都使用相同的 Key。Symmetric Encryption 在理解上相对简单，而作速度一般比 Asymmetric 快，因而被广泛使用。不过 Symmetric Encryption 一直所面对的问题就是 Key 的交换，由於只要得到 Key 就能解密，在传送 Key 给对方时必需非常仅慎，避免 Key 外泄。
Asymmetric Encryption 非对称式加密
Asymmetric Encryption 非对称式加密可谓密码学上的一大突破！Asymmetric Encryption 中有两条 Key，分别是 Public Key 与 Private Key。Public Key 是公开的，而 Private Key 只由自己保管。透过 Public Key 加密的密讯可以用 Private Key 解密，相反，使用 Private Key 加密的密讯可以用 Public Key 解密。所以，如果有人想把密讯传给我，他只要把讯息用我的 Public Key 加密，然後传给我，我就可以用我的 Private Key 解密。因为只有我自己的 Private Key 可以解密，而我的 Private Key 是不会公开的，这样就解决了 Symmetric Encryption 需要传送 Key 的问题。
Rivest, Shamir, and Adleman (RSA)
现在介绍第一款 Asymmetric Enccryption 的演算法，称为 RSA 演算法。计算流程如下：
先选两个极大的质数 p 与 q，一般长度为 512 bits。为了简单示范，在本例子中我们用 p=3, q=11。
计算 n = (p)(q) = (3)(11) = 33
计算 Φ (n) = (p – 1)(q – 1) = (2)(10) = 20
假设 Public Key = (e,n) ，Public Key 是公开的，可任意设定 e 值，例如设定成 7，那麽 Public Key 就是 (7,33)。
假设 Private Key = (d,n)，计算一个 d 值使 (d)(e) mod Φ (n) = 1
(d)(7) mod 20 = 1
d = 3
所以 Private Key 就是 (3,33)。
假设要加密的讯息是 m = 2，用 Public Key 进行加密，加密公式为密讯 c = m^e mod n
c = 2^7 mod 33 = 29
密讯 c = 29，现在尝试用 Private Key 解密，解密公式是 m = c^d mod n
m = 29^3 mod 33 = 2
ElGamal Encryption Scheme
第二种演算法为 ElGamal Encryption Scheme。计算流程如下：
先选极大质数 p，为了简单示范，在本例子中我们用 p=23，
另选常数 g，令 g mod p ≠ 1, g^2 mod p ≠1…… g^(p-2) ≠ 1, 本例子选 g = 11，
选常数 r = 3
设 Private Key x = 6
计算 Public Key y = g^x mod p = 11^6 mod 23 = 9
Public Key y = 9
现为讯息 M = 10 用 Public Key 进行加密：
A = g^r mod p = 11^3 mod 23 = 20
B = (M)(y^r) mod p = (10)(9^3) mod 23 = 22
所以加密讯息 C = (20,22)。
用 Private Key 解密 C = (20,22)
K = A^x mod p = 20^6 mod 23 = 16
M = BK^(-1) mod 23, K^(-1) 的意思是 K 的 Inverse，
K 的 inverse 意思是世上存在一个 K^(-1) 使 KK^(-1) mod 23 = 1
由於 K=16，16K^(-1) mod 23 =1 ，得知 K^(-1) = 13
M = (22)(13) mod 23
M = 10
相關主題
Jan Ho 2021-07-22
Posted In: 其他技术 Others
发表回复