概论

密码学分类

• 从原理
  • 单钥（对称）体制：加密密钥和解密密钥相同
• 双钥（非对称）（公钥 ）体制：公钥公开用于加密，私钥私有用于解密。（将加密能力与解密能力分开，可一对多和多对一）
• 从加密方式
  • 流密码：明文消息按字符逐位加密
  • 分组密码：将明文消息分组（含有多个字符），逐组地进行加密

密码学攻击与安全

柯克霍夫原则

密码学上的柯克霍夫原则（Kerckhoffs’s principle）：即使密码系统的任何细节已为人悉知，只要密匙未泄漏，它也应是安全的。 所以现代密码学（基于柯克霍夫原则）的安全性，是密钥而非算法的安全性。

密码算法分类

1. 根据功能

• 加密算法：用于机密性解决方案
• Hash 函数：用于完整性解决方案
• 数字签名：用于认证性和不可否认性

1. 根据密钥特点

• 对称密码体制（单钥密码体制）
• 非对称密码体制（共钥、双钥密码体制）

1. 根据加密方式

• 流密码
• 分组密码

评估原则

1. 无条件安全性：使用无限密文不可破解（理论上的，实际不能满足）
2. 计算安全性：使用有限资源（时间）进行分析而未能破解
3. 可证明安全性（Provable Security）：密码体制的安全性可以规约为某一个**数学问题，且这个数学问题是难解**的

古典密码

置换密码 （易位）

把明文中的字母重新排列，字母本身不变，但其位置发生了改变，这样编排成的密码称为置换密码。

1
2
3
4
5
6
7
8

#例如：把明文中的字母颠倒过来，然后截取固定长度的字母组作为密文

#明文：明晨五点行动
MING CHNEG WU DIAN XING DONG

#密文：
GNODG NIXNA IDUWG ENHCG NIM

步骤：

1. 明文分块（固定长度 $d $）
2. 取置换函数 $f$ ，从 1~d1 中选取整数排列
3. 每个块中的字母依据 $f$ 重新排列

例如：

把明文按某一顺序排列成一个矩阵，然后按另一个顺序选出矩阵中的字母形成密文，最后截成固定长度的字母组作为密文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#例如：明晨五点反攻

#明文：
MING CHENG WU DIAN FAN GONG

#矩阵：将明文五个一组排列

MINGCH
ENWUDI
ANFANG
ONG###

#选出顺序：按列排序

#密文：
MEAO INNN  NWFG GUA# CDN# HIG#

置换密码经不起已知明文攻击

代替密码

明表 → 密表的数字映射（A~Z → 0~25）

单表替换：主要在英文字母中出现
例如: bee ，将b替换成w, e替换p，单词就变成wpp

经不起穷举攻击

• 未隐藏明文字母出现频率，可以统计分析
  

加法密码

• 加密: $y = x+k\quad(mod 26)$

• 解密: $x = y-k\quad(mod 26)$
  例子：凯撒Caesar密码就是一种加法密码
  凯撒加密:把26个字母进行位移、往左边或者往右边移动，在移动时注意最多只能移动25位

  • 

    乘法密码

• 加密: $y = kx\quad(mod 26)$

• 解密: $x = k^{-1}y\quad(mod 26)$
• 条件: $(k,26)=1$（k $对模 26 存在逆元$$k^{-1}$）

仿射密码

• 密钥：$a, b\quad(0 ≤ a,\ b ≤ 25)$
• 加密：$y=ax+b\quad(mod 26)$
• 解密：$x=a^{-1}(y-b)\quad(mod 26)$
• 条件：$(a,26)=1$

对称加密

分类依据是在加密和解密的过程中是否使用相同的密钥——这里前者相同，而后者不同

对称密钥体制面临的问题更多在于如何保障密钥的安全性。
(①通信双方如何安全地共享密钥、②如何防止攻击者通过解析算法、已有密文乃至某些明密文对之间的关系来猜解出密钥)

如何防止攻击者成功猜解密钥呢？我们不妨从攻击者的角度来考虑，虽然攻击者没有密钥，但因为加密算法是公开的，那么攻击者便可尝试利用已知的算法、密文甚至其一些明密文对来解析加密所使用的密钥。由此有两种思路来避免上述情况的发生：

• 一是提高算法的复杂度，让攻击者难以解析成功
• 二是每次加密都采用不同的密钥，且让这些密钥之间没有相关性
  基于这两种思路，分别有了分组密码体制和流密码体制。

