分组密码二元扩散结构的几点注记

0-1矩阵常用于设计分组密码的扩散结构,首先证明,当GF(2n)上的矩阵重新定义在扩域GF(2mn)上时其分支教保持不变,据此补充了Choy等人关于GF(2n)上二元矩阵分支数上界的证明.构造了一批分支数达到最优的8阶二元可逆矩阵,给出了一类差分分支数和线性分支数相等的二元可逆矩阵,并从中搜索出了大量16阶分支数达到最优的二元矩阵和对合二元矩阵.     

基于Cauchy矩阵的线性变换的研究

P-置换是实现分组密码扩散原则的关键组件.一般来说,分支数越大,扩散效果越明显.人们利用MDS矩阵设计最优线性变换作为分组密码组件的扩散层.在达到最优线性变换的同时,针对扩散矩阵还应满足矩阵中元素尽量少的要求,对Cauchy型MDS矩阵分别与Hadmard矩阵和循环移位矩阵的相互结合方式构造最优线性层的方法进行了研究.对Cauchy-Hadmard矩阵(同时是Cauchy矩阵和Hadmard矩阵)构造线性变换的一种方法进行了分析,给出了算法的C语言的关键程序,根据算法给出了一个最优线性变换的示例;对循环移位矩阵构造Cauchy矩阵进行了尝试和证明.结果显示Cauchy-Hadmard矩阵满足矩阵元素最少和运算复杂度低的要求,利用循环移位矩阵无法构造出Cauchy矩阵.这些结论为设计分组密码组件的扩散层提供了重要的方法参考.     

GF(2k)上的遍历矩阵及其特性分析

对有限域GF(2k)上的"遍历矩阵"进行了探讨.通过本文的分析,可以发现GF(2k)上的遍历矩阵具有很多可应用于密码学的良好特性.为了寻找所需的遍历矩阵,我们引入了GF(2k)中的一个递推公式,并基于此给出了一个寻找算法.通过该算法可以有效地找到GF(2k)上特定数目的n阶遍历矩阵,且每一个n阶遍历矩阵均可用GF(2k)上的一个n维向量来表示,因此可大大节省存储和传输相应矩阵所需的空间及带宽.     

GF(2k)上的遍历矩阵及其特性分析

对有限域GF（2^k）上的“遍历矩阵”进行了探讨.通过本文的分析,可以发现GF（2^k）上的遍历矩阵具有很多可应用于密码学的良好特性.为了寻找所需的遍历矩阵,我们引入了GF（2^k）中的一个递推公式,并基于此给出了一个寻找算法.通过该算法可以有效地找到GF（2^k）上特定数目的n阶遍历矩阵,且每一个n阶遍历矩阵均可用GF（2^k）上的一个n维向量来表示,因此可大大节省存储和传输相应矩阵所需的空间及带宽.     

一种SPN线性层的设计方法

提出了线性码理论用于SPN分组密码线性层（或称扩散层）设计,并给出了过线性码设计最优扩散线性层的方法,从而为密码结构中的线性变换的没计提供了理论基础。利用该方法进行了实例设计与分析,并对其扩散特性进行了仿真。     

几种线性部件的构造

本文研究了线性部件的构造方式,给出了域GF(2)和域GF(28)上分支数达到最优的线性部件。在域GF(2)上,我们给出了分支数为4的所有4×4级矩阵,在域GF(28)上通过线性码、柯西矩阵、Hadamard矩阵三种方式构造了具有最优扩散性的线性部件。     

二元最佳扩散矩阵的一种构造方法

扩散结构的好坏直接影响了分组密码的扩散速度和安全强度,以分支数尽可能大的线性变换为分组密码算法的扩散结构是设计分组密码的一种重要方法,线性变换的构造可通过可逆矩阵的构造完成。针对块数为8的扩散结构进行了研究,给出了分支数达到最大的二元矩阵的构造方法和构造算法。该算法运行速度很快,能够满足实际的应用需要。     

一类SP结构的不可能差分区分器证明

