面向ECDSA的低复杂度多标量乘算法设计.docx资源-CSDN文库

版权申诉

139 浏览量 2022-11-28 20:27:17 上传评论收藏 185KB DOCX 举报

资源推荐

资源详情

资源评论

数字签名往往是通过公钥密码来进行的,与物理签名相比,具有不能被他人

更改的特性,通过身份认证和密钥协商可以保证通信安全

[1]

。在数字签名体系中,

与同为公钥密码体制的 RSA 算法相比 , 椭圆曲线密码 (Elliptic Curve

Cryptography,ECC)的加密和解密使用的密钥长度较短,可以减少存储空间和

功耗,适合在有限的硬件资源上体现

[2]

。根据椭圆曲线密码应用或密码协议所规

定的运算规程,现有的协议常见的有椭圆曲线密码数字签名算法(Elliptic Curve

Cryptography Signature Algorithm,ECCSA), 椭圆曲线密码密钥交换协议

(Elliptic Curve cryptography Diffie-Hellman,ECDH)和加密解密机制。椭圆曲线

密码算法性能依赖于标量乘算法运算性能,标量乘又可分解为点加(计算 P+G,

计算量用 A 表示)、倍点(计算 2P,计算量用 D 表示)、三倍点(计算 3P,计算量

用 T 表示)和五倍点(计算 5P,计算量用 Q 表示)等运算。

在生成公钥时,ECDSA 签名过程和 ECDH 密钥交换过程中使用的是单标

量乘算法,在 ECDSA 验签过程中使用的是多标量乘算法

[3]

。单标量乘主流算法

有倍点——点加二进制方法(Doubling and Addition method,D&A)

[4]

,非邻接表

示形 (Non-Adjacent-ForM,NAF)

[5]

和带窗口的非邻接表示形 (window width-

Non-Adjacent-Form,wNAF)

[6]

等算法 , 标量非 ‘0' 概率分别为 1/2 、 1/3 和

1/(w+1)。这些算法核心思想是通过额外的预处理,来扩大标量 k 中的 0 的位数

减少点加的次数,来加速标量乘。然而,窗口 w 扩大不仅使汉明权重下降,也导致

预处理的计算复杂度大幅度增长。目前,文献[7]所提出的多基链思想因其独特

的运算优势也成为了标量乘讨论的热点之一。根据基的个数,可以分成双基链

(Double-Base Chain,DBC)和多基链(Multi-Base Chain,MBC),多基链的宗旨是

将标量生成如下形式:

k= ∑i=1m∑i=1ms

bin

tri

qui

。

(1)

以多基链为优化方向的算法存在一个构建多基链时间长短的问题。根据贪

心法生成的思想,若构建的链过大,则会导致标量乘运行变慢;若构建一个最优的

链,则又会导致用在构建的时间上过长。文献[8]优化了三基链并提出了优化的

5P 运算,重新排序了基底有关{2.3.5}的运算顺序。文献[9]通过设计一个基于伪

四维投射坐标的多基链算法来优化构建多基链的方式,从而使得整体开销相对

于常规算法降低了 8.7%,文献[10]对双基链进行优化后可以保证相对比 wNAF

优化了超过 60%。文献[11]设计了一种基于 2,3 的双基链保证比 NAF 优化超

过 45%。

对于多标量乘算法,主流的算法有 Shamir

[12]

,联合稀疏形式(Joint Sparse

Form,JSF)

[13]

,联合双基链算法(Joint Double-Base Chain,JDBC)和联合多基链

算法(Joint Multi-Base Chain,JMBC )。Shamir 和 JSF 的汉明权重分别为 3/4

和 2/3。JMBC 在 MBC 的基础上,将两个标量联合表示为

(k1k2)k1k2= ∑i=1m(cidi)∑i=1mcidi2

bin

tri

qui

。

(2)

文献[14]提出了一种高效的转换联合三基方式。该方法设计很简单,使用的

硬件较少。文献[15]对 JSF 算法和 JMBC 进行了分析比对,并在三基链的基础

上进一步优化,大大提高了 ECDSA 的速度。文献[16]对 JMBC 的算法思想进行

了详细的描述和分析。文献[17]指出 A、D、T 和 Q 在雅克比坐标下的花费分

别为 12M+4S,4M+6S,6M+10S 和 15M+10S,其中 M 和 S 分别表示模乘和模平

方,模乘和模平方本质上都是模乘,这里可以近似将模乘和模平方视为同一运算

(模乘和模平方的计算比例约为 0.8M=1S

[18]

)。只需通过统计上述操作的模乘次

数即可评估复杂度。ECC 的整体运算是在有限域上运行的,其模乘等操作均有

取模运算,可以保证数据不会出现数据越界情况。并且,多基链所出现的非 0 位

和 0 位的概率并不固定,无法通过分析获得私钥值,可以保证其私钥的安全性。

由于在 ECC 系统既要用到单标量乘算法也要用到多标量乘算法,且为了追求效

率常常采用不同的多标量乘算法和单标量乘算法分别进行运算处理,这意味着

未考虑其他情况下重新进行标量乘算法的调用会导致计算复杂度的提升。

目前关于上述问题的解决方法,文献[19]在 KSS 曲线下提出了一种倾斜的

Frobenius 映射技术,并在其基础上设计了一个快速算法。文献[20]设计了一种

基于“平行点倍(点加和倍点平行)”的适用于单标量乘算法和多标量乘算法的并

