椭圆曲线密码,即基于椭圆曲线离散对数问题的密码体制,于1985年由N Koblitz和V Miller分别提出。椭圆曲线是代数数论、代数几何和解析数论这三门古老且富有活力的数学学科的一个交会点,本身具有许多独特的性质,将其应用到工程领域的密码技术而产生的椭圆曲线密码体制,一出现便吸引了很多密码学者的关注,从而成为公钥密码学的一个研究热点。 自椭圆曲线密码体制提出以后,经过众多密码学者十多年的研究,取得了丰富的研究成果。椭圓曲线具有最强的单位比特强度,而且对于椭圆曲线离散对数问题而言,目前还没有像解决离散对数问题那样的解决办法,因而椭圆曲线密码体制被一致认为是将要取代RSA体制的未来公钥密码体制。尽管如此,要达到适用化的程度,椭圆曲线密码体制还有许多问题尚待解决,如椭圆曲线密码体制的快速实现问题、随机安全椭圆曲线的选取问题、椭圆曲线密码体制的应用问题等等。 本文主要研究了椭圆曲线公钥密码体制中标量乘法运算的快速算法。主要从两个方面来研究快速算法,一是研究数域系统以加快标量乘法运算,二是研究标量乘法运算的并行算法。全文共分六章。其中,第一章概括地介绍了椭圆曲线密码研究的背景、意义、现状和本文研究的主要内容。第二章首先通过研究各种椭圆曲线密码体制,将椭圆曲线密码的快速实现问题归结为对标量乘法的计算,然后简单概述了标量乘法快速运算的一般算法。第三章从数域系统的角度出发,给出了基于SDBNS、Sub_SDBNS的快速标量乘法运算算法。第四章、第五章研究了标量乘法运算的并行实现,其中,第五章给出了并行窗口算法,第六章提出了一种新的并行算法NSP,这两个并行算法都在曙光2000上进行了模拟实现,并且,本文对实验结果进行了分析。