流密码非线性布尔函数可重构运算单元设计方法RA-NLBF

doi:10.11772/j.issn.1001-9081.2022111690

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (11): 3527-3533.DOI: 10.11772/j.issn.1001-9081.2022111690

所属专题：先进计算

流密码非线性布尔函数可重构运算单元设计方法RA-NLBF

张宗仁¹^,², 戴紫彬¹(), 刘燕江¹, 张晓磊¹

^1.解放军信息工程大学，郑州 450001
^2.31642部队，云南临沧 677000

收稿日期:2022-11-15 修回日期:2023-03-07 接受日期:2023-03-20 发布日期:2023-05-12 出版日期:2023-11-10
通讯作者: 戴紫彬
作者简介:张宗仁（1994—），男，湖北襄阳人，硕士研究生，主要研究方向：安全专用芯片设计、可重构计算
戴紫彬（1966—），男，河南西峡人，教授，博士生导师，博士，主要研究方向：信息安全、体系结构 daizb2004@126.com
刘燕江（1990—），男，河南南阳人，博士，主要研究方向：安全专用芯片设计、侧信道攻击
张晓磊（1992—），男，河北青县人，硕士研究生，主要研究方向：安全专用芯片设计。
基金资助:
“核高基”国家科技重大专项(2018ZX01027101?004)

RA-NLBF： design method of reconfigurable operation unit for stream cipher non-linear Boolean function

Zongren ZHANG¹^,², Zibin DAI¹(), Yanjiang LIU¹, Xiaolei ZHANG¹

^1.PLA Information Engineering University，Zhengzhou Henan 450001，China
^2.Unit 31642 of PLA，Lincang Yunnan 677000，China

Received:2022-11-15 Revised:2023-03-07 Accepted:2023-03-20 Online:2023-05-12 Published:2023-11-10
Contact: Zibin DAI
About author:ZHANG Zongren， born in 1994， M. S. candidate. His research interests include special security chip design， reconfigurable computing.
DAI Zibin， born in 1966， Ph. D.， professor. His research interests include information security， architecture.
LIU Yanjiang， born in 1990， Ph. D. His research interests include special security chip design， side-channel attacks.
ZHANG Xiaolei， born in 1992， M. S. candidate. His research interests include special security chip design.
Supported by:
National Science and Technology Major Project(2018ZX01027101-004)

摘要/Abstract

摘要：

分组密码中的S盒（多输出）以及流密码中的反馈函数都需要特殊的布尔函数来保证密码算法的安全性。为解决现有流密码算法中非线性布尔函数（NLBF）可重构硬件运算单元资源占用过大、时钟频率低等问题，提出一种高效的基于与非锥（AIC）的NLBF可重构运算单元设计方法（RA-NLBF）。以密码学理论为基础，在着重分析多种流密码算法的NLBF特性，提取了涵盖与项次数、与项个数、输入端口数等NLBF函数特征的基础上，提出基于“混合极性Reed-Muller（MPRM）”和“传统布尔逻辑（TB）”双逻辑混合形式的NLBF化简方法，NLBF的与项数量减少29%，形成了适用于AIC的NLBF表达式；根据化简后的表达中与项个数、与项次数分布等特征，设计了可重构AIC单元和互联网络，形成可满足现有公开流密码算法中的NLBF运算的可重构单元。基于CMOS 180 nm工艺对提出的RA-NLBF进行逻辑综合验证，结果显示该方法的面积为12 949.67 μm2，时钟频率达到505 MHz，与现有相同功能的单元可重构序列密码逻辑单元（RSCLU）相比，面积减少了59.7%，时钟频率提高了37.3%。

关键词: 流密码, 可重构实现, 非线性布尔函数, 与非锥, 混合极性RM

Abstract:

