标量乘法底层域快速算法研究

低存储需求的快速标量乘法算法李忠;彭代渊【摘要】The scalar multiplication of Elliptic Curve Cryptosysytem(ECC) has big computational costs and memory consumption. Aiming at this problem, by means of the 2MOF representation of scalar, this paper uses the direct computation 2Q+P strategy, proposes a lower memory cost and some efficient left-to-right scalar multiplication algorithm. The analysis result indicates that this algorithm has lower computational cost and memory consumption, and can enhance the ECC's efficiency in resource constrained environment.%在椭圆曲线密码体制(ECC)中,标量乘法的运算时间和存储资源消耗较大.为此,借助标量的2MOF表示,利用混合坐标系下直接计算2Q+P的策略,提出一种低存储需求的从左向右标最乘法算法.理论及实例分析表明,该算法的时间和空间消耗较少,能有效提高ECC在资源受限环境中的实现效率.【期刊名称】《计算机工程》【年(卷),期】2012(038)004【总页数】3页(P137-139)【关键词】椭圆曲线密码体制;标量乘法;混合坐标;标量表示;直接计算【作者】李忠;彭代渊【作者单位】西南交通大学信息科学与技术学院,成都610031;宜宾学院计算机与信息工程学院,四川宜宾644000;西南交通大学信息科学与技术学院,成都610031【正文语种】中文【中图分类】TP309.71 概述相对于目前广泛使用的公钥密码体制RSA，椭圆曲线密码体制(Elliptic Curve Cryptosystems,ECC)具有密钥短、功耗低、计算速度快等突出优点，特别适合在无线传感器网络、掌上电脑等处理能力、存储空间、带宽、功耗等受限的环境中应用[1]，已成为公钥密码学中较为活跃的一个分支。

椭圆曲线密码中标量乘的序列改进算法
唐四云
【期刊名称】《广西工学院学报》
【年(卷),期】2006(0)S2
【摘要】提高标量乘的计算效率是椭圆曲线密码体制得以广泛应用的基础,通过改进带符号滑动窗口编码方法,大大减少了标量乘算法的加法和倍点运算次数。

分析表明,改进后的算法较以前的算法,在密钥位数大的时候更有优势,具有实用价值。

【总页数】4页(P7-10)
【关键词】椭圆曲线密码体制;有限域;标量乘;离散对数
【作者】唐四云
【作者单位】广西工学院信息与计算科学系
【正文语种】中文
【中图分类】TN918.1
【相关文献】
1.椭圆曲线密码体制中快速标量乘算法实现 [J], 王永恒
2.椭圆曲线密码中抗功耗分析攻击的标量乘改进方案 [J], 张友桥;周武能;申晔;刘玉军
3.椭圆曲线密码中标量乘算法的改进方案 [J], 刘双根;李萍;胡予濮
4.GF(2n)域椭圆曲线密码体制中快速标量乘算法的研究 [J], 赖忠喜;陶东娅;张占军
5.基于梳状算法的椭圆曲线密码标量乘改进方案 [J], 田祎;刘爱军;申卫昌
因版权原因，仅展示原文概要，查看原文内容请购买。

基于HECC的快速标量乘算法研究摘要：超椭圆曲线密码体制（Hyperelliptic Curve Cryptosystem，HECC），它是基于有限域Jacobian商群上的离散对数难题(HECCDLP)提出的一种公钥密码体制。

与ECC、RSA公钥密码体制相比在相同有限域上建立起来的密码体制具有更高的安全。

但是由于HECC 参数选取复杂、计算困难，目前还未得到广泛使用，本文提出一种改进型HECC除子计算方法，能在牺牲部分存储空间的前提下，获取计算速度的大幅度提升。

关键字：超椭圆曲线密码体制；标量乘算法；公钥密码体制1引言对HECC的应用研究，smart等人曾多次研究了在特征为3的域上如何快速计算标量乘[[1]]；日本的Yasuyuki Sakai等人也对有限域GF(2n)和GF(p)上的HECC 进行了实现；J Pelzl等人在ARM处理器上实现亏格为2和3的HECC加密算法，并且发现在相同安全条件下特定参数的HECC比ECC具有更低的复杂度[[2]]; Park T J等人利用非邻接表示降低超椭圆曲线标量的汉明重量提高HECC的计算速度，并将椭圆曲线的GLV快速自同态算法拓展到超椭圆曲线使其快速标量乘算法提升15.6%-28.3%;李明在其博士论文中系统的阐述利用非邻接表示法和滑动窗口法相结合，降低HECC标量的汉明重量来提高HECC标量乘的方法[[3]]。

