A5/1 流密码的实现

　　Virtex-4 FPGA 利用 1.2v 90nm 三栅极氧化层技术制造而成，与前一代器件相比，其性能和密度均加倍，而功耗却减半。FPGA是可编程门阵列。不同与市场上买到的专用IC,这种芯片允许你自己定制编程，实现你想要的功能，比如通信方面，你可以让他做各种调制，解调算法，FSK,QPSK,QAM等等。现在主要的FPGA Vender有ALTERA,XILINX。

　　本文以实现不同分组密码时所用的代码片段（code snippet） 为侧重点，将向您介绍如何实现 A5/1 流密码。外，为提高安全性，我们还将探讨几个原始 A5/1 算法的新的不同变体。具体来说，我将改变反馈功能的作用方式、重新设计合成器的输出。为此，我需要采用赛灵思 Virtex-4 LX 系列 FPGA 进行硬件实现，采用赛灵思 ISE? 进行综合，以及 Mentor Graphics 的ModelSim 6.0 进行仿真。

　　在具体的实现工作开始之前，让我们首先简要了解一下A5/1 算法。　

　　在GSM 标准中，信息以帧序列的形式通过电波进行传输。帧序列包含数字化的用户语音数据以及用于移动互联网浏览的音/视频数据流。该系统按顺序传输每一个帧，时间间隔为4.6 毫秒。每帧由228 位构成，前114 位称为"上行链路数据",后114 位称为"下行链路数据".

　　我们采用64 位密钥和22 位宽的已知帧编号来初始化A5/1.下一步是将帧的输入位和密钥提供给三个线性反馈移位寄存器（LFSR），大小分别为19位、22位和23 位。在对选定抽头进行异或（XOR） 运算后，即可提供反馈，这有助于提高终输出的随机性。我将三个LFSR 分别命名为R0、R1 和R2,每个LFSR 跟随一个原函数。R0、R1 和R2 分别使用X19+X5+X2+X+1、X22+X+1 和X23+X15+X2+X+1 作为各自的原函数。

　　LFSR 的时钟序列需要采用一种特定的机制，否则会很容易破解LFSR 的输出。因此，时钟采用多数裁定规则（majority rule），使用从R0、R1 和R2 中分别抽取的一个值，然后判定主要的抽头是0 还是1.也就是说，当两个或两个以上的抽头为0 时，则多数情况值为0;反之，则为1.一旦多数情况判定成立，若LFSR 的输入位与多数情况位相匹配，则为LFSR 提供时钟。若输入位与多数情况值不匹配，则不在LFSR 中插入任何输入位，因此也就不会有移位。此外，我们还可通过在原始A5/1 中对R0、R1 和R2 的每个输出位进行异或运算来得到结果。在本例中，我采用一种我们称为"合成器"的更的输出生成函数来替代标准异或函数。

　　A5/1 算法的主要设置例程如下：

　　将R0、R1 和R2 初始化为0;

　　按先后次序在LFSR 中加载会话密钥KC 的值和帧Fn.会话密钥KC 在加载中占用64 个周期，而Fn 则占用另外22 个周期。在每个周期中，输入位都与选择抽头产生的线性反馈值进行异或运算；

　　随后，让LFSR 运行100 个时钟周期，该过程称为混合。此时线性反馈处于工作状态，芯片也被启用，从而使移位/非移位也处于工作状态；

　　混合步骤完成后，接下来的228 个周期用于生成终的输出密钥流。上行链路流与下行链路流（各包含114 位）用于加密和解密运算。与上文所述的传统A5/1 算法相比，本步骤采用非线性反馈以及改进的合成器。

　　对每一个新的帧Fn,可以重复上述步骤。帧号会不断更新，但会话密钥保持不变，直至协议将其激活。

硬件实现

　　我在赛灵思Virtex-4 系列FPGA 上完成了所提出的算法的硬件实现。由于我们设计实现为了逻辑更紧凑，所以我选择了Virtex-4 系列中型的器件，即XC4VLX15.图1 显示了该顶层模块的总体架构情况。

