Cryptography Course Review Note

C0 考试相关信息

- 题型分布 -

计算题 10' * 6/7
分析题 20' (4)
综合题 20' (2/3)

* 对称 50'/公钥50'.

- 考核范围 -

C1 密码学概论、C2 密码学基础、C3 古典密码体制、C4 分组密码、C5 序列密码

C6 Hash 函数和消息验证、C7 公钥密码体制、C8 数字签名技术、 C9+ 不考

- 教师寄语 -

WCJ: 另外，关于考试呢，可能题目比较长，有些题目看起来比较吓人，但是那其实题目长不代表它难，所以咱们同学在考试的时候也要能够去读题，并且能够根据题目把这个他的要求做下来基本上就就能够把这个题目完成了，实际上他没有他看起来那么难。

C1 密码学概述

信息安全的目标：

机密性：保证信息部泄露给非授权的用户和实体
完整性：保证信息处于保持完整或为受损的状态，防止对信息特性和状态的中断，窃取篡改，伪造
可用性：授权用户按需随时访问所需信息而不被非法拒绝
认证性：确保消息的来源，可分为消息认证和实体认证
不可否认性：保障用户无法在事后否认曾经对消息的生成、签发、接收

密码体制，也称密码系统，5部分组成：

明文空间 M
密文空间 C
密钥空间 K，加密密钥 K_e 和解密密钥 K_d
加密算法 E，M-->C 的加密变换
解密算法 D，C-->M 的解密变换

根据密码分析者对明文、密文等数据资源的掌握程度，可以将密码分析攻击分为以下几种：

惟密文攻击 -被动攻击密码分析者仅能根据截获的密文进行分析，以得出明文或密钥（破译难度最大）穷举和统计分析都是惟密文攻击
已知明文攻击 -被动攻击密码分析者除了有截获的密文外，还有一些已知的明文--密文对来破译密码
选择明文攻击 -主动攻击密码分析者除得到一些“明文-密文对”外，还可以选择加密的明文，并获得相应的密文 攻击者短暂控制加密机
选择密文攻击 -主动攻击密码分析者可以选择一些密文，并获得相应的明文 攻击者控制解密机，多用于攻击公钥密码体制
选择文本攻击 -主动攻击密码分析者同时控制加密机和解密机

密码体制安全性：

无条件安全（理论安全性）即使密码分析者具有无限的计算能力，密码体制也不能被攻破
计算安全性 攻破一个密码体制的最好算法用现在或将来可得到的资源不能再足够长的时间内破译
可证明安全性（规约安全性）密码体制的安全和一个问题是相关的

C3 古典密码体制

* 能够清楚给出明文对其加密或者给出密文对其破解
* 单表和多表的形式
* 典型的古典密码的密钥空间问题，安全性
* 重合指数等不会考

- 经典密码的定义和分类 -

经典密码体制都是对称密码体制，密钥由安全信道传递，可分为：代换密码与置换密码。

代换密码

代换密码/替换密码（Substitution）—用一个符号代替另一个符号。

代换密码根据预先建立的替换表，将明文依次通过查表，替换为相应字符，生成密文，替换密码的密钥就是替换表

单表替换密码——使用一个固定的替换表：明文、密文字符一一对应

- 密码分析 - 穷举分析、统计特性(字母出现的频率)。
- 凯撒密码
  - 加密：c = (m + k) mod 26
  - 解密：m = (c - k) mod 26
  - 密钥空间: 26
- 乘数密码
  - 加密：c = (m * k) mod q
  - 解密：m = (c * k^-1) mod q
  - 密钥空间: phi(26) = phi(2) * phi(13) = 1 * 12 = 12
- 仿射密码 -- 移位密码 & 乘数密码
  - 选取 k_1，k_2 两个参数，其中 gcd(k_1, 26)=1
  - 加密：c = k_1 * m + k_2 mod 26
    - k_1 = 1 时 -> 移位密码
    - k_2 = 1 时 -> 乘数密码
  - 解密：m = (c - k_2) * k_1^-1 mod 26
  - 密钥空间: n = 26 时 -> 12*26-1
多表替换密码——使用多个替换表

提高代换密码强度的一种方法是采用多个密文字母表，使密文中的每一个字母有多种可能的字母来代替

- 密码分析 -
- 确定密钥长度 -- 确定使用的加密表个数: Kasiski 测试法、重合指数法。
- 确定具体的密钥字: 重合互指数。
- Playfair
  - 思想: 双字母转换, (一次一密: 每个明文字母都采用不同的替换表或密钥进行加密)
  - 密钥: 5×5矩阵（由一个关键词构造，I/J 视为相同）
    
    KEY -> 去重 -> 填充 5*5 矩阵，eg: FIVESTARS

- 加密：对每一**对**明文 m1, m2 加密如下：

1. 若 m1 和 m2 同行，则密文 c1 和 c2 分别紧靠 m1，m2 **右端**的字母，其中第一列看做最后一列的右方。

2. 若 m1 和 m2 同列，则密文 c1 和 c2 分别是紧靠 m1，m2 **下方**的字母，其中第一行看做最后一行的下方。

3. 若 m1 和 m2 不同行也不同列，则 c1 和 c2 是 m1，m2 确定的矩形的其他**两角**的字母，并 c1 和 m1 ，c2 和 m2 同行。

4. 若出现**重复**字母，即 𝑚1 = 𝑚2，则在其中插入字母 **Q**，eg: LLY -> L**Q**LY。

