密码学与计算机安全
- 安全服务要求
- 机密性
- 完整性
- 可用性
- 消息认证(鉴别)
- 不可否认性
- 身份鉴别
- 访问控制
- 有效性
- 基本术语
- 密码技术（Cryptography）：把可理解的消息变换成不可理解消息，同时又可恢复原消息的方法和原理的一门科学或艺术。
- 明文（plaintext）：变换前的原始消息
- 密文（ciphertext）：变换后的消息
- 密码算法（cipher）：用于改变消息的替换或变换算法
- 密钥（key）：用于密码变换的，只有发送者或接收者拥有的秘密消息
- 编码（encipher /encode）：把明文变为密文的过程
- 译码（decipher /decode）：把密文变为明文的过程
- 密码分析（cryptanalysis /codebreaking）：在没有密钥的情况下，破解密文的原理与方法
- 密码学（cryptology）：包括加密理论与解密理论的学科
- 密码学算法分类:
- 私钥加密算法(private-key encryption algorithms)/对称加密算法(symmetric encryption algorithms)
- 公钥加密算法(public-key encryption algorithms)/非对称加密算法(asymmetric encryption algorithms)
- 数字签名算法(digital signature algorithms)
- 哈希函数（hash functions）
- 密码分析学
- 唯密文攻击 (ciphertext only)
- 只知道算法与一些密文
- 利用统计方法
- 需要能够识别明文
- 已知明文攻击（known plaintext）
- 知道一些明文/密文对
- 利用已知的明文密文对进行攻击
- 选择明文攻击（chosen plaintext）
- 能够选择明文并得到相应的密文
- 利用算法的结构进行攻击
- 选择密文攻击（chosen ciphertext）
- 能够选择密文并得到对应的明文
- 利用对算法结构的知识进行攻击
- 算法复杂性类型
- 常数级: 复杂性不依赖于 \(n\)，用 \(O(1)\) 表示
- 线性复杂度: 复杂度是 \(O(n)\)
- 多项式复杂度: 复杂度是 \(O(n^k)\)，\(k\) 是一常数
- 指数性复杂度: 复杂度是 \(O(cf(n))\)，\(c\) 是一常数，\(f(n)\) 是指数函数
- 指数型算法: 复杂度高于任何多项式函数，如 \(O(2^n)\)， \(O(n!)\)，\(O(n^{\log{n}})\) 等
- 问题复杂性及其分类
- P 类问题
- 多项式时间内可解的问题
- 例如：排序、矩阵乘法、最短路径等
- NP 类问题
- 多项式时间内可验证的问题
- 例如：旅行商问题、子集和问题等
- 无条件安全与计算安全
- 无条件安全（unconditional security）
- 即使攻击者拥有无限计算资源，也无法破解密码
- 例如：一次性密码本(one-time pad)
- 计算安全（computational security）
- 在现有计算资源下，破解密码在合理时间内不可行，或者破解密码所需的代价超过了其价值
- 例如：RSA、AES 等现代密码算法