一种二进制域非相邻表示型的生成算法

为了节约存储空间,通过分析非相邻表示型的定义与性质,提出一种二进制域基于字存储的非相邻表示型的多位生成算法。该算法将数字生成非相邻表示型的同时重点记录非零值及其在传统序列中所在位置,且将一个或多个非零值及其位置信息存储在一个存储字中,减少了存储字。结果表明,当窗口宽度为3,标量k的二进制长度为283时,存储k的非相邻表示型平均可节省75%左右的存储单元,访问内存71次。窗口宽度越大,需要的存储单元个数越少,访问内存的次数也越少。

基于二进制的相邻表示型多位生成算法研究

信息安全一直是研究热点,而椭圆曲线加密在该领域占有举足轻重的作用,椭圆曲线的标量乘又是快速实现的关键点,其中二进制数的非相邻表示型(NAF)被应用在该点运算上,通常的NAF算法是一位一位的生成相应数位,而这在时间上产生极大的浪费.为了节省运算时间,分析NAF定义与性质,提出一种基于二进制的NAF多位生成算法,一次生成多位NAF值,减少了操作次数,替换了费时运算,从而节省了运行时间.经过分析及建模验证多位生成算法较原算法时间效率提高50%左右.

NAF的二进制表示法及其算法研究

椭圆曲线加密的快速实现研究一直是该领域的研究热点,其中二进制数的非相邻表示型(NAF)因此被广泛应用,它主要应用在点乘运算,在该算法中用到的NAF是由带符号位的数字组成,所以通常采用一位一存储的方式,然而在一些存储资源有限的设备上这是极大的浪费;为了节省存储资源,提出一种NAF的二进制表示方法,这样就能将多位NAF数值按照运行平台的字长来存储,大大提高了存储资源的利用率;在此基础上给出NAF二进制表示法的算法及其点乘算法;实验结果表明该表示法的运算效率较原算法的效率没有太大的影响,尤其在点乘运算中影响更是微弱,但是在提高存储效率方面表现突出,节省存储空间达96%以上。

NAF算法的改进

椭圆曲线上的点乘运算是影响椭圆曲线加密(ECC)效率的一个关键因素。分析了普遍用于点乘算法的非相邻表示型(NAF)算法,对NAF算法和窗口宽度w的NAF算法进行了改进。减少了运算中的移位运算次数,缩短了运算时间。经分析,改进算法的运行效率是原算法效率的2/(w+1)倍,建模仿真也表明改进算法的运行时间要短于原算法的运行时间。

基于NAF_w的二进制域乘法算法

椭圆曲线上的乘法运算速度是提高椭圆曲线加密(ECC)性能的一个关键;分析了宽度w的非相邻表示型(NAF)算法和多项式乘法算法,提出了一个基于NAFw的二进制域乘法算法;算法减少了运算中的异或运算次数和预计算个数,缩短了运算时间且节省了存储空间;经建模仿真,结果表明本算法运算效率较comb多项式乘法平均快14.7%左右,预计算只需要计算2w-1-1个,从存储预计算个数和时间消耗综合考虑w=4也是较优的窗口宽度选择。

双线性对计算算法的优化

基于身份的公钥密码体制独特的优点使其成为PKI公钥密码体制后的一个新研究热点。基于身份的密码体制的实现基于双线性对的快速计算,Miller算法是一种计算线性对的有效算法。利用窗口宽度为w的NAF倍乘算法,结合Miller算法,提出一种有效提高线性对计算速度的方法,这种方法倍加中加法运算次数改进为原来的2/w。

探测窗口的NAF_ω算法

椭圆曲线上的点乘运算是椭圆曲线加密(ECC)的一个关键运算,它的速度直接影响椭圆曲线加密的速度。本文分析了窗口宽度w的非相邻表示型(NAFω)算法,根据NAF的性质提出了一个探测窗口的NAFω算法。本算法减少了运算中的移位和异或运算次数,缩短了运算时间。经建模仿真,结果表明本算法的时间消耗大约是原算法的1/(ω+1)倍,且随ω的增大运算效率也在提高。

ECC中一种点乘的快速算法在电子商务中的应用研究

SET协议一般采用DES和RSA加密算法;与RSA相比,ECC体制具有单位比特最高强度的安全性,提出了椭圆曲线密码体制ECC;在ECC的加密/解密、签名/验证签名的过程中,其核心计算是标量乘法,采用NAF(非相邻表示型)方法对标量乘法进行优化,然后将其运用到SET协议中,以提高效率。

MD5选择前缀碰撞算法的改进及复杂度分析

针对MD5选择前缀碰撞算法在实际应用时复杂度分布的失衡问题,提出了改进的MD5选择前缀碰撞算法。结合非相邻表示型(NAF),给出了生日搜索复杂度中概率值在特定条件下的推导方式,建立了平衡参数与生日搜索复杂度之间的关系;并基于上述理论结果,通过引入新的消息差分,改进了选择前缀碰撞所需的生日碰撞形式,得到改进算法。在实际应用所需的参数条件下,改进算法相对MD5算法平均可降低1比特的复杂度。分析结果表明:相对于原MD5算法,改进算法缓和了复杂度分布的失衡现象,降低了算法复杂度,更适用于实际应用。

二元扩域超奇异Koblitz曲线的标量乘计算

二元扩域超奇异Koblitz曲线是目前双线性对计算中被广泛采用的曲线。研究二元扩域超奇异Koblitz曲线上标量乘的快速实现算法。由于Koblitz曲线存在特殊的自同态映射τ,使得标量乘算法可以由"double-and-add"算法变成"τ-and-add"算法,因此可以大大提高标量乘的运算效率。基于这个思想,提出了二元扩域超奇异Koblitz曲线上基于τ的非相邻表示型TNAF(τ-adic Non-Adjacent Form)窗口标量乘的实现算法;同时,为了抵御简单功耗分析SPA(Simple Power Analysis)攻击,将TNAF算法进一步改进为规则序列TNAF算法。以窗口取4为例,在同等安全强度下,规则序列TNAF4算法的运算效率比传统的二进制规则序列NAF4标量乘算法提高50%,比传统的Montgomery标量乘算法提高23%。