5. 如明文字母是**单数**，将 Q 放在明文的末端, eg: ABC -> ABC**Q**。
```py
m = Pl ay fa ir ci ph er wa sa ct ua ll y 
  = Pl ay fa ir ci ph er wa sa ct ua lq ly
c = QK BW IT VA AS OK VB IG IC TA WT QZ KZ
```
- 密钥空间：**25!**

Vigenère
- 26 * 26 的方阵
- 密钥: k = k_1, k_2, ... , k_n
- 明文: m = m_1, m_2, ... , m_n
- 加密: c_i = m_i + k_i mod 26
- 解密: m_i = c_i - k_i mod 26
Hill密码
- 密钥：k = n * n 可逆矩阵
- 明文 m 和密文 c 均为 n维向量
- 加密：c = k * m mod 26
- 解密：m = k^-1 * c mod 26
- k^-1 为 k 在模 26 上的逆矩阵

置换密码

置换密码/换位密码（Permutation）—对符号进行重新排序

置换密码：明文字符集保持不变，但顺序被打乱.

C4 分组密码

* DES和AES的相关规则，方式方法，思想
* DES的结构，加密解密思想，验证正确性
* 把加密解密结构图画出来，用数学符号写出过程并证明
* DES对合运算，加解密过程怎样可以是完全一样的，用数学符号实现证明
* DES中p盒，s盒规则，根据实例，写出中间计算的结果
* DES，2des，3des安全性能分析，明文空间，密文空间，密钥空间
* AES安全性能分析，明文空间，密文空间，密钥空间，加解密过程，同上，对字上面的加法乘法进行运算
* IDEA明文密文密钥空间以及安全性能
* 工作模式：ECB，CBC，CFB，OFB，CTR能够用图表示出来，并且能用数学符号表示出来，性能分析，尤其是对其错误传播率，基本效率和安全性能

- 分组密码概述 -

将明文划分成长为 𝑚 (如 𝑚=64 或 128 )的分组 𝑃＝(𝑝0, 𝑝1, 𝑝2, ….,𝑝_(𝑚−1))，各明文分组分别在长为 t 的密钥 𝐾＝(𝑘0, 𝑘1, 𝑘2, ….,𝑘_(𝑡−1)) 的控制下变换成长为 𝑛 的密文分组 𝐶＝(𝑐0, 𝑐1, 𝑐2, …,𝑐_(𝑛−1))。(一般 𝑚=𝑛)

- 特点 -

速度快、安全性较高、易于标准化和便于软硬件实现，是信息与网络安全中实现数据保密性的核心机制，在计算机通信和信息系统安全领域有着广泛应用。也是构造伪随机数生成器、序列密码、消息认证码和 Hash 函数的方法。

- 设计要求 -

分组长度要足够大、密钥量要足够大、密码变换要足够复杂、加密和解密运算简单、无数据扩展和压缩。

- 混淆与扩散 -

混淆(Confusion)：是一种使密钥与密文之间的关系尽可能模糊的加密操作。如今实现混淆常用的一个元素就是替换，这个元素在 DES 和 AES 中都有使用。
扩散(Diffusion)：是一种为了隐藏明文的统计属性而将一个明文符号的影响扩散到多个密文的加密操作。最简单的扩散元素就是位置换，它常用于 DES 中；而 AES 则使用更高级的 Mixcolumn 操作。

数据加密标准 - DES

- 算法描述 -

明密文分组均为 64-bit，有效密钥长度为 56-bit.
由初始置换、16轮迭代、逆初始置换组成.
加解密算法相同，只是解密子密钥和加密子密钥的使用顺序相反.

- Festial 结构 - 要求会画

- 数学描述 -

初始置换： $L_{0}R_{0} \leftarrow IP(64\-bits \ m)$
16 轮迭代： $L_{i} \leftarrow R_{i-1}, R_{i} \leftarrow L_{i-1} \oplus F(R_{i-1}, K_{i}) \ \ i = 1, 2, ..., 16$
逆初始置换： $64\-bit \ c \leftarrow IP^{-1}(R_{16}, L_{16})$

- ▲ DES 对合性 & 可逆性 -

可逆性证明

定义变换 T 是把 64 位数据的左右两部分交换位置
$T(L, R) = (R, L), T^2(L, R) = T(R, L) = (L, R)$ 则 T 变换为对合变换。
记 DES 第 i 轮中的主要运算为 $F$ ，即
$F_{i}(L_{i-1}, \ R_{i-1}) = (L_{i-1} \oplus F_{i}(R_{i-1}, K_i), R_{i-1})$
${F_{i\}\}^{2} = (F_{i}(L_{i-1} \oplus F_{i}(R_{i-1}, K_i), R_{i-1}), R_{i-1})$
$= ((L_{i-1} \oplus F(R_{i-1}, K_i)) \oplus F(R_{i-1}, K_i), R_{i-1})$
$=(L_{i-1}, \ R_{i-1})$
$F_{i} = {F_{i\}\}^{-1}$
则 $F$ 为对合变换。
结合 1 、2 构成 DES 的轮运算 $H_{i} = F_{i}T$
$(F_{i}T)(TF_{i}) = (F_{i}(TT)F_{i}) = F_{i}F_{i} = I$
则 $(F_{i}T)^{-1}=(TF_{i})$ , $(F_{i}T)=(TF_{i})^{-1}$
则 $H_{i}$ 为对合变换。

初始置换IP/逆初始置换IP^-1

$IP$ 在第一轮迭代之前进行，目的是将原明文块的位进行换位操作（查表）。

