标量乘法

摘要： 近年来,通信领域得到了巨大的发展,网上银行、移动通信等应用增加了资源受限环境下的安全需求.与传统密码算法相比,椭圆曲线密码体制(Elliptic curve cryptography,ECC)提供了更好的安全标准,为优化性能参数提供了更大的空间.为此,文中提出了一种高效的椭圆曲线密码硬件设计方案.该方案在已有研究的基础上,利用投影坐标系LD Montgomery阶梯算法对ECC中最核心的标量乘运算进行了研究,并对群运算层采用并行调度来缩短延迟;对于有限域运算,采用位并行乘法算法和改进的Euclidean求逆算法来实现;基于Xilinx Virtex-5和Virtex-7FPGA器件,在二进制域域长分别为163,233和283时实现了该体系结构.实验结果表明,该方案所需现场可编程门阵列(Field-Programmable Gate Array,FPGA)资源消耗更少,运算速度更快,与其他方法相比,硬件资源消耗减少了52.9％,标量乘法运算速度提高了5倍,能更好地适用于资源受限设备的应用.

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

摘要： 针对Edwards曲线上标量乘法的运算效率问题,提出一种安全快速的标量乘算法.首先,详细地介绍了Edwards曲线的基本内容,引入了一种安全快速的标量乘算法EDSM(scalar multiplication on Edwards curve).其次,为了减少标量乘法的运算量,对EDSM算法进行了改进.改进方案将标量k表示成四进制形式,根据尼的表示设计出四进制形式的标量乘算法,经过理论分析和计算表明,改进后的EDSM算法的运算效率优于EDSM算法,标量乘法的计算速度提高了10％左右.最后,结合现场可编程门阵列(Field Programmable Gate Array,FPGA)并行计算的特点,在Xilinx Virtex5系列的XC5VLX20T芯片中运行结果表明,完成一次256位标量乘法仅需0.37ms.和高基Montgomery模乘流水化阵列结构相比,标量乘的运算速度提高了50％,而且运算中并没有使用器件内部的专用乘法器,所以具有良好的可移植性.

摘要： 针对传感器网络所处环境恶劣、携带能源较少的特点,论文提出了一种基于等价替换标量乘法的椭圆曲线加密算法.该算法是在素场上对标量乘法进行基于点的阶的等价替换,减少标量乘法运算量的新方法.通过分析,在给定区间内,新方法比传统标量乘法的计算量大大减少,计算速度大大增加,并给出了阶为奇数或偶数时,计算量减少的加速度.该方法由于加密运算数据量少、加密速度快、加密时消耗能量低,适合用于无线传感网络中.

摘要： 针对传感器网络所处环境恶劣、携带能源较少的特点,论文提出了一种基于等价替换标量乘法的椭圆曲线加密算法。该算法是在素场上对标量乘法进行基于点的阶的等价替换,减少标量乘法运算量的新方法。通过分析,在给定区间内,新方法比传统标量乘法的计算量大大减少,计算速度大大增加,并给出了阶为奇数或偶数时,计算量减少的加速度。该方法由于加密运算数据量少、加密速度快、加密时消耗能量低,适合用于无线传感网络中。

摘要： 标量乘法是影响椭圆曲线加密算法执行效率的一个重要因素,椭圆曲线的标量乘法的方法很多,基于双基链的标量乘法是一种效率较好的算法,文中讨论基于树型方法计算双基链表示的基本原理和在Delphi环境下的实现.

