李　博　王　威　严迎建　李　伟

(解放军信息工程大学　河南 郑州 450001)



预计算类ECC标量乘算法高速存储控制电路设计

李博王威严迎建李伟

(解放军信息工程大学河南 郑州 450001)

摘要为提升椭圆曲线密码体制中最耗时的标量乘运算的计算速度，解决采用预计算的快速实现算法中数据存储问题，提取分析了NAF窗口算法、固定基窗口算法、固定基comb算法的存储需求和共性特征，设计了适合ECC处理器的统一寻址电路和向量结构的高效访存电路，有效支持目前具有预计算存储需求的典型算法，并使得访存效率和资源利用率大幅提升。在少量资源消耗下，与传统存储结构相比，访问存储性能提升达75%到95%。

关键词椭圆曲线密码标量乘预计算存储结构

DESIGNING HIGH-SPEED STORAGE CONTROL CIRCUIT FOR ECC SCALAR MULTIPLICATION ALGORITHM WITH PRE-COMPUTATION

Li BoWang WeiYan YingjianLi Wei

(PLA Information Engineering University,Zhengzhou 450001,Henan,China)

AbstractIn order to improve computation speed of most time-consuming scalar multiplication operation in ECC and to solve data storage problem of fast implementation algorithm using pre-computation, we extract the common features and analyse the storage requirements in regard to NAF window algorithm, fixed base window algorithm, fixed base comb algorithm, design efficient access and storage circuit suitable for unified addressing and vector structure of ECC processor, which effectively supports for current typical algorithms with pre-computation storage needs, and significantly enhances the efficiency of access and storage and the resource utilisation. While the resource consumption is few, its performance of access and storage improves up to the range of 75% to 95% compared with traditional storage structure.

KeywordsElliptic curve cryptography (ECC)Scalar multiplicationPre-computationStorage structure

0引言

椭圆曲线公钥密码体制ECC以其运算速度快，占用资源少、单比特安全强度高等特点已成为公钥密码的新标准[1]。标量乘是椭圆曲线密码算法的核心运算，决定着椭圆曲线密码体制的运算速度，如何高效实现标量乘是当前研究的一个热点。在众多标量乘算法中，NAF窗口算法、固定基窗口算法、固定基comb算法等通过采用预计算，成为最具速度优势的一类快速实现算法[2]。椭圆曲线密码体制通常采用专用的ECC处理器进行实现。预计算数据带来了额外的存储资源以及数据频繁访问存储的新问题，这也成为此类算法在处理器中适配的难点和瓶颈。

目前，许多研究者关注于算法本身，通过改进算法[3-6]，在保证速度的同时尽量降低存储消耗。……