Slippery hill-climbing technique for ciphertext-only cryptanalysis of periodic polyalphabetic substitution ciphers

Abstract

We present a stochastic method for breaking general periodic polyalphabetic substitution ciphers using only the ciphertext and without using any additional constraints that might come from the cipher’s structure. The method employs a hill-climbing algorithm for individual key alphabets, with occasional slipping down the hill. We implement the method with a computer and achieve reliable results for a sufficiently long ciphertext (150 characters per key alphabet). Because no constraints among the key alphabets are used, this method applies to any periodic polyalphabetic substitution cipher.

Keywords:

• cryptanalysis
• hill-climbing
• periodic polyalphabetic substitution cipher
• Quagmire
• slippery hill-climbing
• Vigenère

Additional information

Funding

None.

Notes on contributors

Thomas Kaeding

Thomas Kaeding has a B.Sc. in Mathematics from the University of Michigan. His M.A. and Ph.D. in Physics are from the University of California.