流密码

一个一个的挨个加密

基本概念

一次一密

• 明文：$x = x_{0}x_{1}x_{2}…$
• 密钥：$k = k_{0}k_{1}k_{2}…$
• 密文：$y = y_{0}y_{1}y_{2}…$
• 加密函数：$y_{i}=x_{i}+k_{i} (mod 26)$
• 解密函数：$x_{i}=y_{i}−k_{i} (mod 26)$

特点是每次加密采用不同的密钥，且这些密钥之间没有相关性。 理论上讲这样的密码体制是最安全的（一次一密钥），但在现有的技术背景下，实现真正严格意义上的一次一密钥是很困难的……

优点

• 密钥随机产生, 仅使用一次
• 无条件安全
• 加密和解密为加法运算, 效率较高
  缺点
• 密钥长度至少与明文长度一样长, 密钥共享困难, 不太实用

流密码核心思想

基本思想

利用密钥 k 产生密钥流 $z=z_{0}z_{1}z_{2}\cdots$，并使用规则 $y_{i}=E_{z_{i}}(x_{i})$进行加密： $\color{red}{y=y_{0}y_{1}y_{2}{\cdots}=E_{z_{0}}(x_{0})E_{z_{1}}(x_{1})E_{z_{2}}(x_{2})\cdots}$

密钥流

• 由密钥流发生器 $f$ 产生 $z_{i}=f(k,\sigma_{i})$

• $\sigma_{i}$ 是加密器中记忆元件（寄存器）在 $\color{red}{i}$ 时刻的状态

  （自）同步流密码

• $\sigma_{i}$ 与密文无关的是同步流密码

• $\sigma_{i}$ 与密文有关的是自同步流密码，产生的错误会向后传播

线性反馈移位寄存器!

工作原理

• 初始状态：用户确定

• 状态转移：

  • 时钟脉冲来临，将第 i 级寄存器内容传递给第 i-1 级寄存器 ($i=2,3,\dots,n$)
  • 第 1 级寄存器的内容作为输出
  • 反馈函数计算的值传递给第 n 级寄存器

  反馈函数

注意：

• 系数不全为0，否则n个时钟脉冲后输出恒为0
• $\color{red}{c_{n}\ne0}$，否则第一级不起作用

周期：

设初始状态位101

• 最长就是$2^n -1$（除全 0 状态），周期达到最大的序列称为 m 序列

分组密码

将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组（可看成长度为n的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列。

分组密码概述

原则

• 设计原则
  • 扩散：扩散的是使明文和密文之间的统计关系变得复杂（防止穷举）
    • 常使用置换方法实现扩散（通常是重复执行置换再加一个函数）
  • 混淆：混淆是使密钥和密文之间的统计关系变得复杂（尽量减少$k_{t-1},k_{t}$的相关度）
    • 使得明文一位改变，密文多位改变，防止部分破译
    • 常使用代替方法实现混淆（通常复杂代换）。
  • 分组N要足够大，否则就等价于古典的代换密码
    • 对n比特的代换结构，密钥的大小是n×2^n比特（n比特的分组长度，有2^n种情况）
    • 一种密钥对应一个代换网络$f_k:x\rightarrow y$
  • 明文密文一一对应：
    • 

结构

分组密码的迭代方式——SP网络

• S表示代替, 又称为混淆层
• P表示置换, 又称为扩散层

• 简化结构
  • S盒：即把每一组叫做一个S盒
    • 
  • 迭代型分组密码设计规范
    • 
    • 
      • 置换P使得S盒内部的扩散性扩散到系统内，防止局部破译（如果没有置换P，一位明文改变只会影响该S盒）

分组密码的迭代方式 — Feistel 网络

【基本参数】

【基本思想】

• 各组并行，每一个分组进行多轮加密
• 输入分组长为$2w$的明文和一个密钥$K$。将每组明文分成左右两半$L_0$盒$R_0$,在进行完$n$轮迭代后，左右两半再合并到一起以产生密文分组。第i轮迭代的输入为前一轮输出的函数：
  • $L_i=R_{i-1}$
  • $R_{i}=L_{i-1}\oplus F(R_{i-1},K_i)$
• 每个分组每一轮加密的（子）密钥不完全同
• 最后一轮输出互换（加解密结构一致）

【过程图解】

【优缺点】