$IP^{-1}$ 在最后一轮迭代之后进行，在加密算法中输出为密文，在解密算法中输出明文。

16 轮迭代

在每轮迭代中，64-bit 的中间结果被分成左右两部分，且作为相互独立的 32-bit 数据进行处理。每轮迭代的输入是上轮的结果 L_i-1 和 R_i-1.

$f$ 函数

$f$ 函数在 DES 的安全性中扮演着重要的角色，在第 $i$ 轮中， $f$ 函数的输入为前一轮输出的右半部分 $L_{i-1}$ 和当地前轮密钥 $k_{i}$ ， $f$ 函数的输出将用作 $XOR$ -掩码，用来加密左半部分输入 $L_{i-1}$ 。

E-盒拓展置换

首先将 $R_{i-1}$ 32-bit输入分为 8 个 4-bit 的分组，然后把每个分组拓展为 6-bit，从而将 32 位的输入拓展为 48 位。这个过程在 E-盒 中进行，E-盒是一个特殊的置换，第一个分组包含的位为 $(1, 2, 3, 4)$ ，第二个分组包含的位为 $(5, 6, 7, 8)$ , 以此类推。
S-盒混淆替换

接着将 E-盒拓展得到的 48 位的结果与轮密钥 $k_{i}$ 进行 XOR 操作，并将 8 个 6 位长的分组送到 8 个不同的替换盒中——这个替换盒也称为 S-盒，每个 S-盒都是一个查找表，它将 6 位的输入映射为 4 位的输出。

每个 6 为的输入位的最重要的位 MSB 和最不重要位 LSB 将选择表行，而 4 个内部位，则选择列。

从密码学的角度来讲，S-盒是 DES 的核心，也是该算法中唯一的非线性元素，并提供了混淆。

P 置换

$f$ 函数中每轮 S-盒替换后的简单置换操作。

密钥编排

DES 子密钥是从初始密钥(种子密钥)产生的，种子密钥 𝐾 为 64-bit，其中有 8-bit 用于奇偶校验，因此 DES 的密钥实际上只有56-bit.密钥编排从原始的 56 位密钥中得到 16 个轮密钥 $k_{i}$ ，其中每个轮密钥 $k_{i}$ 都是 48 位。轮密钥的另一个术语叫子密钥。

初始密钥置换 PC-1 / 64-bits -> 56-bits
轮密钥置换 PC-2 / 返回 key_i

DES 安全性

DES 安全性的主要争议：

对 DES 的 S 盒、迭代次数、密钥长度等设计准则的争议
DES 存在一些弱密钥和半弱密钥
DES 的 56-bit 密钥无法抵抗穷举攻击
DES 代数结构存在互补对称性

主要安全问题：

互补性
选择明文攻击下工作量减半 ( $2^{56} \rightarrow 2^{55}$ )
$c_{1} = E_{k}(m)$ , $c_{2} = E_{k}(\overline {m})$ $\rightarrow \overline {c_{2\}\} = E_{\overline k}(m)$
穷举密钥 k, 密文为 $c_{1}$ 则找到密钥 k, 密文为 $\overline c_{2} $ 则找到密钥的补 $\overline k$ 。
2DES

双重 DES 中间相遇攻击 牺牲空间来换取时间，可使得复杂度 $2^{112} \rightarrow 2^{57}$ 。

明文 P, 密文 C, 使用所有的密钥 k 加密 P, 结果存放到 T 表中，使用所有的密钥 k' 解密 C 与 T 表中的值进行比较，若相等则用测试的两个密钥对 P 进行加密，如结果为 C 则找到密钥。
3DES
- EEE3/EDE3 -> 3 * 56-bit
- EEE2/EDE2 -> 2 * 56-bit

高级加密标准 - AES

分组长度 128-bit，密钥长度可以为 128/192/256-bit，一般使用密钥长度 128-bit，迭代轮数为 10 轮.

AES 的处理单位为字节(1-byte = 8-bit)，128-bit 的明文分组和输入密钥都被分为 16-byte，一般明文分组用以字节为单位的正方形矩阵描述，称为状态矩阵，算法的每一轮中，状态矩阵的内容不断发生变化，最后的结果作为密文输出。

- AES 加密框图 -

解密流程为加密的逆流程。

AES 每轮由 4 个阶段组成：

字节代换层
ShiftRows 层 / 行移位
MixColumn 层 / 列混合
密钥加法层

第一轮开始前进入密钥加法层与原始密钥异或，最后一轮次不进行列混合。

字节代换层(S-Box)

简单的查表，4-byte * 4-byte 组成的矩阵，每个元素的内容是一个字节的值。

ShiftRows 行移位

左循环移位，第 0 行不变，第 1 行左移 1 个字节，第 2 行左移 2 个字节，第 3 行左移 3 字节。

MixColumn 列混合

对一个状态逐列进行变换，矩阵元素的加法和乘法都是定义在基于 $Z_2[𝑥]$ 中的不可约多项式为 $𝑚(𝑥) = 𝑥^8+𝑥^4+𝑥^3+𝑥+1$ 构造的GF( $2^8$ )上的二元运算，加法等价于两个字节的异或.

乘法: 将每列视为有限域GF( $2^8$ )上的一个多项式。

