素数域[GF(P)]上椭圆曲线快速标量乘算法的研究

基于求逆转换为乘法的思想,利用仿射坐标提出了直接计算椭圆曲线上[7P]的算法,该算法运算量为I+23M+10S,比现有的算法节省了一次求逆运算,同时也给出了直接计算[7kP]的快速算法,该算法比重复计算[k]次[7P]更有效。结合多基数系统将这些新算法应用到标量乘法中,实验结果表明,在NIST推荐的椭圆曲线上,新算法的效率优于徐凯平等人所提的算法及传统的ternary-binary、3-NAF、Dimitro算法,相交处I/M可降至2.4。     

基于Frobenius映射的快速标量乘算法

标量乘法的效率决定着椭圆曲线密码体制的性能,而Koblitz曲线上的快速标量乘算法是标量乘法研究的重要课题,在标量k的TNAF约简基础上,给出了一种基于Frobenius映射的上层运算：Comb算法.在预计算阶段,该算法利用Frobenius映射对宽度为r的序列计算其对应椭圆曲线上的点,从而建立预计算表,在累加赋值阶段结合约简后的TNAF（k）和预计算表来提高效率.Comb算法基于高效的Frobenius映射无须进行倍点运算,经过Comb矩阵的组合,其所需点加量是传统算法的1/5～1/4,当行数r任意时,其效率在任意坐标下比传统Comb算法提高至少67%.     

一种基于加法链的快速标量乘算法

给出一种标量的串长加法链算法来提高椭圆曲线标量乘法的效率。新的标量乘算法结合底层域直接计算2Q+P、2^nR+S算法,使用大小窗口法将串长算法和滑动窗口算法结合,加法链长度、存储空间和预计算都减少,其效率比二元法提高53%,比NAF法提高47.5%,比串长算法提高46.2%,比Windows法提高42.2%。     

基于重编码的快速标量乘算法

采用回溯法设计出一种重编码算法。该算法只需对标量序列进行一次变换、至多四个中间变量,以及只需基于比特位比较赋值操作,效率更高,利于硬件实现标量乘法,并证明了所得结果具有正则序列的性质。该算法应用到计算数字签名中常用的gP+hQ时,得到g、h的具有最小联合重量序列。     

Edwards曲线快速标量乘算法研究

标量乘法是椭圆曲线密码算法中最核心的运算,其运算速度影响着整个密码体制的实现效率。首先,详细地介绍了Edwards曲线的基本概念。其次,为了提高标量乘法的运算速度,针对椭圆曲线标量乘算法进行了研究,引入了一种可以用来计算连续倍点2◢△mP◣的算法CDA。为了提高CDA的计算效率,提出了将标量◢k◣表示为4-NNAF形式以减少◢k◣的长度,再结合CDA计算标量乘法可以有效地减少运算量。最后根据算法的运算量分析和具体例子得出,减少标量◢k◣长度后的计算效率提高了13%以上。为了进一步加快运算速度,又提出了对CDA中乘法运算和模逆运算采用并行结构来减少标量乘法的运算次数。计算结果表明,并行后的计算效率提高了36%以上。     

基于折半运算的快速双基数标量乘算法

为了提高椭圆曲线标量乘法效率,对二元域上椭圆曲线的基于双基数的标量乘法进行改进。在底层域推导出直接计算3^kP的快速算法,该算法只需一次求逆;新设计的以1/2和3为基的双基数编码可结合高效的直接计算3^kP和折半运算,基于该双基数编码的标量乘算法只涉及到点加运算、折半运算、三倍点和直接计算3^kP,底层域运算复杂性得到降低,在NIST推荐的椭圆曲线上比Dimitrov算法效率提高70%以上,比Wong方法提高10%以上。     

椭圆曲线底层域快速算法的优化

