密码学与计算机安全¶
-
安全服务要求
-
机密性
-
完整性
-
可用性
-
消息认证(鉴别)
-
不可否认性
-
身份鉴别
-
访问控制
-
有效性
-
-
基本术语
-
密码技术（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 等现代密码算法
-
-