论文部分内容阅读
椭圆曲线公钥密码学基于椭圆曲线离散对数难题。由于一般椭圆曲线上的椭圆曲线离散对数难题没有亚指数时间的攻击算法,所以椭圆曲线比RSA等其他公钥密钥体制的密钥短。国际上已提出一些椭圆曲线密码标准,如FIPS186-2, ANSI X9.62, IEEE P1363。我国为了满足电子认证服务系统等应用需求,也发布了SM2椭圆曲线公钥密码算法标准。椭圆曲线密码系统得到越来越广泛的应用,主要在受限的环境中,如智能卡、芯片等。在椭圆曲线密码应用过程中,最费时的是标量乘算法。我们主要研究了降低标量表示的Hamming重量来提高无预计算的标量乘算法的速度,得到了以下结果。一、在标量的双基链表示中,我们改进了传统的贪心算法,提出了利用靠近直线搜索的算法,提高了计算双基链的效率,降低了标量表示的Hamming重量。进而,利用靠近平面的搜索,提高三基贪心算法计算三基链的效率。二、我们提出了add/sub三基转换算法。使用基底为{2,3,5}的该算法产生三基链的密度为1/5.61426,是现有算法中密度最小的。利用该三基链计算标量乘的速度也是最快的。其重编码过程迅速、有效,且该算法非常适合软件实现。三、在理论上,我们分析三基系统固有的展开长度。给出了整数(?)的基底为{2,3,5}的最短三基展开长度的上界为并且证明了存在无穷多个整数(?),其基底为{2,3,5}的最短三基展开长度大于或者等于其中c是一个正常数。这表明我们给出的上界接近最好上界。有些环境的加密过程是可以被检测的,因此,就要求能够抵抗简单能量攻击的标量乘算法。Montgomery算法能够抵抗简单能量攻击,这方面的主要成果有:一、我们给出了新的素域上的点加和倍点公式改进了素域上的椭圆曲线Montgomery算法,提高了Montgomery算法的效率。二、我们给出了特征3域上的新的点加和倍点公式改进了特征3域上的椭圆曲线Montgomery算法,提高了Montgomery算法计算标量乘的速度。椭圆曲线签名协议的验证过程,需要计算多标量乘。我们首次提出了联合三基链的概念。由于三基系统的稀疏性,我们提出了联合三基算法计算联合三基链来提高多标量乘算法的效率。在使用相同个数预计算点的情况下,该联合三基表示的Hamming重量是已知表示中最小的。利用该三基表示计算多标量乘的速度也是最快的。基于身份的加密协议一般要求从字符串到椭圆曲线的映射为散列函数。这方面的成果主要有:一、我们构造了从有限域到twisted Edwards曲线的确定性的散列函数。二、我们构造了四种从有限域到Montgomery形式椭圆曲线的散列函数,并基于这些映射构造了与随机谕言不可区分的函数。三、我们利用开立方根的方法构造了从字符串到C34曲线的散列函数,并在此基础上,构造了与随机谕言不可区分的函数。以上的这三个工作为椭圆曲线及C34曲线上实现基于身份的加密奠定了基础。