论文标题:椭圆曲线公钥密码体制中标量乘法运算快速算法的研究
Researches on the Fast Algorithm for the Scalar Multiplication in the Elliptic Curve Cryptosystems
论文作者 张宝华
论文导师 殷新春,论文学位 硕士,论文专业 计算机应用技术
论文单位 扬州大学,点击次数 152,论文页数 77页File Size4788k
2004-03-01论文网 http://www.lw23.com/lunwen_50607937/ 椭圆曲线;椭圆曲线密码体制;标量乘法;双基数系统;窗口算法;并行算法
elliptic curves; elliptic curve cryptosystems; scalar multiplication; number system; window algorithm; parallel algorithm
椭圆曲线密码,即基于椭圆曲线离散对数问题的密码体制,于1985年由N Koblitz和V Miller分别提出。椭圆曲线是代数数论、代数几何和解析数论这三门古老且富有活力的数学学科的一个交会点,本身具有许多独特的性质,将其应用到工程领域的密码技术而产生的椭圆曲线密码体制,一出现便吸引了很多密码学者的关注,从而成为公钥密码学的一个研究热点。 自椭圆曲线密码体制提出以后,经过众多密码学者十多年的研究,取得了丰富的研究成果。椭圓曲线具有最强的单位比特强度,而且对于椭圆曲线离散对数问题而言,目前还没有像解决离散对数问题那样的解决办法,因而椭圆曲线密码体制被一致认为是将要取代RSA体制的未来公钥密码体制。尽管如此,要达到适用化的程度,椭圆曲线密码体制还有许多问题尚待解决,如椭圆曲线密码体制的快速实现问题、随机安全椭圆曲线的选取问题、椭圆曲线密码体制的应用问题等等。 本文主要研究了椭圆曲线公钥密码体制中标量乘法运算的快速算法。主要从两个方面来研究快速算法,一是研究数域系统以加快标量乘法运算,二是研究标量乘法运算的并行算法。全文共分六章。其中,第一章概括地介绍了椭圆曲线密码研究的背景、意义、现状和本文研究的主要内容。第二章首先通过研究各种椭圆曲线密码体制,将椭圆曲线密码的快速实现问题归结为对标量乘法的计算,然后简单概述了标量乘法快速运算的一般算法。第三章从数域系统的角度出发,给出了基于SDBNS、Sub_SDBNS的快速标量乘法运算算法。第四章、第五章研究了标量乘法运算的并行实现,其中,第五章给出了并行窗口算法,第六章提出了一种新的并行算法NSP,这两个并行算法都在曙光2000上进行了模拟实现,并且,本文对实验结果进行了分析。
The Elliptic Curve Cryptosystems(ECC), based on the standard Elliptic Curve Discrete Logarithm Problem(ECDLP), was proposed by N Koblitz and V Miller in 1985. Elliptic curve is an intersection of the three subjects: algebra theory, algebra geometry and parse algebra. It has lots of particularly characters, to apply it to the engineering field such as cipher technology then bring a new subject ECC has attracts many cipher scholars interesting at the beginning, and became a hotspot of the public key cryptosystems.ECC has been studied for more than ten years since it had been proposed, and many results have been made by the cipher scholars. ECC has the most shortest key intensity, and the ECDLP is considered as the most difficult question. So ECC is consistently considered as the future public key cryptosystems instead of the RSA cryptosystems. In order to reach the extent of applicability, there are still many questions have to been resolved. For instance, the question of the efficiency implementation of elliptic curve cryptosystems, and the question of the random security selection of the elliptic curves, and the question of the application of the elliptic curve cryptosystems, etc.In this dissertation the elliptic curve cryptosystems and fast scalar multiplication algorithms are investigated. The methods to speed up the scalar multiplication computation are mainly discussed in two ways: one is the number system, another is parallel algorithm. It is consists of six chapters. In chapter one, some introductive materials are presented, including the motivations and the developments of the elliptic curve cryptosystems, the intentions of the research work, the main contents of the paper and the list of the results. In chapter two, the fast implementation problems of the elliptic curve cryptosystems are studied. In this chapter, the problems are firstly reduced to the computations of the scalar multiplication of the elliptic curves. Then all thealgorithms for the fast computations of the scalar multiplication of the elliptic curves are summarized. In chapter three, at the angle of number system, we proposed the fast algorithm for scalar multiplication based on DBNS, SDBNS, and SubSDBNS. In chapter four and five, we studied the parallel algorithm for scalar multiplication. In chapter four the parallel window method is proposed, in chapter five a new parallel method NSP is proposed. Both two algorithms are implementation on the Drawn-2000, and the results are been analysised.
|
