Jacobi Quartic曲线上GLV/GLS标量乘算法

目前GLV/GLS(Gallant,Lambert,Vanstone/Galbraith,Lin,Scott)标量乘算法的研究主要集中在Weier-strass曲线上,尝试寻找和构造更多或者更高次数的可有效计算的自同态.本文主要研究了Jacobi Quartic曲线上GLV/GLS标量乘算法.首先利用曲线之间的双有理等价,给出了该类曲线在素域上可有效计算自同态的具体构造,得到2维GLV方法.然后考虑椭圆曲线的二次扭曲线,利用曲线之间双有理等价和Frobenius映射,给出了该类曲线在二次扩域上可有效计算自同态的具体构造,得到2维GLS方法.将上述GLV和GLS方法结合起来,同时利用曲线在二次扩域上的两个不同的自同态,得到4维GLV方法.最后针对j不变量为0或1728两类特殊形式的椭圆曲线,利用更高次的扭曲线,得到4维GLV方法.实验结果表明:对于Jacobi Quartic曲线,2维GLV方法和4维GLV方法比5-NAF方法分别提速37.2％和109.4％以上.同时,在三种不同的实现方式下,Jacobi Quartic曲线上标量乘效率都优于Weierstrass曲线.     

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

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

基于二进制Edwards曲线的椭圆曲线加密多标量乘结构设计与实现

标量乘及多标量乘算法是影响椭圆曲线密码系统性能的关键.基于二进制Edwards曲线提出并实现了一种新型的椭圆曲线标量乘法器.由于Edwards曲线的完备性,这种乘法器可对曲线上任意一点进行计算,而不用区分倍乘或者负元,实现较简单,有很高的运算速度和很强的抗侧信道攻击的能力.     

椭圆曲线密码体制中快速标量乘算法实现

椭圆曲线密码(ECC),是一种以椭圆曲线离散对数问题为出发点而制定出的各种公钥密码体制,在1985年由学者Koblitz和Miller两人分别独立提出。ECC的主要特征是采用有限域上的椭圆曲线有限点群而非是传统的基于离散对数问题密码体制中所采用的有限循环群。因为标量乘算法是ECC中最耗时同时也是最为重要的算法,因为其运算效率的高低将直接影响到ECC实现的效率。本篇论文即是研究椭圆曲线密码中的标量乘法,以期能够探寻出一种快速安全的标量乘算法。     

Koblitz曲线上改进的ECDSA算法

标量乘法的效率决定着椭圆曲线密码体制的性能,而Koblitz曲线上的快速标量乘算法,是标量乘法研究的重要课题.Lee et al算法采用Frobenius映射扩展正整数k,并将其扩展后的系数改写成二进制形式,有效地提高标量乘算法效率.文中将JSF应用到扩展后的系数中,以较小存储空间为代价来提高算法效率k并将算法用到改进...     

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

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

基于MPI双处理器ECC标量乘算法的并行化研究

本文借鉴串行范畴内椭圆曲线密码体制中原有的二进制标量乘算法,从并行计算的角度提高ECC中标量乘运算的效率、进而提高ECC的整体性能。本文设计了基于MPI双处理器标量乘算法并行执行模型。通过分析ECC中的二进制标量乘算法和并行的2r标量乘算法,分别给出了相应的改进标量乘算法设计与实现,改进算法有效地提高了标量乘运算的效率。     

抗SPA攻击的椭圆曲线NAF标量乘实现算法

针对椭圆曲线非相邻形式（NAF）标量乘法不能很好地抵抗简单功耗分析攻击（SPA）的问题,对NAF标量乘的实现算法以及对NAF标量乘的SPA攻击原理进行了分析,提出一种新的标量乘实现算法——平衡能量NAF标量乘法。通过对智能卡功耗分析平台的实测波形进行分析验证,平衡能量NAF标量乘法不仅继承了NAF标量乘法运算效率高的优点,而且能够很好地抵抗SPA攻击,提高密码芯片的安全性。     

一类安全椭圆曲线的选取及其标量乘法的快速计算

安全椭圆曲线的选取和标量乘法的快速计算是有效实现椭圆曲线密码体制的两个主要问题.本文将二者结合起来考虑给出了一类适合普通PC机实现的安全椭圆曲线,并详细给出了选取这类曲线的具体步骤和基于"大步-小步法"思想构造了一种新的计算这类曲线上标量乘法的快速算法.这类曲线不仅选取容易而且利用本文所提出方法计算其标量乘法时能使所需椭圆曲线运算次数大大减少.此外,选用这类曲线后基域中元素不再需要专门的表示方法,各种运算能非常快地得到实现,从而能极大地提高体制的整体实现速度.     

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

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

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.     