• 缺点：扩散速度慢，每一轮有一半没改变
• 优点：轮函数F不要求可逆，快

【轮函数F的构造】

• 扩展置换E：将32比特的$R_{i-1}$扩展为48比特，以方便后续和子密钥运算
  • 将32比特分为8组，每组扩充2个比特。原比特对应新比特2-5位，第1比特为上一组的第4比特，第六比特为下一组第二比特（第一组和第八组视为相邻的组）
  • 
  • 32个输入比特中的16个在输出中出现了2次，并且2次位于不同的组，增加了扩散性。
• 轮密钥加：与子密钥逐比特异或
• S盒：输入48位，输出32位
  • 分为八组操作
  • 
• 置换P：扩散，视为扩展置换E的再次扩散

DES数据加密标准

分组密码中的流密码，

【参数设定】
分组长度：64比特
密文长度：64比特
密钥长度：64比特，其中有8位奇偶校验位，因此有效的密钥长度为56比特
子密钥长度：48比特

【步骤】

1. 对原密钥进行置换和移位，生成16轮的的子密钥
2. 对明文进行初始置换
3. 轮函数变换与置换：利用生成的子密钥和Feistel结构，进行代换-置换。其中轮函数F利用了S盒进行代换
4. 将最后输出的结果进行逆初始置换，得到最后密文

【图解】

初始置换与逆初始置换

• 初始置换是将64 bit明文的位置进行置换，得到一个乱序的64 bit明文组。
  • 
• 逆初始置换：将16轮迭代后给出的64 bit组进行置换，得到输出的密文组。输出为阵中元素按行读得的结果。初始置换的逆过程
  

• 初始置换和 逆初始置换在密码意义上作用不大，它们的作用在于打乱原来输入x的ASCII码字划分的关系。

16轮迭代运算

• 每一轮迭代
  • 
  • 注意：第十六轮不进行交换操作，目的是使加解密可以用同一个算法。
  • 

    轮函数f

包含四个变换

• 扩展置换 EP（Expansion Permutation）
  • 目的（位数变化）：32 位 输入 $\longrightarrow$ 48 输出 （原因：保持位数一致，与 48 位子密钥异或）
  • 过程：将 32 位输入分成 8 组，每组 4 位。左边增加左侧相邻分组的最后一位（第一组左侧是第八组），右边增加右侧相邻分组的第一位，扩展成 6 位。
  • 过程
• 子密钥异或
  • 过程：将扩展置换得到的 48 位结果与子密钥 $k_{i}$ 进行异或
• S盒代替（混淆）
  • 概念：非线性运算，是DES的核心。即 $S(x)\oplus S(y) \ne S(x\oplus y)$
  • 目的（位数变化）：48位 输入 $\longrightarrow$ 32 位 输出
  • 过程：
    • 分组：分为 8 组，每组 6 位$\longrightarrow\large x_{1}x_{2}x_{3}x_{4}x_{5}x_{6}$
    • 输入处理：分别输入 8 个不同的S盒，将 ${x_{1}x_{6}}$ 转换成十进制数$0\sim 3$代表行号，再将 ${x_{2}x_{3}x_{4}x_{5}}$ 转换成十进制数$0\sim 1$代表列号。
    • 查表（S盒）：得到的行号和列号在对应的S盒查表得到输出结果。
    • 
• P盒置换（扩散）
  • 说明：输出即为轮函数 $f(R_{i-1},k_{i})$的最终结果。
  • 过程：32位根据P盒变换位置。
  • 特点：

    1. 一行中的数据来自**不同行**
    2. 一行中的数据**都不来自本行**
    

子密钥生成

• 1. 初始置换 PC-1
  • 目的（位数变化）：64位密钥 $\longrightarrow$ 56位，并重排
  • 过程：根据PC-1表格，将密钥重新排列（去掉奇偶校验位）；分成左右两半$C_{0}$（前28位）和$D_{0}$（后28位）
• 2. 循环左移位
  • 过程：根据轮数不同，每轮移位次数如表所示。循环移动的总位数为28位，刚好使得$C_{0}=C_{16},D_{0}=D_{16}$。
• 3. 压缩置换 PC-2
  • 目的（位数变化）：56 位有效密钥 $\longrightarrow$ 48 位子密钥。
  • 过程：根据PC-2表，去掉了第9,18,22,25,35,38,43,54位。同时，$C_{i},D_{i}$还是下一轮子密钥计算的输入。
  • 

    解密过程

