一类j=0超奇异椭圆曲线的性质及其标量乘算法

doi:10.3969/j.issn.0372-2112.2018.09.013

电子学报 ›› 2018, Vol. 46 ›› Issue (9): 2131-2138.DOI: 10.3969/j.issn.0372-2112.2018.09.013

一类j=0超奇异椭圆曲线的性质及其标量乘算法

翁江¹, 康晓春², 豆允旗³, 马传贵⁴

1. 空军工程大学信息与导航学院, 陕西西安 710077;
2. 中国传媒大学信息工程学院, 北京 100024;
3. 数学工程与先进计算国家重点实验室, 河南郑州, 450001;
4. 陆军航空兵学院基础部, 北京 101123

收稿日期:2016-09-19 修回日期:2018-05-10 出版日期:2018-09-25
- 通讯作者:
- 马传贵
- 作者简介:
- 翁江男,1986年3月出生,陕西西安人.现为空军工程大学信息与导航学院讲师,主要研究方向为网络密码和椭圆曲线密码.E-mail:wengjiang858@163.com;康晓春 女,1989年4月出生,河南商丘人.现为中国传媒大学硕士研究生.主要从事信息安全方面的研究.E-mail:kangxiaochun0585@khtsc.com.cn;豆允旗 男,1987年8月出生,河南商丘人.2017年毕业于信息工程大学,获得博士学位.研究方向为椭圆曲线密码学.E-mail:douyunqi@126.com
- 基金资助:
- 国家自然科学基金项目 (No.61379150）; 数学工程与先进计算国家重点实验室开放基金课题 (No.2016A02）; 河南省重点科技攻关计划项目 (No.122102210126，No.092101210502）

Property and Scalar Multiplication Algorithm on Supersingular Elliptic Curves with j Invariant 0

WENG Jiang¹, KANG Xiao-chun², DOU Yun-qi³, MA Chuan-gui⁴

1.Information and Navigation College, Air Force Engineering University, Xi'an, Shaanxi 710077, China;
2.Information Engineering School, Communication University of China, Beijing 100024, China;
3.State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou, Henan 450001, China;
4.Department of Basic, Army Aviation Institution, Beijing 101123 China

Received:2016-09-19 Revised:2018-05-10 Online:2018-09-25 Published:2018-09-25
- Corresponding author:
- MA Chuan-gui
- Supported by:
- National Natural Science Foundation of China (No.61379150); Subject supported by Open Fund of State Key Laboratory of Mathematical Engineering and Advanced Computing (No.2016A02); Key Technology Research and Development Program of Henan Province (No.122102210126, No.092101210502)

摘要/Abstract

摘要： 针对非超奇异椭圆曲线上的标量乘算法已经有比较多的研究.与非超奇异曲线不同，超奇异椭圆曲线的自同态环是四元数代数的一个序模，为非交换环.本文主要针对特征大于3的有限域上一类j不变量为0的超奇异椭圆曲线，分析了曲线自同态环及其商环的结构.进而研究了此类曲线上整数表示的性质，并基于这种表示方法提出了一种针对此类曲线的标量乘算法.理论上证明了针对此类超奇异曲线，当选择合适系数集合时，此表示实质上为p-adic展开.实验结果表明：相较于4-NAF等方法，p-adic表示方法提高标量乘效率一倍以上.

关键词: 超奇异椭圆曲线, 四元数代数, 自同态环, Frobenius自同态, τ-adic展开

Abstract: The scalar multiplication algorithms for non-supersingular elliptic curves have been widely studied. In contrast, the endomorphism ring of supersingular elliptic curve is an order in a definite quaternion algebra, which is not commutative. This paper focuses on a class of supersingular elliptic curves of j-invariant zero in characteristic greater than 3. We make analysis of the structures of its endomorphism ring and quotient ring. Further we study the properties of integer expansion according to this class of curves. Based on this representation, a scalar multiplication algorithm is proposed. We demonstrate that the representation is essentially the p-adic expansion in theory when a suitable digit set is chosen. The experimental results show that compared with the method of 4-NAF, the p-adic method improves the efficiency of scalar multiplication of more than 100%.

Key words: supersingular elliptic curve, quaternion algebra, endomorphism ring, Frobenius endomorphism, τ-adic expansion

中图分类号:

TP309

翁江, 康晓春, 豆允旗, 等. 一类j=0超奇异椭圆曲线的性质及其标量乘算法[J]. 电子学报, 2018, 46(9): 2131-2138.

WENG Jiang, KANG Xiao-chun, DOU Yun-qi, et al. Property and Scalar Multiplication Algorithm on Supersingular Elliptic Curves with j Invariant 0[J]. Acta Electronica Sinica, 2018, 46(9): 2131-2138.

参考文献

[1] Joye M,Yen S M.Optimal left-to-right binary signed-digit recoding[J].IEEE Transactions on Computers,2000,49(7):740-748.
[2] Muir J A,Stinson D R.Minimality and other properties of the width-w nonadjacent form[J].Mathematics of computation,2005,75(253):369-384.
[3] Dimitrov V,Imbert L,Mishra P K.Efficient and secure elliptic curve point multiplication using double-base chains[A].ASIACRYPT 2005[C].Chennai,India:Springer,2005.59-78.
[4] Hisil H,Wong K,Carter G,Dawson E.Jacobi quartic curves Revisited[A].ACISP 2009[C].Brisbane,Australia:Springer,2009.452-468.
[5] Bernstein D J,Lange T.Faster addition and doubling on elliptic curves[A].ASIACRYPT 2007[C].Kuching,Malaysia:Springer,2007.29-50.
[6] Solinas J A.Efficient arithmetic on Koblitz curves[J].Design,Codes and Cryptography,2000,19(2):125-179.
[7] Gallant R,Lambert R,Vanstone S A.Faster point multiplication on elliptic curves with efficient endomorphisms[A].CRYPTO 2001[C].Santa Barbara,California,USA:Springer,2001.190-200.
[8] Galbraith S,Lin X,Scott M.Endomorphisms for faster elliptic curve cryptography on a large class of curves[A].EUROCRYPT 2009[C].Cologne,Germany:Springer,2009.518-635.
[9] Koblitz N.An elliptic curve implementation of the finite field digital signature algorithm[A].CRYPTO 1998[C].Santa Barbara,California,USA:Springer,1998.327-337.
[10] Blake I F,Murty V K,Xu G.Efficient algorithms for Koblitz curves over fields of characteristic three[J].Journal of Discrete Algorithms,2005,3(1):113-124.
[11] Avanzi R M,Heuberger C,Prodinger H.Redundant τ-adic expansions I:Non-adjacentdigit sets and their applications to scalar multiplication[J].Designs,Codes and Cryptography,2011,58(2):173-202.
[12] Heuberger C.Redundant τ-adic expansions Ⅱ:Non-optimality and chaotic behavior[J].Mathematics in Computer Science,2010,3(2):141-157.
[13] Avanzi R M,Heuberger C,Prodinger H.Arithmetic of Supersingular Koblitz Curves in Characteristic Three[OL].https://eprint.iacr.org/2010/436.pdf,2016-07-29.
[14] Avanzi R,Heuberger C.Faster and lower memory scalar multiplication on supersingular curves in characteristic three[A].PKC 2011[C].Taormina,Italy:Springer,2011.109-127.
[15] Kleinrahm A.Arithmetic of subfield elliptic curves in small characteristic[D].Bochum,Germany:Ruhr-Universitat Bochum,2011.
[16] Heuberger C,Mazzoli M.Symmetric digit sets for elliptic curve scalar multiplication without precomputation[J].Theoretical Computer Science,2014,547(1):18-33.
[17] Silverman J H.The Arithmetic of Elliptic Curves (Graduate Texts in Mathematics)[M].2 Ed.New York:Springer,2009.
[18] Washington L C.Elliptic Curves:Number Theory and Cryptography[M].New York:Chapman & Hall/CRC,2008.
[19] Murty M R,Esmonde J.Problems in Algebraic Number Theory (Graduate Texts in Mathematics 190)[M].2 Ed.New York:Springer,2005.
[20] Ireland K,Rosen M.A classical introduction to modern number theory (Graduate Texts in Mathematics 84)[M].New York:Springer,1990.
[21] The Magma Development Team.MAGMA Computational Algebra System[EB/OL].http://magma.maths.usyd.edu.au/magma,2016-06-18.
[22] Bernstein D J,Lange T.Explicit-formulas database[EB/OL].http://hyperelliptic.org/EFD,2016-06-18.
[23] Mishra P K,Dimitrov V.Efficient quintuple formulas for elliptic curves and efficient scalar multiplication using multibase number representation[A].ISC 2007[C].Valparaíso,Chile:Springer,2007.390-406.

一类j=0超奇异椭圆曲线的性质及其标量乘算法

Property and Scalar Multiplication Algorithm on Supersingular Elliptic Curves with j Invariant 0

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	宋昭阳, 王一诺, 王浩文, 马鸿洋. 基于Hopfield网络“伪吸引子”与交替量子随机行走的抗攻击彩色图像加密方案[J]. 电子学报, 2023, (): 1-13.
[2]	曾卓, 汪成亮, 马飞. 基于差分隐私的活动模式保护与时空轨迹发布方法[J]. 电子学报, 2023, 51(3): 552-563.
[3]	赵开强, 康萍, 刘彬, 郭真, 冯朝胜, 卿昱. 支持云代理重加密的CP-ABE方案[J]. 电子学报, 2023, 51(3): 728-735.
[4]	张丹丹, 宋亚飞, 刘曙. MalMKNet：一种用于恶意代码分类的多尺度卷积神经网络[J]. 电子学报, 2023, (): 1-11.
[5]	唐飞, 冯卓, 黄永洪. 基于区块链的公平可验证数据持有方案[J]. 电子学报, 2023, 51(2): 406-415.
[6]	郭庆, 田有亮, 万良. 基于代理重加密的区块链数据受控共享方案[J]. 电子学报, 2023, 51(2): 477-488.
[7]	王经纬, 吴静雯, 殷新春. 抗共谋攻击的多授权电子健康记录共享方案[J]. 电子学报, 2023, (): 1-8.
[8]	王硕, 王坚, 王亚男, 宋亚飞. 一种基于特征融合的恶意代码快速检测方法[J]. 电子学报, 2023, 51(1): 57-66.
[9]	田晖, 严艳, 汤莉莉, 吴俊彦, 王慧东, 全韩彧. 基于分数基音延迟动态搜索的语音隐写算法[J]. 电子学报, 2023, 51(1): 67-75.
[10]	李顺东, 赵雪玲, 家珠亮. 集合交集元素和的保密计算[J]. 电子学报, 2023, 51(1): 86-92.
[11]	轩勃娜, 李进. 基于改进CNN的恶意软件分类方法[J]. 电子学报, 2022, (): 1-11.
[12]	郑锐, 汪秋云, 林卓庞, 靖蓉琦, 姜政伟, 傅建明, 汪姝玮. 一种基于威胁情报层次特征集成的挖矿恶意软件检测方法[J]. 电子学报, 2022, 50(11): 2707-2715.
[13]	任正伟, 李雪婷, 王丽娜, 童言, 徐士伟, 丁炜. 云存储中外包数据确定性删除研究综述[J]. 电子学报, 2022, 50(10): 2542-2560.
[14]	蔡莹, 朱翔, 王舰, 李昊远, 韩建伟. 基于激光注入的FPGA加密防护设计验证研究[J]. 电子学报, 2022, 50(10): 2381-2386.
[15]	徐明, 胡沐宇. 窃听信道下基于双分簇技术的信源安全有损传输[J]. 电子学报, 2022, 50(9): 2196-2204.