模2n加的异或差分概率的快速计算方法

分析模2n加变换的异或差分概率计算算法的计算复杂性,利用以空间换时间的思想,将该算法中的矩阵乘积运算预先计算并予以存储,从而以查表运算替代多个矩阵乘积运算等方法对模2n加变换的异或差分概率计算算法进行改进,改进后算法的计算复杂性小于现有方法计算复杂性的7.7%。     

异或加整体逼近模2n加差值函数的和概率分布

为求解密码算法中异或加整体逼近模2n加运算所得差值函数之和的概率分布问题,利用概率分布的定义,通过直接统计满足条件变量的计数,给出2个差值函数之和的概率分布,并进一步提出2个差值函数之和的概率平方和计算公式,将其计算复杂度由O(24n)降为O(1).     

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

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

MIX函数的模加差分概率分析

S函数由Nicky Mouha提出,是只需输入字的第i个bit和第i个运算状态S[i]即可计算出输出字的第i个bit的一类函数,利用其可以有效研究模加、异或运算的性质。为研究Skein算法的核心部件MIX函数的模加差分性质,将MIX函数转化为S函数的形式,给出了一种精确计算MIX函数模加差分概率的方法,通过理论分析,说明相对于通过求各运算部件概率之积以获得整体函数的概率的一般方法,利用S函数的方法得到的结果更为精确。     

高效缩1码模2n+1加法器设计与优化

针对目前存在的缩1码模2~n+1加法器的优缺点,设计出一个有效的基于进位选择的缩1码模2~n+1加法器。在模加法器的进位计算中,采用进位选择计算代替传统的进位计算,进位计算前缀运算量明显减少。分析和实验结果表明,对于比较大的n值,进位选择缩1码模2~n+1加法器在保持较高运算速度的前提下,有效地提高了集成度。     

改进的广义Feistel结构轻量级分组密码算法

随着复杂环境信息物理系统的更加开放,数据的安全传输问题备受关注.轻量级分组密码算法是保证信息物理系统数据安全传输的重要方法之一,但其仍存在软件实现速率低、硬件实现复杂和灵活性缺乏等问题.针对上述问题,提出了一种基于四分支的广义Feistel结构的高性能轻量级分组密码算法.相较于传统的广义Feistel结构算法,该算法进行了以下优化:1)采用由模加、循环位移和异或3种操作组合成的ARX （modular addition, rotation and XOR）结构替换传统广义Feistel结构中的S盒（非线性替换层）和P盒（线性置换层）,简化了算法的轮函数结构; 2)增加非对称双子密钥以处理每轮加密的明文中间状态,使得中间状态不存在未处理的分支,提高了算法的安全性; 3)设计了可扩展的轮常数加模块,提高了算法的灵活性; 4)分支中增加混淆扩散结构f_x,加快了算法的混淆和扩散速度;5)灵活设计了6个版本的轻量级分组密码算法,以适应不同位数的CPU平台.实验和分析表明,该算法实现效率高,具有良好的混淆和扩散能力,以及较高的安全性.     

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

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

密码算法中的循环移位“异或”运算实质性研究

针对移位和"异或"运算的复合运算进行了研究,指出了m位二进制数的循环移位"异或"变换和移位"异或"变换等同于GF(2)上的多项式乘法问题,并给出了这种变换的可逆性判断的充分必要条件。     

ARX函数的两轮迭代线性化条件研究

含模加运算、循环移位运算和异或加运算的密码算法称为ARX型算法,3种运算的混合使用可以达到更好的扩散和混乱效果。为此,给出二元ARX函数的定义,研究其两轮迭代同时线性化的条件,利用统计分析方法得到线性化条件成立的元素个数的计算公式。分析两轮独立条件下得到的线性化条件成立的概率,发现利用统计分析的方法能够更准确地刻画线性化条件成立概率的影响因素,并且增加一个左右块变换不会对两轮ARX函数的线性化条件产生影响。     

可编程可伸缩的双域模乘加器研究与设计

模乘和模加减作为椭圆曲线公钥体制的核心运算,在ECC算法实现过程中使用频率极高。如何高效率、低成本地实现模乘模加减是当前的一个研究热点。针对FIOS类型Montgomery模乘算法和模加减算法展开研究,结合可重构设计技术,并对算法进行流水线切割,设计实现了一种能够同时支持GF(p)和GF(2n)两种有限域运算、长度可伸缩的模乘加器。最后对设计的模乘加器用Verilog HDL进行描述,采用综合工具在CMOS 0.18μm typical工艺库下综合。实验结果表明,该模乘加器的最大时钟频率为230 MHz,不仅在运算速度和电路面积上具有一定优势,而且可以灵活地实现运算长度伸缩。     

New Minimum Distance Bounds for Linear Codes over Small Fields

