面向双线性对的  F   p 2   -FIOS模乘算法及其实现架构研究

doi:10.11959/j.issn.1000-436x.2022040

通信学报 ›› 2022, Vol. 43 ›› Issue (2): 100-108.doi: 10.11959/j.issn.1000-436x.2022040

面向双线性对的 $F_{p^{2}}$ -FIOS模乘算法及其实现架构研究

姜占鹏¹, 孙铭玮², 黄海¹, 徐江¹, 刘志伟¹, 白瑞³, 方舟³, 曲家兴³

¹ 哈尔滨理工大学计算机科学与技术学院，黑龙江哈尔滨 150080
² 哈尔滨理工大学电气与电子工程学院，黑龙江哈尔滨 150080
³ 黑龙江省网络空间研究中心，黑龙江哈尔滨 150090

修回日期:2022-01-28 出版日期:2022-02-25 发布日期:2022-02-01
作者简介:姜占鹏（1984-），男，黑龙江哈尔滨人，博士，哈尔滨理工大学副教授，主要研究方向为嵌入式微处理器和总线接口电路设计等
孙铭玮（1995-），男，黑龙江密山人，哈尔滨理工大学硕士生，主要研究方向为数字集成电路设计
黄海（1982-），男，内蒙古巴彦淖尔人，博士，哈尔滨理工大学教授、博士生导师，主要研究方向为信息安全、可重构技术、集成电路设计等
徐江（1997-），男，山东日照人，哈尔滨理工大学硕士生，主要研究方向为信息安全
刘志伟（1987-），男，黑龙江哈尔滨人，博士，哈尔滨理工大学讲师，主要研究方向为可重构计算、高速密码算法、并行加密技术、密码芯片的安全设计等
白瑞（1990-），男，内蒙古海拉尔人，黑龙江省网络空间研究中心工程师，主要研究方向为网络安全、卫星应用、大数据等
方舟（1983-），女，黑龙江哈尔滨人，博士，黑龙江省网络空间研究中心高级工程师，主要研究方向为物联网内容安全与隐私保护、网络安全、卫星应用、大数据等
曲家兴（1979-），男，黑龙江哈尔滨人，博士，黑龙江省网络空间研究中心研究员级高级工程师，主要研究方向为物联网内容安全与隐私保护、网络安全、卫星应用、大数据等
基金资助:
国家重点研发计划基金资助项目(2018YFB2202100);中央引导地方科技发展专项基金资助项目(ZY20B11);黑龙江省自然科学基金优秀青年基金资助项目(YQ2019F010);黑龙江省普通高校基本科研业务费专项资金资助项目(2019KYYWF0214)

Research on $F_{p^{2}}$ -FIOSmodular multiplication algorithm for bilinear pairs and its implementation architecture

Zhanpeng JIANG¹, Mingwei SUN², Hai HUANG¹, Jiang XU¹, Zhiwei LIU¹, Rui BAI³, Zhou FANG³, Jiaxing QU³

¹ School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China
² School of Electrical and Electronic Engineering, Harbin University of Science and Technology, Harbin 150080, China
³ Heilongjiang Province Cyberspace Research Center, Harbin 150090, China

Revised:2022-01-28 Online:2022-02-25 Published:2022-02-01
Supported by:
The National Key Research and Development Program of China(2018YFB2202100);Special Projects for the Central Government to Guide the Development of Local Science and Technology(ZY20B11);The Natural Science Foundation of Heilongjiang Province(YQ2019F010);The Fundamental Research Funds for the Central Universities of Heilongjiang Province(2019KYYWF0214)

摘要/Abstract

摘要：

针对双线性对运算效率低的问题，提出了一种面向双线性对的二次扩域细集成操作数扫描（ $F_{p^{2}}$ -FIOS）模乘算法。该算法通过优化二次扩域下(AB+CD)mod P的运算过程，有效降低了模乘中的模约减次数；设计了满足不同应用需求的2种硬件架构及其调度方式以提升算法的计算效率；采用TSMC 55 nm工艺实现了双线性对运算单元。与现有文献相比，所设计的架构在一次模乘时间、时钟频率和面积时间积等性能指标上优于同类模乘设计，在整体Optimal ate对运算实现上也有一定的优势。

关键词: 双线性对, 扩域, 模乘, 硬件实现架构

