Fast and secure elliptic curve scalar multiplication algorithm based on special addition chains

To resist the side chaimel attacks of elliptic curve cryptography, a new fast and secure point multiplication algorithm is proposed. The algorithm is based on a particular kind of addition chains involving only additions, providing a natural protection against side channel attacks. Moreover, the new addition formulae that take into account the specific structure of those chains making point multiplication very efficient are proposed. The point multiplication algorithm only needs 1 719 multiplications for the SAC260 of 160-bit integers. For chains of length from 280 to 260, the proposed method outperforms all the previous methods with a gain of 26% to 31% over double-and add, 16% to22% over NAF, 7% to 13% over4-NAF and 1% to 8% over the present best algorithm--double-base chain.

Elliptic Curve Scalar Multiplication with x-Coordinate

This paper gives a comprehensive method to do Elliptic Curve Scalar Multiplication with only x-coordinate. Explicit point operation formulae for all types of defining equations of the curves are derived. For each type of curve, the performance is analyzed. The formulae are applied in Montgomery Ladder to get scalar multiplication algorithm operated with only x-coordinate. The new scalar multiplication has the same security level and computation amount with protected binary scalar multiplication （PBSM） against side channel attack, and has the advantages of higher security and little memory needed.

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, Muller and Smart proposed two efficient algorithms for point scalar multiplications over even or odd finite fields respectively. This paper reduces the corresponding 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

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.

Multiple positive solutions for a class of nonlinear four-point boundary value problem with p-Laplacian

