混沌置换网络的设计及其硬件实现

    摘要：利用Logistic映射迭代产生的混沌序列作为二维置换网络的置换地址，构造二维置换网络对明文进行置换加密。同时提出了一种Logistic混沌映射的整数实现方法，给出了它的FPGA实现。并通过硬件装置实现了Logistic映射的混沌二维置乱网络。

    关键词：Logistic映射 混沌序列 置换网络

在密码学研究中，置换网络起着中心作用，明文字母之间的双射变换可以由一个输入和输出字母相同的置换网络实现。一个置换网络可看作是有n个多输入和n个多输出变量的黑盒子，其每个输出变量都是n个输入的布尔函数，它的好坏直接影响到分组密码的抗破译性。置换网络的研究涉及电话交换、开关理论和密码学多个领域[1]。密码学中，使用置换来进行数据变换，主要有两种作用，其一是对数据内容作不可预测的替换，其二是改变数据在数据序列中的位置，即随机换位。对于第二种置换网络也称为置乱网络，本文主要研究一种二维混沌置乱方法来对数据进行换位加密。

混沌现象是非线性动力系统中一种确定性的类随机过程，混沌信号具有初始值的高度敏感性、不可预测性，并具有遍历性[2,3]等特点。因此，特别适合于混沌保密通信。本文将Logistic映射生成的混沌序列引入置换网络，它可以作为理想的置换网络地址产生器[4]。

FGPA（现场可编程门阵列）是由掩膜可编程门阵列PLD演变而来的，并将二者的特性结合在一起，使FPGA既有掩膜可编程门阵列的高逻辑密度和通用性，又有PLD的可编程性。FPGA技术的发展使得单个芯片上集成的逻辑门数越来越多，其实现的功能越来越复杂。它以编程方便、集成度高、速度快等特点受到设计人员的青睐。人们可以通过硬件编程的方法设计和开发ASIC（专用集成电路）芯片，极大地提高了芯片的研制效率、降低了开发费用。本文用它来作为混沌序列发生器，产生置换网络的置换地址。

1 Logistic映射及其FPGA实现

Logistic映射由下式定义：

x(n+1)=μxn(1-xn) 0<μ≤4 0

x(n+1)=4xn(1-xn) 0

Logistic映射的输入和输出都分布在（0，1）上，可以用概率统计方法定量分析其序列的特性，Schuster H.G证明了[5]式（2）产生的混沌序列{xk:k=0,1,2…}的概率分布密度函数ρ(x)如下式所示：

    从式（3）可以看出，Logistic映射生成的混沌序列具有遍历性，同时它还具有δ-like型自相关函数和零的互相关函数[6]，因而可以作为良好的置换网络地址产生器。

对于式（2）所表示的Logistic混沌映射，如果用浮点运算，计算的精度与产生混沌序列的周期长度有以下近似关系：

L（N）=2（log2N+2）    （4）

从式（4）可以看出如果运算精度比较小，运算结果将很快脱离混沌态，但运算精度过大又会造成运算时间过长、使用资源较多，不利于硬件电路的实现。这里提出一种Logistic混沌映射的整数实现方法，在降低运算精度的情况下，可以使混沌序列仍保持混沌态。下面在给出Logistic混沌映射整数实现方法的基础上，给出了它的FPGA实现方法。

Logistic映射的输入和输出都分布在区间（0，1）上，把区间上的小数x写成精度L的二进制小数形式：

    式（5）中是一个L为二进制表示的整数，它与L位二进制小数x一一对应。

把xk+1和xk写成式（5）的形式，将它代入式（2）中，得到：

Xk+1=4Xk(2L-Xk)/2 L    (6)

X0=[2Lx0]

对于式（6）确定的混沌系统经计算机模拟试验表明，当L=32时，计算得到的序列未脱离混沌态，因此只要实现32位乘32位的整数计算就能得到混沌序列。（6）式对于硬件的实现是很有利的，2 L-Xk是Xk的补，乘4和除2L分别利用寄存器左移和右移就可以实现，所以关键是实现32位乘以32位的整数计算。

