基于并置方法构造的正形置换性质研究

正形置换在密码体制中有重要应用,根据正形置换和正形拉丁方截集的等价关系,研究了基于并置方法构造的正形置换的线性性、不动点、轮换和周期,给出了一些具体的结果。     

一种安全性更高的正形置换发生器

作为一种完全映射,正形置换是对称密码体制中一类重要的基础置换.正形置换已经被证明拥有完全平衡性.自1995年以来,国内外学者对于正形置换的研究主要集中在构造与计数方面,但是对于正形置换的密码学性质,比如差分均匀度和非线性度等则相对关注得较少,而具有良好密码学性质的正形置换可以直接用来设计对称密码算法中的密码学部件.修正了一个关于复合函数密码学性质的结论中关于非线性度所存在的问题;接着分析了一般BDLL正形置换发生器的抗差分分析和抗线性分析的密码学性质;然后基于复合函数提出了一种改进的正形置换发生器,并结合修正后的复合函数结论证明了该正形置换发生器相比于一般BDLL正形置换发生器,能够生成数量更多、拥有更高非线性度和代数次数的非线性正形置换.     

正形置换的一种启发式构造策略

正形置换是对称密码体制中一类重要的基础置换.论文提出了一种利用演化算法来优化正形置换的方案,并基于该方案得到了一些密码学性质优良的正形置换.该方法同时使得正形置换的构造实现了自动化,为构造正形置换提供了一种新方法.     

（4,4）—拉丁阵在密码设计上的一种应用

密钥流由m序列产生的流密码是可破的.【2,3]中提出了拉丁阵概念并给出了(4,4)-拉丁阵的枚举和计数.本文提出m序列冠以(4,4)-拉丁阵对应的置换族密码体制并论证了它的安全性.同时讨论了密钥中(4,4)-拉丁阵的产生方法.将m序列换为其它伪随机序列也是可行的.     

一类具有最大分支数的16阶0-1矩阵构造

具有最大分支数的0—1可逆矩阵被广泛应用于分组密码的扩散结构设计中。为构造16阶该类矩阵,将16阶0—1矩阵划分为以4阶0-1矩阵为单元的4阶块矩阵,根据特征和域上重量均为2的4维0-1向量相加后所得向量的重量分布特点,在行置换同构意义下构造满足某种特殊结构的4阶0．1矩阵单元组,以此为基础,根据Hadamard矩阵的结构特点,利用矩阵的分块构造思想,给出一类分支数达到最大值8的16阶0-1可逆矩阵和对合矩阵构造方法,并在行置换同构意义下给出对合矩阵的计数。     

基于自对偶MDS码的P置换研究

P置换的设计是分组密码设计中的一个重要课题。一直以来，利用编码理论中的MDS码可以设计出许多性质优良的P置换。本文讨论了线性码中的自对偶MDS码，基于这种码，我们可以设计出性质比一般MDS码更好的P线性置换。文中我们给出了一种基于自对偶的广义RS码的线性置换的构造方法。     

基于比特承诺的计算安全量子密码协议

比特承诺是重要的密码学元素，在复杂密码协议设计（如：零知识证明）中扮演着重要角色．Mayers，Lo和Chau分别独立证明了所有无条件安全的量子比特承诺方案都是不安全的，即著名的Mayers-Lo-Chau不可行定理．但这并不排除存在计算安全的量子比特承诺．2000年，Dumais等人给出了一个基于计算假设的量子单向置换可以用于构造计算安全的比特承诺方案．利用纠错码的方法，把量子比特承诺扩展成量子多比特承诺方案，并证明了所给方案的隐蔽性质和约束性质．以比特承诺方案为基础，给出了量子数字签名和量子加密认证方案的设计方法，并给出了协议的安全性证明．     

密码处理ASIP中的置换加速

密码处理ASIP是针对密码算法处理的专用微处理器体系结构,结构设计的重点是怎样良好地匹配算法要素和算法结构.置换是对称密码算法中重要的编码环节,在密码处理ASIP结构下加速置换要尽量减少使用非共用硬件,开发处理并行性,适应各种位宽置换的处理要求.通过对分组算法置换特性的深入分析,在提出的密码处理ASIP结构下,构造了加速置换操作的部件结构和互连结构,设计了专用的指令,给出了性能和实现结果,证明置换加速机制高效、低代价、通用性强.     