在超椭圆曲线密码体制中基点生成算法，除子加法以及除子随机生成算法是实现HECC的基本要素，而除子标量乘是HECC走向应用的关键算法。

本章主要研究超椭圆曲线密码体制有限域上的除子表示方法，除子阶的确定算法并提出了一种改进的HECC快速标量乘算法。

2HECC标量乘算法在超椭圆曲线密码体制中，Jacobian商群上的除子倍加问题是其核心问题。

除倍加问题也被称作除子标量乘，除子标量乘算法的效率是决定HECC应用的关键问题。

本节主要研究的内容为标量乘的快速算法[[4]]。

椭圆曲线四进制快速标量乘算法研究为提高智能电网ECC公钥算法中椭圆曲线标量乘的快速性和安全性，提出一种新算法——四进制快速标量乘算法，在Jacobi坐标上计算4P和4kP，在Jacobi-Affine坐标上计算点加，实现标量乘运算的快速性；在此基础上，提出一种改进算法——四进制分段并行标量乘算法，通过采用分段并行算法，隐藏真实能量消耗，以提高新算法的安全性。

研究表明：与NAF标量乘算法相比，四进制分段标量乘算法效率提高了57.9%，并能有效抵御SPA攻击，可根据设备的存储能力获得不同的运算效率。

新算法及其改进算法对改善椭圆曲线密码体制的性能具有一定理论意义与工程应用价值。

标签：椭圆曲线密码；四进制；标量乘；边信道攻击，信息安全0 引言智能电网信息安全是智能电网建设中的关键环节，国内学者在互联电力信息安全与安全管理、电力信息系统网络安全态势评估以及智能电网数据安全存储等方面做了大量的研究[1-4]。

椭圆曲线密码体制（elliptic curve cryptography，ECC）具有安全性高、密钥长度短、计算量小、计算速度快、[]占用存储空间少、带宽要求低等特点，而且ECC公钥算法不存在知识产权问题，因而被广泛应用于智能电网信息安全建设[5-8]。

标量乘运算是ECC中最主要的运算算法，即椭圆曲线非相邻形式（NAF）采用二进制编码，在单个坐标系上运算点加和点乘，具有耗时低效和不能抵御边信道（SCA）的缺陷。

快速、安全实现椭圆曲线密码体制对保证智能电网信息安全至关重要，因此如何提高标量乘的效率和抵御边信道攻击是提高椭圆曲线密码算法性能的关键。

本文针对椭圆曲线标量乘的快速实现和安全性，在NAF标量乘算法的基础上，提出一种新算法——四进制快速标量乘算法，在Jacobi坐标上计算4P 和4kP ，在Jacobi-Affine坐标上计算点加，实现标量乘运算的快速性；在此基础上，提出两种改进算法——四进制分段并行标量乘算法通过采用分段并行算法，隐藏真实能量消耗，以提高新算法的安全性。