行结构,并保证所用的时间和 NAF 算法几乎相同。文献[21]通过基于窗口的方

法进行了加速,使其相对于 shamir 和 NAF 优化了至少 7.9%。文献[22]使用了

GLV 方法来进行多标量乘算法的优化,保证在三维或四维 GLV 方法性能最好。

文献[23]利用三维 GLV 方法探索了在 r 坐标系上的快速标量乘法。构造并实现

了两种三维微分加成链 ,比使用 DJB 链的双标量乘法快约 6%。文献 [24]以

2,3,7 为基底的多基链整数表示形式及两种多标量乘快速算法,在素数域上,至

少比传统算法优化 3.1%。文献[25]使用了双基分解方法并进行对 Montgomery

曲线和 Edwards 曲线混合来进行加速。

笔者通过整除基底{2,3}并对二者不能整除的部分取模 3

的方式来构建

JDBC 表示形式,同时对余数进行预处理来进一步降低计算复杂度,从而保证了

在减少预处理的前提下避免了因分别运算处理导致的计算复杂度提升的问题。

1 低计算复杂度多标量乘算法设计

无论在 ECDSA 的签名过程,ECDH 密钥交换和 ECC 的密钥生成过程使用

的 private_keyG 单标量乘算法 , 还是在 ECDSA 验签过程中使用到

G+k

public_key 多标量乘算法(G 是椭圆曲线上的一个公共点,private_key 是

私钥,public_key 是对应 private_key 的公钥),都存在着对 k

G 进行计算。

因此在构建以{2,3}为基底进行转化 JDBC 的形式中,对两个标量进行整除

基底 2 和 3 的操作时,不能整除基底的部分则对两个标量进行同时取模 3

,并

对余数有关 G 和 P+G 的多倍点操作进行预处理,使得两个标量可以同时处理标

量 k

和 k

的共同部分。当在调用单标量乘的过程中 k

是 0 的情况下,直接对 G

的预处理进行相应的计算,从而保证了单标量乘和多标量乘算法的正确性。计

算形如 mG+nP 的多标量转换则如下所示:

mG+nP→,b

(m1Gn1(P+G)+b2(m2Gn2(P+G)+...bi(miGni(P+G))))m1Gn1

(P+G)+b2m2Gn2(P+G)+...bimiGni(P+G),⎛⎝⎜m1n1b1⎞⎠⎟m1n1b1=⎧⎩⎨⎪⎪

⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎛⎝⎜m1=0n1=0b1=3

⎞⎠⎟

若

m≡0⎛⎝⎜mod3⎞⎠⎟

且

n≡0⎛⎝⎜mod3⎞⎠⎟

,⎛⎝⎜m1=0n1=0b1=2⎞⎠⎟

若

m≡0⎛⎝⎜mod2⎞⎠⎟

且

n≡0⎛⎝⎜mod2⎞⎠⎟

,⎛⎝⎜m1=mmod3x2y−n1,n1=nmod3x2yb1=2⎞⎠

⎟

若

和

不能整除

或

,m1=0n1=0b1=3 若 m≡0(mod3)且

n≡0(mod3)　　,m1=0n1=0b1=2 若 m≡0(mod2)且

n≡0(mod2)　　,m1=mmod3x2y-n1,n1=nmod3x2yb1=2 若 m 和 n 不能整除 2 或

3　　,m=(m-m

-n

)//b

,n=(n-

剩余13页未读，继续阅读

评论收藏

内容反馈

版权申诉

罗伯特之技术屋

粉丝: 3542
资源: 1万+

面向ECDSA的低复杂度多标量乘算法设计.docx

一种低复杂度的改进wNAF标量乘算法.docx

西南交通大学算法分析与设计实验报告 - 染色问题时间复杂度.docx

面向多椭圆曲线的高速标量乘法器设计与实现.docx

算法的设计与分析——时间复杂度.docx

安全高效的两方协同ECDSA签名方案.docx

ECDSA签名算法ECDSA签名算法ECDSA签名算法ECDSA签名算法

椭圆曲线数字签名算法ECDSA.pdf

ECDSA签名【利用ECDSA签名算法实现密码加密】

ecdsa.zip_ECDSA_ecdsa C语言

ECDSA算法实现源码.rar_ECDSA_ECDSA 算法_Openssl ECDSA_ecdsa openssl

ECC和ECDSA算法

ECDSA.rar_ECDSA_ECDSA 编程实现_ecdsa算法_认证

ecdsa-0.15-py2.py3-none-any.whl

ECDSA-Test.rar_ECDSA_ECDSA签名算法

python-ecdsa-0.11-3.el7.noarch.rpm

无线局域网产品采用的ECDSA和ECDH密码算法椭圆曲线和参数.pdf

ECDSA快速验签算法

ECDSA算法实现源码

ECDSA椭圆曲线加密算法

The Elliptic Curve Digital Signature Algorithm (ECDSA).pdf

ecdsa-0.10.tar.gz

trezor-crypto, 面向嵌入式设备的重优化密码算法.zip

相关实用应用程序（Windows可用）

免费可用的ChatGPT网页版.zip

ChatGPT使用总结：150个ChatGPT提示词模板（完整版）

chromedriver-win64.zip

全国计算机二级WPSoffice精选350道选择题题库（含答案）.pdf

民宿网站

桌面聊天室

最新资源