有限域F2n上的2类正形置换多项式研究

研究有限域 上的正形置换多项式,针对有限域 上2d-1次和2d次正形置换多项式存在性的问题,利用同余类知识和有限域上乘积多项式的次数分布规律,分析其原因并给出有限域 上2d-1次正形置换多项式不存在和2d次正形置换多项式存在的判定结果。     

代数免疫阶最高的Boole函数的构造和计数

代数免疫阶是针对代数攻击而提出的新的密码准则。为了抵抗代数攻击,流密码中所使用的Boole函数应该具有高代数免疫阶。文中运用替换掉Dalai所构造的代数免疫对称Boole函数支撑集中一些点的方法构造了大量具有最高代数免疫阶的Boole函数,并给出了所构造函数的计数。特别地,对于某些代数次数低于n/2的多项式p(x),构造了代数标准形中单项式系数都不小于n/2的q(x)使得p(x)+q(x)具有最高代数免疫阶。     

正形置换的一种新递归构造方法

提出了复合截集的概念,基于复合截集给出了由n元正形置换构造n+1元正形置换的新的递归构造方法,并解决了相应的计数问题。     

最大值堆的枚举计数公式及其实现

根据堆的定义,在构造与最大值堆对应的n元排列的过程中推导出了n个结点最大值堆的枚举总数目的计算公式,讨论了当堆为满堆时的情况,给出了一个复杂度为O(n)的算法实现了任意最大值堆的枚举计数公式.     

一些非一次相关置换和对合的产生方法

本文讨论非一次相关置换和对合的产生问题.对于置换，首先给出了由给定置换进行仿射变换产生一类相关次数相同置换的方法，然后给出了由低维非一次相关置换递归产生高维非一次相关置换的方法，并估计了这些方法产生的置换个数.对于对合，给出了一个从特定非一次相关对合的不动点上构作不相交p-组产生非一次相关对合的方法，并估计出一个对合个数的松下界.     

Transportation problems on permutations: properties of estimates in the branch and bound method

A combinatorial transportation problem is examined. In contrast to the classical problem, transportations are permutations of the given vector of possible volumes of transportation. A function is shown to be an estimate of the feasible subset in solving this problem by the branch and bound method. The property of the proposed estimate is revealed, which increases the efficiency of the branch and bound method.     

On the combinatorics of suffix arrays

We present a bijective characterization of suffix array permutations obtained from a characterization of Burrows–Wheeler arrays given in [1]. We show that previous characterizations [2], [3], [4], or their analogs, can be obtained in a simple and elegant way using this relationship. To demonstrate the usefulness of our approach, we obtain simpler proofs for some known enumeration results about suffix arrays [3]. Our characterization of suffix arrays is the first based on their relationship with Burrows–Wheeler permutations.     

一种基于复合加密的公钥密码系统

公钥密码系统以其算法设计简单、安全性高已经成为密码学领域的一个非常重要的研究课题。为了更加高效地构造公钥密码系统,文中利用方程Ax By=C的解的不定性,提出了将两个加密算法复合成新加密算法的方法,对此做了分析,并给出了具体例子。实践表明,这种基于复合加密的公钥密码系统,算法的时间复杂度和空间复杂度并未受到影响,但其安全性较早期各同类系统更高、更易被用户采纳。     

A new approximation algorithm for sorting of signed permutations

Sequence comparison leads to a combinatorial optimization problem of sorting permutations by reversals and transpositions.Namely,given any two permutations,find the shortest distance between them.This problem is related with genome rearrangement,genes are oriented in DNA sequences.The transpositions which have been studied in the liteature can be viewed as operations working on two consecutive segments of the genome.In this paper,a new kind of transposition which can work on two arbitrary segments of the genome is proposed,and the sorting of signed permutations by reversals and this new kind of transpostitions are studied.After establishing a lower bound on the number of operations needed,a 2-approximation algorithm is presented for this problem and an example is given to show that the performance ratio of the algorithm cannot be improved.     

布尔置换的构造及其计数

布尔置换在密码体制设计中有很重要的应用。给出了两种构造布尔置换的新方法,解决了这两种方法构造的布尔置换的计数问题。将这两种构造方法与武传坤、邢育森、温巧燕以及Kim等人的构造方法进行了比较,结果表明这两种构造方法实际上推广了这些文献中的结论。