The common substitution cipher that shifts every letter in the alphabet n letters to the left or right is known to every cereal box reader. Perhaps less known is its extension to poly-alphabetic substitution ciphers invented in 1553 where consecutive letters are shifted by different amounts. This can be according to a periodic key or a one-time pad, introduced in 1917. The randomly generated non-repeating key, i.e. one-time pad or running key cipher, is not possible to decipher. However, if the non-repeating key is text, a common encryption mistake, then the message can occasionally be deciphered. In this paper we show how to decipher using the Viterbi algorithm. The case of repeating keys, both English text or random, will be treated as well. We measure the error rate of the decryption on a test set where the messages and keys are known. We further resolve a cipher text for which the original message and key was not available to us.
By: Peder Olsen; John Hershey; Steven Rennie; Vaibhava Goel
Published in: RC25109 in 2011
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .