APP下载

基于双基链的快速标量乘算法研究

2016-11-14武永波彭青松高茂庭

现代计算机 2016年29期

武永波,彭青松,高茂庭

(上海海事大学信息工程学院,上海 201306)

基于双基链的快速标量乘算法研究

武永波,彭青松,高茂庭

(上海海事大学信息工程学院,上海201306)

在有限域GF(2m)上,实现椭圆曲线密码体制(ECC)中关键运算是标量乘算法,该算法也是椭圆曲线密码体制中耗时最长、极易受到攻击的运算之一。为了提高椭圆曲线密码算法计算的安全性和效率性,从分析以2、3为底的双基链椭圆曲线标量乘特点出发,在现在有的双基链算法基础之上,提出一种新的快速标量乘算法。新算法中,通过应用米勒算法和2-3链相结合的方法,寻找出权重更小的双基链。此外,考虑到小权重也有其局限性。引入了技术Tate配对与2-3链相结合来提高算法效率,比基于贪心算法的双基链更加高效。经仿真实验比较分析和研究,表明该改进算法可以很好提高计算效率,并且同时能大大降低存储量。

椭圆曲线密码体制;标量乘法;双基数系统;Tate配对

0 引言

1985年,N.Koblitz和V.Miller各自独立地提出了椭圆曲线公钥密码体制 (ECC,Elliptic-Curve-Cryptographic),这是椭圆曲线理论在密码学中又一次全新的应用[1]。椭圆曲线密码体制的安全性是基于椭圆曲线上离散对数问题求解的困难性,并且目前还没有找到解决此问题的亚指数时间算法,具有一些其他公钥密码体制无法比拟的优点,例如在相同的安全强度下,具有系统参数和密钥尺寸短 (如160 bits的ECC和1024 bits的RSA具有相当的安全强度),选择机会较大等特点[2]。正因如此,十几年来,ECC一直是数学界、密码学界和计算机科学界所关注的重大课题。……

登录APP查看全文