基于250位模乘平台的Tate对最终模幂算法的改进

doi:10.3969/j.issn.1006-2475.2014.02.043

计算机与现代化

基于250位模乘平台的Tate对最终模幂算法的改进

（同济大学电子与信息工程学院，上海 201804）

收稿日期:2013-09-05 出版日期:2014-02-14 发布日期:2014-02-14
作者简介:王晓静(1988-)，男，上海人，同济大学电子与信息工程学院硕士研究生，研究方向：加密算法，智能卡。

Improvement of Final Modular Exponentiation Algorithm in Tate Pairing Based on 250 Bits Modular Multiplication Platform

(School of Electronics and Information Engineering, Tongji University, Shanghai 201804, China)

Received:2013-09-05 Online:2014-02-14 Published:2014-02-14

摘要/Abstract

摘要： 在只支持250 bits模乘的硬件平台上，实现457 bits的二元扩域Tate对Miller算法的（双线性对的一种）最终模幂运算。在计算过程中采用一种改进的Montgomery模乘算法和中国剩余定理算法。通过具体数据实现双线性对最终模幂的运算，使用数学软件Sage来验证这种改进方案的正确性。通过理论分析和数据计算可以证明使用该方案可实现457 bits最终模幂。

关键词: Montgomery算法, Miller算法, 模幂, 中国剩余定理, 模乘

Abstract: The purpose of this article is to realize the 457 bits final modular exponentiation in the Tate pairing Miller algorithm (one kind of bilinear pairings) of binary extension field on the hardware platform which only supports 250 bits modular multiplication. In the procedure of calculation, we adopted an improved Montgomery modular multiplication algorithm and Chinese remainder theorem algorithm. The final modular exponentiation will be realized with definite data, and we will use the mathematical software Sage to verify the improved scheme. So we can prove that this scheme can realize the 457 bits final modular exponentiation through theory analysis and data calculation.

Key words: Montgomery algorithm, Miller algorithm, modular exponentiation, Chinese remainder theorem, modular multiplication

中图分类号:

TP309

王晓静. 基于250位模乘平台的Tate对最终模幂算法的改进[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2014.02.043.

WANG Xiao-jing.

Improvement of Final Modular Exponentiation Algorithm in Tate Pairing Based on 250 Bits Modular Multiplication Platform

[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2014.02.043.

参考文献 14

[1]	Miller V S. Short Programs for Functions on Curves[DB/OL]. http://crypto.stanford.edu/miller/miller.pdf, 1986-05-06.
[2]	Joux A. A one round protocol for tripartite Diffie-Hellman[C]// Proceedings of the 4th International Symposium on Algorithmic Number Theory. 2000:385-394.
[3]	赵昌安,张方国. 双线性对有效计算研究进展[J]. 软件学报, 2009,20(11):3001-3009.
[4]	Boneh D, Franklin M K. Identity-based encryption from the Weil pairing[C]// Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology. 2001:213-229.
[5]	Hess F, Smart N P, Vercauteren F. The Eta pairing revisited[J]. IEEE Transactions on Information Theory, 2006,52(10):4595-4602.
[6]	Zhao C, Zhang F, Huang J. A note on theAte pairing[J]. International Journal of Information Security, 2008,7(6):379-382.
[7]	Alfred Menezes, Scott Vanstone, Tatsuaki Okamoto. Reducing elliptic curve logarithms to logarithms in a finite field[C]// Proceedings of the 23rd Annual ACM Symposium on Theory of Computing. 1991:80-89.
[8]	Jean-Claude Bajard, Laurent Imbert, Graham A Jullien, et al. A CRT-based Montgomery Multiplication for Finite Fields of Small Characteristic[DB/OL]. http://hal.archives-ouvertes.fr/docs/00/10/64/55/pdf/d512.pdf, 2005-07-15.
[9]	Wang Mao-cai, Hu Han-ping, Dai Guang-ming. An efficient algorithms for Tate pairing computation[J]. Journal of Communication and Computer, 2007,4(8):20-23.
[10]	Alfred Menezes. An Introduction to Pairing-based Cryptography[DB/OL]. http://cacr.uwaterloo.ca/~ajmeneze/publications/pairings.pdf, 2008-12-20.
[11]	Soonhak Kwon. Efficient Tate pairing computation for supersingular elliptic curves over binary fields[C]// Proceedings of the 10th Australasian Conference on Information Security and Privacy. 2005:134-145.
[12]	McCusker K, O’Connor N, Diamond D. Low-energy finite field arithmetic primitives for implementing security in wireless sensor networks[C]// Proceedings of the 2006 International Conference on Communications, Circuit and Systems. 2006,3:1537-1541.
[13]	Darrel Hankerson, Alfred Menezes, Scott Vanstone. 椭圆曲线密码学导论[M]. 张焕国译. 北京:电子工业出版社, 2005:55.
[14]	Henri Cohen, Gerhard Frey, Roberto Avanzi, et al. Handbook of Elliptic and Hyperelliptic Curve Cryptography[M]. Chapman & Hall/CRC, 2006:196.

基于250位模乘平台的Tate对最终模幂算法的改进

Improvement of Final Modular Exponentiation Algorithm in Tate Pairing Based on 250 Bits Modular Multiplication Platform

可视化

摘要/Abstract

引用本文

使用本文

参考文献 14

相关文章 1

编辑推荐

Metrics

本文评价