ZUC算法的线路优化实现  

Optimization of Circuit Implementation for ZUC Algorithm

作　　者：邹剑 黄倩[1,2] 魏子豪 李立基 吴文玲[4] ZOU Jian;HUANG Qian;WEI Zi-Hao;LI Li-Ji;WU Wen-Ling(College of Computer and Data Science,Fuzhou University,Fuzhou 350108,China;Key Lab of Information Security of Network Systems,Fuzhou University,Fuzhou 350108,China;Data Communication Science and Technology Research Institute,Beijing 100191,China;Trusted Computing and Information Assurance Laboratory,Institute of Software,Chinese Academy of Sciences,Beijing 100190,China)

机构地区：[1]福州大学计算机与大数据学院,福州350108 [2]福州大学网络系统信息安全重点实验室,福州350108 [3]数据通信科学技术研究所,北京100191 [4]中国科学院软件研究所可信计算与信息保障实验室,北京100191

出　　处：《密码学报（中英文）》2024年第5期1108-1125,共18页Journal of Cryptologic Research

基　　金：国家自然科学基金(61902073,62072445);福建省自然科学基金(2021J01623)。

摘　　要：当前还未发现ZUC算法S盒的高效线路实现方案,一般以查找表的方式进行实现.该操作将消耗大量的硬件资源,非常不适用于在受限环境下使用ZUC算法.针对上述不足,本文首次给出ZUC算法S盒的完整线路实现以及线性变换的in-place实现,可以有效地降低ZUC算法线路实现的资源开销.ZUC算法中的S盒由4个大小为8×8的S盒组合而成,即S=(S_(0),S_(1),S_(2),S_(3)),其中S_(0)=S_(2),S_(1)=S_(3).首先,使用穷举剪枝的搜索策略以及基于SAT的S盒优化技术给出S_(0)中3个P变换的高效线路实现,进而首次得到S_(0)的紧凑线路实现.其次,根据S_(1)的代数表达式,通过应用几种最先进的组合逻辑最小化技术,对正规基下F28域上求逆运算的720种塔域表示进行全面的研究,得到S_(1)的紧凑线路实现.相较于以往基于复合域的实现方法,节省了25.48%的硬件开销.最后,将ZUC算法中的线性变换转换成矩阵形式,并使用优化线性矩阵的启发式算法得到其in-place实现,减少了34.77%的XOR门数,且不需要使用额外的辅助比特.本文研究将会对传统环境下以及量子环境下ZUC算法的线路实现产生积极的影响.Currently,no efficient implementation scheme for the ZUC algorithm S-box has been found.In general,it is implemented through lookup tables,while such operation consumes a large amount of hardware resources and is not suitable for using the ZUC algorithm in limited environments.In response to these shortcomings,the complete circuit implementation of S-box of ZUC algorithm and the in-place implementation of linear transformation are raised in this study,designated to effectively reduce the resource cost of the ZUC algorithm circuit implementation.ZUC’s S-box is composed of four 8×8 S-boxes,i.e.,S=(S_(0),S_(1),S_(2),S_(3)),where S_(0)=S_(2),S_(1)=S_(3).Firstly,this study uses the search strategy of exhaustive pruning and the SAT-based S-box optimization technique to give the efficient implementation of three P transforms in the S_(0),and then obtains an S_(0)compact circuit implementation for the first time.Secondly,according to the algebraic expression of S_(1),by applying several advanced combinatorial logic minimization techniques,720 cases of the tower field representations for inverse of F28 field under normal basis are studied,and the compact circuit implementation of S1 is obtained.Compared to previous implementation methods based on composite field,it saves 25.48%of hardware overhead.Finally,the linear transformation in ZUC algorithm is converted into matrix form,and its in-place implementation is obtained by using the heuristic algorithm of optimizing linear matrix.It reduces XOR gates by 34.77%and does not require the use of additional auxiliary bits.The research is of a positive impact on the circuit implementation of ZUC algorithm in traditional environment and quantum environment.

关 键 词：ZUC S盒 线性变换 线路实现 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]