中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
椭圆曲线数乘运算的并行化研究
作者: 王亮
答辩日期: 2004
专业: 计算机软件
授予单位: 中国科学院软件研究所
授予地点: 中国科学院软件研究所
学位: 博士
关键词: 椭圆曲线密码 ; 数乘运算 ; 并行化
摘要: 椭圆曲线密码算法是一种重要的非对称密码算法,被许多著名的国际标准组织采纳,并广泛应用于商用密码领域。椭圆曲线密码算法中最主要的运算是数乘运算,数乘运算的效率决定了椭圆曲线密码算法的加解密速度。在串行的范畴内,人们对改进数乘运算的效率进行了大量的研究,并提出了不少改进算法。本文尝试从并行计算的角度来提高椭圆曲线密码算法中数乘运算的效率,并获得初步的成功。本文首先简要地介绍了椭圆曲线的数学基础、两种有限域上的椭圆曲线,基于椭圆曲线的密码体制,以及国内外改进椭圆曲线上数乘运算的现状。改进的途径大体分为四种,即:提高底层大整数运算及域运算的效率,使用不同的坐标系统,修改加法链,以及针对某些特殊曲线所做的优化。通过分析二进制算法及作为其改进算法的2~r-ary算法、加减链算法的运行时间的影响因素,论文继而提出了将2~r-ary算法并行化的算法,并对该并行算法的运行时间进行了理论上的分析。论文最后设计并实现了一个实验系统,以检验该并行算法的效果,并对实验数据加以分析。分析结果表明:受数乘运算中倍点运算次数与处理器数目无关这一瓶颈的制约,并行算法的效率受倍点运算的效率影响很大。当存在高效的倍点运算算法时,并行算法能较大幅度地提高数乘运算的速度,如在Fp域(p的长度为192-256),采用高效的倍点运算算法时,并行2~4-ary算法在4个处理器上并行执行时速度比串行的二进制算法约能提高76%,比串行的2~4-axy算法约能提高50%。
英文摘要: Being a important asymmetrical cryptography, Elliptic curve cryptography (ECC) is adopted by many famous international standardization organizations, and is widely used in commercial encryption. Scalar multiplication is the main operation in ECC. It determines the speed of encryption / decryption in ECC. Many studies were carried out on improving scalar multiplication, and many improved algorithms were presented. In this article, I present an algorithm based on parallelization. Firstly I present the basic mathematics of elliptic curves, and then present the elliptic curves defined on two finite fields, and then present the encryption schemas based on elliptic curves. Then I present the studies on improving scalar multiplication. Improving methods can be categorized into four classes, namely improving underlying operations, using another coordination system, improving addtion chains and improving some special elliptic curves. Then based on the analysis of running time of binary algorithm and its imroved variant, I present a parallel algorithm of scalar multiplication, and analyze the running time of that parallel algorithm. At last I design and implement a experimental system to test the performance of the parallel algorithm, and analyze the outcome of experiment. The data show that: restricted by the fact that the number of double operations is independent of the number of processors, the parallel algorithm is greatly affected by Double algorithm. Only when a efficient Double algorithm existes can the parallel algorithm greatly improve the speed of scalar multiplication. For example, when in Fp field, (the length of p is rangd from 192 to 256), and adopting the efficient Double algorithm, the parallel algorithm of 2~4-ary run on 4 processors can gain a speedup of about 76% than binary algorithm, and about 50% than sequentail 2~4-ary.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/6848
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
LW014096.pdf(1842KB)----限制开放-- 联系获取全文

Recommended Citation:
王亮. 椭圆曲线数乘运算的并行化研究[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2004-01-01.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[王亮]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[王亮]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace