对称密钥加密方案 Sysmetric-key encryption scheme(SKES)由下列五部分组成

• 明文空间M-The plaintext space
• 密文空间C-The ciphertext space
• 密钥空间K-The key space
• 一套加密函数 E:M→C, ∀k∈K
• 一套解密函数 D:C→M, ∀k∈K
  且满足D_k (E_k (m))=m for all m∈M, k∈K

使用对称密钥加密方案SKES来保证保密性

1. Alice和Bob在安全通道里面商定一个密钥
2. Alice通过这个密钥来加密明文m， 并把加密后的密文c通过公共通道传送给Bob
3. Bob通过解密函数D以及提前商定的k来获取明文

基本假设：我们假设对手(Adversary)知道关于此SKES的全部内容除了密钥k

安全模型：定义对手的计算能力，以及她如何与交流方互动

定义安全：对手的目标 Adversary’s Goal

1. 得到密钥 Recover the secret key
2. 可以从密文系统性的恢复明文（无需知道key)
3. 通过密文可以得到明文的部分信息（除了它的长度）

• 如果对手可以实现1和2， 那么这个SKES被认为完全不安全 Totally Insecure(totally broken)
• 如果对手无法从密文得到任何部分明文信息（除了可能知道长度），这个SKES被称为语义上安全semantically secure
• 隐藏长度信息非常难(流量分析)

定义安全：对手的互动 Adversary’s Interaction

• 被动攻击：Passive attacks
  • 仅密文攻击 Ciphertext-only attack
  • 明文攻击 Known-plaintext attack：对手知道一些明文以及对应的密文
• 主动攻击：Active attacks
  • 选择明文攻击 Chosen-plaintext attack：对手可以选择一些明文并获取到相应的密文
  • 选择密文攻击 Chosen-ciphertext attack：对手可以选择一些密文并获取到相应的明文
• 其他攻击：Other attacks
  • 旁道攻击 Side-channel attack：监听加密和解密设备(定时攻击，功率分析攻击，电磁辐射分析等)
  • 物理攻击 Physical attacks：贿赂(bribery)，勒索(balckmail)等

定义安全： 对手的计算能力 Computational Power  of the Adversary

• 信息理论安全 Information-theoretic security： Eve有无限的计算资源
• 复杂理论安全 Complexity-theoretic security： Eve是多项式图灵机
• 计算安全 Computational security：Eve 计算资源有限，有X个电脑/工作站/超级计算机(Eve is computationally bounded)

2^40 次操作被认为是非常简单 Very Easy
2^56 次操作被认为是简单 Easy
2^64 次操作被认为是可行 Feasible
2^80 次操作被认为是勉强可行 Barely Feasible
2^128 次操作被认为是不可行 Infeasible

安全的对称密钥加密方案的定义 Defination of a Secure SKES

可抵御受计算限制的对手的选择明文攻击

A symmetric-key encryption scheme is said to be secure if it is semantically secure against a chosen-plaintext attack by a computationally bounded adversary

• 此定义包含的元素
  • 选择明文攻击Chosen-plain attack （互动 interaction）
  • 计算资源有限Computationally bounded（计算能力 computational power）
  • 语义上安全Semantically secure（目标 Goal）
• 要想打破一个对称密钥加密方案，对手必须完成以下操作
  • 得到一个有挑战的密文C（由Alice或者Bob使用它们的密钥生成）
  • 在计算过程中， 对手可以选择明文并获取到相应的密文（从Alice或者Bob处获得）
  • 经过可行的数量的计算之后，对手得到有关C对应的明文的一些信息（长度除外）

安全等级 Security Level

我们称一个加密方案具有 L bits 的安全级别如果已知的最快攻击方案需要大约 2^L 次操作

对称加密方案的要求 Requirements for a SKES

• 已知高效的加密解密算法
• 密钥应该尽可能短，但是足够长使得穷举密钥搜索(exhaustive key search)变得不可行
• 方案应该安全
• 如果方案的设计者是攻击者，方案应该仍然安全
• 满足基本假设(Kerckhoffs’s principle, Shannon’s maxim)即对手知道关于这个加密算法除了密钥以外的所有信息

简单替换密码 The simple substitution cipher

M All English messages
C All encrypted messages
K All permutations of the English alphabet
E_k Apply permutation k to m, one letter at a time
D_k: Apply inverse permutation k^(−1) to c, one letter at a time.

• 密钥26个字母重新排列的序列，简单替换密码的加密过程是依次将明文中的每一个字母按照替换表替换成另一个字母
• 简单替换密码是不安全的，因为无法抵挡选择明文攻击
• 但是可以抵挡穷举密钥搜索攻击，因为需要尝试 次，基本不可行
• 一个可行的破解方法是字母频率分析

多字母密码 Polyalphabetic ciphers

• 简单替换密码的升级版，可以防止字母频率分析
• 基本思想：使用更多的排列组合，明文将被加密为不同的密文字母
• 应用：Vigenere cipher
  • 密钥是一个无重复字母的英语单词 如 CRYPTO
  • 顺序排列作为密钥
  • 明文的字母表顺序加上对应的密钥的字母表顺序得到密文的字母表顺序（mod 26）
  • 解密过程正好相反，密文减去密钥的字母表顺序（mod 26）

• 这种加密方式也无法抵挡选择明文攻击
• 破解Vigenere cipher 的过程
  • 找到密钥长度
    • 先猜测密钥的长度为 L
    • 将密文分割为L租
    • 对每一组进行字母频率分析
    • 如果单词频率跟典型英语文本字母频率相同，那么密钥长度的猜测可能是正确的
  • 当密钥长度确定了之后
    • 每组中密文字母是通过字母置换而获得的，该置换是字母表对相应明文字母的循环移位。
    • 通过密文中的字母频率来猜测密钥对应的字母
    • 使用猜测出的字母来组成一个完整的密钥
    • 使用密钥解密，检验是否得出了可读的内容

• 密钥26个字母重新排列的序列，简单替换密码的加密过程是依次将明文中的每一个字母按照替换表替换成另一个字母
• 简单替换密码是不安全的，因为无法抵挡选择明文攻击
• 但是可以抵挡穷举密钥搜索攻击，因为需要尝试 次，基本不可行
• 一个可行的破解方法是字母频率分析

一次性密码本 One-Time Pad

•  是Vigenere cipher 的修改版
  • 由Vernam发明于1917年用于电报系统
  • 密钥是一串于明文相同长度的随机字母
  • 明文和密钥进行XOR异或运算得到密文
  • XOR是可逆的，密文和密钥进行XOR运算即可以得到明文
  • 一次性密码本的密钥不应该被重复使用
  • 如果一次性密码本的密钥是随机且无重复使用的，那么将是理论上无法破解的
  • 无任何实际应用意义