为了提高椭圆曲线底层域运算的效率,基于将乘法转换为平方运算的思想,提出在素数域[FP]上用雅克比坐标直接计算[2kP]和[3kP]的改进算法,其运算量分别为[(3k-1)M+(5k+3)S]和[(6k-1)M+(9k+3)S],与DIMITROY和周梦等人所提的算法相比,算法效率分别提升了6.25%和5%。另外,利用相同的原理,给出了素数域[FP]上用在仿射坐标系直接计算[3kP]的改进算法,其运算量为[I+(6k+1)M+(9k+1)S],与周梦和殷新春等人所提的算法相比,效率分别提升了3.4%和24%。     

椭圆曲线底层域快速算法的研究

为了提高椭圆曲线底层域运算的效率,基于将求逆转换为乘法运算的思想,提出了在素数域[FP]上用仿射坐标直接计算4P和5P的快速算法,其运算量分别为I+7M+8S和I+12M+10S,与Duc-Phong和徐凯平等人所提的算法相比,效率分别提升了4.6%和2.6%。同时在仿射坐标下给出了一种直接计算[5kP]的快速算法,其运算量为[I+(15k+1)M+][(10k-1)S],与徐凯平和Mishra等人所提的算法相比,效率分别提升了5.7%和26.8%。     

一种基于半点运算与双基表示的双标量乘算法

椭圆曲线密码体制的核心运算是标量乘法运算,在一些椭圆曲线公钥密码体制中需要计算双标量乘法。为了提高椭圆曲线双标量乘法的效率,在现有半点运算和双基表示的基础上提出了一种新的双标量表示形式,并给出基于该表示形式的双标量乘算法。该算法用快速的半点运算替代传统的倍点运算,从而有效提高了双标量乘法的效率。实验结果表明,在NIST推荐的椭圆曲线上,新算法的效率比基于双基表示的并列点乘算法大约提高了32%,比基于JSF表示的双标量乘算法提高了35%。     

椭圆曲线中一种计算7P和7kP的改进算法

为了提高椭圆曲线底层域运算的效率,基于将乘法运算转换为平方运算的思想,提出在素数域[GFP]上用仿射坐标直接计算[7P]和[7kP]的改进算法,其运算量分别为[I+18M+12S]和[I+(17k+2)M+(14k+1)S],与已有的最好算法相比,效率分别提升了8.3%和10.3%。另外,基于相同的思想给出了素数域[GFP]上用仿射坐标系直接计算[5kP]的改进算法,其运算量为[I+(9k+2)M+(14k+1)S],与徐凯平和Mishra等人所提的算法相比,效率分别提升了17.2%和35.7%。     

基于滑动窗口技术的快速标量乘法

标量乘法是椭圆曲线密码体制的核心运算,它的有效实现是近年来信息安全领域研究的一个热点内容。借 助于标量的wMOH表示思想,利用混合坐标表示下直接计算2kQ+尸的策略,改进了基于滑动窗口技术的标量乘法 算法。分析表明,所得算法效率明显提升,并降低了存储需求,能有效提升ELL的实现效率。     

两类超奇异椭圆曲线的快速标量乘法

研究了特征为2和3的域上的超奇异椭圆曲线的快速标量乘法。该两类曲线适合建立可证明安全的密码体制,利用这两类曲线的复乘性质,结合Frobenius自同态和可以简单计算的自同态,给出了一种不用预计算的快速算法,相较IEEE1363标准算法,计算效率分别提高了4倍和3倍。     

基于w-NNAF的快速Edwards曲线标量乘法

在分析利用Edwards曲线上三倍点公式计算3nP(n=1,2,...)的基础上,根据各3"P的坐标具有统一表示形式的特性,提出了一种通过减少求逆运算而快速计算3"P (n=2, 3}..)的新算法I}ripling_Algorithm,并将此算法与标量k的二NNAF表示方法相结合,给出了一种计算标量乘法kP的高效算法ImprovedSM-3-NNAF。通过对ImprovedSM-3-NNAF的计算复杂性与安全性分析表明,利用该算法计算kP不仅是安全的,而且至少可节约20. 78%的计算量,大大改进了Edwards曲线上标量乘法的计算效率。     

