Fast Elliptic Curve Cryptography Using Optimal Double-Base Chains
Fast Elliptic Curve Cryptography Using Optimal Double-Base Chains
复制标题
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Vorapong Suppakitpaisarn;M. Edahiro;H. Imai
中科院分区：
文献类型：
--
作者：
Vorapong Suppakitpaisarn;M. Edahiro;H. Imai
在这项工作中，我们提出了一种算法来产生双基链，以优化计算椭圆曲线密码系统所用的时间。双碱基链是结合了二元和三元表示的表示。通过这种方法，我们可以减少展开式的汉明重量，减少计算标量点乘(Q=RS)的时间，这是椭圆曲线密码体制的瓶颈运算。这种表示法是非常多余的，即我们可以通过多次展开来表示一个数。然后，我们可以选择使操作最快的方法。然而，以往关于双碱基链的工作都采用了贪婪算法，其解并不是最优的。我们提出了基于动态规划的算法，输出优化的双碱基链。实验表明，该算法的标量乘运算时间减少了3.88-3.95%，乘法运算时间减少了2.55-4.37%，较大位数集上的多标量乘法运算时间减少了3.5-12%。
In this work, we propose an algorithm to produce the doublebase chains that optimize the time used for computing an elliptic curve cryptosystem. The double-base chains is the representation that combining the binary and ternary representation. By this method, we can reduce the Hamming weight of the expansion, and reduce the time for computing the scalar point multiplication (Q = rS), that is the bottleneck operation of the elliptic curve cryptosystem. This representation is very redundant, i.e. we can present a number by many expansions. Then, we can select the way that makes the operation fastest. However, the previous works on double-bases chain have used a greedy algorithm, and their solutions are not optimized. We propose the algorithm based on the dynamic programming scheme that outputs the optimized the double-bases chain. The experiments show that we have reduced the time for computing the scalar multiplication by 3.88-3.95%, the multiscalar multiplication by 2.55-4.37%, and the multi-scalar multiplication on the larger digit set by 3.5-12%.