基本理念：用一个伪随机的密钥来代替在一次性密码本中使用的随机密钥

• 伪随机位生成器Pseudorandom Bit Generator （PRBG）是一个确定性算法，将（随机）种子作为输入，并输出更长的“伪随机”序列称之为密钥流
• 这个随机的种子就是密钥，他在Alice和Bob之间共享，他们可以通过这个种子+PRBG来生成伪随机序列从而加密解密信息
• 不再需要完美的保密性-安全性取决于PRBG的质量
• 我们又称PRBG为 Keystream generator 流生成器

伪随机位生成器的安全要求

• 密钥流应与一个随机序列“无区别“（不可区分性）
• 如果对手知道密文的c1部分，和对应的明文m1，那么她就可以轻松找到密钥流的对应部分k1 = c1⊕m1。 从而给定密钥流的一部分,不应该知道有关其余密钥流的任何信息（不可预测性）

密钥流生成器Keystream generator 是流密码的关键安全组件

将生成器视为一个有限状态机 Finite state machine：

• 状态：存储的内部值
• 状态更新函数：在每个时间间隔更改存储的内部值
• 输出函数：密钥流输出是现在存储值的函数值

设计限制

• 效率
  • 输出密钥流的速度
  • 对于实时应用，必须不对数据传输和恢复产生延迟
• 实施要求
  • Footprint(硬件/软件)
  • 内存 Memory
  • 功率 Power
• 保持同步 Maintaining synchronization
  • 高效的处理失去同步的问题

带有1个输入的密钥流生成器

• 初始流密码的设计包括了只有1个输入(key)的密钥流生成器
• 优点
  • 密文和明文长度相同
• 缺点
  • 密钥和密钥流之间一一对应
  • 不能使用相同的密钥来加密不同的密文

带有2个输入的密钥流生成器

• 现代流密码设计包括了具有2个输入(key, initialisation vector)的密钥流生成器
• 优点
  • 可以搭配不同的初始化向量(IV)重复使用一个密钥
• 缺点
  • 需要跟密文一起传输这个初始化向量IV -> 常量开销

基于帧的加密

• 将每个通信视为一系列帧或数据包，并且使用由相同密钥构成的密钥流依次进行加密，但是有不同的帧号。
• 失去同步只会导致在该数据包中剩余的数据丢失，但下一帧将重新获得同步
• A5/1 算法应用了此加密方式用于GSM电话通讯
  • 每一个交流使用一个64 bits的密钥加密
  • 把这个交流分割为228 bits长度的帧
  • 使用22 bit 的帧编号去生成228位的密钥流
  • 在4.6毫秒内完成加密

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

• LFSR是流密码设计中的常见组件。
• LFSR简单，快速地在硬件和软件中实现，并具有良好的伪随机性。
• 任何无限周期序列递归关系定义

• The vector (s0; s1; : : : ; sn−1) is called the initial state vector 初始状态向量
• 初始状态向量与上面的关系可以定义序列的所有项。
• 幻灯片P26-30包括了一个例子
• LFSR的属性-有三个属性来测量密钥流生成器的强度，序列应该有
  • 尽可能大的周期 Large Period
  • 尽可能大的线性复杂度 Large Linear complexity
  • 随机噪音般的特征 random noise-like characteristics
• LFSR的周期
  • 确定性伪随机二进制数生成器会产生一个周期性序列，这意味着它会在一段时间后重复。

• 举例：011101110111011101110111…的周期为4

• 针对于小周期的攻击 Attack on small period
  • 对于良好的流密码，我们期望密钥流的长度大于明文的长度。
  • 如果密钥流的周期小于明文的长度，那么将有2部分信息使用密钥流的相同部分加密
  • 通过对这两个部分进行异或XOR运算，密钥流将抵消，就可以获取明文字符串的XOR结果。
  • 然后可以通过利用明文的冗余来攻击。
• 我们不想直接使用LFSR的输出来形成密钥流。所以我们有以下两种基本方法
  • 可以对序列的多个输出进行采样并通过非线性滤波器。
  • Multiple outputs from the sequence can be sampled and passed through a non-linear filter.
  • 多个LFSR的输出可以通过一个非线性组合器。
  • The outputs from multiple LFSRs can be passed through a non-linear combiner.
    • 应用：A5 cipher

A5 Cipher

• A5密码是二进制同步流密码，今天在大多数GSM移动电话中应用。
• A5有三个变体：
  • A5 / 1是1987年定义的原始算法
  • A5 / 2是A5 / 1的弱化版本，最初旨在在欧洲以外部署，但在GSM标准下不再允许
  • A5 / 3是用于第三代移动系统(3G)的最新算法
• 设计师最初对A5 / 1的设计保密，但在1994年公开
• A5 / 1算法使用了3个LFSR，并组合他们的输出。
• 这三个LSFR的时钟是不规则的(irregularly clocked)，这意味着总输出不是线性的
• 每个LFSR都有一个时钟位（下图中的橙色）。 如果每个LFSR的自己的时钟位与其他LFSR的时钟位多数一致，则对每个LFSR进行时钟控制（更新）。
• 密钥长度为64位，用于定义每个LFSR的状态向量。 在部署中，据说密钥的10位是固定的。 (请注意，每个LFSR必须具有非零的初始状态。)

• A5 / 1密码分析
  • 1997年，Golic发表了首次A5 / 1密码分析，所需时间（）比暴力搜索（）少得多
  • 已经发布了一些改进，但是都需要一些已知明文。 其中最好的方法是需要“不到一分钟”的已知语音。
  • 2003年，Barkan，Biham和Keller基于GSM中的实现细节破解了了A5 / 1。
  • 在2011年，具有快速GPU和TB级闪存的普通PC可以在几秒钟内破解A5 / 1加密的GSM会话，概率超过90％
• 用于现代GSM和GPRS通信的A5 / 3（KASUMI）目前基本安全（尽管理论上的弱点是已知的）。

RC4 Stream Cipher

• 由Ron Rivest 发明于1987年
  • 直到最近，被广泛用于商业产品，包括Adobe Acrobat，Windows密码加密，Oracle安全SQL，SSL / TLS等
  • 优点：非常简单； 极快 可变密钥长度，没有发现灾难性的弱点。
  • 缺点：设计标准是专有的；直到2001年为止没有太多的公众审查
  • RC4有两个组成部分：一个密钥调度算法和一个密钥流生成器。

无线安全 Wireless Security

• 无线网络已经变得普遍。
• 无线网络的流行标准：
  • IEEE 802.11（范围更大，速度更高，通常用于无线局域网）。
  • 蓝牙（短距离，低速）。
• 新的安全问题：
  • 更多攻击机会（无需物理访问）。
  • 可远程攻击（在高性能天线下可超过1公里）。
  • 无法取得攻击的物理证据。