This paper deals with the existence of multiple positive solutions for a class of nonlinear singular four-point boundary value problem with p-Laplacian：{（φ（u′））′＋a（t）f（u（t））=0, 0〈t〈1, αφ（u（0））-βφ（u′（ξ））=0,γφ（u（1））＋δφ（u′（η））0,where φ（x） = ｜x｜^p-2x,p 〉 1, a（t） may be singular at t = 0 and/or t = 1. By applying Leggett-Williams fixed point theorem and Schauder fixed point theorem, the sufficient conditions for the existence of multiple （at least three） positive solutions to the above four-point boundary value problem are provided. An example to illustrate the importance of the results obtained is also given.

THE EXISTENCE AND MULTIPLICITY OF k-CONVEX SOLUTIONS FOR A COUPLED k-HESSIAN SYSTEM

In this paper,we focus on the following coupled system of k-Hessian equations:{S_(k)(λ(D^(2)u))=f_(1)(|x|,-v)in B,S_(k)(λ(D^(2)v))=f2(|x|,-u)in B,u=v=0 on■B.Here B is a unit ball with center 0 and fi(i=1,2)are continuous and nonnegative functions.By introducing some new growth conditions on the nonlinearities f_(1) and f_(2),which are more flexible than the existing conditions for the k-Hessian systems(equations),several new existence and multiplicity results for k-convex solutions for this kind of problem are obtained.

Upper Bound of Scalars in the Integer Sub-decomposition Method： The Theoretical Aspects

The focal point of this paper is to present the theoretical aspects of the building blocks of the upper bounds of ISD （integer sub-decomposition） method defined by kP = k11P ＋ k12ψ1 （P） ＋ k21P ＋ k22ψ2 （P） with max {｜k11｜, ｜k12｜} 〈 Ca√n and max{｜k21｜, ｜k22｜}≤C√, where C=I that uses efficiently computable endomorphisms ψj for j=1,2 to compute any multiple kP of a point P of order n lying on an elliptic curve E. The upper bounds of sub-scalars in ISD method are presented and utilized to enhance the rate of successful computation of scalar multiplication kP. Important theorems that establish the upper bounds of the kernel vectors of the ISD reduction map are generalized and proved in this work. The values of C in the upper bounds, that are greater than 1, have been proven in two cases of characteristic polynomials （with degree 1 or 2） of the endomorphisms. The upper bound of ISD method with the case of the endomorphism rings over an integer ring Z results in a higher rate of successful computations kP. Compared to the case of endomorphism rings, which is embedded over an imaginary quadratic field Q = [4-D]. The determination of the upper bounds is considered as a key point in developing the ISD elliptic scalar multiplication technique.

基于FPGA的Edwards曲线标量乘法改进与实现

点加是Edwards曲线标量乘法的基本运算,当点加算法确定后,通过减少点加运算次数来提高标量乘法运算效率是一种有效的方法。首先,根据标量乘法在椭圆曲线公钥密码中的使用特点,将标量乘法分成固定点标量乘法、随机点标量乘法和多点标量乘法;其次,采用预计算和窗口法来减少标量乘法中的点加运算次数;最后,在复旦微的JFM7K325T的现场可编程门阵列(FieldProgrammableGateArray,FPGA)中进行了实现和测试。结果表明,与原有实现方法相比,改进算法计算256比特固定点标量乘法速度提升了450%,计算随机点标量乘法速度提升了39%,计算多点标量乘法速度提升了66%。

一种高效轻量的双参数椭圆曲线数字签名批量验证方案

为解决大规模交易任务的签名验证给区块链节点带来繁琐的开销和经典的椭圆曲线数字签名算法(ECDSA)中耗时的模逆运算,提出一种高效轻量的双参数椭圆曲线数字签名(TP-ECDSA)批量验证方案。一方面,TP-ECDSA在签名和验证阶段均无模逆运算,在该算法中引入批量验证能将标量乘的计算次数从2t减少到[2,t+1]。另一方面,KGLP算法能加速标量乘运算,引入该算法能显著地提升签名验证的效率。实验表明,与ECDSA相比,不论是独立验证还是批量验证,TP-ECDSA的运行速度均提高了50%以上,签名验证效率显著提升。

一种基于模乘相等检测的标量乘碰撞攻击方法

碰撞攻击是针对椭圆曲线密码的主要分析技术之一,其关键取决于对点加、倍点碰撞检测的正确率.由于随机操作数和分支语句的影响,对点加、倍点的碰撞检测几近于随机猜测,因而如何对点加、倍点进行碰撞检测成为亟需解决的问题.本文以Weierstrass曲线中基于雅可比坐标的点加、倍点为分析对象,提出了基于模乘相等的标量乘碰撞攻击方法.首先,结合点加和倍点的运算流程,从中识别出了有助于碰撞检测的模乘,并在模乘间构造了新的碰撞关系,将攻击转化为模乘碰撞检测.其次,本文发现在雅可比坐标中存在由坐标Z完全决定的模乘,基于此首次提出了模乘相等检测,将攻击转化为判断模乘两个操作数是否相同,从而避免了随机操作数的影响.最后,本文对一款硬件实现芯片进行碰撞检测实验,通过对曲线基于主成分分析进行压缩处理,将点加和倍点碰撞检测的准确率提高到了99%.本文提出的碰撞检测方法对采用了随机掩码和分支平衡的标量乘实现仍有效.

基于比特重组快速模约简的高面积效率椭圆曲线标量乘法器设计

针对现有椭圆曲线密码标量乘法器难以兼顾灵活性和面积效率的问题,该文设计了一种基于比特重组快速模约简的高面积效率标量乘法器。首先,根据椭圆曲线标量乘的运算特点,设计了一种可实现乘法和模逆两种运算的硬件复用运算单元以提高硬件资源使用率,并采用Karatsuba-Ofman算法提高计算性能。其次,设计了基于比特重组的快速模约简算法,并实现了支持secp256k1, secp256r1和SCA-256(SM2标准推荐曲线)快速模约简计算的硬件架构。最后,对点加和倍点的模运算操作调度进行了优化,提高乘法与快速模约简的利用率,降低了标量乘计算所需的周期数量。所设计的标量乘法器在55 nm CMOS工艺下需要275 k个等效门,标量乘运算速度为48 309次/s,面积时间积达到5.7。

基于GPU的zk-SNARK中多标量乘法的并行计算方法

针对zk-SNARK(zero-knowledge succinct non-interactive argument of knowledge)中计算最为耗时的多标量乘法(multiscalar multiplication,MSM),提出了一种基于GPU的MSM并行计算方案。首先,对MSM进行细粒度任务分解,提升算法本身的计算并行性,以充分利用GPU的大规模并行计算能力。采用共享内存对同一窗口下的子MSM并行规约减少了数据传输开销。其次,提出了一种基于底层计算模块线程级任务负载搜索最佳标量窗口的窗口划分方法,以最小化MSM子任务的计算开销。最后,对标量形式转换所用数据存储结构进行优化,并通过数据重叠传输和通信时间隐藏,解决了大规模标量形式转换过程的时延问题。该MSM并行计算方法基于CUDA在NVIDIA GPU上进行了实现,并构建了完整的零知识证明异构计算系统。实验结果表明:所提出的方法相比目前业界最优的cuZK的MSM计算模块获得了1.38倍的加速比。基于所改进MSM的整体系统比业界流行的Bellman提升了186倍,同时比业界最优的异构版本Bellperson提升了1.96倍,验证了方法的有效性。

椭圆曲线标量乘高效方案设计

对于一些资源受限的应用场景而言,椭圆曲线密码算法的计算量还是比较大,这严重影响了网络的生命周期,需要对算法进行轻量化改进以减少资源消耗。标量乘运算是影响椭圆曲线密码算法执行效率的关键,针对无线传感器节点的内存和处理特点,首先对其底层的域运算进行改进,提出了二进制域上的3-Karatsuba联合区块乘法算法、快速模约减算法、模平方及模逆算法,减少了域运算过程的基本运算和内存读写次数,最后基于Montgomery算法设计了GF(2~m)上的标量乘快速实现方案。在8 bit AVR微处理器上实验表明,完成一次GF(2~(163))域上的ECC点乘运算共需要5 160 991个时钟周期,时间消耗大约为0.70 s,改进后的方案在运算效率方面有一定优化。

Efficient Scalar Multiplication for Elliptic Curves over Binary Fields

Scalar multiplication [n]P is the kernel and the most time-consuming operation in elliptic curve cryptosystems. In order to improve scalar multiplication, in this paper, we propose a tripling algorithm using Lopez and Dahab projective coordinates, in which there are 3 field multiplications and 3 field squarings less than that in the Jacobian projective tripling algorithm. Furthermore, we map P to（φε^-1（P）, and compute [n]（φε^-1（P） on elliptic curve Eε, which is faster than computing [n]P on E, where φε is an isomorphism. Finally we calculate （φε（[n]φε^-1（P）） = [n]P. Combined with our efficient point tripling formula, this method leads scalar multiplication using double bases to achieve about 23% improvement, compared with Jacobian projective coordinates.

椭圆曲线公钥密码体制的研究热点综述

椭圆曲线密码体制是公钥密码中的研究热点。该文介绍了椭圆曲线密码体制的基本概念及相关知识,讨论了目前基于椭圆离散对数问题的椭圆曲线密码的研究动态,并指出今后的研究方向和重点。

基于素数域上复合运算的快速标量乘算法

底层有限域上点群运算是影响椭圆曲线密码效率的主要因素,利用混合坐标下快速复合运算2P+Q代替传统的点加运算作为基本计算单元,对NAF标量乘算法进行改进,改进后算法与基于最优坐标下的NAF标量乘算法相比,效率提高7%。通过预计算对标量k进行分段编码,提出基于复合运算的分段并行标量乘快速算法,在基点和标量长固定的情况下,该算法与原有NAF算法相比计算效率提高了46.5%,而且改进后算法仅需存储三个预计算点坐标,存储空间小。

快速椭圆曲线签名验证算法

从签名方程出发,推导出一组椭圆曲线签名验证算法,这些算法在验证步骤中,采用±的形式,只运用了一次标题乘运算,而目前国际上公认的椭圆曲线签名算法为ECDSA算法,也还有一些相关的签名算法,这些算法在验证步骤中都采用kP±lQ的形式,需要计算两次标题乘运算。因为关键运算为标题乘运算,其它运算时间可忽略不计,所以给出算法的验证步骤的运算时间仅为ECDSA算法所需时间的一半,接着还通过实验进行了验证。

椭圆曲线密码中一种多标量乘算法

标量乘和多标量乘是实现椭圆曲线密码体制的核心运算,其运算速度从整体上决定了椭圆曲线密码体制的实现效率.提出了一种多标量乘算法,该算法的基本思想是,将标量用带符号的整数阶乘展开式表示,并结合固定基窗口标量乘算法,使得实现多标量乘算法只需做点加运算即可.这不仅突破了传统求多标量乘算法的模式,而且提高了多标量乘的计算速度.同时,还对算法正确性和复杂度进行了分析.由实验结果可知,在m=2的情况下,该算法在计算效率上比已有的多标量乘算法提高了约47.8%~56.5%.

基于FPGA的高速椭圆曲线标量乘法结构

椭圆曲线密码系统是最近十几年来获得迅速发展的一类密码系统.为了提高椭圆曲线密码系统的处理速度,针对其中最关键的运算——椭圆曲线标量乘法设计并实现了一种基于FPGA的硬件结构,完成GF(2m)上的椭圆曲线标量乘法计算.该结构最大程度地对标量乘算法的内部模块进行了并行处理,缩短最大延迟路径,从而达到提高运算速度的目的.这一结构在FPGA上实现后,计算一次GF(2163)上的椭圆曲线标量乘法只需要36μs,这一性能是目前国际上已知的基于FPGA的标量乘法器中最好的.

基于椭圆曲线离散对数问题的公钥密码

自1985年Koblitz和Miller首次提出椭圆曲线密码之后,这种公钥密码的潜力越来越被人们所认识。首先对椭圆曲线及其相关知识做了简单介绍,而后以相当篇幅从三个方面介绍当前椭圆曲线密码的研究热点,最后给出典型椭圆曲线密码。作为一篇综述,文中反映了椭圆曲线密码的发展状况以及当前所面临的问题,体现了该领域目前的最新成就。