Breaking Substitution Ciphers Using a Relaxation Algorithm Substitution ciphers are codes in which each letter of the alphabet has one fixed substitute, and the word divisions do not change. In this paper the problem of breaking substitution ciphers is represented as a probabilistic labeling problem. Every code letter is assigned probabilities of representing plain text letters. These probabilities are updated in parallel for all code letters, using joint letter probabilities. Iterating the updating scheme results in improved estimates that finally lead to breaking the cipher. The method is applies successfully to two examples. CACM November, 1979 Peleg, S. Rosenfeld, A. Cryptography, substitution ciphers, probabilistic classification, relaxation 3.42 3.63 CA791103 DB January 23, 1980 11:15 AM 3175 5 3175 3175 5 3175 3175 5 3175