Speeding up Scalar Multiplication in Genus 2 Hyperelliptic Curves with Efficient Endomorphisms

This paper proposes an efficient scalar multiplication algorithm for hyperelliptic curves, which is based on the idea that efficient endomorphisms can be used to speed up scalar multiplication. We first present a new Frobenius expansion method for special hyperelliptic curves that have Gallant‐Lambert‐Vanstone (GLV) endomorphisms. To compute kD for an integer k and a divisor D, we expand the integer k by the Frobenius endomorphism and the GLV endomorphism. We also present improved scalar multiplication algorithms that use the new expansion method. By our new expansion method, the number of divisor doublings in a scalar multiplication is reduced to a quarter, while the number of divisor additions is almost the same. Our experiments show that the overall throughputs of scalar multiplications are increased by 15.6 to 28.3 % over the previous algorithms when the algorithms are implemented over finite fields of odd characteristics.     

Fast Multiplication on Elliptic Curves over Small Fields of Characteristic Two

We discuss new algorithms for multiplying points on elliptic curves defined over small finite fields of characteristic two. This algorithm is an extension of previous results by Koblitz, Meier, and Staffelbach. Experimental results show that the new methods can give a running time improvement of up to 50 % compared with the ordinary binary algorithm for multiplication. Finally, we present a table of elliptic curves, which are well suited for elliptic curve public key cryptosystems, and for which the new algorithm can be used. Received 14 January 1997 and revised 4 September 1997     

用替换标量加速椭圆曲线点乘的研究

在优化有限域上椭圆曲线点乘的研究中,寻找标量的等价表示形式以减少点加和倍点运算的数量一直是关注的热点。因为点乘运算在一个H阶有限群中,利用有限群的性质,Q=kP=（n-k）（-P）。对于椭圆曲线,n-k和-P容易计算,于是计算点乘的标量k可以替换为n-k。因此,计算点乘时可通过选取代价更小的标量来减少计算量。理论和实验研究表明,替换标量可在微小的开销下使通常的重复倍加点算法的点加次数平均减少约5％。     

基于边信道原子的椭圆曲线标量乘算法

提出了一种能够抵抗简单能量分析攻击的边信道原子结构,减少了椭圆曲线密码体制中标量乘的倍点和点加运算次数,从而节省了运算时间,最后通过调用Crypto＋＋库函数,对于NIST提供的160 bit素域上椭圆曲线编程实现算法,发现此算法的效率比Montgomery Ladder算法提高了37.6%。     

基于Markov链的椭圆曲线标量乘法算法性能分析

在椭圆曲线密码系统中,采用规范重编码、滑动窗口等优化技术可以有效提高椭圆曲线上点的标量乘法k·P的运算性能,但在实现中,需要对不同优化技术的算法性能进行定量分析,才能确定标量乘法的最优实现.本文运用Markov链对标量k规范重编码表示的滑动窗口划分过程进行了建模,提出了一种对椭圆曲线标量乘法的平均算法性能进行定量分析的方法,并运用该方法分析了不同参数下标量乘法运算的平均性能,计算了滑动窗口的最优窗口大小.最后,通过比较说明,采用规范重编码和滑动窗口技术的椭圆曲线标量乘法的运算开销比用m-ary法少10.32~17.32％,比单纯采用滑动窗口法也要少4.53~8.40％.     

基于GF(2~m)上椭圆曲线点乘的实现

给出了椭圆曲线加密算法的点乘实现.在实现模乘运算时,把相乘过程和模约多项武过程结合起来,以改善运算效率.片外双口RAM的使用,加快了数据存取速度,同时通过预留RAM空间,增强了系统的可扩充性.本设计用VerilogHDL语言作为设计工具,在synopsys DC Z-2007 03 solaris9工作平台上,基于chartered 0.35 CMOS的综合库,50MHz约束下综合出结果约为18657门.     

一种基于折半运算的Comb标量乘算法

通过将折半运算应用于Comb算法,提出了一种新的Comb标量乘算法,它可以提高域Fm2上的椭圆曲线标量乘法的效率.在预计算阶段和赋值阶段,新算法分别用高效的折半运算取代倍点运算.对新算法运行时间进行分析,并与传统的Comb算法进行比较,当窗口宽度w=4时,新算法效率提高58%~63%.     

一类超椭圆曲线上的快速除子标量乘

 除子标量乘是超椭圆曲线密码体制中的关键运算.基于单除子标量乘的思想,将Duursma与Sakurai给出的关于奇素数域上一类特殊超椭圆曲线上的一个除子标量乘算法推广到奇素数域扩域上更一般的此类超椭圆曲线上,得到了两个效率更高的公式化的除子标量乘新算法.这两算法所需的运算量比二元法降低12%以上.     

有限域F_2~m上椭圆曲线阶的快速算法

讨论了Schoof算法在有限域F_2~m上的快速实现,并且给出了筛选椭圆曲线的方法,在实际中可以基本满足椭圆曲线密码体制的需要。     