多重加密（DES）

双重DES

使用两个密钥进行两次加密

解密时逆序使用两个密钥

约化为单次加密（补充）——

若给定两个密钥$K_1,K_2$，则可能存在$K_3$使得：$E(K_2,E(K_1,P))=E(K_3,P)$所以使用了两个密钥并没有提高太多安全性

中途相遇攻击法Meet-in-the-Middle Attack

理解方式：用空间换时间

首先用全部可能的$K_1$值加密$P$得到所有的$X$，再用全部可能的$K_2$解密$C$并与$X$$ 比较，如果配对那么密钥就是当前对应的两个$K_1,K_2$。

三重DES

对付中间相遇攻击的方法：用三个密钥进行三次加密。
采用“加密-解密-加密”序列

K3可以等于K1

AES 高级加密标准

AES的结构

• 状态
  算法中间的结果

• 种子密钥

以字节为元素的矩阵阵列描述，阵列为4行,
列数为密钥长度除32, 即4列(128比特)、6列(192比特)、8列(256比特)。

• 算法结构四个阶段

• 包括一个置换和三个代替：
  • 轮密钥加（AddRoundKey）：当前分组和拓展密钥的一部分进行按位异或。
  • 字节代替（Substitute bytes）：（非线性）用一个S盒完成分组的字节到字节的代替。
  • 行移位（ShiftRows）：一个简单置换。
  • 列混合（MixColumns）：（线性）利用有限域$GF(2^8)$算术特性的一个代替。

每个阶段均可逆：后三个阶段都有对应的逆函数，而轮密钥加的逆就是用同样的轮密钥和分组相异或（异或本来就是可逆的）。

分组密码工作模式

加密算法： 加密算法是用于将明文转换为密文或将密文转换为明文的特定数学函数。它是密码系统的核心，决定了加密的强度和安全性。常见的加密算法包括AES（Advanced Encryption Standard）、DES（Data Encryption Standard）、3DES（Triple Data Encryption Algorithm）、RC4、RC5、RC6等。这些算法定义了如何对数据进行逐位或逐块的转换。

工作模式： 工作模式是一种使用加密算法对数据进行加密和解密的特定方法。它解决了如何将加密算法应用于不同大小的数据块和流的问题。工作模式还提供了如何处理多个数据块的方法，以及如何引入随机性和唯一性（如初始化向量IV）来增强安全性。

• ECB（Electronic Codebook）：每个明文块独立加密，相同的明文块会产生相同的密文块，不推荐用于安全要求高的场合。
• CBC（Cipher Block Chaining）：每个明文块先与前一个密文块进行异或操作，然后进行加密，需要初始化向量IV。
• CFB（Cipher Feedback）：加密过程类似于CBC，但解密过程以反馈模式进行，可以用于流加密。
• OFB（Output Feedback）：加密算法的输出用于生成密钥流，与明文进行异或操作以产生密文，可以用于流加密。
• CTR（Counter）：每个明文块与一个唯一的计数器值进行加密，产生一个密钥流，用于加密或解密，可以并行处理数据。

总结区别：

• 加密算法定义了如何对数据进行加密转换。
• 工作模式定义了如何使用加密算法对数据进行处理，包括如何处理数据块、如何引入随机性和唯一性等。

ECB电码本模式

• 特点：等长划分明文块，分别加密，将密文块连接（分组密码的工作模式）
• 优点：可并行计算速度快，错误不传播
• 缺点：未隐藏统计规律，不能抵抗替换攻击

CBC密码分组链接模式

• 特点：引入初始向量 $IV$、记忆，同明文可产生不同密文
• 计算方式：当前明文块 $\oplus$前一密文块，使用初始向量 $IV$ 加密首块明文
• 优点：隐藏统计规律
• 缺点：错误传播
  • 加密时出错：向后影响全体
  • 解密时出错：至多有限传播 2 块（这一块盒下一块）

CFB密码反馈模式

• 特点：可按字符、字节或 bit 处理
• 计算方式（见图）：
  • 使用密钥 $k$ 加密初始向量 $IV$ 得到 $n$ 比特序列
  • 序列高 $j$ 比特 $\oplus$ $j$ 比特明文块 $\longrightarrow$ 密文块
  • $IV$ 左移 $j$ 比特，将密文块接在 $IV$ 后，成为新 $IV$（ $\approx$ 密钥流生成器）