乘 0x01 -> 不变
乘 0x02
- 最高位为 0，直接左移一位
- 最高位为 1，左移一位后与0001 1011 异或
乘 0x03，0000 0011= 0000 0010⊕0000 0001
乘以 0x03 可以拆为分别称为 0x01 和 0x02，再将结果异或.
eg: $(0000 0011)∙(𝑎_7 𝑎_6 𝑎_5 𝑎_4 𝑎_3 𝑎_2 𝑎_1 𝑎_0)$
$ =[(0000 0010) ⊕ (0000 0001)] ∙(𝑎_7 𝑎_6 𝑎_5 𝑎_4 𝑎_3 𝑎_2 𝑎_1 𝑎_0) =[(0000 0010) ∙(𝑎_7 𝑎_6 𝑎_5 𝑎_4 𝑎_3 𝑎_2 𝑎_1 𝑎_0)] ⊕ (𝑎_7 𝑎_6 𝑎_5 𝑎_4 𝑎_3 𝑎_2 𝑎_1 𝑎_0)$

密钥加法层轮密钥加

将轮密钥与状态按比特进行异或运算。

密钥扩展

包括两个部分：密钥扩展 和 轮密钥选取

首先将种子密钥输入到 4x4 矩阵中，每列组成一个字，w[0]，w[1]，w[2]，w[3]

对 w 数组扩展 40 个新列构成 44 列的密钥数组:

若 i 不是 4 的倍数，那么 w[i] = w[i-4] ⊕ w[i-1]
若 i 是 4 的倍数，那么 w[i] = w[i-4] ⊕ T(w[i-1])

T 函数，由字循环、字代替和轮常量异或组成:

字循环：将一个字的 4 个字节循环左移一个字节.
字节代换：对字循环的结果使用 S 盒进行字节代换.
轮常量异或：将前两步的几个同轮常量 Rcon[j](轮数)进行异或.

典型的分组密码

IDEA 国际数据加密算法(International Data Encryption Algorithm)

明文分组长度 64-bit，密钥长度 128-bit，迭代 8 轮，构成64-bit的密文块。

SMS4

分组长度 128-bit，密钥长度 128-bit，加密算法与密钥扩展算法都采用 32 轮非线性迭代结构。

工作模式

电码本模式(ECB ，Electronic Code Book)

直接用分组密码算法来进行消息的加密和解密，根据算法对明文进行分组，必要可进行填充(Padding)，一个明文分组被加密成一个密文分组，相同的明文分组加密成相同的密文分组。

- 特点 -
- 操作简单，主要用于内容较短且随机的报文的加密，可进行并行运算，速度快；
- 相同明文（在相同密钥下）得出相同的密文，即明文中的重复内容将在密文中表现出来，容易实现统计分析攻击、位图攻击、分组重放攻击和代换攻击；
- 链接依赖性：各组的加密都独立于其它分组，可实现并行处理；
- 错误传播：单个密文分组中有一个或多个比特错误只会影响该分组的解密结果。
密码分组链接模式(CBC ，Clipher Block Chaining)

* 通过引入一些随机化，尤其是初始向量(Initialization Vector, IV)来实现概率加密。
1. 所有分组的加密都链接在一起，每个密文分组不仅依赖于产生它的明文分组，还依赖于它前面的所有分组；
2. 加密过程中使用初始向量(IV)进行随机化，实现概率加密(每次加密相同的明文都会得到不同的密文)。
3. 链接依赖性：对于一个正确密文分组的正确解密要求它之前的那个密文分组也正确，不能实现并行处理；
4. 错误传播：密文分组中的一个单比特错误会影响到本组和其后分组的解密，错误传播为两组；
5. 初始化向量 IV 不需要保密，它可以明文形式与密文一起传送。
输出反馈模式(OFB，Output Feedback)

首先使用分组密码加密 IV，得到的密钥输出为 b 位密钥序列的第一个集合，将前一个密钥输出反馈给分组密码进行加密，即可计算出密钥序列的下一个分组，不断重复这个过程。

OFB 模式形成了一个同步序列密码，密钥序列不依赖与明文，也不依赖与密文。

密码(文)反馈模式(CFB，Cipher Feedback)

与 OFB 相同的是 CFB 也使用了反馈，与 OFB 不同的是，OFB 反馈的是分组密码的输出，CFB 反馈的是密文的输出，密钥序列以分组方式产生。
要生成第一个密钥序列 $s_{1}$ ，必须先加密 IV，而所有后续密钥序列分组 $s_2, s_3,...$ 都是通过加密前一个密文得到的。

优点：自同步能力强，可以处理任意长度的消息。
缺点：
- 明文某一组中有错，使以后的密文组都受影响，但经解密后，除原有误的一组外，其后各组都正确地恢复。
- 密文里的一位错误会引起明文的一个单独错误，此错误进入移位寄存器，导致密文成为无用信息，直到该错误从移位寄存器中移出。

计数器模式(CTR，Counter)

使用分组密码作为序列密码的另一种模式就是计数器(CTR)模式，与 OFB 和 CFB 模式一样，密钥序列也是以分组方式计算的，分组密码的输入为一个计数器，每当分组密码计算一个新的密钥序列时，该计数器都会产生一个不同的值。

优点：不需要任何反馈，可以实现并行化。

C5 序列密码

* 线性移位反馈寄存器，根据反馈函数或者本原多项式或者联系多项式，给出输出序列，周期，性能
* 序列密码随机性能的问题，对几个指标进行分析
* 不会单独考核算法

- 概述 -

使用随机序列（密钥流）与明文序列按位叠加产生密文，同时用同一随机序列与密文序列叠加可恢复明文。

- 密钥流要求 -