针对分组密码SP结构的不可能差分区分器轮数的下界进行证明,提出的方法使用线性代数的理论,对系数矩阵P及P-1进行分析,提出了系数矩阵部分子空间存在两个行向量线性相关时,可证明至少存在四轮不可能差分区分器。uBlock算法是SPN结构,提出的方法对uBlock算法进行了分析验证,说明了结论的正确性,进一步,使用该算法搜索到比uBlock算法设计文档更多的不可能差分区分器。针对SPN结构线性扩散层P,使用了本原指数的概念,使用线性扩散层P的本原指数对SPN结构不可能差分的轮数进行论证。分析结果表明,分组密码SP结构至少存在四轮不可能差分区分器。     

矩阵乘法的一个最优并行算法

本文给出了向是一机上计算两个n阶矩阵乘法的并行算法。处理机台数P=n;并行步数T＝(n);效率＝0（1）。此算法从阶上已达到并行矩阵乘法的复杂性下界，同时在保证效率为0（1）的前提下，使处理机台数的上界达到最优。     

关于求鳞状循环因子矩阵m次根的一种快速算法

利用快速傅里叶变换给出求鳞状循环因子矩阵m次根一种快速算法,同时证明了n阶鳞状循环因子矩阵的m次根中仍为鳞状循环因子矩阵的个数为m^n。该算法已编成M文件在Matlab 7.0上运行通过,验证了该算法是稳定有效的。     

Optimal linear filter design for systems with correlation in the measurement matrices and noises: recursive algorithm and applications

This paper addresses the optimal least-squares linear estimation problem for a class of discrete-time stochastic systems with random parameter matrices and correlated additive noises. The system presents the following main features: (1) one-step correlated and cross-correlated random parameter matrices in the observation equation are assumed; (2) the process and measurement noises are one-step autocorrelated and two-step cross-correlated. Using an innovation approach and these correlation assumptions, a recursive algorithm with a simple computational procedure is derived for the optimal linear filter. As a significant application of the proposed results, the optimal recursive filtering problem in multi-sensor systems with missing measurements and random delays can be addressed. Numerical simulation examples are used to demonstrate the feasibility of the proposed filtering algorithm, which is also compared with other filters that have been proposed.     

无移位操作的快速comb乘法算法

有限域GF(2n)上乘法运算是影响GF(2n)上椭圆曲线密码实现效率的关键运算之一.基于窗口技术的comb乘法算法,被认为是目前有限域GF(2n)上乘法运算最快的算法之一.但是,它仍然使用了移位操作,而移位操作恰好又是域GF(2n)乘法运算中很耗时的操作.提出并实现了一种新的基于窗口技术的快速comb乘法算法,该算法避免了移位操作,且不增加异或运算次数.理论分析和实验结果表明,新算法有很好的实现效率,适合于有限域GF(2n)上椭圆曲线密码算法的软件实现.     

一种双域Montgomery求逆算法与硬件实现

有限域上的求逆运算是椭圆曲线密码算法的关键运算之一。分别对GF（p）和GF（2ⁿ）域上的Montgomery模逆算法进行分析,并将GF（2ⁿ）域上的Montgomery模逆算法中对变量阶数的比较进行了改进,这样不仅利于GF（p）和GF（2ⁿ）域上的模逆运算在统一的硬件结构上实现,也解决了数据位数较大时进行阶数比较延迟较大的问题,在此基础上提出一种基于GF（p）和GF（2ⁿ）双域上统一的模逆算法,并根据算法,采用双域可伸缩运算单元,实现了一种可扩展的统一Montgomery模逆硬件结构。设计采用Verilog-HDL语言进行硬件描述,并基于0.18 μm工艺标准单元库进行了综合,结果表明该设计与其他设计相比具有灵活性好、性能高的特点。     

Optimal distributed Kalman filtering fusion for a linear dynamic system with cross-correlated noises

In this article, we study the distributed Kalman filtering fusion problem for a linear dynamic system with multiple sensors and cross-correlated noises. For the assumed linear dynamic system, based on the newly constructed measurements whose measurement noises are uncorrelated, we derive a distributed Kalman filtering fusion algorithm without feedback, and prove that it is an optimal distributed Kalman filtering fusion algorithm. Then, for the same linear dynamic system, also based on the newly constructed measurements, a distributed Kalman filtering fusion algorithm with feedback is proposed. A rigorous performance analysis is dedicated to the distributed fusion algorithm with feedback, which shows that the distributed fusion algorithm with feedback is also an optimal distributed Kalman filtering fusion algorithm; the P matrices are still the estimate error covariance matrices for local filters; the feedback does reduce the estimate error covariance of each local filter. Simulation results are provided to demonstrate the validity of the newly proposed fusion algorithms and the performance analysis.     

