GF(2^m)时空权衡乘法器算法研究

The finite fields GF(2^m) are frequently required in computer communication, information security, etc. The multiplier is one of the most important computation module in Elliptic Curve Cryptosystem over GF(2^m). In this project, we focus on the space and time complexity trade-off multiplier and its optimization to meet performance requirements under various constraints, such as limited cost, low power and narrow bandwidth. There are three main respects in this project, including: (1) Research on the Divide and Conquer (D&C) algorithm for efficient GF(2^m) multiplication. Various D&C algorithms will be designed to reduce both the space and time complexity of the field multiplication. (2) Research on the application of D&C algorithms to build efficient space and time trade-off multiplier. We consider bridging the gap between the mathematical algorithms and their hardware implementations. (3) Research on the design theory of this type of multipliers. The multiplier efficiency is evaluated under different D&C algorithms, irreducible polynomials and field element representation and then explicit formulae in terms of space and time complexities is given. The best choice the multiplier parameters is also investigated. The result of this project will further enhance the international status of China in the field of cryptographic chip design.

有限域GF(2^m)在计算机通信、信息安全等领域中有着广泛的应用。乘法器是GF(2^m)椭圆曲线密码芯片的核心运算模块。本项目在低成本、低功耗和窄带宽等资源受限条件下，研究权衡时间与空间复杂度的GF(2^m)乘法器算法，并着重考虑算法的最优化问题。具体包括：(1) 研究高效实现GF(2^m)乘法的分治算法，减少乘法运算的时间与空间复杂度；(2) 研究基于分治算法的时空权衡乘法器方案，解决理论算法到芯片设计的关键问题；(3) 研究不同的分治算法、域多项式以及域元素形式等因素对乘法器性能的影响，确立乘法器的时间与空间复杂度等性能指标与上述因素之间的数学关系，得出最优性能的乘法器设计参数，并形成设计理论。本项目的研究成果将进一步提升我国在密码芯片设计领域的国际地位。

课题拟以设计资源受限的条件下权衡时间与空间复杂度的高效GF(2^m)乘法器为目标，深入研究了适应于多项式模乘的分治算法、基于分治算法的时-空权衡乘法器，大幅度提升我们在该方面的研究水平。经过三年的努力，课题组先后研究了适用于GF(2^m)乘法高效实现的分治算法；研究基于分治算法的时空权衡乘法器方案以及时-空权衡乘法器的设计理论总结与归纳，并着重考虑算法的最优化问题。项目亮点如下：1、课题组在中国计算机学会推荐A类期刊IEEE Transactions on Computers发表论文, 该论文获得了期刊编辑Jean-Michel Muller的大力推荐。2、课题组在Integration, the VLSI journal, VLSI Design等期刊发表了高质量的论文。目前在投的2篇文章其结果与当前国内外相关方向上的最好结果相当。