% CUI Hao
密码学 Cryptography
加密：军事、商业保密、身份认证、日记...
- 计算机出现前：加密人类语言文字。
- 计算机出现后：加密比特流（ASCII文本、网络协议）
古典替换式密码
凯撒密码
文本中每个字母在字母表上后移
k 个位置。ATTACK -> DWWDFN (k=3) IBM -> HAL (k=-1)
改进
重新排列字母表（单字母替换）：
alphabet: ABCDEFGHIJKLMNOPQRSTUVWXYZ map to: RCPWUXNQBZFMYTLIEGVDJOAKHS example: ATTACK -> RDDRPF
"密码组合"有
26! 种之多。维吉尼亚密码
每k个字母一组，与长度k的密码做加法：
ATTACKATDAWN (plaintext) + LEMONLEMONLE (key: LEMON) = LXFOPVEFRNHR (ciphertext)
多个字母的凯撒密码。
替换式密码
substitution cipher
单字母替换/多字母替换/密码本...
- 加密算法：映射
- 密码：描述映射关系
- 解密算法：反过来映射
另一种设计方案
也许是中国人发明的吧：
群书万卷常暗诵， 主人顾盼千金重。 药物楚老渔商市， 丸剑跳踯霜雪浮。
移位式密码 (transposition cipher)
列移位密码
按密码重新排列文本各列，然后竖着读出来：
KEY: 6 3 2 4 1 5 TEXT: W E A R E D CT: I S C O V E ==> EVLNEACDTKESEAQROFOJDEECUWIREE R E D F L E E A T O N C E Q K J E U (WE ARE DISCOVERED. FLEE AT ONCE)
密码分析
- 系统是否安全？
- 如何破解加密？
密码攻击 (COA)
仅仅获取到密文（ciphertext only attack），如何破解？
| Letter | Freq. |
|---|---|
| e | 12.702% |
| t | 9.056% |
| a | 8.167% |
| ...... | ....... |
样本越多，猜测越准确。
密码攻击 (CPA)
二战中，英国人对德国密码系统的种花攻击 (gardening)：
- 在A地放地雷
- 截取密文
...FRQALFFDSFGRE... - 在B地放地雷
- 截取密文
...FRQALFFDSFUGA...
选择明文攻击 (chosen plaintext attack)：
试探设定的明文的加密结果，获取映射关系。
一致性破坏
不破解明文，仍可以有意地篡改解密结果，欺骗接收方：
- PT:
JOHN 1000; JACK 2000 - CT:
[01] [02]; [03] [04] - CT (modified):
[01] [04]; [03] [02] - PT (modified):
JOHN 2000; JACK 1000
极端的安全性
- 经常更换密码 -> 一次性密码
- 更大的密码空间 -> 超长的密码
- 防止字典猜测 -> 密码随机选择
One Time Pad
维吉尼亚密码：使用和明文同样长的随机字母串作为密码
计算机的维吉尼亚密码：加法 -> 按位异或
U S T C plaintext: 01010101 01010011 01010100 01000011 key: 10110111 11110111 10111110 10011010 ciphertext: 11100010 10100100 11101010 11011001
OTP 为什么安全
非OTP：错误的密码 -> 无效的结果（乱码，无意义文本）
OTP：错误的密码 -> 可能得到看似正确的结果
- 不可能被COA（密文得到很多看似正确的结果）
- 不可能被CPA（一次性）
ciphertext: 11100010 10100100 11101010 11011001 wrong key: 10101010 11110001 10111001 10001101 wrong text: 01001000 01010101 01010011 01010100 H U S T
一次性
异或运算的性质：
(p1 xor k) xor (p2 xor k) = p1 xor p2
如果多次使用OTP，则可以通过密文间异或消去密码。
已知的漏洞：
- WIFI加密(WEP)
- MS-PPTP(MSCHAP-v1)
实用性
- Q: 如何安全地传送一次性密码？
- A: 加密传输密码？死循环...
现实场景：密码应当便于交换和记录...
（其实可以通过量子密码实现绝对的OTP）
实际的加密方案
密码本模式
electronic code book, ECB
各种加密算法
- 都可以归于替换式密码和移位式密码的复杂组合
- 归根结底，就是多"字母"替换
实际的例子：
- DES: 64位的替换单位
- AES: 128/192/256 位的替换单位
缺点：同前
密码块链模式
cipher block chaining
为了避免ECB模式中移动块顺序篡改数据的风险：
- 第i块明文加密之前，和上一块密文异或操作
- 第1块明文和随机生成的初始向量 (Initial Vector) 做异或
既避免了篡改数据，还可以防止COA、CPA（相同数据两次加密结果不同）
流式密码
stream cipher
块密码中，如果任何一位传输错误，则会影响整个块（甚至下一块）的解密。
基于OTP的思路，设计一种伪OTP：
- 密钥作为随机数种子
- 通过伪随机数算法生成伪OTP密钥
- 按照OTP的流程进行加密
为了避免重用攻击，也可以引入初始向量增加随机性。
其他模式
思考：文件系统加密，上述方法是否实用？
非对称加密
对称加密的矛盾：
- 密钥必须被安全地保护起来
- 密钥必须被分发给需要的用户
是否存在一种算法：
- Decrypt(Encrypt(P, K1), K2) = P
- 很难从K1推出K2
...以后再讲 (例：RSA)
生日悖论
如果一个房间里有23个或23个以上的人，那么至少有两个人的生日相同的概率要大于50%。
n(p, d) = sqrt(2d ln(1/(1-p))) n(0.5, d) = 1.2 sqrt(d) n(0.99, d) = 3.0 sqrt(d)
不要低估暴力穷举破解 (brute-force) 的危险性。
最后的话
公开算法
Kerckhoff 原则：密码学算法应当是公开的
- 保密的是数据和密钥
- 算法可以得到更多研究者的检验
不要对自己的轮子保有过度的信心。
密码学其他科技
- 数字签名
- DRM (蓝光加密算法 AACS)
- 同态加密 (Homomorphic encryption)
- ......
the End
谨慎采信本 slides 的内容：
似乎本 slides 没有出现 Alice 和 Bob
