基于Grover算法的ECC扫描式攻击

相对于传统的RSA等公钥密码,ECC具有密钥长度短,计算复杂度高等特点,因此针对ECC加密体制的攻击复杂度高、难度大。研究针对ECC公钥密码的攻击方法有利于提前完善和防止不必要的损失。Grover算法作为一种量子搜索算法,将搜索步数从经典算法的N缩小到N^(1/2),实现了对经典搜索算法的二次方加速作用,能更快速地寻找所需的解。扫描式攻击作为一种新生的侧信道攻击技术,它的出现给当前密码系统的安全性带来了极大的威胁。文章利用量子Grover搜索算法的快速搜索优点,对Rynuta提出的针对ECC密码芯片的扫描式攻击进行了改进,提出了基于Grover算法的ECC扫描式攻击方法。该算法对于密钥长度为N的ECC,计算复杂度由2~N降低到2N^(3/2),进一步提高了破解效率。由于Grover搜索算法的确定性,该算法的攻击成功率为100%。