第2章：序列密码

伪随机序列的发展

伪随机数的算法与应用

  • 随机序列：被称为随机数，目前没有统一的数学定义，主要从统计学的角度阐述，应该是独立的、互不相关的、具有长周期、均匀分布、不可压缩等。
  • 真随机数：由某些物理过程产生，如热噪声、宇宙噪声、放射性衰变等，完全不可预测，在任何情况下不可能重复产生两个完全相同的随机数。
  • 伪随机数：由数学公式产生，若生成随机数的算法确定，随机数也确定。伪随机序列就是具有某种随机特性的确定序列，能通过一系列测试检验的伪随机数可作为真随机数使用。
  • 伪随机数在数据加密、密钥产生、密钥管理、数字签名等方面扮演核心角色。

伪随机序列的定义与性质

  • 定义：如果一个序列可以随意产生和重复进行，且具有近似随机的统计特性，就称为伪随机序列。
  • 常用的伪随机序列有：m序列、Gold序列、Walsh序列、R-S序列等。周期达到最大值的序列称为m序列。
  • 性质：
    • 均衡特性：m序列在一个周期中1与0出现的次数基本相等，1的个数比0多1个。
    • 游程分布随机性：m序列在一个周期中长度为i的游程数占总游程数的1/2i，且在等长的游程中”0”、”1”游程各占半。
    • 移位相加特性：一个周期为T的m序列mT与任意次位移序列mr模二相加后所得序列仍是mT序列某次移位后的序列。
    • 自相关性：周期序列的自相关函数表示序列与其移位后的序列在一个周期内对应位相同和相异的位数之差的一个参数。

伪随机数产生器

  • 产生伪随机数序列的算法称为伪随机数产生器，是一个确定算法，将短的随机比特序列（种子）扩展为长得多的、近似随机的比特序列。
  • 方法：
    • 平方取中法：选取2s位整数作为种子，将其平方得到4s位整数，取中间2s位作为下一个种子，生成随机数。
    • 线性同余法：常用方法，采用均匀分布思想，递推公式为：$ x_{i+1} = (ax_i + c) \mod m $，其中a、c和m为常数。
    • BBS产生器：基于大整数因子分解，选择两个大素数p和q，满足$ p ≡ q ≡ 3 \mod 4 $，令$n = pq$，随机选择整数s，计算$ x_0 = s^2 \mod n $。
常用的序列密码算法

A5 序列密码算法

  • 基于线性反馈移位寄存器（LFSR）的流密码算法。
  • 构造：由3个LFSR组成，分别包含19、22和23比特，密钥（种子密钥）为64位。
  • 工作机制：利用3个LFSR进行钟控方法，每个时间单元将R1[18]、R2[21]和R3[22]进行异或并作为输出密钥流。

C4 序列密码算法

  • 开发者：麻省理工学院的Rivest，也是RS4的开发者之一。
  • 特点：易于在软件中实现，是世界上使用最广泛的序列密码之一。
  • 应用：广泛用于Microsoft Windows、Lotus Notes等软件，以及SSL和无线系统安全。

ZUC 序列密码算法

  • 由中国科学院数据保护和通信安全研究中心研制，是加密算法128-EEA3和完整性算法128-EIA3的核心。
  • 构造：由LFSR、比特重组（BR）和非线性函数F组成。
  • 线性反馈移位寄存器：包括16个31比特寄存器单元，定义在素数域上，有初始化状态和工作状态。
  • 比特重组：从LFSR的8个寄存器单元抽取128比特组成4个32比特的字供下层非线性函数F和密钥输出使用。
  • 非线性函数F：包含2个32比特记忆单元变量R1和R2，输入为3个32比特字X0、X1、X2，输出为32比特字W。
  • 密钥封装：将初始密钥k、初始向量iv和常量串d作为LFSR的初始状态。
序列密码的设计与分析

线性反馈移位寄存器（LFSR）

  • 基本概念：LFSR是一种用于生成伪随机序列的硬件电路，通过线性反馈函数生成密钥流。
  • 工作原理：初始状态由用户确定，当时钟脉冲来临时，将寄存器内容移位，并通过反馈函数计算新的状态。
  • 线性反馈：如果反馈函数是线性函数，则称为线性反馈移位寄存器。反馈函数形式为：$ f(a1, a_2, …, a_n) = a_n \oplus a{n-1} \oplus … \oplus a_1 $（模2加法）。

已知明文攻击

  • 利用LFSR的线性性，基于已知明文攻击可以较容易破译流密码算法。
  • 攻击步骤：
    1. 由明文和密文序列得到密钥序列。
    2. 根据密钥序列求解线性反馈寄存器的反馈函数。