图1 －顶层模块架构图

     顶层包含两个构建模块与胶合逻辑。我设计胶合逻辑是为了实现芯片连接、启动逻辑以及数据加载等功能。还有另外两个构建模块，多数/抽头规则与LFSR 组，每个都有其自身独特的功能。

     多数/抽头规则模块可从LFSR 组接收选择的抽头位置，并独立执行两项单独的功能。由于多数或抽头规则的选择标准依据的是R0、R1 和R2 的一个抽头，因而多数规则和抽头规则的逻辑是并行实现的。此外，在实现多数规则方面，我还进行了另一项优化。选择多数情况的伪算法具体如下：

      同样，我们发现maj2 的值建立在抽头编号7、5、8 的基础之上。根据这些多数函数，我们定义R0 的芯片使能端为：

     我以简单的与/或门形式为来实现用于选择maj1 和maj2 的伪代码。同样，将芯片使能端的伪代码映射到简单的XNOR 函数上，从而既可合并所有逻辑，也能缩小面积。

     该方法使用选择语句(case statement) 实现抽头规则算法。原始的A5/1 算法仅依据多数规则来决定LFSR 的移位运算或芯片使能端。由于我引入了改进的多数规则和额外的抽头规则来进行LFSR 移位，因而还需要另一种机制。因此，我依据PoliSel 信号来进行R0、R1 和R2 芯片使能端的终选择，让PoliSel 信号来决定是否输出由多数规则或抽头规则建立的芯片使能端信号。PoliSel 信号符合该等式：PoliSel = R0[18] XOR R1[21] XOR R2[22]。

LFSR 组

      LFSR 组模块集成了多种函数与实现方法。该模块可利用可变参数例化LFSR，以建立R0、R1 和R2 LFSR。这些LFSR 的宽度分别为19、22 和23。该模块还可例化在A5/1 基础上改进的线性反馈函数。此外，该LFSR 组还能够实现我们新开发的非线性反馈逻辑，而且我还在该模块中实现了用于产生终输出的合成器。图2 显示了LFSR 组的结构图。在此，LFSR 是串行输入、并行输出的移位寄存器。赛灵思Virtex-4 器件可方便地将此类移位寄存器映射到硬件上。使用如下所示的LFSR 标准模板，我们还能推导出一般性的串行寄存器。

      通过使用参数，可在更高的层面上轻松例化LFSR。使用Verilog 的“defparam”特性可进行参数的传输，从而在顶层推导出所需的19 位、22 位和23 位宽的LFSR。采用下列代码行即可便捷完成推导工作：

图2 －LFSR 组模块中R0、R1 和R2 输入与输出的逻辑块

 

图3 －非线性反馈控制器与输入选择值

 

（后者控制着实例lsr. 中的参数宽度）

从以下代码段可以看出，LFSR 的输入加载路径可用简单的异或运算来准确定义。

     异步门的存在增加了关键路径的长度。但是，这里还是没有超出容限范围，因为本例中的关键路径仅由三个异或门与一个多路复用器构成。

     加载完毕之后，反馈路径可在线性或非线性反馈之间进行选择，具体的选择取决于非线性反馈控制器。选择非线性反馈会立即更改设计规范和参数。例如，非线性反馈函数每11 个时钟周期激活，并在10 个时钟周期内保持激活状态。为了缩小实现面积，我们采用了计数器而非加法器来强制执行非线性反馈函数的周期性行为。实现时需要为R0、R1 和R2 分别配备计数器，以便计算抽头为1 的次数。本实现的伪算法如下：

　　探测ldlfsr 信号的下降沿；

　　计数100 个周期；

　　100 个周期后，每10 个周期激活流中断器（stream breaker），然后休眠10 个周期，依此类推直至114 个时钟周期结束。

流中断器的伪代码：

　　汇总lfsr 19、22、23 的内容

　　若count19 > 10、count22 > 11 或count23 > 11

　　则将1 传输至LFSR

　　否则

　　将0 传输至LFSR

    由于需要在每个时钟周期中决定是否在R0、R1 和R2 的输入中插入1 或0，因而一旦激活非线性反馈，计数器与加法器的数量就会显著增加占用面积与关键路径长度。

    将芯片使能端与输入相结合，可使非线性反馈路径根据流中断器的算法来呈现为1 或0。图3 是实现该方案的硬件构建模块。

    使用带设定阈值的加法器可协助非线性反馈控制器的实现。注意，切勿使加法器在降至0 以后继续减少，或在R0、R1 和R2 达到相应值（即19、22 和23）后继续增加。下列代码段为实现该计数器提供了一个范例：

     此外，该代码还说明，增加和减少不仅取决于芯片使能端信号，而且还取决于时钟的每个上升沿在LFSR 输入侧的值。

     对于未来的移动通信标准而言，实现紧密而安全的加密算法至关重要。对于此类应用所需的并行性、高速度以及高带宽，赛灵思Virtex-4 器件可谓理想的解决方案。该平台具备工作电压低、功耗超低等特性，能够轻松适应新兴的安全移动应用。采用本文所述的小窍门与代码段，您可轻而易举地将A5/1 及其将来的变体映射到赛灵思FPGA 上。