Both the S-box （multiple outputs） in block ciphers and the feedback function in stream ciphers require special Boolean functions to ensure the security of the cipher algorithm. To solve the problems of excessive resource consumption of reconfigurable hardware operation units and low clock frequency caused by Non-Linear Boolean Function （NLBF） in the existing algorithms of stream cipher， a high-efficiency AIC（And-Inverter Cone）-based design scheme for NLBF reconfigurable operation units was proposed， namely RA-NLBF. Based on the theories of cryptography， after analyzing the NLBF characteristics of various stream cipher algorithms and extracting the function features of NLBF including the times of AND terms， the number of AND terms， and the number of input ports， an NLBF simplification method based on the dual-logic hybrid form of “Mixed Polarity Reed-Muller （MPRM）” and “Traditional Boolean function （TB）” was proposed， which reduced the number of NLBF AND terms by 29% and formed an NLBF expression suitable for the AIC. Based on the simplified expression characteristics， such as the distribution of the number of AND terms and the times of AND terms， reconfigurable AIC units and interconnection networks were designed to form the reconfigurable units that can satisfy the NLBF operation in the existing public stream cipher algorithms. The proposed RA-NLBF was verified by logic synthesis based on CMOS 180 nm technology， and the results show that the area of RA-NLBF is 12 949.67 μm2， and the clock frequency reaches 505 MHz， which is a 59.7% reduction in area and a 37.3% increase in clock frequency compared with Reconfigurable Logic Unit for Sequence Cryptographic （RSCLU）， an existing method with the same function.

Key words: stream cipher, reconfigurable implementation, Non-Linear Boolean Function (NLBF), And-Inverter Cone (AIC), Mixed Polarity Reed-Muller (MPRM)

中图分类号:

TP309.7

张宗仁, 戴紫彬, 刘燕江, 张晓磊. 流密码非线性布尔函数可重构运算单元设计方法RA-NLBF[J]. 计算机应用, 2023, 43(11): 3527-3533.

Zongren ZHANG, Zibin DAI, Yanjiang LIU, Xiaolei ZHANG. RA-NLBF： design method of reconfigurable operation unit for stream cipher non-linear Boolean function[J]. Journal of Computer Applications, 2023, 43(11): 3527-3533.

图/表 12

表1 流密码NLBF与项次数、输入端口频率分布

Tab. 1 Distribution of NLBF AND term times and input port frequency in stream ciphers

与项次数	出现频率/%	输入端口数	出现频率/%
1	30.6	［1，6］	16.3
2	34.2	［7，12］	10.2
3	14.9	［13，18］	44.9
4	16.9	［19，24］	14.3
>4	3.4	>24	14.3

表2 密码算法中的NLBF任意4变量组合形式

Tab. 2 Arbitrary 4-variable combination forms of NLBF in cryptographic algorithms

频率	正则表达式
高频	$x 1 ⊕ x 2 ⊕ x 3 ⊕ x 4$ ， $x 1 x 2 x 3 x 4$ ， $x 1 ⊕ x 2 ⊕ x 3 x 4$ ， $x 1 x 2 ⊕ x 3 x 4$ ， $x 1 ⊕ x 2 x 3 x 4$ ， $x 1 x 2 ⊕ x 2 x 3 x 4$
中频	$x 1 x 2 ⊕ x 1 x 2 x 3 x 4$ ， $x 1 x 2 x 3 ⊕ x 1 x 2 x 3 x 4$ ， $x 1 ⊕ x 1 x 2 x 3 x 4$ ， $x 1 ⊕ x 1 x 2 ⊕ x 3 x 4$ ， $x 1 x 2 ⊕ x 1 x 2 x 3 ⊕ x 1 x 2 x 3 x 4$ ， $x 1 ⊕ x 3 ⊕ x 1 x 2 ⊕ x 3 x 4$ ， $x 1 ⊕ x 1 x 2 ⊕ x 1 x 2 x 3 x 4$ ， $x 1 x 2 ⊕ x 1 x 3 ⊕ x 1 x 4 ⊕ x 2 x 3 ⊕ x 2 x 4 ⊕ x 3 x 4$
低频	$x 1 ⊕ x 1 x 2 ⊕ x 1 x 2 x 3 ⊕ x 1 x 2 x 3 x 4$ ， $x 1 ⊕ x 2 x 3 ⊕ x 1 x 2 x 3 ⊕ x 1 x 2 x 3 x 4$ ， $x 1 ⊕ x 2 x 3 ⊕ x 1 x 2 x 4 ⊕ x 1 x 2 x 3 x 4$ ， $x 1 ⊕ x 2 ⊕ x 1 x 2 ⊕ x 1 x 2 x 3 ⊕ x 1 x 2 x 3 x 4$

