Finding the key length of a Vigenère cipher: How to improve the twist algorithm

Abstract

A Vigenère cipher applies a single short key repeatedly to encrypt a plaintext. If a cryptanalyst correctly finds out the key length, the ciphertext can be divided into multiple instances of shift cipher and be broken by frequency analysis. To determine the key length, the twist algorithm, an alternate method to the standard Kasiski and Friedman tests, was recently proposed. In this article, we propose the twist⁺ algorithm, an improved twist algorithm, which can estimate the key length more accurately than the original twist algorithm.

Keywords:

• cryptanalysis
• polyalphabetic cipher
• substitution cipher
• twist index
• twist⁺ algorithm
• Vigenère cipher

About the authors

Seongmin Park is a graduate student at Myongji University. He received a B.S. degree in information and communication engineering from Myongji University in 2019. His research interests include computer security and blockchain.

Juneyeun Kim is a graduate student at Myongji University. He received a B.S. degree in electronic and electrical engineering from Pohang University of Science and Technology (POSTECH) in 2012. His research interests include cryptographic protocols and algorithms.

Kookrae Cho is a senior researcher at Daegu Gyeongbuk Institute of Science and Technology (DGIST). He received a B.S. degree from Pukyong National University in 2004 and an M.S. degree from the Pohang University of Science and Technology (POSTECH) in 2006. His research interests include cryptography, mobile device management, data analysis, and deep learning.

Dae Hyun Yum is an Associate Professor at Myongji University. He received a B.S., M.S., and Ph.D. degrees from the Pohang University of Science and Technology (POSTECH) in 1998, 2000, and 2006, respectively. He was a visiting researcher with New York University in 2005 and with Georgia Institute of Technology in 2007. His research interests include cryptography, combinatorics, and probability.

Acknowledgments

The authors would like to thank Tae Gu Kang and Jinwoo Lee for their helpful comments.

Additional information

Funding

This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2017R1D1A1B03031413).