F2上安全的Edwards曲线

Edwards曲线提供了大量的可以抵挡旁道攻击的椭圆曲线,因此引起了人们特别的关注。最近Bernstein、Lange和Farashahi将一般的Edwards曲线推广到了特征为2的域上,并认为这类椭圆曲线必将会有广泛的应用。但是这类曲线的安全性却仍然是一个值得商榷的问题。文中通过双有理等价映射讨论了F2上的Edwards曲线与Koblitz曲线之间的关系,并由此推出这类Edwards曲线会在一些扩域上具有安全性。     

改进椭圆曲线加密算法抗边际信道攻击的研究

纯粹的加密算法的应用对于边际信道的攻击的防御是比较弱的，椭圆加密算法是近年来人们认为加密能力比较强的算法之一。本文讨论了目前存在的增强椭圆曲线算法抗边际信道攻击的方法，就其可行性提出了一些看法．并对其中几种方法的时间、空间复杂度进行比较。最后探讨了此类研究的应用前景。     

GF（2^m）域高速椭圆曲线加密处理器设计

针对高速椭圆曲线加密应用的要求,设计了一种多项式基表示的有限域GF(2m)上的高速椭圆加密处理器.为提高运算速度,点加和倍点模块并行运算,且分别采用全并行结构实现;为减少资源,初始化和最后的坐标变换求逆模块通过优化分解成一系列乘和加运算,合并在一个模块中用串行结构实现.Xilinx公司的VirtexEXCV2600 FPGA硬件实现结果表明,完成有限域GF(2163)上任意椭圆曲线上的一次点乘的全部运算时间消耗约为31.6μs,适合高速椭圆曲线加密应用的要求.     

Design of highly efficient elliptic curve crypto-processor with two multiplications over GF（2^163）

In this article, a parallel hardware processor is presented to compute elliptic curve scalar multiplication in polynomial basis representation. The processor is applicable to the operations of scalar multiplication by using a modular arithmetic logic unit (MALU). The MALU consists of two multiplications, one addition, and one squaring. The two multiplications and the addition or squaring can be computed in parallel. The whole computations of scalar multiplication over GF(2163) can be performed in 3 064 cycles. The simulation results based on Xilinx Virtex2 XC2V6000 FPGAs show that the proposed design can compute random GF(2163) elliptic curve scalar multiplication operations in 31.17 μs, and the resource occupies 3 994 registers and 15 527 LUTs, which indicates that the crypto-processor is suitable for high-performance application.     

GF(2m)域椭圆曲线密码算法的高速实现

文章提出椭圆曲线密码中算术处理的几个快速算法及其实现,并在此基础上提出一个新的、高速的ECC芯片结构体系,具有高速、低功耗、面积小等优势。     

椭圆曲线密码体制的VLSI并行算法研究

文章分析了有限域上椭圆曲线密码体制的基本操作,针对实现中计算量最大的两个问题乘法和求逆运算,提出了ＶＬＳＩ并行算法,设计了相应的脉动阵列,并指出了它在椭圆曲线密码体制实现中的重要意义。     

Speed up rational point scalar multiplications on elliptic curves by Frobenius equations

Let q be a power of a prime and φ be the Frobenius endomorphism on E（Fqk）, then q = tφ - φ^2. Applying this equation, a new algorithm to compute rational point scalar multiplications on elliptic curves by finding a suitable small positive integer s such that q^s can be represented as some very sparse φ-polynomial is proposed. If a Normal Basis （NB） or Optimal Normal Basis （ONB） is applied and the precomputations are considered free, our algorithm will cost, on average, about 55% to 80% less than binary method, and about 42% to 74% less than φ-ary method. For some elliptic curves, our algorithm is also taster than Mǖller＇s algorithm. In addition, an effective algorithm is provided for finding such integer s.     

F2^n上基于ONB的椭圆曲线乘法器的设计与实现

文章在介绍有限域运算法则，域上椭圆曲线及点的运算法则的基础上，设计了一个F2^n上基于优化正规基的串行椭圆曲线乘法器，其点乘运算速度可达80．87次／秒，为进一步完成椭圆曲线加密系统提供了硬件基础。     

A Custom Instruction Approach for Hardware and Software Implementations of Finite Field Arithmetic over \mathbbF2163 \mathbb{F}_{{2^{{163}} }} using Gaussian Normal Bases

This paper presents a comprehensive analysis of the design of custom instructions in a reconfigurable hardware platform dedicated to accelerate arithmetic operations in the binary field , using a Gaussian normal basis representation. The resulting platform is capable of running real applications, thus allowing a precise measurement of the execution overheads, and a fair comparison of the hardware and software speedups at several implementation levels. By using this approach, we determine which field operations (e.g., multiplication) are better suited to constrained environments, and which ones provide an enhanced performance in general-purpose systems. Experimental results reveal that by using our fastest field multiplier implemented as a custom instruction in a combined hardware/software approach, we accelerate point multiplication (the fundamental operation in Elliptic Curve Cryptography) over 126 times.