椭圆曲线快速点乘算法优化.PDF

第２９卷第８期 计 算 机 应 用 研 究 Ｖｏｌ．２９Ｎｏ．８ ２０１２年８月　 ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ Ａｕｇ．２０１２ 椭圆曲线快速点乘算法优化 周　梦，周海波 （北京航空航天大学　数学与系统科学学院，北京 １００１９１） 摘　要：转换乘法为平方运算，是一种快速计算椭圆曲线密码点乘的代数方法。利用此方法，提出了素域Ｆ上 ｐ ｋ 雅可比坐标系下的３Ｐ和３Ｐ算法，其运算量分别为６［Ｍ］＋１０［Ｓ］和（６ｋ）［Ｍ］＋（１０ｋ）［Ｓ］，与已有的最好算法 ｋ 相比，算法效率分别提升了１１．８％和 １０．５％。另外，还在文献［１，２］基础上，对素域Ｆ上仿射坐标系下的２Ｐ ｐ ｋ 和３Ｐ的算法进行了改进，其算法效率比文献［１，２］分别提高了６．３％和３．３％。 关键词：椭圆曲线密码体制；点乘；仿射坐标；雅可比坐标；乘法 中图分类号：ＴＰ３０９　　　文献标志码：Ａ　　　文章编号：１００１３６９５（２０１２）０８３０５６０３ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１３６９５．２０１２．０８．０６６ Ｏｐｔｉｍｉｚｉｎｇｆａｓｔｓｃａｌａｒｍｕｌｔｉｐｌｉｃａｔｉｏｎｉｎｅｌｌｉｐｔｉｃｃｕｒｖｅｓ ＺＨＯＵＭｅｎｇ，ＺＨＯＵＨａｉｂｏ （ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃｓ＆ＳｙｓｔｅｍＳｃｉｅｎｃｅ，ＢｅｉｈａｎｇＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１００１９１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｒａｄｉｎｇｆｉｅｌｄｍｕｌｔｉｐｌｉｃａｔｉｏｎｓｆｏｒｆｉｅｌｄｓｑｕａｒｉｎｇｉｓａｎａｌｇｅｂｒａｉｃｍｅｔｈｏｄｔｏｉｍｐｒｏｖｅｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆｓｃａｌａｒｍｕｌｔｉｐｌｉ ｋ ｃａｔｉｏｎｉｎＥＣＣ．Ｔｈｉｓｐａｐｅｒｇａｖｅｔｈｅａｌｇｏｒｉｔｈｍｓｏｆ３Ｐａｎｄ３ＰｏｖｅｒＦｉｎｔｅｒｍｓｏｆＪａｃｏｂｉａｎｃｏｏｒｄｉｎａｔｅｓ．Ａｎｄｔｈｅｉｒｃｏｍｐｕｔａｔｉｏｎａｌ ｐ ｃｏｍｐｌｅｘｉｔｙｗｅｒｅ６［Ｍ］＋１０［Ｓ］ａｎｄ（６ｋ）［Ｍ］＋（１０ｋ）［Ｓ］ｒｅｓｐｅｃｔｉｖｅｌｙ，ｗｈｉｃｈｗａｓｉｍｐｒｏｖｅｄｔｏ１１．８％ａｎｄ１０．５％ｒｅｓｐｅｃ ｋ ｋ ｔｉｖｅｌｙｔｈａｎｔｈｅｂｅｓｔａｌｇｏｒｉｔｈｍｓａｔｐｒｅｓｅｎｔ．Ｉｎａｄｄｉｔｉｏｎ，ｔｈｉｓｐａｐｅｒｉｍｐｒｏｖｅｄｔｈｅａｌｇｏｒｉｔｈｍｓｏｆ２Ｐａｎｄ３ＰｏｖｅｒＦｉｎｔｅｒｍｓｏｆ ｐ ａｆｆｉｎｅｃｏ