• 优点：适应多种格式
• 缺点：错误传播至多影响 $\color{red}\lceil n/j\rceil$ 块密文，加密效率低
  

OFB输出反馈模式

• 特点：采用加密函数的输出反馈
• 计算方式同上
• 优点：预处理密钥流，错误不传播

CTR计算器模式

• 特点：使用固定密钥 $k$ 分别加密 $t$ 个 $n$ 比特互异向量 $CTR_{i}$，作为密钥流
• 计算方式： ${\color{black}{c_{i}=E_{k}(CTR_{i})\oplus m_{i}}}\quad{1\le i \le t}$

总结

非对称密码

公钥密码

公钥密码概述

对称密码体制存在的问题

• 加密能力与解密能力的捆绑
• 密钥的更换、传递和交换需要安全信道
• 密钥管理困难：如在$n$个用户相互通信的系统中, 每个用户需要维护$n-1$个密钥。
• 不能实现身份认证和不可否认性

公钥密码的改进

• 公钥密码算法的基本工具不再是替换和置换，而是数学函数;
• 区别于传统的单密钥密码体制 (或称对称密钥密码体制)，公钥密码体制是所谓的双密钥 (非对称) 密码体制，加密密钥可以公开。即任何人都可以用这个公开的密钥进行加密，而相应的解密密钥是保密的。
• 密钥管理方便：n个用户，n份密钥

原则上不能说传统密码优于公钥密码，也不能说公钥密码优于传统密码

公钥密码组成

• 明文空间_M_：加密算法的输入或解密算法的输出
• 公钥和私钥对：分别用于加密和解密
  • 每一用户拥有一对密钥, 分别用来加密和解密消息
  • 其中一个密钥 (公钥) 存于公开的寄存器或其他可访问的文件中; 另一个密钥 (私钥) 秘密保存
• 加密算法_E_：使用密钥, 对明文加密, 输出密文
• 解密算法_D_：使用密钥, 对密文解密, 还原明文
• 密文空间_C_：解密算法的输出, 依赖于解密算法和密钥

公钥密码两个基准模型

• 加密通信——公钥加密私钥解密
  
• 认证——私钥加密公钥解密

公钥密码要求

• 解密的唯一性
• 计算加密解密的有效性：存在（低次）多项式时间算法实现加\解密
• 安全性：
  • 敌手由密文和$B$的公钥恢复明文在计算上是不可行的
  • 敌手由密文和$B$的公钥恢复对应的私钥在计算上是不可行的
• 可交换性*：$C=M,\forall m\in M,\color{}D_{SK{B}}(E_{PK_{B}}(m))=E_{PK_{B}}(D_{SK{B}}(m))=m$
  • 满足可交换性的算法比较少，如：RSA、Rabin、椭圆曲线、Diffe-Hellman、DSS

本质：是找到一个单向陷门函数

单向陷门函数

单项陷门函数是满足下列条件的可逆函数$f_{k}$：

1. 已知$k$和$s$，计算$y=f_{k}(x)$是容易的
2. 已知$y$，在$k$未知时，计算$x$使得$y=f_{k}(x)$是困难的——单向函数
3. 已知$k$，对于任意的$y$，计算$x$使得$y=f_{k}(x)$是容易的——陷门性
   寻找合适的单向陷门函数是构造公钥密码算法的关键。

RSA

密钥生成：

1. 选取两个大素数$p,q$
2. 计算$n=pq,z=(p-1)(q-1)$
   • 其中$z$是$n$的欧拉函数值。
3. 选取随机数$e(e<n)$,且$ez互素$
   • 保证了e模z的逆元一定存在，即一定能够计算出d
4. 选取$d$使得$z|ed-1$(或者说$ed\ mod\ z = 1$)
5. 公钥$(n,e)$，私钥$(p,q,d)$

加密解密：

首先对明文进行比特串分组，使得每个分组对应的十进制数小于$n$，然后依次对每个分组$m$做一次加密，所有分组的密文构成的序列即是原始消息的加密结果。

1. 由$c=m^e\ mod \ n$，将明文m转换为密文c（$m^e$除以n的余数）【要求$m<n$,如需要可以分片】
2. 解密时，$m=c^d \ mod \ n$
   

原理

欧拉定理，当$gcd(a,N)=1$时，$a^{\phi(N)}\ mod\ N=1$

在RSA中：
$N=pq,\phi(N)=(p-1)(q-1)$