一个新的基于radix-4从左到右编码的标量乘算法

椭圆曲线标量乘是椭圆曲线密码系统中最关键、最耗时的运算,因此如何快速高效实现标量乘运算是研究的重点。目前常见的标量乘算法有:double-and-add算法,NAF算法,MOF算法等,但它们都是基于radix-2编码表示的,无论采用何种编码,倍点运算的次数都不变,减少的只是点加(或点减)运算的次数。提出一个基于radix-4表示的新的编码方法,并提出一个基于radix-4表示的标量乘算法,通过用四倍点运算代替倍点运算,且编码是从左到右(即从最高位向最低位)进行,编码和主计算可以合并,提高实现效率并节省内存空间。实验结果表明,该算法较经典的double-and-add算法能够提高效率30%以上。     

椭圆曲线标量乘的快速实现

提出一种计算固定基点标量乘的快速实现算法,该算法的计算速度明显快于Fixed-base Windowing算法;且当预计算量小于255时,计算速度稍快于Fixed-base Comb算法。而且,该算法可以灵活地改变计算时间和占用内存的大小来适应不同的应用环境。     

一种改进的固定基点标量乘快速算法

对于固定基点的标量乘法,LLECC算法具有很高的计算效率,但是预计算量大、存储空间要求高限制了算法的应用.采用基于窗口的非相邻编码方法对标量k编码并按照新的排列方式得到系数矩阵后,利用编码方法的稀疏特性便可降低算法的存储量;为解决新的编码方式下增加的倍点计算,利用二进制有限域上计算效率较高的半点计算代替一般的倍点运算,从而提高改进算法的计算效率.对比分析显示,在标量长度为160bit、编码窗口宽度为4bit等相同条件下,改进算法与原算法相比计算效率提高了12.4％,存储量降低了53.3％.     

基于域GF（2^m）上的椭圆曲线中标量乘的快速算法

标量乘法的快速运算是椭圆曲线密码学中研究的一个焦点。本文讨论基于域GF（2^m）的非超奇异椭圆曲线上2P＋Q运算，给出了在域GF（2^m）中的椭圆曲线点此类运算的一个完整的改进算法，并对算法做了简单的分析。得出结论：我们所给出的算法比IEEE给出的标准算法效率提高10％以上。     

NAF标量乘算法的改进

影响椭圆曲线加密效率的主要因素是椭圆曲线上的动点标量乘法和定点标量乘法,针对定点的标量乘法已经有了很好的算法,然而,动点的标量乘法还有待提高,NAF算法是目前存在的最优的动点标量乘算法。首先对NAF算法进行分析,指出传统NAF算法的不足,再利用m—ary算法和滑动窗口算法的思想,将K的NAF二进制表示变成NAF的2^r进制表示,计算时滑过值为0的位,并将要处理的数划为（2^r）th（h为奇数）。理论和实践证明,已做到能进一步减少椭圆曲线上点加的次数,大大提高椭圆曲线加密的效率。     

一种快速的椭圆曲线标量乘方法

该文提出并实现了一种快速的椭圆曲线标量乘方法。理论分析与实验结果表明,该方法安全、有效。例如,对于160位的大整数标量乘,与固定基窗口方法相比,其实现速度提高了82.5%。     

GF(2m)上椭圆曲线标量乘的硬件结构实现

基于Reyhani Masoleh提出的GF(2m)高斯正规基乘法实现了三拍非流水的正规基乘法器,并基于该乘法器实现了一种高性能López-Dahab标量乘硬件结构.Reyhani-Masoleh算法利用乘法矩阵的对称性降低了乘法的复杂度;而López-Dahab标量乘算法由于采用投影坐标,计算速度快且可以有效降低存储需求.基于Reyhani-Masoleh乘法器的López-Dahab标量乘结构可以有效利用两种算法的优势,可以达到目前最好的标量乘硬件结构的性能.