基于伪四维投射坐标的多基链标量乘法徐明;史量【摘要】针对椭圆曲线密码系统的标量乘运算开销较大和易受能量分析攻击的问题,提出基于伪四维投射坐标的快速群运算和基于伪四维投射坐标的多基链标量乘法,对椭圆曲线密码系统的群运算层和标量乘运算层进行优化,旨在提高椭圆曲线密码系统的整体性能并抵御常见的能量分析攻击.实验表明,与现有算法相比,所提算法离散群运算的倍点运算开销降低5.71%,三倍点运算开销降低3.17%,五倍点运算开销降低8.74%.此外,在密钥长度为160位的情况下,所提算法连续群运算的三倍点运算开销降低36.32%,五倍点运算开销降低17.42%,系统整体开销降低8.70%.能量波形分析表明,所提算法可以有效抵御SPA攻击和DPA攻击.%In order to address the problem of elliptic curve cryptosystem (ECC) for the expensive cost in scalar multipli-cation and the vulnerability to the power analysis attacks, a pseudo 4D projective coordinate-based multi-base scalar mul-tiplication was proposed to optimize group operation layer and scalar multiplication operation layer, which aimed at in-creasing the performance of ECC and resisting common power analysis attacks. Experimental results show that compared with the state-of-the-art algorithms, the proposed algorithm decreases 5.71% of point doubling cost, 3.17% of point tri-pling cost, and 8.74% of point quintupling cost under discrete group operations. When the key length is 160 bit, the pro-posed algorithm decreases 36.32% of point tripling cost, 17.42% of point quintupling cost, and 8.70% of the system cost under continuous group operations. The analyzing of powerconsumption wave shows that the proposed algorithm can re-sist SPA and DPA attack.【期刊名称】《通信学报》【年(卷),期】2018(039)005【总页数】11页(P74-84)【关键词】椭圆曲线密码系统;坐标变换;多基链标量乘法;能量分析攻击【作者】徐明;史量【作者单位】上海海事大学信息工程学院,上海 201306;同济大学电子与信息工程学院,上海 201804;上海海事大学信息工程学院,上海 201306【正文语种】中文【中图分类】TP3931 引言公钥密码体制是密码学的重要组成部分。

一个新的基于radix-8的标量乘算法
程一飞;陈文莉
【期刊名称】《计算机技术与发展》
【年(卷),期】2007(017)010
【摘要】椭圆曲线标量乘是椭圆曲线密码系统中最关键、最耗时的运算,因此如何快速高效实现标量乘运算是研究的重点.目前常见的标量乘算法有:double-and-add算法,NAF算法,MOF算法等,但它们都是基于radix-2编码表示的,无论采用何种编码,倍点运算的次数都不变,减少的只是点加(或点减)运算的次数.提出一个基于radix-8表示的新的编码方法,及一个基于radix-8表示的标量乘算法,通过用八倍点运算代替倍点运算,且编码是从左到右(即从最高位向最低位)进行,编码和主计算可以合并,提高实现效率并节省内存空间.实验结果表明,该算法较经典的double-and-add算法能够提高效率30%以上.
【总页数】4页(P155-157,161)
【作者】程一飞;陈文莉
【作者单位】安庆师范学院,计算机系,安徽,安庆,246011;安庆师范学院,计算机系,安徽,安庆,246011
【正文语种】中文
【中图分类】TP309.7
【相关文献】
1.优化扩域上椭圆曲线标量乘的一个新算法 [J], 刘铎;戴一奇
2.一种新的基于半点运算与多基表示的标量乘法扩展算法 [J], 张占军
3.基于一个新的四维离散混沌映射的图像加密新算法 [J], 朱淑芹;李俊青;葛广英
4.一个新的基于MOF从左到右编码的多标量乘算法 [J], 程一飞
5.一个新的基于radix-4从左到右编码的标量乘算法 [J], 程一飞;侯整风
因版权原因，仅展示原文概要，查看原文内容请购买。

一种椭圆曲线标量乘的DSP并行算法
王继曾;张祥梅
【期刊名称】《科学技术与工程》
【年(卷),期】2008(008)012
【摘要】计算椭圆曲线标量乘是椭圆曲线密码算法的基础, 为了提高运算效率,探讨了椭圆曲线标量乘的基本实现算法,并设计了DSP并行环境,提出了一种并行实现算法.实验表明该并行算法有效地提高了标量乘运算的效率.
【总页数】3页(P3180-3182)
【作者】王继曾;张祥梅
【作者单位】兰州理工大学,计算机与通信学院,兰州,730050;兰州理工大学,计算机与通信学院,兰州,730050
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.一种椭圆曲线标量乘法的快速算法 [J], 蒋辉芹
2.一种基于FPGA的素域椭圆曲线标量乘结构 [J], 邬贵明;王淼;谢向辉
3.一种高效安全的椭圆曲线标量乘算法 [J], 陈熹;祝跃飞
4.一种抗侧信道攻击椭圆曲线标量乘算法的设计与实现 [J], 刘丽;徐明
5.一种高效的椭圆曲线密码标量乘算法及其实现 [J], 时丽平; 王子健
因版权原因，仅展示原文概要，查看原文内容请购买。

