基于Markov链的椭圆曲线标量乘法算法性能分析

在椭圆曲线密码系统中 ,采用规范重编码、滑动窗口等优化技术可以有效提高椭圆曲线上点的标量乘法k·P的运算性能 ,但在实现中 ,需要对不同优化技术的算法性能进行定量分析 ,才能确定标量乘法的最优实现 .本文运用Markov链对标量k规范重编码表示的滑动窗口划分过程进行了建模 ,提出了一种对椭圆曲线标量乘法的平均算法性能进行定量分析的方法 ,并运用该方法分析了不同参数下标量乘法运算的平均性能 ,计算了滑动窗口的最优窗口大小 .最后 ,通过比较说明 ,采用规范重编码和滑动窗口技术的椭圆曲线标量乘法的运算开销比用m ary法少 10 32～ 17 32 % ,比单纯采用滑动窗口法也要少 4 5 3～ 8 4 0 % .