摘要： 针对Edwards曲线上标量乘法的效率及安全性，提出了马尔科夫点加-倍点链（Markov Addition-Double Chain，MADC）。基于MADC的椭圆曲线标量乘算法每次循环都固定执行“点加-倍点”运算，从而能够天然抵抗简单能量攻击。此外，倍点运算占总运算量的一半，由于Edwards曲线的倍点公式相对点加公式所需的运算量极少，新算法的运算量将大大减少。实验结果表明，MADC的最佳链长为160，MADC-160相对于EAC-320、SAC-260和GRAC-258，效率分别提高了27%、10.4%和9.7%。%In view of the efficiency and safety of Edwards curve scalar multiplication, this paper proposes Markov Addition-Double Chain(MADC). The each loop of scalar multiplication algorithm based on MADC executes fixed“point addition-double”operation, which can resist the simple power analysis naturally. In addition, the timing cost of new algorithm will be reduced greatly because that the calculation of double operation accounts for half of the total and the computation of double operation needs very little calculation compared with point addition for Edwards curve. The experimental results show that, the length of MADC is 160 in the best case and the efficiency is increased by 27%, 10.4%and 9.7%respectively relative to EAC-320, SAC-260 and GRAC-258.

摘要： To raise the efficiency of field operations on elliptic curve, based on the idea of trading multiplications for squares, two improved algorithms are proposed to compute 7P and 7k P directly over GFP in terms of affine coordinates, their computational complexity is I+18M+12S and I+(17k+2)M+(14k+1)S respectively, and the new algorithm's efficiency is improved by 8.3% and 13.5% respectively compared with the best algorithms at present. In addition, based on the same idea, a modified method is given to compute 5k P directly over GFP in terms of affine coordinates, its com-putational complexity is I+(9k+2)M+(14k+1)S , and the efficiency of the new method is improved by 17.2%and 35.7%respectively compared with Xu Kaiping's and MISHRA's method.%为了提高椭圆曲线底层域运算的效率,基于将乘法运算转换为平方运算的思想,提出在素数域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%.

摘要： 标量乘运算是椭圆曲线密码的关键运算.为有效提高椭圆曲线密码标量乘法的运算效率,给出了一种改进的带符号整数拆分形式标量乘快速算法.首先通过对标量进行带符号的整数拆分形式编码,然后将标量乘运算转化为由一组椭圆曲线上的点累加和形式进行计算,同时在预计算阶段采用更为高效的折半运算代替倍点运算.算法性能分析的结果表明:与已有的基于整数拆分形式标量乘快速算法相比,新算法的能够大幅提升运算效率,在应用椭圆曲线密码的各种系统中具有较好的实际应用价值.

摘要： In order to improve the security of elliptic curve cryptographic algorithms and efficiency of the existing side-channel attacks and scalar multiplication algorithm on the basis of a new scalar multiplication algorithm is proposed.Scalar multiplication is the elliptic curve cryp-tosystem (ECC) of the basic operation, is also one of the most time-consuming and vulnerable to attack. Elliptic curve scalar multiplica-tion, 2-3 double-base chain represents an integer N, can improve the efficiency of the scalar multiplication. In a scalar Multiplication algorithm, to find the optimal 2-3 double-base chain will takes longer than scalar multiplication itself, the cost of pay more. New algo-rithm, the application of Tate pairing and 2-3 chain combination, to find out better 2-3 chain. In addition, than 2-3 chain based on greedy algorithm. Simulation results show that the improved algorithm can reduce the storage with improving the calculation efficiency.%在有限域GF（2m）上，实现椭圆曲线密码体制（ECC）中关键运算是标量乘算法，该算法也是椭圆曲线密码体制中耗时最长、极易受到攻击的运算之一。为了提高椭圆曲线密码算法计算的安全性和效率性，从分析以2、3为底的双基链椭圆曲线标量乘特点出发，在现在有的双基链算法基础之上，提出一种新的快速标量乘算法。新算法中，通过应用米勒算法和2-3链相结合的方法，寻找出权重更小的双基链。此外，考虑到小权重也有其局限性。引入了技术Tate配对与2-3链相结合来提高算法效率，比基于贪心算法的双基链更加高效。经仿真实验比较分析和研究，表明该改进算法可以很好提高计算效率，并且同时能大大降低存储量。

摘要： Kobliz提出的不规则二进制曲线具有许多提高标量乘法运算速度的算术特性。Solinas提出了Koblitz曲线上的τ-NAF并将其在群F2n上的Hamming重量缩减到了约n/3，在《PKC 2004》一书中，Avanzi 等人提出将τ–NAF与单点等分联系起来，并将其Hamming重量缩减到了2n/7。最近，Avanzi等人通过引入广义q-NAF改进了上述方法，使其Hamming重量达到了n/4。我们设计的Koblitz曲线标量乘法速度比τ-NAF方法快40%，比Avanzi方法快20%，且不需要另外附加的内存。