极大的周期
真正的随机序列是非周期的，但算法产生的序列都是存在周期的。
良好的统计特性
随机序列有均匀的游程分布
- 游程称序列中连续的 i 个 1 为长度等于 i 的 1 游程，同样，称序列中连续的 i 个 0 为长度等于 i 的 0 游程，如 ……0 111 0000 10…… 有长为 3 的 1 游程，长为 4 的 0 游程，长为 1 的 1 游程。
- 一般要求周期内满足同样长度的0游程和1游程的个数相等或近似相等。
良好的线性复杂度
不能用级数较小的线性反馈移位寄存器近似代替.
用统计方法由密钥序列提取密钥生成器结构或种子密钥在计算上不可行.

线性反馈移位寄存器 - LFSR

实际序列密码使用的密钥位序列 $s_{1}, s_{2}, ...$ 是通过具有某种属性的密钥流生成器得到的。一种得到长伪随机序列的简单方法就是使用线性反馈移位寄存器（LFSR）, LFSR 很容易使用硬件实现，许多序列密码都是使用 LFSR 来实现的，但不是全部。

一个 LFSR 有若干时钟存储原件（触发器）和一个反馈路径组成，存储原件的数目给出了 LFSR 的度。换言之，一个拥有 m 个触发器的 LFSR 可以称为度为 m。反馈网络计算移位寄存器中某些触发器的 XOR 和，并将其作为上一个触发器的输入。

如果这里的反馈函数是线性的，我们则将其称为 LFSR，此时该反馈函数可以表示为：

f(a_{1},a_{2}, ..., a_{n}) = c_{1}a_{1} \oplus c_{2}a_{2} \oplus ... \oplus c_{n}a_{n}

其中 $c_{i}=0$ 或 $1$ ， $⊕$ 表示异或（模二加）。

LFSR 寄存器的空间状态受限于寄存器位数最大只能达到 $2^{n}$ ，去除初始状态之后有 $2^{n}-1$ 即可到达循环节。

>> 度长为 $m$ 的 LFSR 可产生的最大周期序列长度为 $2^{m}-1$ .

只要选择合适的连接多项式便可使线性移位寄存器的输出序列周期达到最大值 $2^n$ –1，并称此时的输出序列为最大长度线性移位寄存器输出序列，简称为 $m$ 序列。

例1 求输出序列及周期

例2 m-序列密码的破译

设敌手得到密文串10110 10111 10010和相应的明文串01100 11111 11001，因此可计算出相应的密钥流为11010 01000 01011( $c \oplus m$ )。进一步假定敌手还知道密钥流是使用 5 级线性反馈移位寄存器产生的，那么敌手可分别用密文串中的前 10-bit 和明文串中的前 10-bit 建立如下方程:

即

而

从而得到

有

密钥流的递推关系为： $a_{i+5} = c_5 a_i \oplus c_2 a_{i+3} = a_i \oplus a_{i+3}$ .
- 逆矩阵求解 -
给 A 的右边拼一个同阶单位阵 $[A|E]$ ，然后通过行变换把左边变位单位阵，这时右边的就是 A 的逆矩阵 $[E|A^{-1}]$ .

序列密码安全性

Golomb 对伪随机周期序列提出的 3 个随机性公设：

在一个周期内，0 和 1 的个数相差至多为1，即{a_i}中 0 和 1 出现的概率基本相同；
在一个周期内，长为 1 的游程占游程总数的 $\dfrac {1}{2}$ ，长为 2 的游程占总数的 $\dfrac {1}{2^2}$ ，长为 i 的游程占总数的 $\dfrac {1}{2^i}$ ，且等长的游程中 0 游程和 1 游程的个数相等，即 0 和 1 在序列的每一位置出现的概率相同；
异相自相关函数是一个常数，即通过对序列与其平移后的序列相比较，不能给出其他任何信息。

序列密码相比分组密码的优点：

在硬件实施上，序列密码的速度一般要比分组密码快，而且不需要有很复杂的硬件电路。
当缓冲不足或必须对收到字符进行逐一处理时，序列密码就显得更加必要和恰当。
序列密码有较理想的数学分析。
序列密码能较好地隐藏明文的统计特性。

常见的流密码

RC4 - 基于非线性数组变换

RC4 是一个典型的基于非线性数组变换的序列密码，是密钥长度可变、面向字节操作的、使用最为广泛的的序列密码之一；分析显示该密码的周期大于 $10^{100}$ 。它以一个足够大的数组为基础，对其进行非线性变换，产生非线性的密钥流序列。
优点：容易用软件实现，加解密速度快（大约比 DES 快 10 倍）

A5 - 基于 LFSR

A5 算法已被应用于 GSM 通信系统中，用于加密从手机到基站的连接，以保护语音通信。一个 GSM 语言消息被转换成一系列的帧，每帧长 228 位，每帧用 A5 进行加密.
A5 算法主要由三个长度不同的线性移位寄存器组成，即 A, B, C。其中 A 有 19 位，B 有 22 位，C 有 23 位. 移位由时钟控制的，且遵循择多的原则。即从每个寄存器中取出一个中间位，三个数中占多数的寄存器参加移位，其余的不移位。

C6 Hash 函数

* 清楚哈希函数的概念，思想、建立它的基础，在哪里会有具体应用
* md5 和 sha-1 不需要记忆算法，但是要清楚对数据的处理过程
* 对哈希函数的安全性能分析

Hash 函数常用于消息认证、口令的安全性、文件的完整性、数字签名等。

Hash 函数性质