表2 密码算法中的NLBF任意4变量组合形式

Tab. 2 Arbitrary 4-variable combination forms of NLBF in cryptographic algorithms

频率	正则表达式
高频	$x 1 ⊕ x 2 ⊕ x 3 ⊕ x 4$ ， $x 1 x 2 x 3 x 4$ ， $x 1 ⊕ x 2 ⊕ x 3 x 4$ ， $x 1 x 2 ⊕ x 3 x 4$ ， $x 1 ⊕ x 2 x 3 x 4$ ， $x 1 x 2 ⊕ x 2 x 3 x 4$
中频	$x 1 x 2 ⊕ x 1 x 2 x 3 x 4$ ， $x 1 x 2 x 3 ⊕ x 1 x 2 x 3 x 4$ ， $x 1 ⊕ x 1 x 2 x 3 x 4$ ， $x 1 ⊕ x 1 x 2 ⊕ x 3 x 4$ ， $x 1 x 2 ⊕ x 1 x 2 x 3 ⊕ x 1 x 2 x 3 x 4$ ， $x 1 ⊕ x 3 ⊕ x 1 x 2 ⊕ x 3 x 4$ ， $x 1 ⊕ x 1 x 2 ⊕ x 1 x 2 x 3 x 4$ ， $x 1 x 2 ⊕ x 1 x 3 ⊕ x 1 x 4 ⊕ x 2 x 3 ⊕ x 2 x 4 ⊕ x 3 x 4$
低频	$x 1 ⊕ x 1 x 2 ⊕ x 1 x 2 x 3 ⊕ x 1 x 2 x 3 x 4$ ， $x 1 ⊕ x 2 x 3 ⊕ x 1 x 2 x 3 ⊕ x 1 x 2 x 3 x 4$ ， $x 1 ⊕ x 2 x 3 ⊕ x 1 x 2 x 4 ⊕ x 1 x 2 x 3 x 4$ ， $x 1 ⊕ x 2 ⊕ x 1 x 2 ⊕ x 1 x 2 x 3 ⊕ x 1 x 2 x 3 x 4$

图1 三级AIC结构

Fig. 1 Structure of three-AIC

表3 x?k与pk、ik的关系

Tab. 3 Relationship between x?k and pk， ik

$p k$	$i k$	$x ˜ k$	$p k$	$i k$	$x ˜ k$	$p k$	$i k$	$x ˜ k$
0	0	$x k$	1	0	$x k ¯$	2	0	$x k$
0	1	0	1	1	1	2	1	$x k ¯$

表3 x?k与pk、ik的关系

Tab. 3 Relationship between x?k and pk， ik

$p k$	$i k$	$x ˜ k$	$p k$	$i k$	$x ˜ k$	$p k$	$i k$	$x ˜ k$
0	0	$x k$	1	0	$x k ¯$	2	0	$x k$
0	1	0	1	1	1	2	1	$x k ¯$

图2 NLBF化简前后结果比较

Fig. 2 Comparison of results before and after NLBF simplification

图3 RA-NLBF总体布局

Fig. 3 General layout of RA-NLBF

表4 常用流密码算法［15］NLBF的资源占用

Tab. 4 Resource consumption of NLBFs in commonly used stream cipher algorithms

流密码算法	功能	输入端口数	2-AIC-g数
A5-1	Z/F	3	1.5
A5-2	F	3	1.5
A5-2	M	12	6
W7	M	28	9.5
Decim	F	14	39.5
Grain	F	16	13
	M	5	5.5
	M	12	9
Trivium	V	5	2
LILI-128	F	10	22.5
Toyocrypt-hs1	F	127	48
Grain-128aead	F	29	9.5
Espresso	S	17	8.5
Sprout/Plantlet	F	32	10.5
Sprout/Plantlet	S	9	3
Fruit-80	M	18	6
Ach-80 /128	A0	15	11.5
	A1	15	10.5
	A2	15	11
	A3	17	16.5
	A4	17	14.5
	A5	17	16
	A6	18	14.5
	A7	18	10
	A8	18	12.5
	A9	17	18
	A10	17	14
	A11	17	15.5
	A12	19	15.5
	S	13	48
	F	29	9
