论文部分内容阅读
自从公钥密码体制被提出以来,它就被广泛用于许多实用密码系统中,比如密钥协商、身份认证、数据完整性保护、数字签名、电子选举、电子商务、电子政务等等。特别以CA和证书为支撑的PKI更是成为构建大型安全网络所必须的基础设施。目前在实际中使用最为广泛的公钥算法是RSA。 椭圆曲线密码制(ECC)是1985提出的新公钥体制,由于在保证相同安全强度下其所需的密钥长度较RSA的短,而特别适用于无线系统或者存储受限的设备。在许多安全标准中,如IPsec、WAPI、WPKI等等,都已经将其采用。在不远的将来ECC会成为应用标准中的首选算法。 在ECC的快速实现中,最关键的就是标量乘kP的计算,其中k为一个大整数而P为椭圆曲线上的一个点。因此,标量乘的快速算法研究成为了许多密码学家关心的问题,并取得了相当多的不错的成果。在前人成果的基础上,本文主要做了以下的工作: 1.基于NAF分解,我们提出了一种新的方法,以任意的正整数w而不仅仅是2为基来表示整数k。因为它以w为基又近似NAF,我们称这种方法为w-NNAF方法。在所有以w为基的表示中,该方法的汉明重量最轻。使用k的w-NNAF表示,结合现存的一些方法,我们提出了一种计算kP的方法。 2.基于Solinas提出的RTNAF方法,我们提出了一种三比特结合的方法用以快速计算ECC中的标量乘。使用这种方法,可以以两个额外的存储为代价节省m/18个点加法。在有多余的存储的情况下,可将该方法推广到(w+1)比特结合,使得标量乘的计算复杂性可以进一步降低。最后定量分析了该方法所降低的计算复杂性。 3.提出了一种RTSNAF方法,它使用τ~2为基底而不象RTNAF方法那样使用τ来分解标量k。通过数学分析证明了该分解的存在性和唯一性。同时给出了该分解的长度和汉明密度的精确估计。最后,确定了使用该分解来计算kP的计算量为3m/14个点加法,相对RTNAF的m/3次有所改善。 4.为了加速ECC中标量乘法kP的计算,通过使用特征多项式为φ~2+2=0的自同态φ,Ciet将标量k分解为φ-NAF表示。通过对φ-NAF表示使用窗口技术,我们得到了七的φ-NAF_w分解。它能比Ciet的方法更高效的计算kP。最后,我们精确的估计了该分解的长度和汉明密度。 5.基于整数NAF(非相邻形式)表示,Solinas提出了一对整数(a,b)的JSF(联合稀疏形式)表示。由于JSF可以产生更多的双零位置,因此在计算ECC中的