作为椭圆曲线密码体制(ECC)的推广,超椭圆曲线密码体制(HECC)的代数结构更加复杂,安全性更高,应用前景更加广阔。然而,HECC仍存在一些瓶颈问题亟待解决,其中尤为突出的问题是如何加快Jacobian群上除子标量乘的运算速度,进而提高整个密码体制的实现效率。本文首先针对传统的除子标量乘算法进行优化及性能分析,然后提出了除子标量乘的通用并行化模型。最后,对算法进行了设计与实现,并在Spark平台进行了两种实验:基于本地环境的除子标量乘串行算法耗时对比实验、基于Spark集群环境的除子标量乘并行算法加速比实验。具体研究内容如下:(1)传统除子标量乘算法的优化及性能分析根据HECC的基本运算架构,自下而上进行了研究。除了针对域运算、Jacobian群运算等原子算法进行优化外,又重点研究和改进了 HECC中传统的除子标量乘法算法,如二元法、NAF算法、滑动窗口算法等,并分析和讨论了时间复杂度。(2)除子标量乘的通用并行化模型的提出及性能分析从理论层面进行了除子标量乘并行化设计,提出了除子标量乘的通用并行化模型,即划分整合模型,并分析了并行化模型的时间复杂度。(3)基于本地环境的除子标量乘串行算法耗时对比实验从实践应用方面,比较了传统算法与优化算法的运算耗时。实验结果表明:优化算法比传统算法的计算效率均有所提高,其中滑动窗口优化算法的效率提高比例最大,提高了 10.66%,其它优化算法相对于传统算法的计算效率也提高了 10%左右,充分证明了优化算法的有效性。(4)基于Spark集群环境的除子标量乘并行算法加速比实验结合常见的除子标量乘算法,采用划分整合模型进行并行化设计,并基于Spark集群环境进行除子标量乘并行计算,分别从“同任务规模,不同节点数量”、“同节点数量,不同任务规模”两个方面,分析并行算法的运算耗时和加速比。实验结果表明:(a)当任务规模一定时(比特长度为150),逐渐添加集群中的节点个数,加速比会保持继续增长。当节点个数8时,基于Spark集群平台的广义双基链算法的加速比达到了 7.4247。然而,随着节点个数增加,节点间通信开销也会增大,因此加速比的增长幅度会逐渐减小;(b)当集群中配置4个节点时,随着问题规模的增加,算法所需的运行耗时基本上呈现指数增长的趋势,加速比的增长趋势也非常明显,最终会逼近于极限加速比4.0。除此之外,进行了除子标量乘优化算法的安全性分析。分析结果表明:优化算法能够抵抗SCA攻击,比传统的除子标量乘串行算法具有更好的安全性能。综上所述,本文针对传统的除子标量乘算法进行优化,提出除子标量乘的通用并行化模型,并在Spark环境中进行设计与实验。实验结果表明,除子标量乘优化算法的计算效率高于除子标量乘传统算法,并且更加具有安全性保障。同时,除子标量乘并行化算法在Spark集群环境中具有良好的加速比,说明除子标量乘并行化算法可以有效缩短运算耗时,从而提高HECC的总体实现效率。