对称加密
# 古典密码
# 密码和密码分析
保密学是研究密码系统或通信安全的科学,它实际上包含两个分支,两者相互独立,相互促进
- 密码学,对信息进行编码实现隐蔽信息的一门科学
- 密码分析学,是研究分析如何破解密码的学问
攻击分类
- 被动:监听、嗅探、分析(对原有内容或过程不做破坏)
- 主动:中断、伪造、篡改(破坏原有内容或过程)
安全类型:系统安全;数据安全;内容安全
密钥类型:
- 单钥:流密码;分组密码
- 公钥:非对称密码
# 凯撒密码
古典密码,使用对称密钥体制,即加密和解密使用同一组密钥,分为
单表代换:加密 y = ax+b,解密 x = (y-b)/a
多表代换:x = [x_1,x_2,...,x_n], a = [a_1,a_2,...,a_n], b = [b_1,b_2,...,b_n]
古典密码中 a,b 即为密钥,显然是单钥,加密和解密仅使用一套密钥
凯撒密码(单表代换密码):a 对应 0,b 对应 1,依次往后,将每个字母循环向后移位 k 位,得到密文,解密时,将密文循环向前移位 k 位,得到明文
模运算单表代换 c 实现
#include <iostream>
using namespace std;
#include <vector>
void print(vector<int> v, int flag){
if(flag){
for(int i = 0; i < v.size(); i++){
cout << (char)(65+v[i]);
}
} else {
for(int i = 0; i < v.size(); i++){
cout << (char)(97+v[i]);
}
}
cout << endl;
}
// flag 为 1 格式化大写字母,为 0 格式化小写字母为仿射变换的字母表数字
vector<int> format(string m, int flag){
vector<int> vec;
for(int i = 0; i < m.size(); i++){
int k = flag ? m[i]-65 : m[i]-97;
vec.push_back(k);
}
return vec;
}
vector<int> encode(vector<int> m, int a, int b){
vector<int> c;
for(int i = 0; i < m.size(); i++){
if(m[i] < 0){ // 空格不加密
c.push_back(m[i]);
continue;
}
// 加密
c.push_back((a*m[i]+b)%26);
}
return c;
}
vector<int> decode(vector<int> c, int a, int b, int d){
// m = 11^(-1)(c-23) (mod 26)
vector<int> m;
for(int i = 0; i < c.size(); i++){
if(c[i] < 0){ // 不处理空格,因为没加密
m.push_back(c[i]);
continue;
}
// 通过逆元模运算解密
// 这里要做一个负数转正数的处理
m.push_back(((d*(c[i]-b)) % 26 + 26) % 26);
}
return m;
}
int main(){
string str1 = "THE NATIONAL SECURITY AGENCY";
string str2 = "edsgickxhuklzveqzvkxwkzukvcuh";
string str3 = "ifyoucanreadthisthankatteacher";
// 输入明文,加密返回密文
// 参数分别为格式化的明文,系数 a,常数 b
vector<int> c = encode(format(str1, 1), 11, 23);
print(c, 1);
// 输入密文,解密返回明文
// 参数分别为明文,系数,常数,系数的逆元
vector<int> m = decode(format(str2, 0), 9, 10, 3);
print(m, 0);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
维吉尼亚密码(多表代换密码):其密钥 B 为 k 位的一组数,如有密钥为字符串
在对明文进行加密时,由于 hello 长度为 5,则明文每 5 个字符一组进行(加减)变换,再举个栗子
注意题目中规定了是左乘,另外模运算满足
就是说被除数和余数中的模数的整数倍,都可以被消去,以简化运算
# 流密码
流密码,也叫序列密码,其通过密钥 k 产生一串生成序列,即密钥流 z,根据密钥流 z 来对明文进行加密
# 流密码的性质
异或操作,也叫二元加法
| X\Y | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
流密码
加密过程为
以上铭文密文以及密钥流均以向量的形式流动
流密码和分组密码、维吉尼亚密码、一次一密密码的区别
| 分组密码 | 维吉尼亚密码 | 一次一密密码 | |
|---|---|---|---|
| 流密码 | 均属于单钥密码,区别在于有无记忆性,即子密钥的产生方式不同 | 参与加密的密钥不同,一个是确定的单钥,一个是根据密钥由密钥产生器产生的密钥流,并且前者作用于分组,后者作用于比特 | 一次一密密码是一种特殊的单钥密码,其密钥只使用一次 |
流密码可进一步分类为同步流密码和自同步流密码:当电子元件的存储状态独立于输入的明文时,为同步流密码,否则为自同步流密码
- 目前大多数研究成果均基于同步流密码
一种常用的流密码:二元加法流密码,加密变换函数 E 为明文和密钥流进行异或操作,当滚动密钥 z 等于密钥本身 k 时,二元加法流密码退化为一次一密密码
密钥流的产生
其中 σ 为电子元件状态,k 为密钥
一个良好的密钥流 z 应该具备的性质
- 极大的周期性
- 良好的统计特性
- 抗线性分析
- 抗统计分析
# 有限状态自动机
第二章课后习题T4
有限状态自动机五要素
- 有限输入集
- 有限输出集
- 有限状态集
- 状态转移函数
- 输出转移函数
密钥流产生器就是一个有限状态自动机,状态就是记忆电子元件的状态,输入为密钥k,输出为密钥流z,转移函数1为状态转移函数,规定元件状态经过当前输入到下一状态的转换,转移函数2为输出函数,输入和当前状态确定一个输出
用有向图表示有限状态自动机,即为转换图,如
从直觉上来说,非线性的密码将更难预测,但完全非线性的有限状态自动机很难实现,于是我们中和一下,将密钥流产生器分解:线性的驱动部分 + 非线性的子系统 = 密钥流生成器 ==> 产生统计性能好的序列作为最终的密钥流
密钥流生成器设计关键在于找到合适的状态转移函数(σ 的转换)和输出函数(密钥 k 和状态 σ 到密钥流 z 的转换)
# 密钥流产生器
# 反馈移位寄存器
先举一个非线性的反馈移位寄存器的栗子,这是一个生成函数
我们会给定 a1,a2,a3 的初始值,假设为 (1,0,1),则有
移位的概念,即指,每运算一次,方程 f 的入参向右整体移动一位,即上一轮为 f(a1,a2,a3),则下一轮运算为 f(a2,a3,a4),其中 a4 是上一轮的输出结果
在状态转换表中,每一行的输出为 a1 出队,同时将当前 f(a3,a2,a1) 的结果从左侧入队,得到下一轮的状态
这样不断输出,一定会得到一串重复的输出,如上述输出为 1011 1011 1011...,当
成立时,我们说 k 是该反馈移位寄存器的周期,一定有
# 线性反馈移位寄存器
上述的栗子中,f 并不是一个线性函数,所以我们说其是反馈移位寄存器,而并非线性,只有当转移函数满足
即 f 为一个线性函数时,其代表的反馈移位寄存器为线性反馈移位寄存器,其中 c 向量为反馈系数,如下图线性移位寄存器,其 f = a4 ⊕ a1(c2 = c3 = c5 = 0)
假定初始序列为 (1,0,0,1,1),则可以得到周期为 31 的重复序列1001101001000010101110110001111100110......
对于线性反馈移位寄存器,有这样几种性质
- 当初始状态全为 0 时,不会产生另外的状态
- n 位最多可以表示 2^n 种状态,减去全 0,所以在反馈移位寄存器中最多只有 2^n-1 种状态,输出序列的周期最大也为 2^n-1
- 当输出序列的周期取到最大时,我们说这样的序列为一个 m 序列
输出序列的周期主要和转移函数有关,我们可以手动选取合适的能产生 m 序列的转换函数
# LFSR 的特征多项式
LFSR 的特征多项式,仅和反馈系数有关(LFSR结构图、递推式与特征多项式 p(x) 是一一对应的)
特征多项式的阶
输出序列的周期一定整除其特征多项式的阶
# m 序列的产生和破译
# m 序列的游程
第二章课后习题T5
游程:指连续的相同元素的长度,如 111 为 1 的 3 游程
m 序列的游程分布是固定的,其中 1 的游程比 0 的游程总数多一个,长为 i 的游程共有
个,被 0 和 1 平分,而长为 n-1 的游程只有 0 有,长为 n 的游程只有 1 有
# 产生 m 序列的特征多项式
反馈函数,即特征多项式决定了输出序列的性质,本章讨论特征式满足什么条件时 LFSR 能产生最大周期的 m 序列
特征多项式的阶
使上整除式成立的最小的正整数 q,即为特征多项式 p(x) 的阶
当 n 级 LFSR 的特征多项式 p(x) 的阶为
且多项式 p(x) 不可约,此时我们称这个特征多项式为本原多项式,根据这个多项式的反馈函数产生的序列一定是一个 m 序列
我们可以说
- 特征多项式既约是 m 序列的必要条件
- 特征多项式阶为 2^n-1 是 m 序列的必要条件
二者同时满足,为 m 序列出现的充要条件
# m 序列的破译
已知
易得
这是二元加法的性质,当我们已知一个 2n 长的明文和其对应的密文时,可以通过这样的二元加法求得一个 2n 长的密钥流
然后通过密钥流的递推关系列出矩阵方程,求解系数向量
总结就是两步
- 根据明文密文对照,二元加法求出密钥流
- 根据密钥流递推关系列出矩阵方程并求解系数向量
# 流密码的非线性部分
# Geffe 序列生成器
就是用一个 LFSR2 作为控制器,当为 1 时,LFSR1 生效,当为 0 时,LFSR3 生效
# JK 触发器
# Pless 生成器
由多个 JK 触发器构成,滚动生成
# 钟控序列生成器
用一个 LFSR 作为钟控,控制另一个 LFSR 是否生效
举个栗子
# 分组密码
# 和多表代换、流密码的区别
block cipher
就是多表代换的进阶版,多表代换是长为 n 的明文,通过子密钥 ki 生成长为 n 的密文,而在分组密码,明文长度为 n,密文长度为 m,根据 n 和 m 的大小分为
- m = n,称作代换
- m > n,存在数据扩展
- m < n,存在数据压缩
这里的子密钥 ki 一般是通过密钥生成函数根据密钥 k 生成,长度固定
分组密码作用的对象是一个个明文组,而流密码的对象是一个个比特位,作用的方式均是“代换”,且加密解密一个对象使用同一组密钥
# Feistel 密码结构
核心是代换-置换网络
迭代方程(代换 + 置换)
轮函数 F 一般为二元加法和盒代换(S盒)复合,子密钥 Ki 由初始密钥 K 通过子密钥产生算法得到(如 DES 用 56 位密钥生成每轮的 48 位子密钥)
置换:每轮代换过后,将把左右两个分组交换位置(在上面的迭代方程中已经体现出来)
Feistel 网络的互逆性:对于明文 M、密文 C、子密钥正序使用 K,子密钥逆序使用 Inv(K),有
# DES 数据加密标准
Data Encryption Standard,重点
明密文分组长度均为 64 比特,密钥长度 56 比特,子密钥 48 比特
符合 Feistel 密码结构
- 初始代换:通过一张 map 直接代换明文位置(IP 函数),该过程可逆
- 16 轮迭代
- 左右交换
- 逆 IP 操作
其中,轮代换(F 函数)为:扩展右半边 R 为 48 位(原 32 位),与子密钥 Ki 进行异或操作,而后经过 S 盒代换,每 6 个比特一组,产生 4 个比特的输出
16 轮迭代和左右交换一起构成 Feistel 网络:由于 Feistel 网络可逆,IP 操作也可逆,故 DES 算法的加密和解密也满足互逆
S 盒代换具体为
- 参与运算共 48 比特位,6 个一组,共 8 组,每组独立使用一个 S 盒
- 6 比特中,第一位和第六位构成列(00~11,0~3),中间四位构成行(0000~1111,0~15),通过查表得到对应数据
两个密钥的三重 DES,此时密钥长度为 2x56 = 112
三个密钥的三重 DES,密钥长度为 3x56 = 168
显然,当 K1=K3,该加密退化为两个密钥的三重 DES;当 K2=K3 或 K1=K2,退化为单重 DES
# 分组密码的运行模式
# ECB
electronic code book
就是将明文按照 64 比特分组,每组采用相同的密钥 K 进行 DES 加密,纯纯的维吉尼亚密码
# CBC
cipher block chain
每轮采用相同的密钥 K 进行 DES 加密,每轮加密过后,将加密完成的密文分组传入下一轮,下一轮的明文分组和上一轮的密文分组先进行异或,再进行 DES 加密
这样可以避免相同的明文分组产生相同的密文分组,实现扩散原则
# CFB
cipher feedback
分组密码通过 CFB 运行模式可以转化为一个自同步的流密码(从密钥产生方式和加密过程来看)
这里操作的是 64 位的密钥 K,每轮选取 j 位进行 DES 加密,加密结果作为当前轮的子密钥和 j 位明文分组采取异或操作实现加密,同时将加密结果,即密文传入下一轮,加入密钥队列队尾,实现扩散性原则
上图中 P 代表一个个明文分组,和每一轮 DES 加密出来的 j 位子密钥异或生成密文分组 C
# OFB
output feedback
和 CFB 类似,唯一的区别在于传入下一轮和下一轮明文分组异或的是上一轮的子密钥,即 j 位由 DES 算法产生的子密钥直接链入下一轮密钥(CFB 链入的是子密钥和明文分组异或的结果,即密文分组)
# AES 算法
Advanced Encryption Standard,记住各部件功能及作用
轮函数:共四个部件组成
- 字节代换
- 行移位
- 列混合
- 密钥加
其中,字节代换由 S 盒实现,是非线性的,构成非线性层;行移位和列混合构成线性混合层;密钥加构成密钥加层,具体实现见书 P63
// 轮函数
void Round(State, RoundKey){
ByteSub(State); // 字节代换,通过代换表(S盒)实现
ShiftRow(State); // 行移位
MixColumn(State); // 列混合
AddRoundKey(State, RoundKey); // 和子密钥异或
}
// 最后一轮不进行列混合
void FinalRound(State, RoundKey){
ByteSub(State); // 字节代换,通过代换表(S盒)实现
ShiftRow(State); // 行移位
AddRoundKey(State, RoundKey); // 和子密钥异或
}
2
3
4
5
6
7
8
9
10
11
12
13
14
密码编排算法,由种子密码生成子密钥
void KeyExpansion(byte Key[4*Nk], W[Nb*(Nr+1)]){
for(int i = 0; i < Nk; i++)
// Wi 为连续的四个种子密钥元素,分组
W[i] = (Key[4*i], Key[4*i+1], Key[4*i+2], Key[4*i+3]);
for(int i = Nk; i < Nb*(Nr+1); i++){
temp = W[i-1];
if(i % Nk == 0)
// ^ 为异或操作
temp = SubByte(RotByte(temp)) ^ Rcon[i/Nk];
W[i] = W[i-Nk] ^ temp;
}
}
2
3
4
5
6
7
8
9
10
11
12
加密算法
void Rijndael(State, CipherKey){
KeyExpansion(CipherKey,ExpandedKey); // 密钥编排,由种子密钥生成子密钥
AddRoundKey(State, ExpandedKey); // 初始密钥加
for(int i = 1; i < Nr; i++)
Round(State, ExpandedKey + N*i); // 轮变换
FinalRound(State, ExpandedKey);
}
2
3
4
5
6
7