QQ客服 官方微博 反馈留言

	一种新的余数系统下快速计算素域椭圆曲线点乘的方法
	吴焘 ; 李树国 ; 刘理天 ; WU Tao ; LI Shu-guo ; LIU Li-tian
	2016-03-30 ; 2016-03-30
关键词	余数系统 椭圆曲线点乘 蒙哥马利梯子 TP332.2
其他题名	A new RNS approach for fast F_p elliptic curve point multiplication
中文摘要	椭圆曲线密码运算主要是椭圆曲线点乘,后者由一系列的模乘构成。利用余数系统下的蒙哥马利模乘算法,素域中对阶取模余的模乘可以转化为对余数系统基底取模余。提出一种新的余数系统下的方法以加速计算椭圆曲线点乘。(1)与传统上取两个几乎对称的余数系统不同,该方法取了两个非对称的余数系统。其中,余数系统Γ包括两个模数{2L,2L-1};余数系统Ω包括八个模数,它们都具有如2L-2 Ki+1的形式。这种选择使其模算术变得简单。(2)在上述非对称的余数系统中,大部分原来需要对椭圆曲线域特征值取模的模乘运算可以在余数系统中直接用乘法代替。此外,计算椭圆曲线点乘时用到了仅计算x坐标的蒙哥马利梯子。在每次并行的倍点和点加结束时,需要四次余数系统下的蒙哥马利模乘,以压缩中间结果的值域。因此,计算一个N位的椭圆曲线点乘,需要的时间约为55.5 N·I,其中,I是一个L/2位的乘法、一次保留进位加法、一个L/2位的加法的总延时。; The basic computation in Elliptic Curve Cryptography(ECC)is Elliptic Curve Point Multiplication(ECPM),which consists of a series of modular multiplications.Through Montgomery modular multiplications in Residue Number System(RNS),the modular multiplications inFpcan be transformed into modular arithmetic over RNS moduli.A new RNS approach is proposed to accelerate ECPM.Firstly,instead of almost two symmetric RNSs,two asymmetric RNSs are chosen,with 2 moduli{2L,2L-1}for RNSΓand 8 moduli with the form of 2L-2Ki+1 for RNSΩ,which makes the modular reductions quite easy.Secondly,in the asymmetric RNSs,most modular multiplications can be performed by direct multiplications in RNS rather than modular multiplications in Fp.Especially,Montgomery ladder with only x coordinates is used for ECPM.At the end of every parallel point doubling and point addition,4 RNS Montgomery modular multiplications are performed to narrow the output range.As a result,the total time for an N-bit FpECPM is around 55.5 N·I,with I being the time delay of a(L/2)-bit multiplication,a carry save addition,and a(L/2)-bit full addition.
语种	中文 ; 中文
内容类型	期刊论文
源URL	[http://ir.lib.tsinghua.edu.cn/ir/item.do?handle=123456789/147098]
专题	清华大学
推荐引用方式 GB/T 7714	吴焘,李树国,刘理天,等. 一种新的余数系统下快速计算素域椭圆曲线点乘的方法[J],2016, 2016.
APA	吴焘,李树国,刘理天,WU Tao,LI Shu-guo,&LIU Li-tian.(2016).一种新的余数系统下快速计算素域椭圆曲线点乘的方法..
MLA	吴焘,et al."一种新的余数系统下快速计算素域椭圆曲线点乘的方法".(2016).

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。