Abstract:

A quadratic extended-domain finely integrated operand scanning ( $F_{p^{2}}$ -FIOS) modular multiplication algorithm for bilinear pairs was proposed to address the problem of low efficiency of bilinear pair operations.The algorithm effectively reduced the number of modular reductions in modular multiplication by optimizing the operation process of (AB+CD)mod P under the quadratic expansion domain.Two hardware architectures and their scheduling methods were designed to meet different application requirements.In order to improve the computational efficiency of the algorithm, the TSMC 55 nm process was used to realize the bilinear pairing operation unit.Compared with the existing literature, the designed architecture is superior to similar modular multiplication designs in performance indicators such as the first modular multiplication time, clock frequency and the area-time product, and also has certain advantages in the overall Optimal ate pair implementation.

Key words: bilinear pair, extended domain, modular multiplication, hardware implementation architecture

中图分类号:

TN918

姜占鹏, 孙铭玮, 黄海, 徐江, 刘志伟, 白瑞, 方舟, 曲家兴. 面向双线性对的 $F_{p^{2}}$ -FIOS模乘算法及其实现架构研究[J]. 通信学报, 2022, 43(2): 100-108.

Zhanpeng JIANG, Mingwei SUN, Hai HUANG, Jiang XU, Zhiwei LIU, Rui BAI, Zhou FANG, Jiaxing QU. Research on $F_{p^{2}}$ -FIOSmodular multiplication algorithm for bilinear pairs and its implementation architecture[J]. Journal on Communications, 2022, 43(2): 100-108.

图/表 8

图1

表1

F p 2 模乘的乘加计算量比较"

算法	乘法	加法
FIOS	4n²+2n	10n²+8n+4
高基蒙哥马利模乘	4n²+2n	8n²+6n+4
$F_{p^{2}} -FIOS$	3n²+n	6n²+2n+2

表1

图2

图3

图4

图5

表2

相关设计实现 F p 2 模乘性能对比"

相关设计	工艺库	乘法运算/bit	乘法器数量/个	频率	周期/个	时间/ns	等效门数/K	AT
文献[10]	TSMC 65 nm	53×320	3	800 MHz	18	22.5	215	4 837.5
文献[11]	SMIC 65 nm	24×256	3	709 MHz	50	70	226	15 820
文献[14]	TSMC 55 nm	64×64	4	1.3 GHz	31	23.87	192	4 583
$F_{p^{2}}$ -FIOS2（本文）	TSMC 55 nm	64×64	2	2.00 GHz	31	15.5	110	1 705
	TSMC 55 nm	32×32	2	1.82 GHz	107	58.85	60	3 531
	TSMC 55 nm	64×64	3	2.00 GHz	24	12.0	139	1 668
$F_{p^{2}}$ -FIOS3（本文）	TSMC 55 nm	32×32	3	1.82 GHz	76	41.8	68	2 842.4
	TSMC 55 nm	16×16	3	1.89 GHz	276	146.28	52	7 606.56
	TSMC 55 nm	8×8	3	1.96 GHz	1060	540.6	45	2 4327

表2

表3

参考文献 23

[1]	SHAMIR A . Identity-based cryptosystems and signature schemes[J]. Lecture Notes in Computer Science, 1985,196(1): 47-53.
[2]	国家密码管理局. SM9 标识密码算法第 1 部分：总则:GM/T 0044.1-2016[S]. 北京:中国标准出版社, 2016.
	State Cryptography Administration. Identity-based cryptographic algorithms SM9-part 1:general:GM/T 0044.1-2016[S]. Beijing:Standards Press of China, 2016.