Lizard	S	53	17.5

图4 Part-A（Part-B）的级联结构

Fig. 4 Cascade structure of Part-A （Part-B）

图5 Part-C的级联结构

Fig. 5 Cascade structure of Part-C

表5 Achterbahn-80/128-A10适配结果

Tab. 5 Achterbahn-80/128-A10 configuration results

初始状态（Ach-A10）	第一轮化简	第二轮化简
$x 0, x 2, x 5, x 6, x 15, x 17, x 18, x 20, x 25$	$x 0, x 2, x 5, x 6, x 15, x 17, x 18, x 25$	$x 0, x 2, x 5, x 6, x 15, x 18, x 25$
$x 8 x 18, x 8 x 20, x 12 x 21, x 14 x 19, x 17 x 21, x 20 x 22$	$x 17 x 21$	$x 17 x 21 ¯$
$x 4 x 12 x 22, x 4 x 19 x 22, x 7 x 20 x 21, x 8 x 18 x 22, x 8 x 20 x 22, x 12 x 19 x 22, x 20 x 21 x 22$
$x 4 x 7 x 12 x 21, x 4 x 7 x 19 x 21, x 4 x 12 x 21 x 22, x 4 x 19 x 21 x 22, x 7 x 8 x 18 x 21, x 7 x 8 x 20 x 21, x 7 x 12 x 19 x 21, x 8 x 18 x 21 x 22, x 8 x 20 x 21 x 22, x 12 x 19 x 21 x 22$	$x 4 x 7 ¯ x 12 x 21, x 4 x 19 x 7 x 21 ¯, x 4 x 12 x 21 ¯ x 22, x 4 x 19 x 21 ¯ x 22, x 7 x 8 x 18 x 21, x 7 x 8 ¯ x 20 x 21, x 7 x 12 x 19 x 21, x 8 x 18 x 21 ¯ x 22 ¯, x 8 ¯ x 20 x 21 ¯ x 22 ¯, x 12 x 19 x 21 ¯ x 22$	同上一轮

表5 Achterbahn-80/128-A10适配结果

Tab. 5 Achterbahn-80/128-A10 configuration results

初始状态（Ach-A10）	第一轮化简	第二轮化简
$x 0, x 2, x 5, x 6, x 15, x 17, x 18, x 20, x 25$	$x 0, x 2, x 5, x 6, x 15, x 17, x 18, x 25$	$x 0, x 2, x 5, x 6, x 15, x 18, x 25$
$x 8 x 18, x 8 x 20, x 12 x 21, x 14 x 19, x 17 x 21, x 20 x 22$	$x 17 x 21$	$x 17 x 21 ¯$
$x 4 x 12 x 22, x 4 x 19 x 22, x 7 x 20 x 21, x 8 x 18 x 22, x 8 x 20 x 22, x 12 x 19 x 22, x 20 x 21 x 22$
$x 4 x 7 x 12 x 21, x 4 x 7 x 19 x 21, x 4 x 12 x 21 x 22, x 4 x 19 x 21 x 22, x 7 x 8 x 18 x 21, x 7 x 8 x 20 x 21, x 7 x 12 x 19 x 21, x 8 x 18 x 21 x 22, x 8 x 20 x 21 x 22, x 12 x 19 x 21 x 22$	$x 4 x 7 ¯ x 12 x 21, x 4 x 19 x 7 x 21 ¯, x 4 x 12 x 21 ¯ x 22, x 4 x 19 x 21 ¯ x 22, x 7 x 8 x 18 x 21, x 7 x 8 ¯ x 20 x 21, x 7 x 12 x 19 x 21, x 8 x 18 x 21 ¯ x 22 ¯, x 8 ¯ x 20 x 21 ¯ x 22 ¯, x 12 x 19 x 21 ¯ x 22$	同上一轮

表6 可重构单元的面积和延迟

Tab. 6 Area and delay of reconfigurable unit

