椭圆曲线密码体制(ECC)是建立在椭圆曲线离散对数问题基础上的。在实现ECC中的加解密计算时,标量乘(点乘)是其中一个基本的运算。所谓标量乘就是将椭圆曲线上的一个有理点连续相加若干次,其中相加的次数是一个整数,称之为标量。将整数标量表示为特殊的形式可以降低标量的海明重量(非零比特的个数),从而加快标量乘的计算,比如非邻接表示(Non-Adjacent Form, NAF)和滑动窗口表示(wNAF)的方法。这些传统的标量乘算法主要是基于标量的二进制表示的。使用两个或者多个基来表示整数标量,可以进一步降低标量的海明重量,比如Doche等人提出的双基链法就是以2和3为基来表示标量。之后还出现了几个双基链的扩展算法,比如多基链、扩展的双基链、基于树的双基链等。这类基于双基链的整数表示,都是通过贪心算法编码获得的,很难精确计算出它们的平均海明重量。于是,这些使用双基链或多基链的标量乘算法中参数的设置是通过经验或者仿真实验来进行的,而这些算法的平均时间复杂性也很难精确分析。此外,编码算法本身的运行速度有时会变慢。Longa和Miri提出的多基NAF、窗口多基NAF和扩展窗口多基NAF,是另一种双基、多基表示。本文讨论了扩展的窗口多基表示,对其分析得到了它的精确平均海明重量,进而计算出使用它的标量乘算法的平均时间复杂性。说明了多基NAF和窗口多基NAF都是扩展窗口多基NAF的特殊情况。正是因为可以对扩展的窗口多基NAF进行精确的形式化分析,该算法中的参数可以根据不同情况方便的选取,使该标量乘算法达到最快。分析结果表明,在大素数域上进行标量乘计算时,扩展窗口多基NAF算法跟类双基链法相比更快,并且其编码算法如传统的NAF算法一样简单和快速。Smart等人曾多次研究了在特征为3的域上如何快速计算标量乘。,本文在特征为3的域上,分别改进了投影、雅可比和LD坐标系上的点运算公式。特别是三倍点和倍点-点加运算公式的加快,使得扩展窗口多基NAF算法在这种情况下可以大大提高标量乘的计算速度。新设计的快速点运算公式与Smart的相比,速度提高了4%-15%。在不需要额外存储空间的情况下,使用改进后的点运算公式的扩展窗口多基NAF算法比Smart等人的“三倍点-点加”算法快了22.5%。如果有足够的存储空间,新算法比Smart等人的快了37.1%。在特征为2的域上计算标量乘时,Bernstein等人曾提出使用二元Edwards曲线来加快计算速度。在二元域上,一条普通的椭圆曲线有多个有理等价的二元Edwards曲线。那么在将普通曲线转换为二元Edwards曲线时,可以挑选参数是稀疏整数(非零比特数目很少)的二元Edwards曲线来加快标量乘的计算。本文通过代数变换,提出了更快的算法来将一般曲线变换为等价的二元Edwards曲线。在某些已有的数论、密码学函数库的实现中,域上的求逆、求元素的迹等运算与乘法相比的比率比较大,这时新算法的时间复杂性明显较低。比如使用NTL5.4.2或者Magma进行仿真实验时,新算法的速度可以提高23.3%-16.6%。超椭圆曲线上的标量乘与椭圆曲线上的非常相似,但是其上的除子运算公式要复杂很多。蒙特卡洛梯度算法是一个经典的标量乘算法,使用它可以有效抵抗简单边带信道攻击。本文在特征为2的域上,通过改进超椭圆曲线上的除子加法运算公式,来加速超椭圆曲线上的蒙特卡洛梯度算法。在特征为2的域上,新的运算公式的运行速度在投影坐标系和Lange提出的两种新坐标系上比之前的公式均有所提高。特别是在类型Ⅱ的曲线上,新公式比之前的公式快了4%-8.3%。双核及多核处理器的广泛应用,促使人们研究如何并行实现椭圆曲线密码体制中的运算。Mishra曾首次考虑将流水线方法和点运算公式原子化的方法相结合,设计适用于双核环境下且可以抵抗边带信道攻击的标量乘计算方案,但是他只考虑了雅可比坐标系。本文进一步将Edwards曲线、反向Edwards曲线和扭曲Edwards曲线上的点运算公式原子化,设计出新的标量乘计算方案。如果使用传统的NAF算法计算标量乘,新方案比Mishra的快了12.5%。如果使用窗口算法计算标量乘,那么当窗口值选取为5时,新方案快了14.3%。此外,新算法可以抵抗简单边带信道攻击和差分边带信道攻击,且没有增加额外的运算量。