技术创新《微计算机信息》(管控一体化)2009年第25卷第8-3期360元/年邮局订阅号：82-946《现场总线技术应用200例》软件时空ECDSA 的算法改进及其标量乘法的选取Algorithm for Scalar Multiplication Based on an Improved Elliptic Curve Digital SignatureAlgorithm（北京化工大学）张凤元武美娜ZHANG Feng-yuan WU Mei-na摘要：本文从椭圆曲线数字签名的安全性和高效性要求出发，改进了椭圆曲线数字签名算法，并对其进行了正确性验证和安全性分析，结果表明，改进算法签名方不需要进行求逆运算，具有更少的时间复杂度。

为了进一步提高改进算法的运算速度，文中选取了优异的快速标量乘法并对其效果进行了分析。

关键词：椭圆曲线;数字签名;标量乘法；加减法中图分类号:TP309文献标识码:AAbstract:This paper studies the requirements of application system security and efficiency of the elliptic curve digital signature algo -rithm,improves the elliptic curve digital signature algorithm,verifies the correctness and analyzes the security of the improved algo -rithm.The results show that,it is no need for the improved algorithm signer to do the inversion ，and it has less time complexity.In order to improve the operation speed of the improved algorithm,we chose a better algorithm for scalar multiplication and analysis the effects.Key words:elliptic curve;digital signature;scalar multiplication;non-adjacent form文章编号:1008-0570(2009)08-3-0168-021引言椭圆曲线密码体制是目前已知公钥密码体制中每比特安全强度最高的密码体制，与RSA 等其他公钥密码体制相比，ECC 具有计算量小，储存空间占用少，处理速度快，带宽要求低，曲线资源丰富等优势，并且它是基于有限域上的椭圆曲线离散对数问题(ECDLP)的公开密钥算法，而ECDLP 计算困难性在计算复杂度上是完全指数级的，这就保证了ECC 极高的安全性。

一种高效安全的椭圆曲线标量乘算法陈熹;祝跃飞【摘要】Most secure Elliptic Curve Scalar Multiplication(ECSM) algorithms based on Point Verification(PV) and Coherency Check(CC) have low efficiency. Aiming at the problem, this paper proposes a new secure algorithm based on ternary representation and proves its correctness. The analysis about its efficiency in the affine coordinates and Jacobian coordinates is presented, whose result shows that the computational efficiency is improved while guaranteeing the security.%基于点验证和基于一致性检测的椭圆曲线标量乘安全算法一般运算效率低下.为此,通过对错误探测方法进行改进,提出一种基于三进制的椭圆曲线标量乘算法,给出算法的正确性证明,并在仿射坐标和Jacobian坐标下对其进行分析,结果表明,在保证安全性的前提下,该算法的效率有较大提高.【期刊名称】《计算机工程》【年(卷),期】2012(038)018【总页数】4页(P103-106)【关键词】点验证;一致性检测;椭圆曲线标量乘;错误分析攻击;三进制表示;仿射坐标;Jacobian坐标【作者】陈熹;祝跃飞【作者单位】解放军信息工程大学信息工程学院,郑州450002;解放军信息工程大学信息工程学院,郑州450002【正文语种】中文【中图分类】TP301.61 概述椭圆曲线密码体制(Elliptic Curve Cryptosystem, ECC)是由文献[1-2]分别提出的，而 ECC独特的优势使其成为公钥密码学研究的热点之一。

超椭圆曲线密码体制中标量乘法的快速算法研究超椭圆曲线密码体制中标量乘法的快速算法研究随着互联网的发展，隐私和安全越来越引起人们的关注。

密码学作为保护通信和数据安全的重要工具，被广泛应用于各个领域。

然而，传统的密码算法由于密钥长度较短，易受到暴力破解的攻击，安全性较低。

为了提高密码算法的安全性，超椭圆曲线（Super Elliptic Curve）密码体制应运而生。

超椭圆曲线密码体制是基于超椭圆曲线的离散对数难题的困难性来保证密码的安全性。

