一.密码学概述和古典密码
基本概念
密码编码学和密码分析学
Plaintext:明文，被隐蔽消息，M
Ciphertext:密文，C
Encryption:加密
Decryption:解密，加密的逆过程
Encryption algorithm: 加密算法，E()
Decryption algorithm: 解密算法，D()
Key: 密钥，控制加密和解密算法操作的数据处理，分别称作加密密钥和解密密钥，k
- 传统密码体制所用的加密密钥和解密密钥相同或实质上等同，从一个易于推出另一个：单钥或对称密码体制，无法实现不可否认性
- 加密密钥和解密密钥不相同，从一个难于推出另一个，双钥，或非对称密码体制
密码体系是一个五元组(M C K E D)
密钥空间K，在单钥体制下K1 = K2 = K
加密变换$E_{k1}$
解密变换$D_{k2}$
(M C K $E{k1}$ $D{k2}$)为保密通信系统
密码分析者，选定变换函数h，对c进行变换，得到的明文是明文空间中的某个元素，
即$m’ = h(x)$
如果m’ = m，则分析成功
保密系统基本要求
- 理论上不可破，即 $ p_r{m’=m}=0 $，当知道已知的明文密文时，要决定密钥或任意明文在计算上是不可行的
- Kerchhoff原则，保密性不依赖于加密体制或算法的保密，而依赖于密钥
- 加密解密算法适用于所有密钥空间中的元素
- 系统便于实现和使用
密码系统的攻击
- 惟密文攻击
- 已知明文攻击
- 选择明文攻击
- 选择密文攻击
| 攻击类型 | 攻击者掌握的内容 | |
|---|---|---|
| 惟密文攻击 | 加密算法，截获的部分密文 | |
| 已知明文攻击 | 以上及一个或多个明文密文对 | |
| 选择明文攻击 | 自己选择的明文消息及由密钥产生的密文 | |
| 选择密文攻击 | 自己选择的密文消息及相应的被解密的明文 | |
无条件安全：无论敌手截获多少密文，花费多长时间都不能解密密文 （一次一密
计算上安全：1，破译密文的代价超过被加密信息的价值。2，破译密文所花的时间超过信息的有用期。
密码学发展
Cryptology - 密码学
三个阶段：
1.1949之前：古典密码 艺术
2.1949-1975：近代密码 艺术->科学
3.1976年至今：现代密码
古典密码：
- 斯巴达棍。算法是缠绕，密钥是棍子的粗细。
- 单表代换密码：凯撒密码，单字母代换。算法是代换，密钥是密码表。
- 多表代换密码：Enigma密码机。
近代密码：
- 1977年，NBS颁布采纳IBM设计的方案作为非机密数据的数据加密标准DES，Data Encryption Standard。
- 2001.11.16，采用AES算法
- 1976，W.Diffie，M.E.Hellman，提出非对称密码算法思想
- 1977，Rivest，Shamir，Adleman提出RSA密码体制
公钥密码学实现加密密钥和解密密钥的分离，伟大革命，使用两个密钥：公钥，私钥
仿射变换
$c = E_{a,b}(m) \equiv am + b(mod26)$
$m = D_{a,b}(c) \equiv a^{-1} + (c - b)(mod26)$
当a和26互为素数的时候才可以解密 最大公因子为1时才互为素数 （不互素的话逆元求不出来，就没法解密
ab为密钥
$a^{-1}$为a的逆元
单表代换优缺点
频次问题
相对位置问题
维吉尼亚密码
加密算法
$c{i+td}=E_k(m{i+td})\equiv(m_{i+td}+k_i)(mod q)$
总结
1.理解保密通信系统模型
2.密码体制从原理分为两大类，单钥和双钥体制
3.加密算法两条安全准则
4.能够计算仿射变换
5.置换密码的操作
二.密码学相关数学知识
1.素数和互素
因子
- b能整除a，b|a : b是a的因子
- b|1 b = $\pm$1
- b|a a|b 则 a=$\pm$b
- b|a b|c. 则对于任意整数m和n -> b|(am+cn)
素数
- 素数是现代数论的核心内容
- p的因子只有 $\pm$1和 $\pm$p
- 整数分解的唯一性定理 任一正整数可以唯一分解成素数的乘积
- $a = p_1^{e_1} + p_2^{e_2} + … + p_t^{e_t}$
- $e_i$是正整数 $p_i$是素数
互素数
- c是a和b的最大公因子 c=gcd(a,b)
- 因为所有不为0的整数都是0的因子，因此，gcd(a,0) = |a|
如果gcd(a,b) = 1，则称a，b是互素的
最小公倍数 lcm。d是a和b的最小公倍数，d=lcm(a,b)
- 若gcd(a,b) = 1，则lcm(a,b) = a * b
2.模运算
数论
是密码学特别是公钥密码学的基本工具
离散的数字集合
运算是模加，模减，逆运算
对整数和多项式进行模运算
字母的通用表示：
- n: 非负整数
p: 素数
Z: 整数集合
- R: 实数集合
Q: 有理数集合
$Z_n$ = {0,1,2…n-1}小于n的非负整数集合
模运算
- a = $\lfloor a/n\rfloor$ n + (a mod n)
同余
- a mod n= b mod n a $\equiv$ b mod n
- n|(a-b) 等价a $\equiv$ b mod n
同余性质
- a $\equiv$ b mod n，则b $\equiv$ a mod n
- a $\equiv$ b mod n，b $\equiv$ c mod n，则a $\equiv$ c mod n
- a $\equiv$ b mod n，d｜n，则a $\equiv$ b mod d
- a $\equiv$ b mod $n_i$ ， d = lcm($n_1,n_2,…n_k$)，则a $\equiv$ b mod d，(i = 1,2,…,k)
同余类/等价类/模n剩余类
- 与a模n同余的全体成为a的同余类记为$[a]_n$
- $Z_n$为模n的等价类集合
等价类性质
- 在做mod n的加法和乘法时，等价类的元素可以替换，结果不变
模运算性质
- 加运算和乘运算先做模和后做模不影响结果
- 满足交换律，结合律，分配律
- 单位元，0是加法单位元，1是乘法单位元
3.模指数运算
模指数运算
- $a^m \pmod p$
- 思路：现将m用二进制表示
- ？快速指数运算查询
- 阶 $ord_n(a)$， 满足 $a^m \equiv $ 1 mod n 的最小正整数m为模n下a的阶
- $ord_n(a)$ = m，$ a^k \equiv 1$ mod n的充要条件是k为m的倍数
4.费马定理和欧拉定理
- 费马定理
- p是素数，a是正整数，且gcd(a,p) = 1,则$a^{p-1}\equiv1$ mod p
- $aa^{p-2}\equiv$ mod p 或者 $a^{-1} \equiv a^{p-2}$ mod p
- $2^{100} $ mod 13 = 3 (满足费马定理，即$2^{12} \equiv 1$ mod 13，即$2^{96} \equiv 1$ mod 13)
5.素性检测
素性检测就是对给定的数检验是否为素数
费马定理的逆命题不成立，伪素数（卡米歇尔数）
辗转相除法
7.中国剩余定理
小数重构大数
大数用小数表示
8.群环域
代数系统
- 代数系统是一种数学模型，包含要处理的数学对象的集合及集合上的关系或运算。
- 群，环，域都是代数系统。
半群
- 任取ab属于S，a和b的运算*都在S中，则S对运算*是封闭的
- 满足结合律
- 满足以上两点，称为
群
- 封闭性
- 结合律
- 单位元：$ae = ea = a$，e称为$
- 逆元：对任取a属于G，存在元素$a^{-1}$,$a a^{-1} = a^{-1} a = e$
- 满足以上几点称为$
- 实例 $
- 实例 XOR，模2加
- 实例，加法群
- 对任意n大于等于1，整数模n的集合构成一个包含n个元素的有限模n加法群，单位元是0，群中任一元素a，它的逆元是n-a，这个群记为$Z_n$
实例，乘法群不是群，是幺半群，不满足逆元的条件
乘法群 $Z_n^*$
- $Z_n^*={x\in Z_n:gcd(x,n)=1}$，小于n的非负整数且与n互素
- 模n乘法群，单位元e = 1
- 是abel群，$|Z_n^*| = \psi(n)$
- 对素数p，$Z_p^* = Z_p - 0$
Abel群
- 运算*表示加法时，称为加法群
- 乘法，乘法群
- 若G的元素是有限的，称为有限群，否则为无限群
- 有限群中，G的元素个数称为群G的阶数，表示为$|G|$ or $#G$
- 还满足交换律，则称为群$
密码学中用到的几乎都为Abel群
实例 $
- 循环群
- $g^i = a$，a为任意的一个元素，g为生成元或本原元
- 即能够自己对自己做运算，最终能够遍历群
- 实例
- $Z_4$
- $Z_p^*$，p为素数，肯定存在生成元
- 定理$Z_n^*$每一个元素都有乘法逆元
- 并不是每一个元素都是生成元
- 本原元的存在性
- 对模素数p
- 其生成元必定存在
- 当g为生成元且p与p-1互素时，$g^a$ mod p也是生成元
- 生成元个数为$\psi(p-1)$
- 对模素数p
- 元素的阶
- 拉格朗日定理推论，提供了群的阶和群中元素阶的关系
- 环
- $
- $
- 分配律
- $
- $
- 域
- $
- $
- 分配律
- $
- $
- 有限域
- 若q是素数的幂，即$q = p^n$ ，p是素数，n是正整数，则阶为q的域记为GF(q)
9.离散对数
10.平方剩余
11.小结
三.应用密码学
1.流密码
流密码的基本思想：利用密钥k产生一个密钥流，使用规则对明文串加密
与维吉尼亚类似，多表代换密码
密钥流通过密钥发生器f产生
$z_i = f(k,\theta_i)$
分组密码和流密码的区别在于有无记忆性
流密码的滚动密钥，由函数f，密钥k和初始状态西格玛完全确定。此后，输入的密文可能影响加密器中内部记忆元件的存储状态，因而可能依赖于所有输入的影响。
可分为同步和自同步两种
对称密码体制
同步流密码的变换$E_i$可以有多种选择，只要变换即可逆即可。
二元加法流密码是最常用的流密码的体制。即异或。
密钥流序列Z应该具有如下性质
- 极大的周期
- 良好的统计特性
- 抗线性分析
- 抗统计分析
有限状态自动机
是具有离散输入和输出的一种数学模型，由三部分组成
- 有限状态集
- 有限输入字符集，有限输出字符集
- 转移函数
密钥流产生器
关键是密钥流产生器。一般可将其看成为参数为k的有限状态自动机，有输出符号集，一个状态集，和两个函数以及一个初始状态组成
两个函数为状态转移函数和字符输出函数
LFSR：线性反馈移位寄存器
最大周期为2的n次方减1，n是几级寄存器
2.分组密码体制
对称密码体制
1.概述
加密解密
构成其他加密算法的组成元素
- 明文
- 明文分组
- 密钥
- 密文分组
- 加密函数
通常取密文分组数量和明文分组数量相等
- 要求
- 分组长度n足够大，防止明文穷举攻击法
- 密钥量足够大，即置换子集中的元素足够多，以防止密钥穷举攻击，但又不能过长，管理问题
- 由密钥确定置换的算法要足够复杂
- 加密和解密运算简单，易于软件和硬件高速实现
2.DES
密钥长度为56位