Improved Scalar Multiplication on Elliptic Curves Defined over F2mn

We propose two improved scalar multiplication methods on elliptic curves over F_qn where q = 2^m using Frobenius expansion. The scalar multiplication of elliptic curves defined over subfield F_q can be sped up by Frobenius expansion. Previous methods are restricted to the case of a small m. However, when m is small, it is hard to find curves having good cryptographic properties. Our methods are suitable for curves defined over medium‐sized fields, that is, 10 ≤ m ≤ 20. These methods are variants of the conventional multiple‐base binary (MBB) method combined with the window method. One of our methods is for a polynomial basis representation with software implementation, and the other is for a normal basis representation with hardware implementation. Our software experiment shows that it is about 10% faster than the MBB method, which also uses Frobenius expansion, and about 20% faster than the Montgomery method, which is the fastest general method in polynomial basis implementation.     

Scalar Multiplication on Elliptic Curves by Frobenius Expansions

Koblitz has suggested to use “anomalous” elliptic curves defined over F₂, which are non-supersingular and allow for efficient multiplication of a point by an integer. For these curves, Meier and Staffelbach gave a method to find a polynomial of the Frobenius map corresponding to a given multiplier. Muller generalized their method to arbitrary non-supersingular elliptic curves defined over a small field of characteristic 2. In this paper, we propose an algorithm to speed up scalar multiplication on an elliptic curve defined over a small field. The proposed algorithm uses the same technique as Muller's to get an expansion by the Frobenius map, but its expansion length is half of Muller's due to the reduction step (Algorithm 1). Also, it uses a more efficient algorithm (Algorithm 3) to perform multiplication using the Frobenius expansion. Consequently, the proposed algorithm is two times faster than Muller's. Moreover, it can be applied to an elliptic curve defined over a finite field with odd characteristic and does not require any precomputation or additional memory.     

Two fast algorithms for computing point scalar multiplications on elliptic curves

The key operation in Elliptic Curve Cryptosystems(ECC) is point scalar multiplication. Making use of Frobenius endomorphism, Mfiller and Smart proposed two efficient algorithms for point scalar multiplications over even or odd finite fields respectively. This paper reduces thec orresponding multiplier by modulo τ^k-1 … τ 1 and improves the above algorithms. Implementation of our Algorithm 1 in Maple for a given elliptic curve shows that it is at least as twice fast as binary method. By setting up a precomputation table, Algorithm 2, an improved version of Algorithm 1, is proposed. Since the time for the precomputation table can be considered free, Algorithm 2 is about (3/2) log2 q - 1 times faster than binary method for an elliptic curve over Fq.     

Using Abelian Varieties to Improve Pairing-Based Cryptography

We show that supersingular Abelian varieties can be used to obtain higher MOV security per bit, in all characteristics, than supersingular elliptic curves. We give a point compression/decompression algorithm for primitive subgroups associated with elliptic curves that gives shorter signatures, ciphertexts, or keys for the same security while using the arithmetic on supersingular elliptic curves. We determine precisely which embedding degrees are possible for simple supersingular Abelian varieties over finite fields and define some invariants that are better measures of cryptographic security than the embedding degree. We construct examples of good supersingular Abelian varieties to use in pairing-based cryptography. Preliminary versions of parts of this paper appeared in the proceedings of Crypto 2002 38, ANTS VI 40 and the Daewoo Workshop on Cryptography 46.     

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

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

基于双基表示的并列点乘算法

 双基表示是一种整数表示法,它将任意整数表示成2和3的混合幂次的和或差的形式,并列点乘是一种快速的点乘算法,应用于一些椭圆曲线密码体制中.本文在现有的双基表示算法以及并列点乘算法的基础上,提出了新的双基表示算法以及基于该双基表示算法的并列点乘算法,该算法利用了一些特殊点的快速计算公式,从而有效地提高了并列点乘算法的执行效率.实验表明,在密钥长度为160比特,[S]/ =0.8时,当 /[M]=30,新算法的效率比基于JSF表示的并列点乘算法提高了22%;当 /[M]=10,新算法比JSF表示提高了6%;当 /[M]=8,新算法比JSF表示提高了3%.     

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.     

优化扩域上椭圆曲线标量乘的一个新算法

提出了一种优化扩域上椭圆曲线标量乘的新算法.算法基于Frobenius映射和二进制串的逻辑操作.文中对这个算法给出了细致精确的分析,而且在此基础上对新算法作了进一步改进.最后从理论分析和实际仿真两个方面就新算法和传统算法进行了比较.指出新算法执行时间比传统的φ-adic算法要少20%到40%.