超椭圆曲线比传统的椭圆曲线具有更高的安全性和更快的计算速度，因而备受研究者的重视。

在超椭圆曲线密码体制中，标量乘法（ScalarMultiplication）作为一种基本的运算，对于密码算法的性能具有重要影响。

标量乘法是指将椭圆曲线上的点与一个标量进行乘法运算，得到另一个点的过程。

对于传统的椭圆曲线密码体制来说，标量乘法是一个相对复杂且耗时较长的运算。

而在超椭圆曲线密码体制中，由于超椭圆曲线具有更高的对称性，标量乘法的运算复杂度得到了显著的降低。

近年来，研究人员们针对超椭圆曲线密码体制中标量乘法的快速算法进行了广泛的研究。

其中最著名的算法是经典的蒙哥马利算法（Montgomery Algorithm），该算法基于超椭圆曲线的对称性，通过对坐标变换和倍乘运算进行优化，大幅度提升了标量乘法的计算速度。

蒙哥马利算法的基本思想是将椭圆曲线的方程转化为超椭圆曲线的方程，并引入一个辅助点来加速标量乘法的计算。

通过对坐标的变换，使得标量乘法的运算只需要进行一次点加和点加倍运算，从而减少了计算复杂度。

此外，蒙哥马利算法结合了位平衡方法和预计算技术，进一步提高了运算速度。

除了蒙哥马利算法，研究人员们还提出了一些其他的快速算法来加速超椭圆曲线密码体制中的标量乘法。

例如，利用窗口方法、扩展欧几里得算法和链表方法等。

这些算法在不同的场景下可以提供更高的运算效率和更好的安全性。

总而言之，超椭圆曲线密码体制中的标量乘法是保障密码安全的核心运算之一。

快速安全的椭圆曲线标量乘算法研究快速安全的椭圆曲线标量乘算法研究椭圆曲线密码学作为公钥密码学的重要研究方向之一，在现代密码学中发挥着重要的作用。

而椭圆曲线标量乘运算是椭圆曲线密码学中的核心运算之一，其在许多密码算法中都得到广泛应用，比如椭圆曲线数字签名算法（ECDSA）和椭圆曲线Diffie-Hellman（ECDH）密钥交换算法等。

在传统的椭圆曲线标量乘运算中，一般采用的是基于加法链的纯纺算法。

然而，由于纯纺算法需要对每一位的比特进行连续的加法和点的加法运算，其复杂度较高，运算速度较慢，不适用于需要大量运算的场景。

因此，研究人员开始尝试寻找更加快速、高效的椭圆曲线标量乘算法。

目前，已经提出了多种快速安全的椭圆曲线标量乘算法，其中较为知名的包括蒙哥马利算法（Montgomery Algorithm）、斯卡拉点乘算法（Scalar Multiplication Algorithm）和窃取者攻击（Twisted Edwards）算法等。

这些算法在不同的场景下都有其优势和适用性。

蒙哥马利算法是一种基于中心投影坐标系的标量乘算法，其具有计算速度快、内存开销小的优点。

斯卡拉点乘算法则是一种基于哈密顿轮换算法的标量乘算法，通过合理选择哈密顿函数和位运算，可有效降低额外的内存开销。

而窃取者攻击算法则是一种基于扭曲爱德华曲线的标量乘算法，通过引入扭曲变换，使加法和标量乘运算的复杂度降低。

此外，为了提高椭圆曲线标量乘运算的安全性，研究人员还引入了一些防抵抗攻击的技术，比如基于完全抵抗攻击的康纳尔蒙哥马利算法（CM-Montgomery Algorithm）、侧信道攻击抵抗的标量乘算法等。

这些技术在提高算法的速度和效率的同时，也能够有效地抵御各种针对椭圆曲线密码学的攻击手段。

总的来说，快速安全的椭圆曲线标量乘算法的研究是椭圆曲线密码学领域中的重要课题之一。

通过合理选择合适的算法和技术，可以在保证计算速度和安全性的同时，为实际的密码学应用提供强大的支持。