回顾《信安数学》

• 如果m1，m2是两个互素的整数，则$\phi( m1m2) = \phi( m1)\phi( m2)．$
• 若X为素数，那么$\phi(X)=X-1$

而$ed=k\phi(N)+1$
则有：$C^d=(M^e)^d=M^{k\phi(N)+1}=M^1 \times (M^{\phi(N)})^k=(根据欧拉定理)=M^1\times (1)^k=M^1=M \ mod N$

举例

安全性

RSA的安全性是基于大整数分解问题的困难性假设：若已知两个大素数p和q,求n=pq是容易的，只需一次乘法运算，而由n,求p和q则是困难的。

为保证算法的安全性, 还对$p$和$q$提出以下要求:

• $p$和$q$不能太接近。
• $p$和$q$的长度应仅相差几位。
• $p－1$和$q－1$都应有大素因子。
• $gcd(p－1, q－1)$应该很小。

Diffie-Hellman密钥交换

• 一种在不安全信道下实现安全密钥交换的方法
• 基于有限域上离散对数问题的难解性

【过程】

1. 协商：用户$A$与用户$B$协商一个素数$\color{red}p$以及该素数的一个本原元（原根）$\color{red}g$ （若a模m的阶等于φ(m)，则称a为模m的一个原根。（其中φ(m)表示m的欧拉函数，阶：对于(a,n)=1的整数，满足a^r≡1 (mod n ) 的最小整数r,称为a模n的阶。））
   • 模$m$原根存在的充要条件是：$m=2,4,p^a,2p^a$其中$p$是奇素数，$a\ge 1$
2. 计算中间值并发送：
   1. 用户$A$：随机选择$x$满足$2\le x\le p-2$，计算$Y_A=g^x\mod p$并发给$B$
   2. 用户$B$：随机选择$y$满足$2\le y\le p-2$，计算$Y_B=g^y\mod p$并发给$A$
3. 计算密钥：
   1. 用户$A$：计算$K={Y_B}^x=g^{xy}\mod p$
   2. 用户$B$：计算$K={Y_A}^y=g^{xy}\mod p$

ECC算法

看车载网

椭圆曲线是连续的，并不适合加密，将椭圆曲线定义在有限域上即可将椭圆曲线变成离散的点！

哈希函数

Hash函数的概念

• Hash函数也称杂凑函数、报文摘要函数或单向散列函数。
• 任意长消息 $m\longrightarrow$ 固定长输出 $h(m)$
• 哈希函数是单项的，没有解哈希

性质

1. 不定长输入 $\longrightarrow$ 定长输出
2. 计算高效：对$\forall x$，计算$h(x)$比较容易
3. 单向性（抗原像攻击）：对给定值$z$，找到满足$h(x)=z$的$x$在计算上是不可行的。
4. 抗弱碰撞性（抗第二原像攻击）：对给定值$x$，找到$y(y\ne x)$满足$h(x)=h(y)$在计算上是不可行的。
5. 抗强碰撞性（抗碰撞攻击）：找到一组$x,y$，满足$h(x)=h(y)$在计算上是不可行的。
6. （补充）伪随机性：$H$的输出满足伪随机性测试标准。

_碰撞性_：输入空间大 $\rightarrow$ 输出空间小，碰撞一定存在，但要求在多项式时间内找不到碰撞（计算安全）。

基本使用

消息认证

“消息认证是用来验证消息完整性的一种机制或服务。消息认证确保收到的数据确实与发送时的一样 （即没有修改、插入、删除和重放） 。此外，通常还要求消息认证机制确保发送方声称的身份是真实的。”

当哈希函数用于提供消息认证功能时，哈希函数值通常称为消息摘要。

场景A

提供认证：使用了对称加密算法$E$因为只有$A$和$B$共享密钥$K$，所以消息必定来自$Bob$且未被更改
哈希码提供实现认证所需的结构冗余。
提供保密：因为加密应用到了整个消息和哈希值，因此有保密性。

场景B
仅提供认证：只使用对称密码加密哈希值，通过比较哈希码实现认证。

对于不要求保密性的应用，降低了加密和解密的开销。

场景C

提供认证：不使用加密算法而只用哈希函数实现消息认证。前提条件是通信双方共享一个相同的秘密值$S$，$Bob$将消息$M$和秘密值$S$连接后计算哈希值，因为$Alice$拥有秘密值$S$，因此可以重新计算哈希值比较认证。
由于秘密值$S$本身未被发送，所以敌手无法修改截获的消息，也不能生成假消息。