Part	面积/μm²	延迟/ns	2-nand/10⁴GE
A	3 219.96	1.70	0.032
B	3 219.96	1.70	0.032
C	4 257.79	1.72	0.043
A+B+C	12 949.67	1.98	0.129

表7 不同方法的性能对比

Tab. 7 Performance comparison of different methods

方法	工艺/nm	2-nand/10⁴GE	延迟/ns	时钟频率/MHz
RNF^［16］	180	2.790	2.67	374
RPNF^［17］	180	1.310	6.01	166
TNF^［18］	180	0.440	5.24	190
RSCLU^［5］	180	0.320	3.16	316
文献［6］方法	180	2.280	3.22	310
SNBFM^［7］	65	—	1.47	680
RA-NLBF	180	0.129	1.98	505

参考文献 18

1	CRAMA Y， HAMMER P L. Boolean Functions： Theory， Algorithms， and Applications［M］. Cambridge： Cambridge University Press， 2011： 564-607. 10.1017/cbo9780511852008
2	CHEN L G， LAI J M， TONG J R. An AND-LUT based hybrid FPGA architecture［J］. Chinese Journal of Semiconductors， 2007， 28（3）：398-403.
3	SARKAR P， MAITRA S. Efficient implementation of "large" stream cipher systems［C］// Proceedings of the 2001 International Workshop on Cryptographic Hardware and Embedded Systems， LNCS 2162. Berlin： Springer， 2001： 319-332.
4	WANG B， LIU L. A flexible and energy-efficient reconfigurable architecture for symmetric cipher processing［C］// Proceedings of the 2015 IEEE International Symposium on Circuits and Systems. Piscataway： IEEE， 2015： 1182-1185. 10.1109/iscas.2015.7168850
5	戴紫彬，王周闯，李伟，等.可重构非线性布尔函数利用率模型研究与硬件设计［J］. 电子与信息学报， 2017， 39（5）： 1226-1232. 10.11999/JEIT160733
	DAI Z B， WANG Z C， LI W， et al. Hardware implementation and utilization model research for reconfigurable non-linear Boolean function［J］. Journal of Electronics and Information Technology， 2017， 39（5）： 1226-1232. 10.11999/JEIT160733
6	SU Y， SHEN J， WANG W. Reconfigurable design and implementation of nonlinear Boolean function for cloud computing security platform［J］. International Journal of Information and Computer Security， 2019， 11（2）：145-159. 10.1504/ijics.2019.098201
7	连宜新，陈韬，李伟，等. 两类非线性密码组件可重构研究与电路设计［J］. 计算机工程， 2022， 48（2）：156-163， 172. 10.19678/j.issn.1000-3428.0060722
	LIAN Y X， CHEN T， LI W， et al. Reconfigurable research and circuit design of two types of nonlinear cryptographic components［J］. Computer Engineering， 2022， 48（2）：156-163， 172. 10.19678/j.issn.1000-3428.0060722
8	PARANDEH-AFSHAR H， BENBIHI H， NOVO D， et al. Rethinking FPGAs： elude the flexibility excess of LUTs with and-inverter cones［C］// Proceedings of the 2012 ACM/SIGDA International Symposium on Field Programmable Gate Arrays. New York， ACM， 2012：119-128. 10.1145/2145694.2145715
9	葛徽. 流密码中密码函数的设计与分析［D］. 西安：西安电子科技大学， 2021：11-23.
	GE H. Analysis and design of cryptographic functions for stream ciphers［D］. Xi’an： Xidian University， 2021： 11-23.
10	MISHCHENKO A， CHATTERJEE S， BRAYTON R. DAG-aware AIG rewriting： a fresh look at combinational logic synthesis［C］// Proceedings of the 43rd ACM/IEEE Design Automation Conference. New York： ACM， 2006： 532-535. 10.1145/1146909.1147048
11	黄志洪.现场可编程门阵列（FPGA）异质逻辑与存储互连结构研究［D］.北京：中国科学院大学，2016：75-91.
	HUANG Z H. Research on heterogeneous logic and storage interconnection structure of Field Programmable Gate Array （FPGA）［D］. Beijing： University of Chinese Academy of Sciences， 2016： 75-91.