标量乘法的FPGA实现王峰;邹候文【摘要】从实际应用出发,研究了椭圆曲线标量乘法算法的FPGA的实现.采用P1363推荐的GF(2163)上的Koblitz曲线,首先设计了一个精简指令集的微处理器IP核,利用此指令集编程实现标量乘法,最终实现的标量乘法需要8 830个ALUT和5 575个register,运行一次标量乘法的时间为184.52 μs.与其他文献的标量乘法运算的硬件实现相比,实现的标量乘法运算在资源速度综合方面具有较大的优势.【期刊名称】《现代电子技术》【年(卷),期】2007(030)022【总页数】4页(P32-35)【关键词】椭圆曲线密码体制;标量乘法;IP核;精简指令集;FPGA【作者】王峰;邹候文【作者单位】福建工程学院,福建,福州,350014;广州大学,数学与信息科学学院,广东,广州,510006【正文语种】中文【中图分类】TP309.7椭圆曲线密码系统(ECC)是1985年分别由ler和Neal Koblitz独立提出。

相对于其他公钥密码系统(如RSA,ElGamal)，椭圆曲线具有计算速度快，存储空间小，带宽要求底等优点，特别适用于Smart卡和无线应用环境，受到人们的广泛关注，成为最有希望的公钥密码系统。

如何快速高效地实现椭圆曲线密码系统一直是人们的一个研究重点。

而制约椭圆曲线密码系统速度的关键是椭圆曲线标量乘法运算。

本文采用P1363[1]推荐的GF(2163)的Koblitz曲线，利用VHDL硬件编程语言，在FPGA上实现椭圆曲线的标量乘法运算。

在具体实现时，采用微处理器模式，首先设计一个支持标量乘法运算指令集的密码处理IP核，然后在此基础上编程实现。

由于标量乘法运算是通过调用有限域上的运算实现的，在此，首先介绍有限域上的乘法运算功能模块。

1 有限域上的乘法运算功能模块有限域GF(2m)形如(α,α2,α22,…,α2m-1)的基称为正规基。

有限域上的运算主要有加法、平方、乘法、求逆运算。

改进的基于整数拆分形式标量乘快速算法张亮【摘要】标量乘运算是椭圆曲线密码的关键运算.为有效提高椭圆曲线密码标量乘法的运算效率,给出了一种改进的带符号整数拆分形式标量乘快速算法.首先通过对标量进行带符号的整数拆分形式编码,然后将标量乘运算转化为由一组椭圆曲线上的点累加和形式进行计算,同时在预计算阶段采用更为高效的折半运算代替倍点运算.算法性能分析的结果表明:与已有的基于整数拆分形式标量乘快速算法相比,新算法的能够大幅提升运算效率,在应用椭圆曲线密码的各种系统中具有较好的实际应用价值.【期刊名称】《中国电子科学研究院学报》【年(卷),期】2016(011)005【总页数】5页(P490-494)【关键词】椭圆曲线密码;标量乘法;折半运算;整数拆分形式【作者】张亮【作者单位】郑州工业应用技术学院,河南郑州 451150【正文语种】中文【中图分类】TP309椭圆曲线密码体制(Elliptic Curve Cryptogram, ECC)是于1985年Koblitz N与Miller V最早提出来的。

ECC是将离散对数有限循环群替换成有限域上的椭圆曲线有限群所构造的密码体制，算法的安全性是建立在椭圆曲线对数问题的难解性之上的，同其余传统的密码算法相比，具备所需密钥长度更短，存储空间更小等优点[1-2]。

其核心运算主要是计算在椭圆曲线群上的标量乘法运算，它的运算速度决定着密码系统整体执行效率的关键。

国内外的研究学者在椭圆曲线密码的标量乘法运算方面做出了许多建设性的工作，为逐步提高椭圆曲线密码的运算效率，加快推进椭圆曲线密码实际应用做了大量贡献。

采用m_ary算法是椭圆曲线密码标量乘法运算的传统运算方式，主要是通过多次使用点加操作与倍点操作来计算[3]。

近年来，其它一些标量乘快速算法也被较多的提出来[4-5]。

其中，文献[6]中石润华等人提出了一种基于整数拆分的标量乘快速算法，并结合预计算的方法，能有效提升标量乘法的计算效率。