国密SM9中R-ate双线性对快速计算
|
摘要
R-ate是国密SM9标识密码算法中一种重要的双线性映射,其计算性能对SM9密码体制的应用至关重要。为提升R-ate双线性对的计算效率,提出一种快速计算算法。通过对BN曲线上R-ate双线性对的计算过程和其中涉及的逆运算原理进行分析,改变计算中同构映射的作用顺序,将大部分逆运算从大特征域转到小特征域,以降低逆元求解的计算损耗。以SM9的系统参数为计算实例进行实验,结果表明,该算法的运行时间低至1.8×10~5 ms。
R-ate is an important bilinear mapping in the Identity-Based Cryptography(IBC) algorithm of China state cryptography standard SM9.Its computational performance is very important to the application of SM9 cryptosystem.To improve the computational efficiency of R-ate bilinear pairing,a fast computational algorithm is proposed.By analyzing the computation process of R-ate bilinear pairing on BN curves and the involved principle of inverse operations,the order in which isomorphic mapping takes effect in computation is changed,and most of the inverse operations are transferred from the large feature domain to small feature domain to reduce the computation loss of inverse element solution.The system parameters of SM9 are taken as an example to carry out experiments.Results show that the running time of the proposed algorithm is only 1.8×10~5 ms.
R-ate is an important bilinear mapping in the Identity-Based Cryptography(IBC) algorithm of China state cryptography standard SM9.Its computational performance is very important to the application of SM9 cryptosystem.To improve the computational efficiency of R-ate bilinear pairing,a fast computational algorithm is proposed.By analyzing the computation process of R-ate bilinear pairing on BN curves and the involved principle of inverse operations,the order in which isomorphic mapping takes effect in computation is changed,and most of the inverse operations are transferred from the large feature domain to small feature domain to reduce the computation loss of inverse element solution.The system parameters of SM9 are taken as an example to carry out experiments.Results show that the running time of the proposed algorithm is only 1.8×10~5 ms.
引文
[1] DIFFIE W,HELLMAN M.New directions in cryptography[J].IEEE Transactions on Information Theory,1976,22(6):644-654.
[2] RIVEST R L,SHAMIR A,ADLEMAN L.A method for obtaining digital signatures and public-key cryptosystems[J].Communications of the ACM,1978,21(2):120-126.
[3] ELGAMAL T.A public-key cryptosystem and a signature scheme based on discrete logarithms[J].IEEE Transactions on Information Theory,1985,31(4):469-472.
[4] MILLER V S.Use of elliptic curves in cryptography[EB/OL].[2018-02-25].https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.
[5] SHAMIR A.Identity-based cryptosystems and signature schemes[J].Lecture Notes in Computer Science,1985,196(2):47-53.
[6] OHGISHI K,SAKAI R,KASAHARA M.Elliptic curve signature scheme with no y coordinate[C]//Proceedings of SCIS’99.Washington D.C.,USA:IEEE Press,1999:285-287.
[7] BONEH D,FRANKLIN M.Identity-based encryption from the weil pairing[J].Journal on Computing Archive,2003,32(3):586-615.
[8] SAKAI R,OHGISHI K,KASAHARA M.Cryptosystems based on pairing[C]//Proceedings of 2000 Symposium on Cryptography and Information Security.Washington D.C.,USA:IEEE Press,2000:56-60.
[9] 闻庆峰,杨文捷,张永强.SM9及其PKI在电子政务邮件系统中的应用[J].计算机应用与软件,2017,34(4):105-109.
[10] 周传玉,王吉伟,李明.物联网中标识密码应用研究[J].信息安全研究,2017,3(11):1040-1044.
[11] 国家密码管理局.中华人民共和国密码行业标准:GM/T 0044.1—2016[S].北京,2016.
[12] 袁峰,程朝辉.SM9标识密码算法综述[J].信息安全研究,2016,2(11):1008-1027.
[13] 卢宇,汪学明.超椭圆曲线上Weil对的变种与计算[J].计算机工程与设计,2017,38(5):1196-1199.
[14] HESS F,SMART N P,VERCAUTEREN F.The Eta pairing revisited[J].IEEE Transactions on Information Theory,2006,52(10):4595-4602.
[15] 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.
[16] MILLER V S.The weil pairing and its efficient calculation[J].Journal of Cryptology,2004,17(4):235-261.
[17] 苏志图.双线性对的快速计算研究[D].西安:西安电子科技大学,2012.
[18] 赵昌安.双线性对的有效计算[D].广州:中山大学,2008.
[19] 赵昌安,张方国.双线性对有效计算研究进展[J].软件学报,2009,20(11):3001-3009.
[20] 李彬,王新梅.高效的R-ate对的参数构造方法[J].通信学报,2010,31(1):118-121.
[21] BARRETO P S L M,NAEHRIG M.Pairing-friendly elliptic curves of prime order[C]//Proceedings of International Workshop on Selected Areas in Crypto-graphy.Berlin,Germany:Springer,2005:319-331.
[2] RIVEST R L,SHAMIR A,ADLEMAN L.A method for obtaining digital signatures and public-key cryptosystems[J].Communications of the ACM,1978,21(2):120-126.
[3] ELGAMAL T.A public-key cryptosystem and a signature scheme based on discrete logarithms[J].IEEE Transactions on Information Theory,1985,31(4):469-472.
[4] MILLER V S.Use of elliptic curves in cryptography[EB/OL].[2018-02-25].https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.
[5] SHAMIR A.Identity-based cryptosystems and signature schemes[J].Lecture Notes in Computer Science,1985,196(2):47-53.
[6] OHGISHI K,SAKAI R,KASAHARA M.Elliptic curve signature scheme with no y coordinate[C]//Proceedings of SCIS’99.Washington D.C.,USA:IEEE Press,1999:285-287.
[7] BONEH D,FRANKLIN M.Identity-based encryption from the weil pairing[J].Journal on Computing Archive,2003,32(3):586-615.
[8] SAKAI R,OHGISHI K,KASAHARA M.Cryptosystems based on pairing[C]//Proceedings of 2000 Symposium on Cryptography and Information Security.Washington D.C.,USA:IEEE Press,2000:56-60.
[9] 闻庆峰,杨文捷,张永强.SM9及其PKI在电子政务邮件系统中的应用[J].计算机应用与软件,2017,34(4):105-109.
[10] 周传玉,王吉伟,李明.物联网中标识密码应用研究[J].信息安全研究,2017,3(11):1040-1044.
[11] 国家密码管理局.中华人民共和国密码行业标准:GM/T 0044.1—2016[S].北京,2016.
[12] 袁峰,程朝辉.SM9标识密码算法综述[J].信息安全研究,2016,2(11):1008-1027.
[13] 卢宇,汪学明.超椭圆曲线上Weil对的变种与计算[J].计算机工程与设计,2017,38(5):1196-1199.
[14] HESS F,SMART N P,VERCAUTEREN F.The Eta pairing revisited[J].IEEE Transactions on Information Theory,2006,52(10):4595-4602.
[15] 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.
[16] MILLER V S.The weil pairing and its efficient calculation[J].Journal of Cryptology,2004,17(4):235-261.
[17] 苏志图.双线性对的快速计算研究[D].西安:西安电子科技大学,2012.
[18] 赵昌安.双线性对的有效计算[D].广州:中山大学,2008.
[19] 赵昌安,张方国.双线性对有效计算研究进展[J].软件学报,2009,20(11):3001-3009.
[20] 李彬,王新梅.高效的R-ate对的参数构造方法[J].通信学报,2010,31(1):118-121.
[21] BARRETO P S L M,NAEHRIG M.Pairing-friendly elliptic curves of prime order[C]//Proceedings of International Workshop on Selected Areas in Crypto-graphy.Berlin,Germany:Springer,2005:319-331.