Let [n, k, d] _q -codes be linear codes of length n, dimension k, and minimum Hamming distance d over GF(q). In this paper we consider codes over GF(3), GF(5), GF(7), and GF(8). Over GF(3), three new linear codes are constructed. Over GF(5), eight new linear codes are constructed and the nonexistence of six codes is proved. Over GF(7), the existence of 33 new codes is proved. Over GF(8), the existence of ten new codes and the nonexistence of six codes is proved. All of these results improve the corresponding lower and upper bounds in Brouwer's table [www.win.tue.nl/aeb/voorlincod.html].     

Improved lower bound on the number of balanced symmetric functions over GF(p)

The lower bound on the number of n-variable balanced symmetric functions over finite fields GF(p) presented by Cusick et al. in [T.W. Cusick, Y. Li, P. Staˇnicaˇ, Balanced symmetric functions over GF(p), IEEE Trans. Inform. Theory 54 (3) (2008) 1304-1307] is improved in this paper. An equivalent characterization is also presented for the general case.     

On Cryptographic Propagation Criteria for Boolean Functions

We determine the functions on GF(2)ⁿ which satisfy the propagation criterion of degree n−2, PC(n−2). We study subsequently the propagation criterion of degree ℓ and order k and its extended version EPC. We determine those Boolean functions on GF(2)ⁿ which satisfy PC(ℓ) of order kn−ℓ−2. We show that none of them satisfies EPC(ℓ) of the same order. We finally give a general construction of nonquadratic functions satisfying EPC(ℓ) of order k. This construction uses the existence of nonlinear, systematic codes with good minimum distances and dual distances (e.g., Kerdock codes and Preparata codes).     

Linear structures of symmetric functions over finite fields

It is shown that nonlinear symmetric functions over finite fields GF(p) have no linear structures other than equal component vectors.     

Performance evaluation of highly efficient techniques for software implementation of LFSR

Linear feedback shift registers (LFSR) are widely used in many different areas. In this paper, we study the operation of LFSR defined over extension fields GF(2ⁿ), instead of traditional binary fields, quantifying and comparing the theoretical with the real performance improvement. We also examine other techniques for efficient implementation, analyzing the effectiveness of both approaches. The experiments show that speedups up to 10.15 can be easily achieved. Surprisingly, data also show that the use of extension fields greater than GF(2¹⁶) is not always worth, due to the increasing internal operation costs. The benefits are clear for all possible applications of LFSR, and specifically for cryptographic purposes.     

P盒为n-MDS矩阵的SPS模型差分概率的新上界

研究了SPS模型中的扩散变换为二元域上n-MDS矩阵对应的仿射变换构造时,差分概率的估计问题.首先给出任意给定一个差分对时,差分概率上界的估算公式,然后给出该类SPS模型差分概率的一个新上界.模拟实验结果表明,该上界比目前最好的上界更紧致.     

Results on rotation symmetric polynomials over GF(p)

In this paper, we generalize the recent counting results about rotation symmetric Boolean functions to the rotation symmetric polynomials over finite fields GF(p). By using Möbius function, we obtain some formulas for more general n, the number of variables. Some known formula in Boolean case are simplified.     

A versatile Montgomery multiplier architecture with characteristic three support

We present a novel unified core design which is extended to realize Montgomery multiplication in the fields GF(2ⁿ), GF(3^m), and GF(p). Our unified design supports RSA and elliptic curve schemes, as well as the identity-based encryption which requires a pairing computation on an elliptic curve. The architecture is pipelined and is highly scalable. The unified core utilizes the redundant signed digit representation to reduce the critical path delay. While the carry-save representation used in classical unified architectures is only good for addition and multiplication operations, the redundant signed digit representation also facilitates efficient computation of comparison and subtraction operations besides addition and multiplication. Thus, there is no need for a transformation between the redundant and the non-redundant representations of field elements, which would be required in the classical unified architectures to realize the subtraction and comparison operations. We also quantify the benefits of the unified architectures in terms of area and critical path delay. We provide detailed implementation results. The metric shows that the new unified architecture provides an improvement over a hypothetical non-unified architecture of at least 24.88%, while the improvement over a classical unified architecture is at least 32.07%.     

The (Non)Enumerability of the Determinant and the Rank

We investigate the complexity of enumerative approximation of two fundamental problems in linear algebra, computing the rank and the determinant of a matrix. We show that both are as hard to approximate (in the enumerative sense) as to compute exactly. In particular, if there exists an enumerator that, given a matrix over some finite field, outputs a list of constantly many numbers, one of which is guaranteed to be the rank of the matrix, then it can be determined in AC ⁰ (with oracle access to the enumerator) which of these numbers is the rank. Thus, for example, if the enumerator is an FL function, then the problem of computing the rank is in FL. For the determinant function we establish the following two results: (1) If the determinant is poly-enumerable in logspace, then it can be computed exactly in FL. (2) For any prime p , if computing the determinant modulo p is (p-1) -enumerable in FL (i.e., if one could eliminate a single possible value for the determinant modulo p ), then the determinant modulo p can be computed in FL. Because there is a close connection between these two functions and logspace counting classes, we hope that our results can give a better understanding of the power of counting in logspace, and the relationships among the complexity classes sandwiched between NL and uniform TC ¹ .