令Xk=a0a1…aL-1的Xk的补，其中ai=0或1，则

    式中ai·Xk映射的FPGA实现原理框图[7]如图1所示，其工作过程是：首先将上一次迭代结果Xk放入L比特寄存器，如果位是第一次迭代，则将外部输入的迭代初值X0放入寄存器；然后将其分成两路，一路将Xk存入2L比特寄存器，另一路取反后加1得到Xk的初Xk；对于Xk将其右移一位，并将移出的最低位分别送到2L到2输入与门的其中一个输入端，同时将Xk左移一位后，将2L比特寄存器中的内容送入与门的另2L个输入端，并将结果送到2L位加法器，经过L次后移位、与和加运算后，即得到Xk(2 L-Xk)；对于2L比特移位寄存器中的Xk(2 L-Xk)左移2位后，其中的高L位即为Xk+1，将其输出并重新输入到上面的L比特寄存器Xk，令Xk=Xk+1，重复执行以上过程，即生成所需要的混沌序列。

2 混沌二维置换网络的设计

置换网络的目的是利用若干步骤的变换，打乱原来每个元素的位置，使原来有规则的元素分布在多次变换后显现无规则。接近随机的分布，从而起到信息保密的作用。这里利用两个Logistic映射产生的混沌序列具有对初始值的高度敏感性、不可预测性及其遍历性等特点，来产生置换网络的置换地址。

混沌二维置换网络框图如图2所示，二维m×n置换阵列的存储单元存放m×n个明文数据，混沌序列产生器a和b分别提供二维置换阵列的行地址和列地址，用来选择要输出的数据，如果这一位置的数据已经输出，则混沌序列产生器a和b再进行一次迭代，直到产生未输出数据的地址为止。这里采用Logistic映射来作为混沌序列产生器。图中si是置换前的明文序列，sτ(i)是置换后的序列。这里si和sτ(i)的关系由混沌序列产生器a和b来确定。

    置换网络的硬件实现原理图[8]如图3所示，这里将RAMI和RAM2分别映射成E0000～E1FFFF和E2000～E3FFF的计算机的4K内存，并采用DMA方式对其存取，从而降低了主机的负担，提高了加密的速度。当对一个文件等进行加密时，首先对XC4010进行初始化，并将Logistic映射的迭代初值（密钥）存入XC4010的寄存器中；然后将加密的明文数据文件分成以2K为单位的数据段，通过DMA方式将一个数据段存入RAM1中，这时隔离器2选通，其它隔离器为三态；数据传送完后，用中断方式通知单片机W77e58，单片机按顺序读出RAM1中的数据，并利用XC4010内部两个Logistic混沌映射产生的序列的高5位和高6位作为RAM2（6116）的11位地址，将读出的数据存入RAM2中，如果两个Logistic混沌序列组成的地址与前面的地址一样，则再进行一次迭代；当所有RAM1中的数据存入RAM2中以后，利用中断通知计算机数据置换完成，计算机用DAM方式将RAM2中的数据存储入密文文件中，这样就完成了一个2K数据段的加密。重复上述过程将明文文件的其它数据进行置换加密，从而完成整个文件的置换加密。解密置换过程与加密置换过程类似，只是数据流向相反，即首先将解密数据存入RAM2中，再利用XC4010产生的置换地址读出，并按顺序存入RAM1中，RAM1中的数据是解密置换后的数据。

这里采用具有密集布线资源的Xilinx公司的X4010，来实现图1所示的Logistic映射的迭代运算过程。单片机采用华邦公司的Turbo51系列的W77e58，因为它具有速度高（10M的指令周期）、内置RAM和ROM、丰富的I/O资源等优点。

3 实验及其结果分析

本文用两个Logistic映射产生的混沌序列作为置换网络的置换地址，其实现精度为32位。图4是由图3装置对图像的加密置换和解密置换试验结果。

这里两个Logistic映射的迭代初值分别为x01=0.3和x02=0.4,图4（b）即为图4（a）加密置换后的图像，图4（c）为两个Logistic映射的初值分别取x01=0.3+0.1 -16和x02=0.4+0.1 -16时进行解密置换时得到的图像，图4（d）为两个Logistic映射的初值与加密置换取值和相同的进行解密置换时得到的图像。可以看出，当用来产生加密置换和解密置换的混沌序列初始值相差很小时，也无法置换出正确的图像。如果用穷举搜索法对此加密方法进行破译时，其密钥的搜索量为2 2×32，可以通过多次置换来增加抗破译的强度。

本文利用混沌序列对初始值的高度敏感性、不可预测性及其遍历性等特点来产生置换网络，克服了以往用简单的移位、取模、线性变换等实现置换网络的缺点。通过硬件方式实现了Logistic映射的混沌置乱网络，并提出一种Logistic混沌映射的整数实现方法，给出了它的FPGA实现方法。试验结果表明这种置乱方法具有置换速度快的优点，是一种高抗破译性置换算法。