基于压缩感知贪婪算法的分组密码设计理论的研究
摘要本文通过研究分析压缩感知贪婪算法中的MP和OMP两种重构算法做为密钥加解码的可行性设计，并对该算法应用于分组密码的设计原理进行阐述，并详细阐述了S盒、P置换、轮函数的设计准则及其对于贪婪算法的构造，以及密钥扩展算法的设计等，进而为用户的信息安全提供理论保证。
【关键词】压缩感知 贪婪算法 MP算法 OMP算法 分组密码
1 引言
为了确保用户的信息安全，通过使用高强保护能力的密码技术来保护用户的信息。分组密码有很多优点，比如标准化较为简单，速度快以及容易实现软硬件等，因此，在网络和信息安全中，很容易实现认证，数字签名，密钥管理，数据加密等，在信息安全领域得到推广和使用。
最近三十年内，越来越多的科学家开始关注噪声中获得正弦信号这一方法，而使用信号的压缩性来采样数据信息为一个新兴课题。有些知名学者提出了压缩感知法，提供了采集压缩信号的更普及更适用的一种方法，此方法需要更少的传感器，所采集的数据冗余度也更小。压缩感知的采集方法并非直接采集数据，而是利用一组特定的波形来感知信号，把信号投影至既定波形的上面，于是便可感知到有压缩数据，进而使用最优方法来解密压缩的数据，最后对原始的信息进行估计。
在上述理论的基础上，利用压缩感知算法做为密钥，通过明文进行数据分组压缩，通过密钥——测量矩阵得到密文，达到加密过程了；密文在利用数据重构算法，得到除去了噪声的明文信号，达到解密过程，这样就顺利的完成了整个加解密过程。
2 压缩感知的原理
对于CS理论，其核心思想为：信号在某正交空间只要有稀疏性，就可以较低频率进行信号的采样，且能够以高概率来重构这个信号。方程中，给定y值就能恢复x的值， 其M□N中 。CS理论包含三个重点内容：第一，信号稀疏。对信号X∈RN，怎样找到一个正交基Ψ，让它在Ψ上表示稀疏。第二，信号采样速度低。怎样设计出一个稳定且和变换基Ψ无关的M×N维的矩阵Φ，以保障稀疏向量θ能从N维降至M维的时侯，不破坏重要的信息。第三，信号的重构。怎样设计出快速重构法，以在线性测量 y=ΦΨθ=Θθ之中恢复原始的信号。
假设已知待采集信号X∈RN在某个紧框架或正交基Ψ上可以压缩，那么
（1）
θ为变换基Ψ的逼近或者等价的稀疏表示。根据（2）来设计出一个稳定且和变换基设Ψ无关的M×N维测量矩阵Φ，并测量对θ获得测量的序列 y。
（2）
信号重构一端，采取用0-范数优化进行X值的求解，逼近或者等值于。
（3）
然而，因为0-范数优化问题属于NP问题，它在多项的式时间里很难求解甚至没法验证解是否可靠。Donoho研究发现，θ满足一定的条件后，l1优化算法和l0优化算法解相同，因此一般可转换成l1优化的问题进行求解。
（4）
目前，有三种压缩感知的重构算法：
第一，贪婪追踪法。此类算法在每一次迭代的时候，都选出一个最优的局部解以逼近原始的信号。具体算法有OMP、MP、分段OMP、正则化OMP(ROMP)几种算法。本文采用的便是这种算法来设计密钥的分组的。
第二，凸松弛算法。此类算法时通过把不凸起问题变成凸起问题来解答，以找到原始信号的逼近值，具体算法有内点发，BP算法，迭代阈值和梯度投影的方法等。
第三，组合算法。此算法采集信号的时候，要通过快速重建或者分组测试，比如链式追踪或者傅里叶采样，HHS追踪法等。
3 分组密码设计的原理
寻找一种算法，可在密钥控制之下，从足够大足够好的一个置换子集里，迅速又简单的挑选一个置换，来加密当前的明文输入数据。通常情况下，分组密码设计的原则有实用性和安全性两个原则。实用性原则注意的是分组密码算法效益和速度的提高，有效性原则针对的是怎样设计才能够达到组高的安全性。
分组密码安全性原则主要基于Shannon提出的扩散与混乱两个原则。其中，混乱原则中，设计出来的密码要让密文，明文，密钥间有复杂的依赖关系，从而让分析密码的人没办法利用这种混乱的关系。而对于扩散原则，设计出来的密码要让密钥每位数字都能够对密文或者明文的多位数字有影响，这样能够防止密码分析者利用逐字破译的方式获知密码。
分组密码设计中的非线性变换通常称为S盒，非线性变换可以提供比较好的混乱；分组密码设计中的线性变换一般称作P置换。我们应当注意：S盒不但能够产生混乱，还能扩散。P置换也有相同的作用。
安全性原则中，在注重扩散原则与安全性原则时，还应当注意密码安全。一般我们会认为密码是特别安全的，可以抗拒全部已经知道的攻击，而此原则便是抗现有攻击原则。
在不同的应用环境中，分组密码的实现使用软件和硬件均可。软件实现有很多优点，代价低，较灵活；而硬件实现则能实现的更快速。所以，分组密码有这两种实现原则。
第一，软件实现设计原则。设计密码算法时，要尽量采用简单运输和字块，而字块长度也应够特别自然地应用在软件的编程里，例如，使用8b，16b，32b字来做异域运算，移位运算或者模加运算。第二，硬件实现设计的原则。为了减少开支和硬件逻辑门使用数量，可把算法设计为和加解密类似的，就是说，相同器件能够加密还能够解密，两种算法不同之处在于密钥使用方法不一样。分组密码算法所采用的整体结构大致可分为以下三种：Feistel型、SPN型和Lai-Massey型。三种结构均是通过迭代与密钥相关的非线性变换来实现的。加解密一致是Feistel型密码的一大优点，但轮函数扩散较慢是它的一个缺点。宽轨迹策略是SPN型密码的特点。本文所采用的就是Feistel型算法。
分组密码的工作模式有：密码分组链，电子密码本，输出反馈，密码反馈，计数器模式等。
除了对分组密码算法进行攻击之外，统计检测在其安全性评估的过程中同样发挥着重要的作用。目前关于分组密码的统计检测方法主要是将分组密码作为一个伪随机数发生器进行检测，目前已出现了很多种随机性检测算法，如频数检测、扑克检测、游程检测、自相关检测等。除此之外，还有一些统计检测方法是与分组密码的分组长度、密码结构等有关的，如明文雪崩检测、密钥雪崩检测、明密文独立性检测等。
4 基于MP和OMP两种重构算法分组密码的实现
本文采用压缩感知贪婪算法中的MP和OMP两种重构算法为主要研究对象，应用于分组密码算法的实现。
4.1 匹配追踪（MP）和正交匹配追踪（OMP）算法概述
算法的主要目标是从y=Φx重构最稀疏的 x，其中信号 是在稀疏基Ψ=[Ψ1,Ψ2,...,ΨN]上具有K-稀疏描述的N采样信号（K≤M≤N），即，这两种算法均通过确定Φ的哪一列参于测量向量y中来确定x的支撑，运用贪婪模式去确定每一列。在每次迭代中，选择Φ中与y的剩余部分最相关的列，然后从y中抽取该列对y的贡献再对其冗余迭代。
下面的算法表示中，ri表示第i次迭代中的残差，t表示迭代次数，Λt表示t次迭代的索引集合。
MP重构算法：
（1）初始化：r0=y，t=1
（2）寻找索引Λt，使得：
（3）计算新的近似xt和残差rt：
rt=rt-1-xt
（4）更新迭代次数：
如果 t=K，停止。输出xt
如果t
OMP重构算法：
（1）初始化：
（2）寻找索引λt，使得：
（3）令
（4）计算 张成空间的正交投影Pt
（5）计算新的近似xt和残差rt：
xt=Pty，rt=y−xt
（6）更新迭代次数：
如果t=K，停止。输出xt
如果 t
OMP算法的运行时间是第二步决定，总的耗费是O（KMN），其中测量矩阵Φ为M×N维。
4.2 重构算法分组密码的实现（E扩展函数实现）
对于一个迭代分组密码通常由加密算法、解密算法和密钥扩展算法三个部分组成。解密算法通常是加密算法的逆运算，同理加密算法也是解密算法的逆运算，所以迭代分组密码的设计重点主要放在加密算法和密钥扩展算法上。在本文中，由于采用的是压缩感知中的重构算法，因此将对解密算法和密钥扩展算法（见第8节）进行分析研究。下列表述均是E扩展函数的实现过程。
假设明文为X，种子密钥为Φ（对应于M×N维的测量矩阵Φ），密文为Y。其中明文X具有K稀疏系数。
将密文Y进行64比特分组，其中的任意一部分记为Y[64]，同理32比特分组的任意一部分可记为Y[32]， 比特分组的任意一部分记为Y[i]（对于明文而言，记为X[i]）。
其中 采用压缩成8个并置8进4出的S盒。
MP算法的解密过程为：
（1）初始化：
（2）寻找索引Λt，使得：
（3）计算新的近似和残差：
（4）更新迭代次数：
如果t=K'，停止。输出xt
如果t
同理对于OMP算法的解密过程为：
（1）初始化：
（2）寻找索引λt，使得：
（3）令
（4）计算张成空间的正交投影
（5）计算新的近似和残差 ：
（6）更新迭代次数：
如果t=K'，停止。输出xt
如果t
（8）进行明文x重构，
5 S盒的设计准则及其构造方法
5.1 S盒的设计准则
在Lucifer算法中首次出现S盒，随着DES的使用S盒变得广为流行。在许多密码算法中S盒是唯一的非线性部件。因此，各种分组密码的安全强度，特别是对抗差分密码攻击和线性密码攻击的能力，都与它们所采用的S盒紧密相关。
尽管目前分组密码算法中采用的S盒都是用表格形式给出的，S盒的运算也是通过查表的方式实现的，但在本质上可以将S盒看作从到的多输出函数，即可以表示为形如
的函数，这里 表示n元布尔函数，这样的S盒通常称作n×m的S盒。当选择的参数m和n比较大时，所有的S盒几乎都是非线性的，而且难以发现某些攻击所用的统计特性。同样，过大的m和n将增加算法的存储量，给S盒的设计带来许多困难。设计S盒的准则为：（1）非线性度；（2）差分均匀性；（3）代数次数及项数分布；（4）完全性和雪崩效应；（5）扩散特性；（6）可逆性；（7）没有陷门。
5.2 S盒的构造方法
解密过程中，密文Y进行4比特分组，得到K'个分组，在通过8个并置的8进4出的S盒进行数据处理，其中S盒中进行的是8×4维的测量矩阵，将测量矩阵Φ同样进行分组，可得到 ΦK'个分组，通过P置换运算，可压缩8位分组，进行重组得到具有 K'稀疏性的明文 X。
6 P置换的设计准则及构造方法
P置换一般是在S盒之后，目的是提供良好的雪崩效应和扩散作用，并进一步提高密码算法的混淆程度。如果m个n×n的S盒并置而形成混淆层，那么P置换往往设计成 到的一个线性置换。
本文算法中，将得到的K'个分组，其中64比特按照下列进行换位，P(y)的第1位为y的第16位，P(y)的第2位为y的第15位， P(y)的第3位为y的第14位，其他依次类推，P置换的结果就是核心轮函数F的输出。
7 轮函数的设计准则
轮函数是指迭代分组密码中单轮加密算法的非线性函数，对于本文所采用的Feistel结构的分组密码，S盒与P置换是其最主要的组件，又是还有其他一些非线性变换。轮函数主要考虑的是如何快速实现密钥与明文的混淆与扩散，并使得密文差分分布均匀，轮函数设计主要有安全性、速度、灵活性三个指标要求。
8 密钥扩展算法的设计
密钥扩展算法是迭代分组密码的一个重要组成部分，迭代的各轮算法要使用密钥扩展算法生成的子密钥。可以说，轮函数的功能是在子密钥的参与和控制下实现的。一般来说，子密钥的生成有以下基本原则：
（1）密钥扩展算法至少应该保证密钥和密文符合位独立原则；
（2）获取子密钥比特的关系在计算上是困难的；
（3）没有弱密钥；
（4）结构尽量简单，便于实现；
（5）保证种子密钥的各比特对每个子密钥比特影响的均衡性。
在上述算法中，每一次迭代过程，都要使用一个32比特的子密钥，其密钥是按照测量矩阵 Φ分组分解 ΦK'得到的，其对应于原密钥M×N维的测量矩阵 Φ，依次通过迭代进行生成。这就保证了密钥的安全性，即不能通过得到明文和密文而推导出密钥
9 结束语
本文简要介绍了压缩感知贪婪算法中的MP和OMP算法，并将两种算法用于分组密码的实现。该方法主要依赖于如下事实：与原始数据的有限次随机投影中包含了原始信号的足够信息；给定一定的约束条件，极小化 范数总是导致一个最稀疏的解。该方法目前还处在起步阶段，还有一些问题有待于进一步解决和完善，比如如何实现分组之后的数据混淆性、其算法所消耗的时间复杂度、对于该算法的雪崩测试等。
参考文献
[1]李波,谢杰镇,王博亮.基于压缩传感理论的数据重建[J].计算机技术与发展,2009-5,Vol.19(5):23-29.
[2]李小波,赵瑞珍.基于压缩感知的测量矩阵研究[D].北京交通大学,2010.
[3]冯登国,吴文玲.分组密码的设计与分析[M].清华大学出版社,2009．
作者单位
华东交通大学江西省南昌市330013