数据压缩，可应用于任意长度的消息，变换为固定长度的输出；
易于计算，对任意给定消息 x，计算 H(x) 比较容易，软硬件均可实现；
单向性（抗原像性），已知 H(x) 找到 x 在计算上是不可行的；
抗弱碰撞性（抗第二原像），对任意给定 x，找到 y ≠ x 且 H(x) = H(y) 在计算上是不可行的；
抗强碰撞性，找到任意满足 H(x) = H(y) 的偶对 (x, y) 在计算上是不可行的；

MD5

MD5 消息摘要算法（MD5 Message-Digest Algorithm），一种被广泛使用的密码散列函数，可以产生出一个 128-bit (16-byte，1-byte = 8-bit) 的散列值 (hash value).

MD5 是输入不定长度信息，分组长度为 512-bit，输出固定长度 128-bit 的算法。经过 4 轮次每轮次 16 步的程序流程，生成四个 32-bit 数据，最后联合起来成为一个 128-bit 散列。基本方式为，求余、取余、调整长度、与链接变量进行循环运算，得出结果。

附加填充位

填充消息：首先填充 1 个 1 和若干个 0 使得消息长度（包括原始消息的长度和本次填充的长度）模 512 与 448 同余。
★ 需要特别注意的是，若原始消息长度刚好满足模 512 与 448 同余，则还需要填充 1 个 1 和 511 个 0 。
补足长度：再将原始消息长度以 64-bit（小端序）表示附加在填充结果的后面，从而使得最终的长度（包括原始消息的长度、本次填充的长度和 64-bit 的消息长度）是 512-bit 的倍数。

☆ Little-endian：低位字节存入低地址，高位字节存入高地址。

SHA-1

分组长度为 512-bit，输出 160-bit 的消息摘要，有更强的抗穷举能力。

共 4 轮，每轮次 20 步。

- 安全性 -

SHA-1 的消息摘要比 MD5 长 32-bit.
SHA-1 中，将 16 字的分组报文扩展为 80 字，因而对于每轮迭代，增加了输入的差异。
抗密码分析攻击的强度，SHA-1 似乎高于 MD5.

- 效率 -

MD5 效率比 SHA-1 高。总的说来， SHA-1 的安全性是以牺牲效率为代价的.

MD5 安全性

攻击者的目标：找到两个不同的消息映射为同一杂凑值。

- 基本攻击方法 -

穷举攻击

最典型的方法是生日攻击：给定初值 H₀=h(M)，寻找 M' ≠ M，使 h(M') = H₀，MD5 算法抗密码分析的能力较弱，生日攻击所需代价是试验 $2^{64}$ 个消息。
密码分析

依赖于 Hash 函数的结构和代数性质分析，采用针对 Hash 函数弱性质的方法进行攻击，如中间相遇攻击、修正分组攻击和差分攻击等。

消息认证码

消息认证是一个过程，用以验证接收消息的真实性（的确是由它所声称的实体发来的）和完整性（未被篡改、插入、删除），同时还用于验证消息的顺序性和时间性（未被重排、重放、延迟等）.

实现消息认证的两类常见手段：

基于加密技术的消息认证
基于散列函数的消息认证

消息认证码(MAC，Message Authentication Code)或报文认证码是一种消息认证技术，利用消息和双方共享的密钥通过认证函数来生成一个固定长度的数据块，并将该数据块附加在消息后。

基于 DES 的消息认证码

采用 DES 运算的密码分组链接模式（CBC），初始向量 IV 为 0，将需要认证的数据分为连续的 64-bit 分组。

基于Hash的认证码

HMAC：将散列函数嵌入到消息认证码的构造过程中，在安全协议 SSL 和 IPSec 中使用 HMAC 实现消息认证功能，对消息认证码的穷举攻击比对使用相同长度密钥的加密算法的穷举攻击更困难。

- 应用 -

通信双方 A 和 B 有一个共享密钥 K。当 A 有要发往 B 的消息时，发送方 A 利用共享密钥 K 计算 MAC，然后将消息和 MAC 一起发往预定的接收者 B.

在接收端 B ，使用相同的密钥 K 对收到的消息执行相同的计算并得出新的 MAC，将收到的 MAC 与计算得出的 MAC 进行比较：如果相同，则消息的确来自 A，且没有被更改过；如果不同，丢弃消息。

C7 公钥密码

* 了解椭圆曲线的思想
* rsa 算法过程进行计算，安全性能进行分析
* 离散对数，应用它进行签名和加密，不要求记住加密签名过程，但是要能够对他进行验证、计算、安全性分析

如何实现密钥的安全传输？有没有不需要安全信道的密码技术？

- 公钥密码学概述 -

公钥密码学(Public Key Cryptography, PKC)

对称加密体制的不足 — 签名和认证问题：对称密码体制中，通信双方共享密钥，因此：

接收方可以伪造原文—不能实现鉴别认证
发送方也可以否认—不能实现不可否认性

解决方案：公钥密码体制。

公钥密码（非对称密码）：每个用户都分别拥有两个密钥：加密密钥(公钥)与解密密钥(私钥) ，两者并不相同，且由加密密钥得到解密密钥在计算上不可行。加密密钥是公开的。

构造可行的不对称密码系统，关键是找到合适的数学函数 — 单向陷门函数。

单向陷门函数 𝒇：

给出 𝑓 定义域中的任意元素 𝑥,计算 𝑓(𝑥) 是容易的；
给出 𝑦 = 𝑓(𝑥) 中的 𝑦，计算 𝑥：

若知道设计函数 𝑓 时结合进去的某种信息（称为陷门），则 𝑥 容易计算；
若不知道该陷门信息，则 𝑥 难以计算。