[3]	HESS F , SMART N P , VERCAUTEREN F . The eta pairing revisited[J]. IEEE Transactions on Information Theory, 2006,52(10): 4595-4602.
[4]	LEE E , LEE H S , PARK C M . Efficient and generalized pairing computation on abelian varieties[J]. IEEE Transactions on Information Theory, 2009,55(4): 1793-1803.
[5]	VERCAUTEREN F . Optimal pairings[J]. IEEE Transactions on Information Theory, 2010,56(1): 455-461.
[6]	KOBLITZ N , MENEZES A . Pairing-based cryptography at high security levels[C]// IMA International Conference on Cryptography and Coding. Berlin:Springer, 2005: 13-36.
[7]	BARRETO P S L M , NAEHRIG M . Pairing-friendly elliptic curves of prime order[C]// International Workshop on Selected Areas in Cryptography. Berlin:Springer, 2005: 319-331.
[8]	ARANHA D F , KARABINA K , LONGA P ,et al. Faster explicit formulas for computing pairings over ordinary curves[C]// Proceedings of the 30th Annual International Conference on Theory and Applications of Cryptographic Techniques:Advances in Cryptology. Berlin:Springer, 2011: 48-68.
[9]	LI Y , HAN J , WANG S ,et al. An 800 MHz cryptographic pairing processor in 65 nm CMOS[C]// Proceedings of 2012 IEEE Asian Solid State Circuits Conference (A-SSCC). Piscataway:IEEE Press, 2012: 217-220.
[10]	HAN J , LI Y , YU Z Y ,et al. A 65 nm cryptographic processor for high speed pairing computation[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2015,23(4): 692-701.
[11]	PANG Y L , ZHANG Y , HAN J ,et al. Fp2 arithmetic acceleration based on modified Barrett modular multiplication algorithm[C]// Proceedings of 2017 IEEE 12th International Conference on ASIC. Piscataway:IEEE Press, 2017: 561-564.
[12]	MIYAMOTO A , HOMMA N , AOKI T ,et al. Systematic design of RSA processors based on high-radix Montgomery multipliers[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2011,19(7): 1136-1146.
[13]	KAYA KOC C , ACAR T , KALISKI B S . Analyzing and comparing Montgomery multiplication algorithms[J]. IEEE Micro, 1996,16(3): 26-33.
[14]	WANG A T , GUO B W , WEI C J . Highly-parallel hardware implementation of optimal ate pairing over Barreto-Naehrig curves[J]. Integration, 2019,64: 13-21.
[15]	HAO Z Y , GUO W , WEI J Z ,et al. Dual processing engine architecture to speed up optimal ate pairing on FPGA platform[C]// Proceedings of 2016 IEEE Trustcom/BigDataSE/ISPA. Piscataway:IEEE Press, 2016: 584-589.
[16]	CHEUNG R C C , DUQUESNE S , FAN J F ,et al. FPGA implementation of pairings using residue number system and lazy reduction[C]// Cryptographic Hardware and Embedded Systems – CHES 2011. Berlin:Springer, 2011: 421-441.
[17]	BAHADORI M , J?RVINEN K , . Compact and programmable yet high-performance SoC architecture for cryptographic pairings[C]// Proceedings of 2020 30th International Conference on Field-Programmable Logic and Applications (FPL). Piscataway:IEEE Press, 2020: 176-184.
[18]	BAG A , BASU ROY D , PATRANABIS S ,et al. FlexiPair:an automated programmable framework for pairing cryptosystems[J]. IEEE Transactions on Computers, 2022,71(3): 506-519.
[19]	于斌, 黄海, 刘志伟 ,等. 面向多椭圆曲线的高速标量乘法器设计与实现[J]. 通信学报, 2020,41(12): 100-109.
	YU B , HUANG H , LIU Z W ,et al. Design and implementation of high-speed scalar multiplier for multi-elliptic curve[J]. Journal on Communications, 2020,41(12): 100-109.
[20]	王晨宇, 汪定, 王菲菲 ,等. 面向多网关的无线传感器网络多因素认证协议[J]. 计算机学报, 2020,43(4): 683-700.
	WANG C Y , WANG D , WANG F F ,et al. Multi-factor user authentication scheme for multi-gateway wireless sensor networks[J]. Chinese Journal of Computers, 2020,43(4): 683-700.
[21]	WANG Q X , WANG D , CHENG C ,et al. Quantum2FA:efficient quantum-resistant two-factor authentication scheme for mobile devices[J]. IEEE Transactions on Dependable and Secure Computing, 2021:doi.org/ 10.1109/TDSC.2021.3129512.
[22]	LI J H , JIN J , LYU L J ,et al. A fast and scalable authentication scheme in IoT for smart living[J]. Future Generation Computer Systems, 2021,117: 125-137.
[23]	NIKRAVAN M , REZA A . A multi-factor user authentication and key agreement protocol based on bilinear pairing for the Internet of things[J]. Wireless Personal Communications, 2020,111(1): 463-494.

相关设计	工艺库	频率/MHz	周期/个	时间/ms	面积
文献[10]	TSMC 65 nm	800	350 740	0.521	323K Gates
文献[14]	Xilinx FPGA Virtex-7	115	394 806	3.43	28K Slices, 128 DSPs
文献[15]	Xilinx FPGA Virtex-6	125	283 111	2.26	4380 Slices, 131DSPs
文献[16]	Xilinx FPGA Virtex-6	165	143 111	0.573	7032 Slices, 32DSPs, 45BRAM
文献[17]	Xilinx FPGA Virtex-6	156	208 000	1.33	3072 Slices, 36DSPs, 18BRAM
文献[18]	Xilinx FPGA Virtex-7	181	2 552 346	14.14	2506 Slices, 40DSPs, 20BRAM
本文架构	TSMC 55 nm	500	97 824	0.186	850K Gates

面向双线性对的 $F_{p^{2}}$ -FIOS模乘算法及其实现架构研究

Research on $F_{p^{2}}$ -FIOSmodular multiplication algorithm for bilinear pairs and its implementation architecture

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 23

相关文章 15

Metrics

推荐阅读 0

[1]	李斌, 周清雷, 陈晓杰, 冯峰. 可重构的素域SM2算法优化方法[J]. 通信学报, 2022, 43(3): 30-41.
[2]	徐明,李旭如,刘朝斌,马尧. 基于双重代理密钥的船舶自组网门限签名方案[J]. 通信学报, 2018, 39(7): 166-175.
[3]	宋成,张明月,彭维平,贾宗璞,刘志中,闫玺玺. 基于双线性对的车联网批量匿名认证方案研究[J]. 通信学报, 2017, 38(6): 49-57.
[4]	杜红珍,温巧燕. 无证书强指定验证者多重签名[J]. 通信学报, 2016, 37(6): 20-28.
[5]	王洁,蔡永泉,田有亮. 基于博弈论的门限签名体制分析与构造[J]. 通信学报, 2015, 36(5): 148-155.
[6]	赵振国. 无证书签密机制的安全性分析与改进[J]. 通信学报, 2015, 36(3): 75-80.
[7]	张宇，杜瑞颖，陈晶，侯健，周庆，王文武. 对一个基于身份签密方案的分析与改[J]. 通信学报, 2015, 36(11): 174-179.
[8]	杜红珍,温巧燕. 改进的无证书有序多重签名方案[J]. 通信学报, 2015, 36(10): 56-61.
[9]	樊爱宛,杨照峰,谢丽明. 强安全无证书签名方案的安全性分析和改进[J]. 通信学报, 2014, 35(5): 118-123.
[10]	樊爱宛1，杨照峰1，谢丽明2. 强安全无证书签名方案的安全性分析和改进法[J]. 通信学报, 2014, 35(5): 16-123.
[11]	叶青1,2，杨赟3，郑世慧2，常利伟2，肖达2，杨义先2,4. 公平的多方并发签名方案[J]. 通信学报, 2014, 35(3): 16-149.
[12]	叶青,杨赟,郑世慧,常利伟,肖达,杨义先. 公平的多方并发签名方案[J]. 通信学报, 2014, 35(3): 140-149.
[13]	田有亮,彭长根,马建峰,林辉,杨凯. 通用可组合公平安全多方计算协议[J]. 通信学报, 2014, 35(2): 54-62.
[14]	田有亮1,2，彭长根1，马建峰2，林辉2，杨凯3. 通用可组合公平安全多方计算协议[J]. 通信学报, 2014, 35(2): 8-62.
[15]	杨小东，李春梅，徐婷，王彩芬. 无双线性对的基于身份的在线/离线门限签名方案[J]. 通信学报, 2013, 34(8): 24-190.

面向双线性对的 F p 2 -FIOS模乘算法及其实现架构研究

Research on F p 2 -FIOSmodular multiplication algorithm for bilinear pairs and its implementation architecture

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 23

相关文章 15

Metrics

推荐阅读 0

面向双线性对的 $F_{p^{2}}$ -FIOS模乘算法及其实现架构研究

Research on $F_{p^{2}}$ -FIOSmodular multiplication algorithm for bilinear pairs and its implementation architecture