摘要： 本文对新的基于双基数链的标量乘法快速算法进行了研究。文章在底层域2kP、3kP、2P±Q、3P±Q的快速算法基础上给出了新的基于双基数链的标量乘法快速算法,借助于双基数表示的稀疏性质和底层域快速算法的优势,算法大大减少了底层域运算中求逆操作的次数,有效提高了算法的执行效率。

摘要： 从分析传统椭圆曲线标量乘法fixed-base comb method入手,将Eisentr(a)ger等人提出的2P+Q的快速运算思想应用到算法中,并分析运行环境不同时算法效率的提高,不考虑预计算情况下,二元域上算法效率提高8％～13％.

摘要： 给出了一类适合普通PC机实现的安全椭圆曲线,详细给出了选取这类曲线的具体步骤和提出了一种新的计算这类曲线上标量乘法的快速算法.新方法能使计算该类曲线上标量乘法所需的椭圆曲线运算次数大大减少.另一方面,这类曲线不仅选取容易而且它充分考虑到了处理该类曲线上运算时CPU的字长,使底层运算能够通过普通PC机得以较快实现,高层运算也能通过Frobenius方法减少运算次数,从而能够极大地提高曲线的整体实现速度.

摘要： 本文基于椭圆曲线密码体制,通过对椭圆曲线上标量乘的分析,提出了在GF(2m)域上实现非超异椭圆曲线的标量乘的一种快速算法,并对参数m的选取进行了分析.当参数m选取最优的情况下,该算法比二进制算法效率提高约50﹪.

摘要： 本文基于椭圆曲线密码体制,通过对椭圆曲线上标量乘的分析,提出了在GF(2m)域上实现非超异椭圆曲线的标量乘的一种快速算法,并对参数m的选取进行了分析.当参数m选取最优的情况下,该算法比二进制算法效率提高约50﹪.

摘要： 本文基于椭圆曲线密码体制,通过对椭圆曲线上标量乘的分析,提出了在GF(2m)域上实现非超异椭圆曲线的标量乘的一种快速算法,并对参数m的选取进行了分析.当参数m选取最优的情况下,该算法比二进制算法效率提高约50﹪.

摘要： 本文基于椭圆曲线密码体制,通过对椭圆曲线上标量乘的分析,提出了在GF(2m)域上实现非超异椭圆曲线的标量乘的一种快速算法,并对参数m的选取进行了分析.当参数m选取最优的情况下,该算法比二进制算法效率提高约50﹪.

摘要： 提供了一种能以高速执行标量乘法的标量乘法器以及标量乘法程序。使用整数变量χ，在对嵌入次数k=12的情况下的特征p、阶数r、费罗贝尼乌斯自同态映射的迹t作为p(χ)=36χ

摘要： 本发明提供一种用于在不安全环境中安全地计算椭圆曲线标量乘法的系统，系统包括：包括安全存储器的安全处理器，安全处理器被配置成：将安全标量K分解成m2个随机值ki，其中i是整数下标；针对下标m2标量乘法；存储器装置；以及与存储器装置通信的处理器。

摘要： 本发明公开了一种最优带符号二进制快速计算方法，以及基于该计算方法的群优化算法和加法群上的椭圆曲线标量乘法优化算法；最优带符号二进制快速计算方法，能够解决带符号二进制算法的最优化问题，包括群上的优化算法，其中加法群上的椭圆曲线标量乘法的优化算法，根据目标系统椭圆曲线上的三个基本运算点加ECADD，倍点ECDBL和点逆ECINV的运算耗费，对标量因子S进行优化，从S的所有(3/2)

