网络安全 第四章 单钥密码体制

网络安全 第四章 单钥密码体制

4.1 密码体制的定义

密码体制的含义: 也叫密码系统,是指能完整地解决信息安全中的机密性、数据完整性、认证、身份识别、可控 性及不可抵赖性等问题中的一个或几个的一个系统。对一个密码体制的正确描述,需要用数学方法清楚地描述其中的各种对象、参数、解决问题所使用的算法等。

语法定义

  • 明文消息空间 M:某个字母表上的串集
  • 密文消息空间 C:可能的密文消息集
  • 加密密钥空间 K:可能的加密密钥集
  • 解密密钥空间 K':可能的解密密钥集
  • 有效的密钥生成算法 ζ:\(N \rightarrow K \times K'\)
  • 加密算法 E:\(M \times K \rightarrow C\)
  • 解密算法 D:\(C \times K' \rightarrow M\)
  • \(\forall m \in M,c \in C \\ c = E_{k_e}(m),m=D_{k_d}(c)=D_{k_d}(E_{k_e}(m))\)
密码体制的分类
密码体制的分类
  • \(k_e = k_d\),则加密算法称为单钥加密体制(对称加密体制或私钥加密体制)
  • \(k_e \neq k_d\),则加密算法称为双钥加密体制(非对称加密体制或公钥加密体制)

4.2 古典密码

古典密码两大基本方法:

  • 置换密码
    • 明文字母保持不变,顺序打乱
    • 简单的换位,可用置换矩阵表示
  • 代换密码
    • 明文字母被替换,但顺序保持不变
    • 单表代换
      • 一个明文字母对应的密文字母是确定的
      • 凯撒密码
        • 将字母按顺序推后 3 位
    • 多表代换
      • 一个明文字母可以表示为多个密文字母
      • 维吉尼亚密码
        • 计算明文字母与密钥字母的模 26 加法
        • 密钥是一个词组
    • 弗纳姆密码
      • 将每消息比特和相应的密钥比特进行比特异或运算
      • 密钥串只使用一次的话,就是一次一密密码

4.3 流密码的基本概念

流密码是将明文划分成字符(如单个字母),或其编码的基本单元(如0, 1数字),字符分别与密钥流作用进行加密,解密时以同步产生的同样的密钥流实现。

流密码的框图
流密码的框图
  • 消息流:\(m=m_1 m_2 ...m_n\)
  • 密钥流:\(\{ k_i \},i \geq 0\)
  • 密文流:\(c=c_1 c_2 ... c_n\)
  • \(c_i=E_{k_i}(m_i),m_i=E_{k_i}(c_i)\)

流密码强度完全依赖于密钥流的随机性不可预测性。则流密码的核心问题也就是密钥流生成器的设计。

若密钥流是一个完全随机的非周期序列,则可以实现一次一密体制,但需要无限存储单元和复杂的输出逻辑函数 f;实用中的流密码大多采用有限存储单元和确定性算法,可用有限状态自动机来描述。

密钥流生成器-有限状态自动机
密钥流生成器-有限状态自动机

根据 \(\sigma_i\) 与明文的关系,可将流密码分为同步流密码和自同步流密码。

同步流密码

\(\sigma_i\) 与明文消息无关,则密钥流独立于明文。其特点:

  • 对于明文而言,这类加密变换是无记忆的,但它是时变的
  • 对失步敏感,只有保持两端精确同步才能正常工作
  • 对主动攻击异常敏感而有利于检测
  • 无差错传播

自同步流密码

\(\sigma_i\) 依赖于 \((k_I,\sigma_{i-1},m_i)\),则密钥流与明文 \(m=m_1 m_2 ... m_{i-I}\) 有关。其特点:

  • 具有自同步能力,强化了抗统计分析能力;收端只要连续正确地收到 n 位密文,则在相同密钥 \(k_I\) 作用下就会产生相同的密钥
  • 有 n 位长的差错传播,传出过程中一位出错,影响后 n 位密钥的正确性

密钥流产生器

同步流密码的密钥流产生其可看作做一个参数为 k 的有限状态自动机(FA)。

作为 FA 的密钥流产生器
作为 FA 的密钥流产生器
  • 输出集 Z,状态集 Σ,状态转移函数 φ,输出函数 ψ,初态 \(\sigma_0\)
  • 通常采用线性状态庄毅函数 φ 以及非线性的输出函数 ψ
  • 将此类产生其分为驱动部分和非线性组合部分
    • 驱动部分控制状态转移(LFSR)
    • 非线性组合部分提供统计特性良好的序列
两种常见的密钥流产生器
两种常见的密钥流产生器

移位寄存器是流密码产生密钥流的 一个主要组成部分。一个 n 级反馈移位寄存器由 n 个二元存储器与一个反馈函数 \(f(a_1,a_2,…,a_n)\) 组成,如图所示:

如果移位寄存器的反馈函数 \(f(a_1,a_2,…,a_n)\)\(a_1,a_2,...,a_n\) 的线性函数,则称之为线性反馈移位寄存器 LFSR (linear feedback shift register),如下图所示:

其中常数 \(c_i\) 取值 0 或 1,⊕ 是模二加法。

4.4 流密码算法 RC4

见 https://wushouyuan.com/posts/7bc92f00/

4.5 分组密码概述

分组密码就是将明文数据按固定长度进行分组,然后在同一密钥控制下逐组进行加密,从而将各个明文分组变换成一个等长的密文分组的密码。

分组密码应该满足的要求:

  • 分组长度 m 要足够大
  • 密钥量要足够大
  • 有密钥确定置换的算法要足够复杂
  • 加密和解密运算简单,易于软件和硬件高速实现
  • 数据扩展
  • 差错传播尽可能地小

安全性设计原则:

  1. 混乱原则
    • 将密文、明文、密钥三者之间的统计关系和代数关系变得尽可能复杂
  2. 扩散原则
    • 将明文的统计规律和结构规律散射到相当长的一段统计中去

设计方法:

  • 乘积密码
    • 顺序地执行两个或多个基本密码系统,使得最后结果的密码强度高于每个基本密码系统产生的结果。
    • S 盒等
  • 迭代密码
    • 将一个弱的密码函数(称为圈函数、轮函数等)迭代若干次,产生一个强的密码函数,既能快速、有效地实现,又能使明文和密钥得到必要的混乱和扩散。
    • S-P 网络(代替-置换网络)、Feistel 网络等

Feistel 网络

将 m bit 明文分成为左右各半、长为 \(\frac m2\)bit 的段,以 L 和 R 表示。然后进行多轮迭代, 其第 i 轮迭代的输入为前轮输出的:

\[L_i = R_{i-1} \\ R_i = L_{i-1} \oplus f(R_{i-1},K_i)\]

其中,\(K_i\) 是第 i 轮用的子密钥,f 是任意密码轮函数,加密和解密采用同一算法实施。

Feistel 网络
Feistel 网络
  • 分组大小:分组越大安全性越高,但速度也越慢。
  • 密钥大小:密钥越长安全性越高,但速度也越慢。
  • 循环次数:循环越多,安全性越高。
  • 圈函数:复杂性越高则抗击密码分析的能力就越强。
  • 子密钥产生算法:越复杂,密码分析就越困难。
  • 此外,还要考虑算法的执行速度,设计的算法要便于分析。

4.6 DES

https://wushouyuan.com/posts/40cbcd22/

4.7 AES

https://wushouyuan.com/posts/11b216dd/

4.8 分组密码的工作模式

密码学中,分组(block)密码的工作模式(mode of operation)允许使用同一个分组密码密钥对多于一块的数据进行加密,并保证其安全性。

分组密码自身只能加密长度等于密码分组长度的单块数据,若要加密变长数据,则数据必须先被划分为一些单独的密码块。通常而言,最后一块数据也需要使用合适填充方式将数据扩展到匹配密码块大小的长度。

通常用电话本(ECB)、密文分组链接(CBC)、密文反馈(CFB)、输出反馈(OFB)、计数器(CTR)五种工作模式。

工作模式概述
工作模式概述

ECB (Electronic Code Book)

对连续排列的消息进行加密(或解密)的最直接方式就是对它们逐段加密(或解密)。在这种情况下,消息分段恰好是消息分组。

\[ECB \ Encryption: \ C_j=CIPH_K (P_J) \ \ \ for \ j=1...n \\ ECB \ Dectyption: \ P_j=CIPH^{-1}_K (C_J) \ \ \ for \ j=1...n\]

  • 优点
    • 由于每块数据的加密是独立的因此加密和解密都可以并行计算
  • 缺点
    • 同样的明文块会被加密成相同的密文块;因此,它不能很好的隐藏数据模式
    • 不是很适合对流数据进行加密
    • 消息必须被填充到块大小的整数倍
The ECB Mode
The ECB Mode

CBC (Cipher Block Chaining)

在 CBC 模式中,每个明文块先与前一个密文块进行异或后,再进行加密。在这种方法中,每个密文块都依赖于它前面的所有明文块。同时,为了保证每条消息的唯一性,在第一个块中需要使用初始化向量 IV。IV 不必保密,但必须是不可u预测的。

  • 优点
    • CBC 模式相比 ECB 有更高的保密性
    • 解密可以并行进行
  • 缺点
    • 对每个数据块的加密依赖与前一个数据块的加密所以加密无法并行
    • 不是很适合对流数据进行加密
    • 消息必须被填充到块大小的整数倍
The CBC Mode
The CBC Mode

CFB (Cipher Feedback)

CFB 模式除了初始向量外,还需一个整型参数 s,\(1 \leq s \leq 分组长度\)。在下面公式描述的算法中,明文和密文片段的长度都是 s bit。

CFB Encryption:

\[ \begin{align} & I_1 = IV; \\ & I_j =LSB_{b-s}(I_{j-1})| C^{*}_{j-1} & for \ j =2...n;\\ & O_j=CIPH_K(I_J) & for \ j =1,2...n; \\ & C^{*}_j=P^{*}_j \oplus MSB_s(O_j) & for \ j =1,2...n; \end{align}\]

CFB Decryption:

\[ \begin{align} & I_1 = IV; \\ & I_j =LSB_{b-s}(I_{j-1})| C^{*}_{j-1} & for \ j =2...n;\\ & O_j=CIPH_K(I_J) & for \ j =1,2...n; \\ & P^{*}_j=C^{*}_j \oplus MSB_s(O_j) & for \ j =1,2...n; \end{align}\]

  • 优点
    • 非常适合对流数据进行加密,消息无需填充
    • 解密可以并行计算
    • 将块密码变为自同步的流密码
  • 缺点
    • 加密过程不能并行化
The CFB Mode
The CFB Mode

在 CFB 中,第一个输入块是 IV,选择其中的 s bit 与明文中最重要的 s bit 进行异或,产生第一个密文块。IV 剩下的 b-s bit 与第一个密文块的 s bit 连接形成第二个输入块。(或者说将第一个输入块左移位 s bit,将第一个密文块的 s bit 填充入后 s 位,形成第二个输入块)

OFB (Output Feedback)

将上一轮加密算法的输出作为本次加密的输入。

OFB Encryption:

\[ \begin{align} & I_1 = IV; \\ & I_j =O_{j-1} & for \ j =2...n;\\ & O_j=CIPH_K(I_J) & for \ j =1,2...n; \\ & C_j=P_j \oplus O_j & for \ j =1,2...n-1; \\ &C^*_n = P^*_n \oplus MSB_u(O_n) \end{align}\]

OFB Decryption:

\[ \begin{align} & I_1 = IV; \\ & I_j =O_{j-1} & for \ j =2...n;\\ & O_j=CIPH_K(I_J) & for \ j =1,2...n; \\ & P_j=C_j \oplus O_j & for \ j =1,2...n-1; \\ &P^*_n = C^*_n \oplus MSB_u(O_n) \end{align}\]

  • 优点
    • 只需要使用块密码进行加密操作,且消息无需进行填充
    • 将块密码变成同步的流密码,不用一直使用一个密钥换
    • 加密解密可以进行一定程度的并行(需要先初始化密钥)
  • 缺点
    • 加密过程不能完全并行化
    • 解密也可以完全并行计算
The OFB Mode
The OFB Mode

CTR (Counter)

用给定的计数序列 \(T_1,T_2,...,T_n\),CTR 算法如下:

CTR Encryption:

\[ \begin{align} & O_j=CIPH_K(T_j) & for \ j =1,2...n; \\ & C_j=P_j \oplus O_j & for \ j =1,2...n-1; \\ &C^*_n = P^*_n \oplus MSB_u(O_n) \end{align}\]

CTR Decryption:

\[ \begin{align} & O_j=CIPH_K(T_j) & for \ j =1,2...n; \\ & P_j=C_j \oplus O_j & for \ j =1,2...n-1; \\ &P^*_n = C^*_n \oplus MSB_u(O_n) \end{align}\]

  • 优点
    • 加解密都可以并行化
  • 缺点
    • 没有真正见到使用,估计 counter 的实现要求一致性
The CTR Mode
The CTR Mode

在 CTR 算法中,计数序列中的,每一块两两不相同。

参考文章:https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38a.pdf

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×