Paper 2021/554

Grover on Caesar and Vigenère Ciphers

Gyeongju Song and Kyungbae Jang and Hyunji Kim and Wai-Kong Lee and Hwajeong Seo

Abstract

Quantum computers can solve or accelerate specific problems that were not possible with classical computers. Grover's search algorithm, a representative quantum algorithm, finds a specific solution from $N$ unsorted data with $O(\sqrt{N})$ queries. This quantum algorithm can be used to recover the key of symmetric cryptography. In this paper, we present a practical quantum attack using Grover's search to recover the key of ciphers (Caesar and Vigenère). The proposed quantum attack is simulated with quantum programming tools (ProjectQ and Qiskit) provided by IBM. Finally, we minimize the use of quantum resources and recover the key with a high probability.