摘要： 本公开公开了基于SM2算法标量乘法编码的抗侧信道攻击方法及系统，包括：生成基准坐标表，生成预编码坐标参数表ParTable；获取椭圆曲线公钥密码算法的参数k；基于基准坐标表、预编码坐标参数表ParTable和椭圆曲线公钥密码算法的参数k，实时生成编码表；基于实时生成的编码表，完成椭圆曲线公钥密码算法中的固定点标量乘法kG的运算，在椭圆曲线公钥密码的数字签名生成过程、数字签名验证过程、加密过程或密钥交换协商过程中使用运算获取的kG，抵御侧信道攻击。

摘要： 不管随机数k的值如何都能够在恒定的计算时间内处理椭圆标量乘法kG，防止椭圆标量乘法kG的定时解析。初始设定部121对标量乘法变量R设定椭圆曲线上的特定点G。标量乘法部122针对表示随机数k的t比特的比特串从上位逐个比特进行参照，每当参照一个比特时，对作业变量R[0]设定对标量乘法变量R进行2倍乘法而得到的值，对作业变量R[1]设定对作业变量R[0]设定的值加上特定点G而得到的值。然后，在标量乘法部122中，如果所参照的比特的值是0，则对标量乘法变量R设定作业变量R[0]，如果所参照的比特的值是1，则对标量乘法变量R设定作业变量R[1]。标量倍点输出部123从标量乘法变量R减去常数值2

摘要： 本发明涉及能够快速进行运算的标量乘法或幂运算的运算方法、以及标量乘法或幂运算的程序。在电子计算机中，关于非负整数n的G的有理点Q的标量n乘法的运算方法和运算程序中，Φq(Q)＝[q]Q＝[t-1]Q成立，由此对标量n以t-1进制展开，使用有理点的弗罗贝尼乌斯自同态映射Φq取代t-1。另外，在电子计算机中，关于非负整数n的H的元素A的n次幂的幂运算方法和运算程序中，令q和r的差为s＝q-r，则对于H的非零元素A，Φq(A)＝Aq＝As成立，由此对指数n以s进制展开，使用关于元素的弗罗贝尼乌斯自同态映射Φq取代s。

摘要： 提供了一种能以高速执行标量乘法的标量乘法器以及标量乘法程序。使用整数变量χ，在对嵌入次数k=12的情况下的特征p、阶数r、费罗贝尼乌斯自同态映射的迹t作为p(χ)=36χ

摘要： 本申请公开了一种抗SPA攻击的国密SM2算法中非定点标量乘法的计算方法、装置、电子设备及存储介质，其中，方法包括：展开待运算的乘法中的标量得到标量展开式；根据预先计算的多个小倍数点和所述标量的展开式，利用固定数目的倍点运算和点加运算进行待运算的标量乘法计算公式的循环计算。通过提出新的求模逆算法和复用中间数据改进算法流程，结合实现过程中对分支选择的进一步优化大幅提高抗SPA攻击的实现方案的运行速度。由此，解决了抗SPA攻击的SM2算法非定点标量乘法实现效率不高等问题。

摘要： 本发明公开了一种基于GPU加速的大规模椭圆曲线多标量乘法的并行计算方法，包括以下步骤：大规模椭圆曲线多标量乘法的原始运算任务的切分得到多个子运算任务；并行存储子运算任务的曲线点；一系列并行稀疏矩阵操作；稀疏矩阵中曲线点元素进行加权求和；规约子运算任务结果获取最终大规模椭圆曲线多标量乘法结果。该计算方法将原始大规模椭圆曲线多标量乘法任务切分成子任务，并且将计算过程中多种复杂操作简化成并行稀疏矩阵运算，为大规模椭圆曲线多标量乘法提供加速。该计算方法的时间复杂度相比于现有方法更少，在理论上可以达到接近GPU提供的线程个数的并行加速。

摘要： 获得用于执行加密操作的标量乘法的单个架构指令。指令被执行，并且该执行包括：确定多个标量乘法函数中由待执行的指令支持的标量乘法函数。获得标量乘法函数的输入，并且该输入包括至少一个源分量和标量值。使用输入来执行标量乘法函数以提供将要在加密操作中使用的输出。