12	黄志洪，李威，杨立群，等.一种基于与非锥簇架构FPGA输入交叉互连设计优化方法［J］.电子与信息学报，2016，38（9）： 2397-2404. 10.11999/JEIT151216
	HUANG Z H， LI W， YANG L Q， et al. An input crossbar optimization method for and-inverter cone based FPGA［J］. Journal of Electronics and Information Technology， 2016， 38（9）： 2397-2404. 10.11999/JEIT151216
13	RAI S， NATH P， RUPANI A， et al. A survey of FPGA logic cell designs in the light of emerging technologies［J］. IEEE Access， 2021， 9： 91564-91574. 10.1109/access.2021.3092167
14	李辉. 混合极性Reed-Muller逻辑电路功耗和面积优化［D］. 宁波：宁波大学， 2011：41-45.
	LI H. Power and area optimization of mixed polarity Reed-Muller logic circuits［D］. Ningbo： Ningbo University， 2011：41-45.
15	赵石磊，刘玲，黄海，等. 流密码算法、架构与硬件实现研究［J］. 密码学报， 2021， 8（6）： 1039-1057. 10.13868/j.cnki.jcr.000495
	ZHAO S L， LIU L， HUANG H， et al. Algorithm， architecture and hardware implementation of stream cipher［J］. Journal of Cryptologic Research， 2021， 8（6）： 1039-1057. 10.13868/j.cnki.jcr.000495
16	秦晓懿，王瀚晟，曾烈光.线性和非线性寄存器系统的并行化技术［J］. 电子学报，2003，31（3）：406-410. 10.3321/j.issn:0372-2112.2003.03.023
	QIN X Y， WANG H S， ZENG L G. Parallelization techniques for linear and non-linear register systems［J］. Acta Electronica Sinica， 2003， 31（3）： 406-410. 10.3321/j.issn:0372-2112.2003.03.023
17	李伟.面向序列密码的反馈移位寄存器可重构并行化设计技术研究［D］.郑州：解放军信息工程大学，2009：34-35.
	LI W. Research on technology of reconfigurable parallel feedback shift register targeted at stream cipher［D］. Zhengzhou： PLA Information Engineering University， 2009： 34-35.
18	陈韬，杨萱，戴紫彬，等.面向序列密码的非线性反馈移位寄存器可重构并行化设计［J］.上海交通大学学报，2013，47（1）：28-32.
	CHEN T， YANG X， DAI Z B， et al. Design of a reconfigurable parallel nonlinear feedback shift register structure targeted at stream cipher［J］. Journal of Shanghai Jiao Tong University， 2013， 47（1）： 28-32.

[1]	陈虹, 刘雨朦, 肖成龙, 郭鹏飞, 肖振久. 基于椭圆曲线的改进RC4算法[J]. 计算机应用, 2019, 39(8): 2339-2345.
[2]	苑超, 徐蜜雪, 斯雪明. 对不同种子密钥长度的RC4算法的明文恢复攻击[J]. 计算机应用, 2018, 38(2): 370-373.
[3]	王周闯, 戴紫彬, 李伟. 高效适配NLBF型序列密码的全局定向搜索算法[J]. 计算机应用, 2016, 36(9): 2442-2446.
[4]	陈银冬向洪艳张亚楠. 代数免疫度最优的偶数元旋转对称布尔函数的构造[J]. 计算机应用, 2014, 34(2): 444-447.
[5]	涂光友何波. 基于时空混沌的伪随机数发生器设计[J]. 计算机应用, 2013, 33(12): 3499-3502.
[6]	牛志华郭丹峰. 计算p^n-周期二元序列的最小错线性复杂度新算法[J]. 计算机应用, 2013, 33(01): 12-14.
[7]	林志强. 2-adic有限状态自动机的新实现方法[J]. 计算机应用, 2012, 32(10): 2783-2785.
[8]	罗松江朱路平. 基于分段非线性混沌映射的流密码加密方案[J]. 计算机应用, 2010, 30(11): 3038-3039.

流密码非线性布尔函数可重构运算单元设计方法RA-NLBF

RA-NLBF： design method of reconfigurable operation unit for stream cipher non-linear Boolean function

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 18

相关文章 8

编辑推荐

Metrics