RSA 公钥密码体制

该算法的数学基础是初等数论中的欧拉定理，其安全性基于大整数因子分解的困难性。

密钥生成

选择两个大素数 $p$ 和 $q$ ( $𝑝 ≠ 𝑞$ ，需要保密，步骤 4 以后建议销毁).
计算 $𝑛 = 𝑝 × 𝑞$ , $\varphi(n) = (p-1)(q-1)$ .
选择整数 $𝑒$ 使 $(\varphi(n)，𝑒) = 1$ , $1 < 𝑒 < \varphi(𝑛)$ .
计算 $𝑑$ ，使 $𝑑 = 𝑒^{-1} \ 𝑚𝑜𝑑 \ \varphi(𝑛)$ .

得到：公钥为 {𝑒, 𝑛}；私钥为 {𝑑} .

加密(用 $𝒆，𝒏$ )：明文 $𝑀 < 𝑛$ ，密文 $𝐶 = 𝑀^𝑒 \ (𝑚𝑜𝑑 \ 𝑛)$ .
解密(用 $𝒅，𝒏$ )：密文 $𝐶$ ，明文 $𝑀 = 𝐶^𝑑 \ (𝑚𝑜𝑑 \ 𝑛)$ .

快速幂

如何快速的计算 $𝒂^𝒎 \ (𝒎𝒐𝒅 \ 𝒏)$ ？

将 $𝑚$ 表示为二进制形式 $b_{k} b_{k−1} … b_0$ ，即：

$ m = b_{k}2^{k} + b_{k-1}2^{k-1} + ... + b_{1}2 + b_0$

如： $19 = 1×2^4 + 0×2^3 + 0×2^2 + 1×2^1 + 1×2^0$ ，所以：

c = 1
c = c * c mod n
if b == 1:
    c = c * a mod n

注意：所有的乘法或乘方运算之后都有一个模运算。

求模逆

攻击方式

针对 n 分解的攻击

试除法
完全尝试所有小于 $\sqrt {n}$ 的素数；
因式分解法
- 二次筛法
- 连分数法
- 椭圆曲线筛法

循环攻击

设 m 为明文，(n, e) 为公钥，密文 c = m^e mod n
- 攻击者得到密文 c 后，对 c 依次进行如下变换：
  c₁ = c^e mod n
  c₂ = c₁^e mod n
  …… ……
  c_k = c_k-1^e mod n
  c_k+1 = c_k^e mod n
- k+1次迭代后，如果 c_k+1 = c，由 c = m^e mod n，则 c_k = m，获得明文。
避免循环攻击：
- ord_n(m) 要大，且 φ(ord_n(m))要有大的素因子。
- ord_n(m) 是 φ(n) 的因子，所以需要 p-1 和 q-1 都有大的因子。

共模攻击

m 为明文，两用户的公钥分别为 e₁ 和 e₂，且互素，共同的模数 n，两个密文分别为 c₁ 和 c₂，攻击者知道 n，e₁，e₂，c₁ 和 c₂。

恢复明文 m：由欧几里得算法可找出 r 和 s 满足 re₁+se₂=1，假定 r 是负数，那么 (c₁^-1)^-r c₂^s = m^re₁+se₂ = m mod n，无需私钥 d 即可获得明文 m。
防御：使用 RSA 公钥加密的通信中，不同用户的密钥不能有相同的模值。

低加密指数攻击

小的公钥 e 可以加快加密的速度，过小的公钥则容易受到攻击。
如果 3 个用户都使用 3 作为公钥，对同一个明文 m 加密，则 c₁ = m³ mod n₁，c₂ = m³ mod n₂，c₃ = m³ mod n₃，且 n₁，n₂，n₃ 互素，m 小于模数.
由中国剩余定理可从 c₁，c₂，c₃ 计算出 c，且 c = m³mod (n₁n₂n₃)，m = c^1/3
如果采用不同的 n，相同的 e，对 e(e+1)/2 个线性相关的消息加密，系统就会受到威胁，所以一般选取 16 位以上的素数(速度快且可防止攻击).
防御：对短消息，用随机数填充以保证 m^e ≠ m^e mod n，从而杜绝低加密指数攻击.

时间攻击

主要针对 RSA 核心运算是非常耗时的模乘，只要能够精确监视 RSA 的解密过程，就能估算出私有密钥 𝑑。

Elgamal 加密方案

安全性基于有限域上的离散对数问题(DLP)：

设 $p$ 至少是 150 位的十进制素数， $p-1$ 有大素因子。 $Z_{p}$ 为有限域，若 $g$ 为 $Z_{p}$ 中的本原元/生成元/原根，有：
${Z_p}^* = \<g\>, \ 𝛽∈{Z_p}^*$ ，求唯一的整数 $a(0 ≤ 𝑎 ≤ 𝑝−2)$ ，满足 $𝑔^𝑎 = 𝛽 \ (𝑚𝑜𝑑 \ 𝑝)$ ，记为 $ a = \log_{g}𝛽$.

一般来说，求解 𝒂 在计算上是困难的.

密钥生成

选取大素数 $p, g∈{Z_p}^* $ 是一个生成元， $p, g$ 作为系统参数所有用户共享，系统中每个用户 U 都随机挑选整数 $𝑥，2 ≤ 𝑥 ≤ 𝑝－2$ ，并计算： $𝑦=𝑔^𝑥\ (𝑚𝑜𝑑 \ 𝑝)$ ， $𝑦, 𝑝, 𝑔$ 作为用户 U 的公钥，而 $𝑥$ 作为用户 U 的私钥。