数字签名

数字签名与消息认证类似，但用途远不止消息认证。（详见第七章）

“在数字签名的情形下，使用用户私钥加密消息的哈希值。知道该用户公钥的任何人都能验证与该数字签名关联的消息的完整性。此时，想要篡改消息的敌手需要知道用户私钥。”

场景E

提供认证：使用了公钥加密算法。$Bob$用私钥加密哈希值，类似方案B。

提供数字签名：由于只有发送方能生成加密后的哈希码，所以这种方法还提供数字签名。

场景F

提供认证：和方案E一样。

提供数字签名：和方案E一样。

提供保密：在方案E的基础上，再使用一个对称密钥加密（（消息）与（用私钥加密后的哈希值）的连接）

迭代型 Hash 函数

• 对输入 $m$ 分组，分为 $L$ 个 $b$ 比特长分组 $Y_{0},Y_{1},\dots,Y_{L-1}$
• 最后一个分组需要进行填充，且包括消息 $m$ 的长度（填充前）

• 初始值：$CV_{0}=IV$
• 链接变量：$CV_{i-1}$
• 压缩函数：$f$（通常 $b\gt{n}$）
  • 第 1 轮需要一个初始值$IV$
  • 第 $i$轮输入：上一轮的输出（链接变量）$CV_{i-1}$，本轮的消息分组 $Y_{i-1}$
  • 第 $i$轮输出：$CV_{i}=f(CV_{i-1},Y_{i-1})\quad{1\le{i}\le{L}}$
  • $Hash$ 值 $H(m)=CV_{L}$最后一轮的输出

基于分组密码 CBC 模式的 Hash 函数

• 输入 $m\longrightarrow$ $L$ 个 $n$ 长分组 $m_{0},m_{1},\dots,m_{L-1}$
• 初始值：$H_{0}=IV$
• 分组密码加密算法 $E_{k}$
  • 第 $i$轮输出： ${\color{red}{H_{i}=E_{H_{i-1}}(m_{i-1})\oplus{m_{i-1}}}}\quad{1\le{i}\le{L}}$
  • $Hash$ 值 $H(m)=H_{L}$最后一轮的输出xi
    

分组密码缺陷：

• 例如DES这样的分组是64比特，长度太短不安全
• 算法速度慢

MD5算法

过程

• 消息填充
  • MD5每个分组是512，因此必须进行位填充
  • 填充比特数： $1\le{i}\le512$（必须填充）
    • 即使消息长度本身满足条件，也必须填充
  • 要求：填充后消息长度$K\ mod\ 512=448$，留出${64}$bit 用于第二步。
  • 内容：第一位是1，之后都是0 $\longrightarrow\underline{1000\cdots}$

    例如：消息长度为448 bit，则需填充512 bit 使其长度变为960 bit。

• 附加消息长度，划分消息
  • 在留出的 64bit，以小端序little-endian方式（低地址存放低有效字节），以$2^{64}$为模数取模表示消息填充前的长度。
  • 填充后的消息长度 $=L\times512=N\times32$
  • 按字（32 bit）表示消息 $M[0,1,\dots,N-1]$
• 对 MD 缓冲区初始化
  • MD5的中间结果CV保存在4个32位的寄存器（A,B,C,D）中
  • 长度：128 bit
  • 划分：4 个字寄存器（32 bit），小端存储
  • 初值：

• 处理消息
  • 分组 $Y_{q}(q=0,…,L-1)$ 经压缩函数 $H_{MD5}$ 处理
• 输出
  • 消息摘要 $MD=$ 第 $L$ 个（最后一个） $H_{MD5}$ 的输出

压缩函数$H_{MD5}$处理过程

(有点像DES)
输入: 512-bit 的明文分组 和 CV 链接向量(类似Key)
输出: 128-bit 结果
以 类似CBC 的模式链接 (即每一组的加密会受到前一组的影响),

符号说明：- 初值 $IV$，第 $q$ 个分组 $Y_{q}$，分组数 $L$，链接变量 $CV_{q}$，最终摘要值 $MD$

$CV_{0}=IV,\quad MD=CV_{L}$

• 轮函数：$RF_{x}$ ，使用基本逻辑函数
• $+$：字的模 $2^{32}$ 加法

