NAF的二进制表示法及其算法研究

Binary Representation of NAF and Its Algorithm Research

椭圆曲线加密的快速实现研究一直是该领域的研究热点,其中二进制数的非相邻表示型(NAF)因此被广泛应用,它主要应用在点乘运算,在该算法中用到的NAF是由带符号位的数字组成,所以通常采用一位一存储的方式,然而在一些存储资源有限的设备上这是极大的浪费;为了节省存储资源,提出一种NAF的二进制表示方法,这样就能将多位NAF数值按照运行平台的字长来存储,大大提高了存储资源的利用率;在此基础上给出NAF二进制表示法的算法及其点乘算法;实验结果表明该表示法的运算效率较原算法的效率没有太大的影响,尤其在点乘运算中影响更是微弱,但是在提高存储效率方面表现突出,节省存储空间达96%以上。

The fast implementation of elliptic curve cryptography has always been a research hotspot in this field,among which the non-adjacent representation of binary numbers(NAF) is widely used. It is mainly used in point multiplication. The NAF used in this algorithm is composed of digits with symbolic bits,so it usually uses one-by-one storage mode. However,it is great waste on some devices with limited storage resources. In order to save storage resources,a binary representation of NAF is proposed,which can store multiple NAF values according to the word length of the running platform,and greatly improve the utilization of storage resources. On this basis,the algorithm of NAF binary representation and its point multiplication algorithm are given. The experimental results show that the efficiency of this representation has little influence on the efficiency of the original algorithm,especially in point multiplication,but it is outstanding in improving the storage efficiency and saving more than 96% of the storage.