Almost sure convergence of iterative learning control for stochastic systems

This paper proposes an iterative learning control (ILC) algorithm with the purpose of controling the output of a linear stochastic system presented in state space form to track a desired realizable trajectory. It is proved that the algorithm converges to the optimal one a.s. under the condition that the product input-output coupling matrices are full-column rank in addition to some assumptions on noises. No other knowledge about system matrices and covariance matrices is required.     

分组密码复杂线性层可分性传播的MILP刻画方法

混合整数线性规划(MILP)作为一种自动化搜索工具, 被广泛地应用于搜索分组密码的差分、线性、积分等密码性质. 提出一种基于动态选取策略构建MILP模型的新技术, 该技术在不同的条件下采用不同的约束不等式刻画密码性质的传播. 具体地, 从可分性出发根据输入可分性汉明重量的不同, 分别采用不同的方法构建线性层可分性传播的MILP模型. 最后, 将该技术应用于搜索uBlock和Saturnin算法的积分区分器. 实验结果表明: 对于uBlock128算法, 该技术可以搜索到比之前最优区分器多32个平衡比特的8轮积分区分器. 除此之外, 搜索到uBlock128和uBlock256算法比之前最优区分器更长一轮的9和10轮积分区分器. 对于Saturnin256算法, 同样搜索到比之前最优区分器更长一轮的9轮积分区分器.     

An Optimal Parallel Co-Connectivity Algorithm

In this paper we consider the problem of computing the connected components of the complement of a given graph. We describe a simple sequential algorithm for this problem, which works on the input graph and not on its complement, and which for a graph on n vertices and m edges runs in optimal O(n+m) time. Moreover, unlike previous linear co-connectivity algorithms, this algorithm admits efficient parallelization, leading to an optimal O(log n)-time and O((n+m)log n)-processor algorithm on the EREW PRAM model of computation. It is worth noting that, for the related problem of computing the connected components of a graph, no optimal deterministic parallel algorithm is currently available. The co-connectivity algorithms find applications in a number of problems. In fact, we also include a parallel recognition algorithm for weakly triangulated graphs, which takes advantage of the parallel co-connectivity algorithm and achieves an O(log² n) time complexity using O((n+m²) log n) processors on the EREW PRAM model of computation.     

随机奇异系统分布式最优融合降阶卡尔曼滤波器

Based on the optimal fusion algorithm weighted by matrices in the linear minimum variance (LMV) sense, a distributed full-order optimal fusion Kalman filter (DFFKF) is given for discrete-time stochastic singular systems with multiple sensors, which involves the inverse of a high-dimension matrix to compute matrix weights. To reduce the computational burden, a distributed reduced-order fusion Kalman filter (DRFKF) is presented, which involves in parallel the inverses of two relatively low-dimension matrices to compute matrix weights. A simulation example shows the effectiveness.     

一类本原σ-LFSR 序列的构造与计数

有限域GF(2k)上本原σ-LFSR序列的分量序列均是二元域上具有相同极小多项式的m-序列,已知一条GF(2k)上本原σ-LFSR序列的距离向量,就可以用二元域上的m-序列构造它.研究了一类本原σ-LFSR序列——Z本原σ-LFSR序列距离向量的计算问题.给出了一种GF(2k)上n级Z本原σ-LFSR序列距离向量的计算方法,其主要思想是,利用GF(2k)上1级Z本原σ-LFSR序列的距离向量来计算n级Z本原σ-LFSR序列的距离向量.与其他现有方法相比,该方法的效率更高.更有价值的是,该方法也适用于GF(2k)上n级m-序列距离向量的计算.最后给出了GF(2k)上n级Z本原σ-LFSR序列的计数公式,说明其个数比GF(2k)上n级m-序列更多.