每一次 HMD5() 中有 4 轮结构相同的逻辑函数, 不同轮次间的唯一区别是参与计算的逻辑函数不同, 分别表示为 FGHI.

MD5四种函数：

（&是与，|是或，！~是非，^是异或）

其中

• $\rho_{1}(i)=\qquad i\;\quad {mod 16}$
• $\rho_{2}(i)=(1+5i)\quad {mod 16}$
• $\rho_{3}(i)=(5+3i)\quad {mod 16}$
• $\rho_{4}(i)=\qquad 7i\;\quad {mod 16}$

每一步的迭代——

此外$H_{MD5}$ 还有一个常数表 T, 常数表 T 为定为 $T[i]=2^{32}× |sin(i)|$ (也就是sin(i)的前 32-bit 小数.) (i 是弧度)

SHA-1

• 框图：和MD5一样

  • 

    处理过程

• 消息填充

  • 和MD5完全相同
• 附加消息长度
  • 与MD5类似，只是大端序 （高字节低地址）
• 缓冲区初始化
  • ABCDE五个缓冲区
• 分组处理
• 输出：以最后一个为输出

四个流程，每个流程迭代20步

3 个字→1 个字

$W_t$导出处理

对比MD5与SHA-1

• SHA的速度要比MD5的速度慢。
• 对抗攻击似乎高于MD5的强度
• SHA抗击穷搜索攻击的强度高于MD5抗击穷搜索攻击的强度

Hash函数的分析方法

安全性分析

评价Hash函数的一个最好方法是看攻击者找到一对碰撞消息所花的代价有多大。
假设攻击者知道Hash算法, 攻击者的主要目标是找到一对或更多对的碰撞消息。

生日攻击

第一类生日攻击（生日悖论I——抗弱碰撞性）

在$k$个人中至少有一个人的生日 【与你】 相同的概率大于$0.5$时，$k$至少多大?

第二类生日攻击（生日悖论II——抗强碰撞性）

在$k$个人中至少有两个人相同的概率大于$0.5$时，$k$至少多大?

• 比较
  • 第II类生日攻击需要的输入远远小于第I类生日攻击的输入, 所以第II类生日攻击问题要比第I类生日攻击问题容易。
  • 抗强碰撞性比抗弱碰撞性要求更高

密码协议

OTP：一次性密码（动态口令）

非常类似于QQ以前的那种动态令牌

OTP的密码有效期仅在一次会话或者交易过程中，因此不容易受到重放攻击

典型的分为HOTP和TOTP

• HOTP：HMAC-based One-Time Password ，基于 HMAC 算法加密的一次性密码。事件同步，通过某一特定的事件次序及相同的种子值作为输入，通过 HASH 算法运算出一致的密码。
• TOTP：Time-based One-Time Password写，基于时间戳算法的一次性密码。 时间同步，基于客户端的动态口令和动态口令验证服务器的时间比对，一般每 60 秒产生一个新口令，要求客户端和服务器能够十分精确的保持正确的时钟，客户端和服务端基于时间计算的动态口令才能一致。
  • 现在为了考虑时间差异，服务端验证时往往采取同时验证前 此时 后三种状态的口令，只要一个匹配即可。

【核心公式】
OTP 基本原理计算 OTP 串的公式：$OTP(K,C) = Truncate(HMAC-SHA-1(K,C))$

其中，K 表示秘钥串；C 为一个特定的数（见下）；HMAC-SHA-1 表示使用 哈希函数 SHA-1 做 HMAC；Truncate 表示怎么截取加密后的串，并取加密后串的哪些字段组成一个数字。
HOTP:C一般是事件序号；TOTP:C一般是时间戳的一个函数
特别的，针对TOTP——$C = (T - T0) / X$; T 表示当前 Unix 时间戳：T0 一般取值为 0，也就是 1970 年 1 月 1 日。X 表示时间步数，也就是说多长时间产生一个动态密码，这个时间间隔就是时间步数 X，系统默认是 30 秒；

对 HMAC-SHA-1 方式加密来说，Truncate 实现如下：
HMAC-SHA-1 加密后的长度得到一个 20 字节的密串；取这个 20 字节的密串的最后一个字节，取这字节的低 4 位，作为截取加密串的下标偏移量；按照下标偏移量开始，获取4个字节，按照大端方式组成一个整数；截取这个整数的后 6 位或者 8 位转成字符串返回。

【业务逻辑】