基于Pell型序列的快速安全标量乘算法
|
摘要
提出了一种新的椭圆曲线快速安全的标量乘算法。利用佩尔序列前后项分割比产生新的佩尔型点加-倍点链(Pell Type Double-and-Add Chain,PTDAC),其循环固定的"倍点-点加"操作可天然抵抗简单能量分析(Simple Power Analysis,SPA)攻击。PTDAC算法结合Edwards椭圆曲线可从底层域减少运算时间,进一步优化算法。经过理论分析和仿真实验表明,PTDAC算法在最优情况下比EAC-270和GRAC-258算法在时间效率上分别提高了2.6%和22.8%。
A new fast and secure elliptic curve scalar multiplication algorithm is presented. The method utilizes the front and back ratio coefficient of Pell sequence to produce new Pell Type Double-and-Add Chain(PTDAC), its circulation fixed on simple operation like"double-and-addition", which can be natural resistance to Simple Power Analysis(SPA)attack. PTDAC algorithm combined with Edwards elliptic curve can reduce the underlying operation time. Theoretical analysis and simulation experiments show that the PTDAC algorithm is 2.6% faster than the Euclid Addition Chain(EAC), and 22.8% faster than the Golden Ratio Addition Chain(GRAC).
A new fast and secure elliptic curve scalar multiplication algorithm is presented. The method utilizes the front and back ratio coefficient of Pell sequence to produce new Pell Type Double-and-Add Chain(PTDAC), its circulation fixed on simple operation like"double-and-addition", which can be natural resistance to Simple Power Analysis(SPA)attack. PTDAC algorithm combined with Edwards elliptic curve can reduce the underlying operation time. Theoretical analysis and simulation experiments show that the PTDAC algorithm is 2.6% faster than the Euclid Addition Chain(EAC), and 22.8% faster than the Golden Ratio Addition Chain(GRAC).
引文
[1]Koblitz N.Elliiptic curve cryptosystems[J].Mathematics of Computation,1987,48:203-209.
[2]Miller V S.Uses of elliptic curve in cryptography[C]//LNCS 218:Advances in Cryptography.Berlin:SpringerVerlag,1985:417-426.
[3]Hankerson D,Menezes A,Vanstone S.Guide to elliptic curve cryptography[M].Berlin:Springer-Verlag,2004.
[4]Kocher P C.Timing attacks on implementations of DiffieHellman,RSA,DSS,and other systems[C]//Advances in Cryptology.Berlin:Springer,1996:104-113.
[5]Liu S,Qi G,Wang X A.Fast and secure elliptic curve scalar multiplication algorithm based on a kind of deformed Fibonacci-type series[C]//2016 International Conference on P2P,Parallel,Grid,Cloud and Internet Computing,2016:398-402.
[6]Sasdrich P.Implementing Curve25519 for side-channelprotected elliptic curve cryptography[M].ACM Transactions on Reconfigurable Technology and Systems,2015,9(1):3.
[7]Kocher P,Jaffe J,Jun B.Differential power analysis[C]//Proceedings of the 19th Annual International Conference on Cryptology,1999:388-397.
[8]李忠.抗SPA攻击的快速标量乘法[J].计算机科学,2014,41(S1):374-376.
[9]Goundar R R,Shiota K I,Toyonaga M.SPA resistant scalar multiplication using golden ratio addition chain method[J].IAENG International Journal of Applied Mathematics,2008,38(2):83-88.
[10]Ping N C,Costello C,Smith B.Fast,uniform,and compact scalar multiplication for elliptic curves and genus2 Jacobians with applications to signature schemes[J].arXiv:1510.03174,2015.
[11]Edwards H.A normal form for elliptic curves[J].Bulletin of the American Mathematical Society,2007,44(3):393-423.
[12]Panchbhai M M,Ghodeswar U S.Implementation of point addition&point doubling for elliptic curve[C]//2015International Conference on Communications and Signal Processing,2015:746-749.
[13]Bernstein D J,Lange T.Inverted Edwards coordinates[C]//LNCS 4851:International Symposium on Applied Algebra,Algebraic Algorithms,and Error-Correcting Codes.Berlin:Springer,2007:20-27.
[14]Bernstein D J,Birkner P,Joye M,et al.Twisted Edwards curves[C]//LNCS 5023:the 1st International Conference on Cryptology in Africa.Berlin:Springer,2008:389-405.
[15]Hisil H,Wong K K-H,Carter G,et al.Twisted Edwards curves revisited[C]//LNCS 5350:International Conference on the Theory and Application of Cryptology and Information Security.Heidelberg:Springer,2008:326-343.
[16]Mao D,Chen C,Xie D.Point compression schemes on twisted Edwards curves[C]//2010 International Conference on Computer Design and Applications,2010:474-478.
[17]丁红发,彭长根,杨震,等.二进制Edwards曲线上的点压缩算法[J].贵州大学学报(自然版),2012,29(3):55-58.
[18]张海灵.椭圆曲线标量乘快速算法的研究与设计[D].江苏扬州:扬州大学,2011.
[19]Rasmi M,Mimi H,Sharif M,et al.Evaluating composite EC operations and their applicability to the on-the-fly and non-window multiplication methods[J].International Journal of Computer Applications,2015,115(1):2099-2103.
[20]陈景润.组合数学简介[M].天津:天津科学技术出版社,1983.
[21]叶世绮.广义Fibonacci数列[J].数学的实践与认识,1992(1):37-49.
[22]周学松.Pell序列和Lucas序列的性质[J].华东交通大学学报,2003,20(4):117-120.
[23]Nicolas M.New point addition formulae for ECC applications[C]//LNCS 4547:International Workshop on the Arithmetic of Finite Fields.Berlin:Springer-Verlag,2007:189-201.
[24]Dou Y,Weng J,Ma C,et al.Secure and efficient ECCspeeding up algorithms for wireless sensor networks[J].Soft Computing,2017,21(19):5665-5673.
[2]Miller V S.Uses of elliptic curve in cryptography[C]//LNCS 218:Advances in Cryptography.Berlin:SpringerVerlag,1985:417-426.
[3]Hankerson D,Menezes A,Vanstone S.Guide to elliptic curve cryptography[M].Berlin:Springer-Verlag,2004.
[4]Kocher P C.Timing attacks on implementations of DiffieHellman,RSA,DSS,and other systems[C]//Advances in Cryptology.Berlin:Springer,1996:104-113.
[5]Liu S,Qi G,Wang X A.Fast and secure elliptic curve scalar multiplication algorithm based on a kind of deformed Fibonacci-type series[C]//2016 International Conference on P2P,Parallel,Grid,Cloud and Internet Computing,2016:398-402.
[6]Sasdrich P.Implementing Curve25519 for side-channelprotected elliptic curve cryptography[M].ACM Transactions on Reconfigurable Technology and Systems,2015,9(1):3.
[7]Kocher P,Jaffe J,Jun B.Differential power analysis[C]//Proceedings of the 19th Annual International Conference on Cryptology,1999:388-397.
[8]李忠.抗SPA攻击的快速标量乘法[J].计算机科学,2014,41(S1):374-376.
[9]Goundar R R,Shiota K I,Toyonaga M.SPA resistant scalar multiplication using golden ratio addition chain method[J].IAENG International Journal of Applied Mathematics,2008,38(2):83-88.
[10]Ping N C,Costello C,Smith B.Fast,uniform,and compact scalar multiplication for elliptic curves and genus2 Jacobians with applications to signature schemes[J].arXiv:1510.03174,2015.
[11]Edwards H.A normal form for elliptic curves[J].Bulletin of the American Mathematical Society,2007,44(3):393-423.
[12]Panchbhai M M,Ghodeswar U S.Implementation of point addition&point doubling for elliptic curve[C]//2015International Conference on Communications and Signal Processing,2015:746-749.
[13]Bernstein D J,Lange T.Inverted Edwards coordinates[C]//LNCS 4851:International Symposium on Applied Algebra,Algebraic Algorithms,and Error-Correcting Codes.Berlin:Springer,2007:20-27.
[14]Bernstein D J,Birkner P,Joye M,et al.Twisted Edwards curves[C]//LNCS 5023:the 1st International Conference on Cryptology in Africa.Berlin:Springer,2008:389-405.
[15]Hisil H,Wong K K-H,Carter G,et al.Twisted Edwards curves revisited[C]//LNCS 5350:International Conference on the Theory and Application of Cryptology and Information Security.Heidelberg:Springer,2008:326-343.
[16]Mao D,Chen C,Xie D.Point compression schemes on twisted Edwards curves[C]//2010 International Conference on Computer Design and Applications,2010:474-478.
[17]丁红发,彭长根,杨震,等.二进制Edwards曲线上的点压缩算法[J].贵州大学学报(自然版),2012,29(3):55-58.
[18]张海灵.椭圆曲线标量乘快速算法的研究与设计[D].江苏扬州:扬州大学,2011.
[19]Rasmi M,Mimi H,Sharif M,et al.Evaluating composite EC operations and their applicability to the on-the-fly and non-window multiplication methods[J].International Journal of Computer Applications,2015,115(1):2099-2103.
[20]陈景润.组合数学简介[M].天津:天津科学技术出版社,1983.
[21]叶世绮.广义Fibonacci数列[J].数学的实践与认识,1992(1):37-49.
[22]周学松.Pell序列和Lucas序列的性质[J].华东交通大学学报,2003,20(4):117-120.
[23]Nicolas M.New point addition formulae for ECC applications[C]//LNCS 4547:International Workshop on the Arithmetic of Finite Fields.Berlin:Springer-Verlag,2007:189-201.
[24]Dou Y,Weng J,Ma C,et al.Secure and efficient ECCspeeding up algorithms for wireless sensor networks[J].Soft Computing,2017,21(19):5665-5673.