Abstract:

Compared with the traditional public key cryptography such as RSA, ECC has a shorter key length but a higher computational complexity. So the attack against ECC encryption system is much harder. Research on the attacks to ECC public key cryptography is in favor of improving and preventing nonessential losses. Grover’s algorithm as a quantum search algorithm, which makes the number of steps of the search of the problem from the classic algorithm of N reduced to \sqrt[]{N}. It realized the secondary acceleration to classical algorithm. It can more quickly find the solutions. Meanwhile, scanning attack, which is a new side channel attack techniques, brings great threat to the current cryptographic system. Utilizing the advantages of the quantum Grover search algorithm, we improve the scanning attack on ECC, and then propose a new scanning attack on ECC which based on the Grover algorithm. For the ECC key length of N, the computational complexity is reduced from 2^N to 2N^3/2, furthering improve the efficiency of the cracks. Because of the determinate of Grover algorithm, the algorithm can success attack the cryptographic algorithms with the success rate of 100%.

Key words: ECC scanning attack, Grover algorithm, ECC, side channel attack, computation complexity