- 加密 -

用户 A 先把明文 $M$ 编码为一个在 0 到 $p-1$ 之间的整数 $m$ ；
用户 A 挑选一个秘密随机数 𝑟 ( 2 ≤ 𝑟 ≤ 𝑝－2 )，并计算： $c_1 ＝ 𝑔^𝑟 \ (𝑚𝑜𝑑 \ 𝑝)；c_2 ＝ 𝑚 \ 𝑦^𝑟 \ (𝑚𝑜𝑑 \ 𝑝)$ ；
用户 A 把二元组 $(c_{1}, \ c_{2})$ 作为密文传送给用户 B。

- 解密 -

用户 B 接收到密文二元组 $(c_{1}, \ c_{2})$ 后，做解密计算: $m = c_2 ${c_{1\}\}^{x}$^{-1}\ mod \ p$ .

算法的正确性：

算法特点

非确定性：密文依赖于加密过程中用户 A 选择的随机数 r ，加密相同的明文可能会产生不同密文 — 概率加密.
密文空间大于明文空间：明文空间为 ${Z_{p\}\}^{\*}$ ，而密文空间为 ${Z_{p\}\}^{\*}$ * ${Z_{p\}\}^{\*}$ .

安全性

同态：假设攻击者获得了消息 m 的密文 $(c_1, \ c_2)$ , 攻击者随机选择 $r'$ 和消息 $m'$ ，并计算：

c_1' = (c_1 ∗ g^{r'}) \ mod \ p $$$$c_2' = (c_2 ∗ y^{r'} ∗ m') \ mod \ p $$ 攻击者将构造的新密文 $(c_1', c_2')$ 送解密机，则返回明文: $(m ∗ m')\ mod \ p$ 从而得到密文 c 的明文 m. 计算离散对数的方法： - 大步-小步法（Giant-step Baby-step） - 指数积分法（Index Calculus） — 更有效，亚指数时间算法 ### 椭圆曲线密码体制 安全性基于 **椭圆曲线上的离散对数问题**，ECC 可用于密钥交换、数字签名和加密。 1. 椭圆曲线加密(`ECC`)最大的优点就是使用比 RSA 和 Elgamal **短得多的密钥**得到相同的安全性，此外， ECC 得到的密文和签名也比较短，因此可以减少处理负荷，使公钥密码的应用领域得到拓展。 2. 很多情况下，ECC 比其他公钥算法都具有**性能优势**，与其他公钥方案相比，ECC 的应用正在慢慢普及，大量的新应用（尤其是嵌入式平台）都是用椭圆曲线密码学。 ## C8 数字签名 ``` * 基于RSA的数字签名方案 * 基于离散对数的数字签名方案 ``` **- 数字签名的目的 -** 保证信息的**完整性**和**真实性**，即消息没有被篡改，而且签名也没有被篡改，消息只能始发于所声称的一方。 一个完善的签名方案应满足以下三个条件： 1. **不可否认性**：签名者事后不能否认或抵赖自己的签名 2. **不可伪造性**：其他任何人均不能伪造签名，也不能对接收或发送的信息进行篡改、伪造和冒充 3. **公正的仲裁**：若当事双方对签名真伪发生争执时，能通过公正的仲裁者验证签名来确定其真伪 ### 基于 RSA 的数字签名方案 **- 签名算法 -** 设 M 为明文，$K_{eA}=(e, \ n)$ 是 A 的公钥，$K_{dA}=(d, \ p, \ q, \ \varphi(n))$ 是 A 的保密的私钥。 则 A 对 M 的签名过程是： $ S_{A} = D(M, K_{dA}) = M^{d} \ mod \ n $ 验证签名的过程： $E(S_{A}, \ K_{eA}) = (M^{d})^{e} \ mod \ n = M $ ### 基于离散对数的 EIGamal 签名方案 **- 签名过程 -** **系统初始化过程**：公钥为 (p, g, y)，私钥为 x (1 ≤ x < p-1)，其中 $y = g^x \ mod \ p$ **签名过程**： 1. 选择随机数 $k ∈ {Z_p}^*$，且 $k$ 与 $(p-1)$ 互素； 2. 首先计算消息的 Hash 值 H(M)，然后计算： $$r = g^k \ mod \ p$$$$s = (H(M) - xr)k^{-1} \ (mod \ p-1)

将 (r, s) 作为签名，与 M 一起发送给接收方。

- 验证签名的过程 -

验接收方收到 M 与其签名 (r, s) 后：

计算消息 M 的 Hash 值 H(M)；
验证公式 $y^rr^s＝ g ^{H(M)} \ mod \ p$ ，成立则确认 (r, s) 为有效签名，否则认为签名是伪造的.

★求模逆

LFSR 正逆向
 逆向 给出序列求解反馈函数

对称密码 

分组密码
\+ 输入长度分组长度密钥长度
\+ DES AES
\+ Festail网络结构 
   会画 
   证明第一步是对和变换 f(f(x))=x
   S盒代换
   2DES 112-bits->57-bits
   互补性
\+ AES 
   128-bit 4c4r 基本流程 总体结构
   列混合 模不可约多项式乘法 2hex乘
   密钥生成子密钥
\+ IDEA SM4 
   简单要求 分组/密钥长度/轮次
\+ 5种工作模式 简单分析(加解密/效率)

\+ Hash函数 
    需要满足的性质 单向函数 架构
\+ MD5 SHA-1 ★填充 整数的二进制表示
\+ 2种消息认证模式 DES/Hash

3ND