面向椭圆曲线密码算法的可配置处理器研究与设计
|
摘要
随着计算机和互联网的飞速发展和广泛应用,信息安全越来越受到关注。椭圆曲线密码体制(ECC)作为一种新兴的公钥密码体制,具有密钥短、处理速度快、数据传输带宽低、安全性高的优点,有着良好的应用前景。本文研究并实现了一种基于传输触发架构(TTA)的可配置的ECC处理器,相比较于传统的专用集成电路、FPGA、通用处理器等实现方式,该处理器可以在速度和面积上获得较好的折衷,更好地符合了现实需求。
本文首先对ECC的核心运算标量乘算法进行了分析和优化,包括曲线点的坐标表示、点加和倍点运算的数据流规划以及模乘算法的优化实现等。然后结合TTA软硬件结构的特点,定制了ECC处理器的整体架构,包括指令格式、流水线、控制通路、数据通路和各个功能单元。其中功能单元作为处理器的核心运算模块,直接决定了处理器的整体性能,因此本文也针对具体的ECC算法,设计了不同的功能单元,主要有模乘预计算单元、模乘加速单元、模加模减单元、算术逻辑功能单元、数据存取单元以及跳转单元,它们都将在一定程度上提升标量乘的处理速度。
ECC处理器硬件验证时,本文在验证各个模块功能正确的基础上,通过编写应用程序进行仿真测试并与C模型进行比较,结果表明处理器能够正确完成标量乘功能。最后对ECC处理器进行综合,结果显示处理器所占面积为9万门,可运行在105MHz的时钟频率下,并能够在1秒内完成427次标量乘运算,相比较于传统的实现方式,本文提出的ECC处理器在整体性能上要更好。
With the rapid development and wide application of computer and network, information security is given more and more attention. As new public-key cryptography, elliptic curve cryptography (ECC) has many excellent attributes: short key length, fast speed, low transport bandwidth and high security. These attributes make it an ideal choice for application. This paper researches and implements a configurable processor for ECC based on transport triggered architecture. This processor can obtain a good compromise between speed and area and better meet the real needs, compared to the traditional implementation, such as application specific integrated circuit, FPGA and general-purpose processor.
Firstly, the scalar multiplication algorithm, the core operations of ECC, is analyzed and optimized in this paper, including coordinate of the curve point, the data flow’s planning over operations of point addition and double point, optimization of modular multiplication algorithm and so on. Then combined with features of TTA’s hardware and software, the whole ECC processor is customized, including instruction format, pipelining, control path, data path and each functional unit (FU). As key computing components of processor, FUs directly determine the overall performance of the processor, so this paper designs different FUs for the specific ECC algorithm, such as modular multiplication precomputed unit, modular multiplication accelerate unit, modular addition and modular subtraction unit, arithmetic logic unit, load_store unit and jump unit. When processing the scalar multiplication, the speed will be increased by using those FUs.
In the hardware verification of ECC processor, the paper firstly insures that the function of each module is right, then writes application program to simulate and compares it with the C module. The result shows that the processor can compute scalar multiplication correctly. Finally, the process is synthesized and it shows the processor uses 90Kgates, runs at 105MHz clock frequency and is able to complete 427 times scalar multiplication in one second. Compared to the traditional implementations, this processor has a better holistic performance.
本文首先对ECC的核心运算标量乘算法进行了分析和优化,包括曲线点的坐标表示、点加和倍点运算的数据流规划以及模乘算法的优化实现等。然后结合TTA软硬件结构的特点,定制了ECC处理器的整体架构,包括指令格式、流水线、控制通路、数据通路和各个功能单元。其中功能单元作为处理器的核心运算模块,直接决定了处理器的整体性能,因此本文也针对具体的ECC算法,设计了不同的功能单元,主要有模乘预计算单元、模乘加速单元、模加模减单元、算术逻辑功能单元、数据存取单元以及跳转单元,它们都将在一定程度上提升标量乘的处理速度。
ECC处理器硬件验证时,本文在验证各个模块功能正确的基础上,通过编写应用程序进行仿真测试并与C模型进行比较,结果表明处理器能够正确完成标量乘功能。最后对ECC处理器进行综合,结果显示处理器所占面积为9万门,可运行在105MHz的时钟频率下,并能够在1秒内完成427次标量乘运算,相比较于传统的实现方式,本文提出的ECC处理器在整体性能上要更好。
With the rapid development and wide application of computer and network, information security is given more and more attention. As new public-key cryptography, elliptic curve cryptography (ECC) has many excellent attributes: short key length, fast speed, low transport bandwidth and high security. These attributes make it an ideal choice for application. This paper researches and implements a configurable processor for ECC based on transport triggered architecture. This processor can obtain a good compromise between speed and area and better meet the real needs, compared to the traditional implementation, such as application specific integrated circuit, FPGA and general-purpose processor.
Firstly, the scalar multiplication algorithm, the core operations of ECC, is analyzed and optimized in this paper, including coordinate of the curve point, the data flow’s planning over operations of point addition and double point, optimization of modular multiplication algorithm and so on. Then combined with features of TTA’s hardware and software, the whole ECC processor is customized, including instruction format, pipelining, control path, data path and each functional unit (FU). As key computing components of processor, FUs directly determine the overall performance of the processor, so this paper designs different FUs for the specific ECC algorithm, such as modular multiplication precomputed unit, modular multiplication accelerate unit, modular addition and modular subtraction unit, arithmetic logic unit, load_store unit and jump unit. When processing the scalar multiplication, the speed will be increased by using those FUs.
In the hardware verification of ECC processor, the paper firstly insures that the function of each module is right, then writes application program to simulate and compares it with the C module. The result shows that the processor can compute scalar multiplication correctly. Finally, the process is synthesized and it shows the processor uses 90Kgates, runs at 105MHz clock frequency and is able to complete 427 times scalar multiplication in one second. Compared to the traditional implementations, this processor has a better holistic performance.
引文
[1]谷利泽,郑世慧,杨义先,现代密码学教程[M],北京:北京邮电大学出版社,2009,1
[2]唐薛峰,椭圆曲线密码算法IP的VLSI实现[D],浙江,浙江大学,2004
[3]朱华,周玉洁,素域上椭圆曲线密码IP的高效VLSI实现[J],计算机工程:安全技术版,2008,34(16): 165-167
[4] W. Shuhua and Z. Yuefei, A timing-and-area tradeoff GF(p) elliptic curve processor architecture for FPGA [C], 2005 International Conference on Communications, Circuits and Systems, 2005, 1308-1312
[5] K. Ananyi, H. Alrimeih, D. Rakhmatov, Flexible hardware processor for elliptic curve cryptography over NIST prime fields [J], IEEE Transactions on Very Large Scale Integration Systems, 2009, 17(8):1099-1112
[6]岳虹,沈立,戴葵等,基于TTA的嵌入式ASIP设计[J],计算机研究与发展,2006,43(4):752-758
[7]仲先海,徐金铺,严迎建,并行可配置ECC专用指令协处理器[J],计算机工程, 2009, 35(5):153-156
[8] Wei Guo, Jizeng Wei, Yongbin Yao, etc, Design of a configurable and extensible Tcore processor based on Transport Trigger Architecture [C], World Congress on Computer Science and Information Engineering, 2009, 3, 536～540
[9] Miller V.S, Use of elliptic curves in cryptography [C], CRYPTO’85, 1986, 417-426
[10] Koblitz N, Elliptic curve cryptosystems [C], Mathematics of computation, 1987, 48(4), 203-209
[11] R.L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems [C], Communications of ACM, 1978, 21(2), 120-126
[12] W. Diffie and M.E. Hellman, New direction in Cryptography [J], IEEE Trans on Information Theory, 1976, 22(6), 644-654
[13]李学俊,敬宗良等,基于椭圆曲线离散对数问题的公钥密码[J],计算机工程与应用,2002,38(6):20-22
[14]陈华锋.椭圆曲线密码算法及芯片实现方法研究[D],浙江:浙江大学,2008
[15] IEEE P1363, Standard specifications for public-key cryptography, ballot draft, 1999, Drafts available at http://grouper.ieee
[16] National Institute of Standards and Technology, FIPS-186-2: Digital Signature Standard, January 2000. Available at http://csrc.nist.gov/publications/fips/
[17] ISO/IEC 14888-3, Information Technology-Security Technology Digital Signatures with Appendix-Part 3: Certificate Based-Mechanisms, 1998
[18] J. Sifakis, Embedded system design– Scientific challenges and work directions [C], Design, Automation and Test in Europe Conference, 2009: 2-2
[19] Chris Rowen(美)著,吴武臣,侯立刚译,复杂SoC设计[M],北京:机械工业出版社,2006, 08: 3-40
[20] Tensilica Corporation [EB/OL], Available at http://www.tensilica.com/
[21] ARC International [EB/OL], Available at http://www.arc.com/
[22] Silicon Hive [EB/OL], Available at http://www.siliconhive.com/
[23] H. Corporaal, Design of Transport triggered architecture [C], Fourth Great Lakes Symposium on VLSI, 1994, 130~135
[24]言峰,基于TTA的可配置处理器研究与设计[D],上海:上海交通大学,2009.12
[25] Jizeng Wei, Wei Guo, Jizhou Sun, ect, Program Compression Based on Arithmetic Coding on Transport Triggered Architecture [C], ICESS2008, Sichuan, 2008, 126~131
[26]王勇,面向AES加密的可配置处理器设计及实现[D],天津:天津大学,2010
[27] P. Hamalainen, J. Heikkinen, M. Hannikainen, Design of transport triggered architecture processors for wireless encryption [C], 8th Euromicro Conference on Digital System Design, 2005: 144-152
[28]赵学秘,王志英,岳虹, TTA-EC:一种基于传输触发体系结构的ECC整体算法处理器[J],计算机学报,007, 30(2): 225-233
[29] D. Hankerson, A. Menezes, S. Vanstone, Guide to Elliptic Curve Cryptography [M], New York: Springer-Verlag Hall/CRC, 2004
[30]唐四云,RSA和椭圆曲线密码算法的研究[D],长沙:湖南大学,2006
[31] Gerardo Orlando, Christof Paar, A scalable gf(p) elliptic curve processor architecture for programmable hardware [C], In CHES 2001, Springer-Verlag, 2001,348-363
[32] P.L.Montgomery, Modular multiplication without trial division [C], Mathematics of Computation, 1985, 44(170):519-521
[33] Xiaohui Yang, Qin Fan, An Optimized Scalable and Unified Hardware Structure of Montgomery Multiplier [C], 2009 International Conference on E-Business and Information System Security, EBISS 2009
[34]黄伟亮,王振,黄勇,一类求模逆元的算法[J],暨南大学学报,2009, 30(1): 57-60
[35] K. Araki, I. Fujita, M. Morisue, Fast Inverters over Finite Field Based on Euclid’s Algorithm [J], Trans. IEICE, 1998, 72(11): 1230-1234
[36] T. Zhou, X. Wu, G. Bai, etc, New algorithm and fast VLSI implementation for modular inversion in galois field GF(p) [C], in Proc. IEEE Int. Conf. Commun. Circuits Syst.West Sino Expo, 2002, 2, 1491–1495
[37]刘志强,彭待渊,基于椭圆曲线加密体制的实现[J],信息安全与通信保密,2006, 04: 94-96
[38] H. Schot, H. Corporaal, Automated design of an ASIP for image processing application [C], 6th International Euro-Par Conference, 2000, 1105-1109
[39]朱礼波,基于TTA技术的多功能可配置DSP处理器设计[D],上海:上海交通大学,2008
[40] Jizeng Wei, Wei Guo, Zaifeng Shi, etc, Design and implementation of co-design toolset for Tcore processor [C], 2008 IEEE Asia Pacific Conference on Circuits and Systems, 2008, 1664-1667
[2]唐薛峰,椭圆曲线密码算法IP的VLSI实现[D],浙江,浙江大学,2004
[3]朱华,周玉洁,素域上椭圆曲线密码IP的高效VLSI实现[J],计算机工程:安全技术版,2008,34(16): 165-167
[4] W. Shuhua and Z. Yuefei, A timing-and-area tradeoff GF(p) elliptic curve processor architecture for FPGA [C], 2005 International Conference on Communications, Circuits and Systems, 2005, 1308-1312
[5] K. Ananyi, H. Alrimeih, D. Rakhmatov, Flexible hardware processor for elliptic curve cryptography over NIST prime fields [J], IEEE Transactions on Very Large Scale Integration Systems, 2009, 17(8):1099-1112
[6]岳虹,沈立,戴葵等,基于TTA的嵌入式ASIP设计[J],计算机研究与发展,2006,43(4):752-758
[7]仲先海,徐金铺,严迎建,并行可配置ECC专用指令协处理器[J],计算机工程, 2009, 35(5):153-156
[8] Wei Guo, Jizeng Wei, Yongbin Yao, etc, Design of a configurable and extensible Tcore processor based on Transport Trigger Architecture [C], World Congress on Computer Science and Information Engineering, 2009, 3, 536～540
[9] Miller V.S, Use of elliptic curves in cryptography [C], CRYPTO’85, 1986, 417-426
[10] Koblitz N, Elliptic curve cryptosystems [C], Mathematics of computation, 1987, 48(4), 203-209
[11] R.L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems [C], Communications of ACM, 1978, 21(2), 120-126
[12] W. Diffie and M.E. Hellman, New direction in Cryptography [J], IEEE Trans on Information Theory, 1976, 22(6), 644-654
[13]李学俊,敬宗良等,基于椭圆曲线离散对数问题的公钥密码[J],计算机工程与应用,2002,38(6):20-22
[14]陈华锋.椭圆曲线密码算法及芯片实现方法研究[D],浙江:浙江大学,2008
[15] IEEE P1363, Standard specifications for public-key cryptography, ballot draft, 1999, Drafts available at http://grouper.ieee
[16] National Institute of Standards and Technology, FIPS-186-2: Digital Signature Standard, January 2000. Available at http://csrc.nist.gov/publications/fips/
[17] ISO/IEC 14888-3, Information Technology-Security Technology Digital Signatures with Appendix-Part 3: Certificate Based-Mechanisms, 1998
[18] J. Sifakis, Embedded system design– Scientific challenges and work directions [C], Design, Automation and Test in Europe Conference, 2009: 2-2
[19] Chris Rowen(美)著,吴武臣,侯立刚译,复杂SoC设计[M],北京:机械工业出版社,2006, 08: 3-40
[20] Tensilica Corporation [EB/OL], Available at http://www.tensilica.com/
[21] ARC International [EB/OL], Available at http://www.arc.com/
[22] Silicon Hive [EB/OL], Available at http://www.siliconhive.com/
[23] H. Corporaal, Design of Transport triggered architecture [C], Fourth Great Lakes Symposium on VLSI, 1994, 130~135
[24]言峰,基于TTA的可配置处理器研究与设计[D],上海:上海交通大学,2009.12
[25] Jizeng Wei, Wei Guo, Jizhou Sun, ect, Program Compression Based on Arithmetic Coding on Transport Triggered Architecture [C], ICESS2008, Sichuan, 2008, 126~131
[26]王勇,面向AES加密的可配置处理器设计及实现[D],天津:天津大学,2010
[27] P. Hamalainen, J. Heikkinen, M. Hannikainen, Design of transport triggered architecture processors for wireless encryption [C], 8th Euromicro Conference on Digital System Design, 2005: 144-152
[28]赵学秘,王志英,岳虹, TTA-EC:一种基于传输触发体系结构的ECC整体算法处理器[J],计算机学报,007, 30(2): 225-233
[29] D. Hankerson, A. Menezes, S. Vanstone, Guide to Elliptic Curve Cryptography [M], New York: Springer-Verlag Hall/CRC, 2004
[30]唐四云,RSA和椭圆曲线密码算法的研究[D],长沙:湖南大学,2006
[31] Gerardo Orlando, Christof Paar, A scalable gf(p) elliptic curve processor architecture for programmable hardware [C], In CHES 2001, Springer-Verlag, 2001,348-363
[32] P.L.Montgomery, Modular multiplication without trial division [C], Mathematics of Computation, 1985, 44(170):519-521
[33] Xiaohui Yang, Qin Fan, An Optimized Scalable and Unified Hardware Structure of Montgomery Multiplier [C], 2009 International Conference on E-Business and Information System Security, EBISS 2009
[34]黄伟亮,王振,黄勇,一类求模逆元的算法[J],暨南大学学报,2009, 30(1): 57-60
[35] K. Araki, I. Fujita, M. Morisue, Fast Inverters over Finite Field Based on Euclid’s Algorithm [J], Trans. IEICE, 1998, 72(11): 1230-1234
[36] T. Zhou, X. Wu, G. Bai, etc, New algorithm and fast VLSI implementation for modular inversion in galois field GF(p) [C], in Proc. IEEE Int. Conf. Commun. Circuits Syst.West Sino Expo, 2002, 2, 1491–1495
[37]刘志强,彭待渊,基于椭圆曲线加密体制的实现[J],信息安全与通信保密,2006, 04: 94-96
[38] H. Schot, H. Corporaal, Automated design of an ASIP for image processing application [C], 6th International Euro-Par Conference, 2000, 1105-1109
[39]朱礼波,基于TTA技术的多功能可配置DSP处理器设计[D],上海:上海交通大学,2008
[40] Jizeng Wei, Wei Guo, Zaifeng Shi, etc, Design and implementation of co-design toolset for Tcore processor [C], 2008 IEEE Asia Pacific Conference on Circuits and Systems, 2008, 1664-1667
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |