Research papers

From Zodiac Killer Ciphers Wiki
Jump to: navigation, search

2021

2020

  • Mohammad Rakhmat Pramudita, Elvi Citraresmana, Susi Yuliawati. "The Similarities of Thematic Progression in Zodiac Killer Letters"
    • This study examines thematic progression in zodiac killer letters. This study aims to reveal the unknown killer whether it is personal killer or group killer. This study employs a descriptive qualitative method since it attempts to describe and analyze textual data accurately. The data of this study come from research publication article. After gathering the data, thematic progression theory proposed by Fries (2002) is employed to analyze the data. Findings show that constant theme is the type of thematic progression that is mostly used in the zodiac killer letters by 65.30%. However, some letters of zodiac killer contain a lot of similarities for instance they usually use constant theme and multiple theme but there is no linear theme. This study conclude that the similarities of thematic progression often occur in zodiac killer letters. It means that the zodiac killer letters are very possible written by one person. So it’s a personal crime, not group killer.

2019

  • Nils Kopal. "Cryptanalysis of Homophonic Substitution Ciphers Using Simulated Annealing with Fixed Temperature"
    • This paper describes the current progress of our research in the area of breaking homophonic substitution ciphers. Furthermore, it presents the state-of-the-art of cryptanalyzing this kind of cipher. There is a huge gap between the success rate of methods published in according research papers and the success rate of already available tools on the Internet. This paper also presents a small general taxonomy of monoalphabetic substitution ciphers. Finally, it shows how we broke different homophonic substitution ciphers in an automatic as well as in a semi-automatic way.
  • Tom S Juzek. "Using the Entropy of N-Grams to Evaluate the Authenticity of Substitution Ciphers and Z340 in Particular"
    • The present paper uses information theoretic entropy as a means to evaluate the authenticity of homophonic substitution ciphers. We motivate the use of entropy on n-grams and then validate its applicability, by using it on various true ciphers and pseudo-ciphers. Differences in entropy allow us to apply further formal analyses, e.g. support-vector machines, in order to make predictions about a potential cipher’s status. We train several support-vector machines and validate them. We then apply the models to two classic ciphers, the Zodiac Killer’s first major cipher, z408, which has been solved, and his second cipher, z340, which remains unsolved. The models correctly identify z408 as a substitution cipher. z340 is classified as an advanced cipher or pseudo-cipher.

2018

  • Jain, Chhibber and Kandi. "Cryptanalysis of Mono-Alphabetic Substitution Ciphers using Genetic Algorithms and Simulated Annealing"
    • In this paper, we intend to apply the principles of genetic algorithms along with simulated annealing to cryptanalyze a mono-alphabetic substitution cipher. The type of attack used for cryptanalysis is a ciphertext-only attack in which we don’t know any plaintext. In genetic algorithms and simulated annealing, for ciphertext-only attack, we need to have the solution space or any method to match the decrypted text to the language text. However, the challenge is to implement the project while maintaining computational efficiency and a high degree of security. We carry out three attacks, the first of which uses genetic algorithms alone, the second which uses simulated annealing alone and the third which uses a combination of genetic algorithms and simulated annealing.

2017

  • Lasry, George. "A Methodology for the Cryptanalysis of Classical Ciphers with Search Metaheuristics" 2017 (PDF)
    • Abstract: Starting from the 1990s, local search metaheuristics such as hill climbing, genetic algorithms, and simulated annealing have been employed, and in some cases, successfully, for the cryptanalysis of several classical ciphers. In most cases, however, results were mixed, and the application of such methods rather limited in their scope and performance. In this work, a robust framework and methodology for the cryptanalysis of classical ciphers using local search metaheuristics, mainly hill climbing and simulated annealing, is described. In an extensive set of case studies conducted as part of this research, this new methodology has been validated and demonstrated as highly effective for the cryptanalysis of several challenging cipher systems and machines, which could not be effectively cryptanalyzed before, and with drastic improvements compared to previously published methods. This work also led to the decipherment of original encrypted messages from WWI, and to the solution, for the first time, of several public cryptographic challenges.
  • Arkan Kh Shakr Sabonchi, Bahriye Akay. "Cryptanalytic of Substitution Ciphers by Artificial Bee Colony Algorithm Guided by Statistics based Fitness Function" (2017)
    • The secrecy and reliability of information have gained importance against the advancing technology and the interest in cryptology has also been increased. The purpose of this study is to analyze cryptanalytic attacks using cryptanalysis combined with Artificial Bee Colony Algorithm which is a swarm intelligence algorithm and successful to solve the complex problems. This study is the first that The Artificial Bee Colony algorithm is used for cryptanalytic in substitution ciphers which are the basic methods of cryptology system. The key and password are broken, and the plain text is obtained as a result of the comparison between the character in the encrypted text and the standard language character used.
  • Selman Repišti. "A Case Study of the Zodiac Letters Based on Forensic Linguistics and Psychology" (2017)
    • Serial killings and their perpetrators are an inexhaustible source of inspiration for professionals in the field of criminology, justice and psychology/psychiatry as well as the broad masses. According to the most famous (FBI) classification, there are organized and disorganized serial killers. Additionally, it is possible that perpetrators of such crimes could be characterized as the mixed type. Features and behavioral patterns of serial killers can be viewed from the angle of the constellation that comprises five features/tendencies: omnipotence, sadistic fantasy, ritual performance, dehumanization, and symbiotic merger. The aim of this paper is to offer a valid profile of a serial killer known as the Zodiac, based on his forensically relevant letters that he sent to newspaper editors. To this end, The current knowledge and insights related to forensic linguistics and psychology were used for this purpose. It was found that the offender could be a middle-aged man, with above-average intellectual abilities, for whom a high level of narcissism and manipulation are typical. In addition, the Zodiac is probably highly educated, well-read person, who is skillful in menial jobs, as well. It is possible that this person is single as well as that he had a strict father, who made his normal maturation into an adult difficult.

2016

  • Vobbilisetty et. al. "Classic cryptanalysis using hidden Markov models." 2016
    • Abstract: In this article, the authors present a detailed introduction to hidden Markov models (HMM). They then apply HMMs to the problem of solving simple substitution ciphers, and they empirically determine the accuracy as a function of the ciphertext length and the number of random restarts. Application to homophonic substitutions and other classic ciphers is briefly considered.
  • Zhong. "Cryptanalysis of Homophonic Substitution Cipher Using Hidden Markov Models." 2016
    • Abstract: We investigate the effectiveness of a Hidden Markov Model (HMM) with random restarts as a mean of breaking a homophonic substitution cipher. Based on extensive experiments, we find that such an HMM-based attack outperforms a previously developed nested hill climb approach, particularly when the ciphertext message is short. We then consider a combination cipher, consisting of a homophonic substitution and a column transposition. We develop and analyze an attack on such a cipher. This attack employs an HMM (with random restarts), together with a hill climb to recover the column permutation. We show that this attack can succeed on relatively short ciphertext messages. Finally, we test this combined attack on the unsolved Zodiac 340 cipher.
  • Vobbilisetty, Rohit, et al. "Classic cryptanalysis using hidden Markov models." Cryptologia (2016): 1-28.
    • Abstract: In this article, the authors present a detailed introduction to hidden Markov models (HMM). They then apply HMMs to the problem of solving simple substitution ciphers, and they empirically determine the accuracy as a function of the ciphertext length and the number of random restarts. Application to homophonic substitutions and other classic ciphers is briefly considered.

2015

  • Prajapat, Shaligram, et al. "Cryptic Mining in Light of Artificial Intelligence." (2015)
    • Abstract: The analysis of cryptic text is hard problem, and there is no fixed algorithm for generating plain-text from cipher text. Human brains do this intelligently. The intelligent cryptic analysis process needs learning algorithms, co-operative effort of cryptanalyst and mechanism of knowledge based inference engine. This information of knowledge base will be useful for mining data(plain-text, key or cipher text plain-text relationships), classification of cipher text based on enciphering algorithms, key length or any other desirable parameters, clustering of cipher text based on similarity and extracting association rules for identifying weaknesses of cryptic algorithms. This categorization will be useful for placing given cipher text into a specific category or solving difficult level of cipher textplain text conversion process. This paper elucidates cipher textplain text process first than utilizes it to create a framework for AI-enabled-Cryptanalysis system. The process demonstrated in this paper attempts to analyze captured cipher from scratch. The system design elements presented in the paper gives all hints and guidelines for development of AI enabled Cryptic analysis tool.
  • Nuhn, Malte, Julian Schamper, and Hermann Ney. "UNRAVEL—A Decipherment Toolkit." ACL-IJCNLP Proceedings Volume 2: Short Papers: 549. (2015)
    • Abstract: "In this paper we present the UNRAVEL toolkit: It implements many of the recently published works on decipherment, including decipherment for deterministic ciphers like e.g. the ZODIAC-408 cipher and Part two of the BEALE ciphers, as well as decipherment of probabilistic ciphers and unsupervised training for machine translation. It also includes data and example configuration files so that the previously published experiments are easy to reproduce."
  • Vobbilisetty, Rohit. "Cryptanalysis of Classic Ciphers Using Hidden Markov Models." (2015).
    • Abstract: "Cryptanalysis is the study of identifying weaknesses in the implementation of cryptographic algorithms. This process would improve the complexity of such algorithms, making the system secure. In this research, we apply Hidden Markov Models (HMMs) to classic cryptanalysis problems. We show that with sufficient ciphertext, an HMM can be used to break a simple substitution cipher. We also show that when limited ciphertext is available, using multiple random restarts for the HMM increases our chance of successful decryption."

2014

  • Serengil, Sefik Ilkin, and Murat Akin. "Attacking Turkish texts encrypted by homophonic cipher." Proceedings of the 10th WSEAS International Conference on Electronics, Hardware, Wireless and Optical Communications. 2014.
    • Abstract: "Homophonic cipher is developed as an alternative to substitution cipher to compose more resistant ciphertexts against to the frequency analysis attacks. Nevertheless, Attacking with taking advantage of characteristic vulnerabilities of the language is probable. In this paper, characteristic vulnerabilities of the Turkish Language for homophonic cipher are exposed and attacking approaches are illustrated."
  • Nuhn, Malte, Julian Schamper, and Hermann Ney. "Improved Decipherment of Homophonic Ciphers." (2014)
    • Abstract: "In this paper, we present two improvements to the beam search approach for solving homophonic substitution ciphers presented in Nuhn et al. (2013): An improved rest cost estimation together with an optimized strategy for obtaining the order in which the symbols of the cipher are deciphered reduces the beam size needed to successfully decipher the Zodiac-408 cipher from several million down to less than one hundred: The search effort is reduced from several hours of computation time to just a few seconds on a single CPU. These improvements allow us to successfully decipher the second part of the famous Beale cipher (see (Ward et al., 1885) and e.g. (King, 1993)): Having 182 different cipher symbols while having a length of just 762 symbols, the decipherment is way more challenging than the decipherment of the previously deciphered Zodiac- 408 cipher (length 408, 54 different symbols). To the best of our knowledge, this cipher has not been deciphered automatically before."
  • Yi, Jeffrey. "Cryptanalysis of Homophonic Substitution-Transposition Cipher." (2014).
    • Abstract: "Homophonic substitution ciphers employ a one-to-many key to encrypt plaintext. This is in contrast to a simple substitution cipher where a one-to-one mapping is used. The advantage of a homophonic substitution cipher is that it makes frequency analysis more difficult, due to a more even distribution of plaintext statistics. Classic transposition ciphers apply diffusion to the ciphertext by swapping the order of letters. Combined transposition-substitution ciphers can be more challenging to cryptanalyze than either cipher type separately. In this research, we propose a technique to break a combined simple substitutioncolumn transposition cipher. We also consider the related problem of breaking a combination homophonic substitution-column transposition cipher. These attacks extend previous work on substitution ciphers. We thoroughly analyze our attacks and we apply the homophonic substitution-columnar transposition attack to the unsolved Zodiac-340 cipher."
  • "Cipher Type Detection" (Malte Nuhn and Kevin Knight), Proc. EMNLP, 2014
    • Abstract: "Manual analysis and decryption of enciphered documents is a tedious and error prone work. Often—even after spending large amounts of time on a particular cipher—no decipherment can be found. Automating the decryption of various types of ciphers makes it possible to sift through the large number of encrypted messages found in libraries and archives, and to focus human effort only on a small but potentially interesting subset of them. In this work, we train a classifier that is able to predict which encipherment method has been used to generate a given ciphertext. We are able to distinguish 50 different cipher types (specified by the American Cryptogram Association) with an accuracy of 58.5%. This is a 11.2% absolute improvement over the best previously published classifier."

2013

  • Dhavare, Amrapali, Richard M. Low, and Mark Stamp. "Efficient cryptanalysis of homophonic substitution ciphers." Cryptologia 37.3 (2013): 250-281.
    • Abstract: "Substitution ciphers are among the earliest methods of encryption. Examples of classic substitution ciphers include the well-known simple substitution and the less well-known homophonic substitution. Simple substitution ciphers are indeed simple— both in terms of their use and their cryptanalysis. Homophonic substitutions are also easy to use, but far more challenging to break. Even with modern computing technology, homophonic substitutions can present a significant cryptanalytic challenge. This paper focuses on the design and implementation of an efficient algorithm to break homophonic substitution ciphers. We employ a nested hill climb approach that generalizes the fastest known attack on simple substitution ciphers. We test our algorithm on a wide variety of homophonic substitutions and provide success rates as a function of both the ciphertext alphabet size and ciphertext length. Finally, we apply our technique to the “Zodiac 340” cipher, which is an unsolved message created by the infamous Zodiac killer."
  • Nuhn, Malte, and Hermann Ney. "Decipherment Complexity in 1: 1 Substitution Ciphers." ACL (1). 2013.
    • Abstract: "In this paper we show that even for the case of 1:1 substitution ciphers—which encipher plaintext symbols by exchanging them with a unique substitute—finding the optimal decipherment with respect to a bigram language model is NP-hard. We show that in this case the decipherment problem is equivalent to the quadratic assignment problem (QAP). To the best of our knowledge, this connection between the QAP and the decipherment problem has not been known in the literature before."
  • Nuhn, Malte, Julian Schamper, and Hermann Ney. "Beam Search for Solving Substitution Ciphers." ACL (1). 2013.
    • Abstract: "In this paper we address the problem of solving substitution ciphers using a beam search approach. We present a conceptually consistent and easy to implement method that improves the current state of the art for decipherment of substitution ciphers and is able to use high order n-gram language models. We show experiments with 1:1 substitution ciphers in which the guaranteed optimal solution for 3-gram language models has 38.6% decipherment error, while our approach achieves 4.13% decipherment error in a fraction of time by using a 6-gram language model. We also apply our approach to the famous Zodiac-408 cipher and obtain slightly better (and near to optimal) results than previously published. Unlike the previous state-of-the-art approach that uses additional word lists to evaluate possible decipherments, our approach only uses a letterbased 6-gram language model. Furthermore we use our algorithm to solve large vocabulary substitution ciphers and improve the best published decipherment error rate based on the Gigaword corpus of 7.8% to 6.0% error rate."
  • Berg-Kirkpatrick, Taylor, and Dan Klein. "Decipherment with a Million Random Restarts." EMNLP. 2013.
    • Abstract: "This paper investigates the utility and effect of running numerous random restarts when using EM to attack decipherment problems. We find that simple decipherment models are able to crack homophonic substitution ciphers with high accuracy if a large number of random restarts are used but almost completely fail with only a few random restarts. For particularly difficult homophonic ciphers, we find that big gains in accuracy are to be had by running upwards of 100K random restarts, which we accomplish efficiently using a GPU-based parallel implementation. We run a series of experiments using millions of random restarts in order to investigate other empirical properties of decipherment problems, including the famously uncracked Zodiac 340."

2011

  • Ravi, Sujith, and Kevin Knight. "Bayesian inference for Zodiac and other homophonic ciphers." Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1. Association for Computational Linguistics, 2011.
    • Abstract: "We introduce a novel Bayesian approach for deciphering complex substitution ciphers. Our method uses a decipherment model which combines information from letter n-gram language models as well as word dictionaries. Bayesian inference is performed on our model using an efficient sampling technique. We evaluate the quality of the Bayesian decipherment output on simple and homophonic letter substitution ciphers and show that unlike a previous approach, our method consistently produces almost 100% accurate decipherments. The new method can be applied on more complex substitution ciphers and we demonstrate its utility by cracking the famous Zodiac-408 cipher in a fully automated fashion, which has never been done before."
  • Dhavare, Amrapali. Efficient attacks on homophonic substitution ciphers. Diss. San Jose State University, 2011.
    • Abstract: "Substitution ciphers are one of the earliest types of ciphers. Examples of classic substitution ciphers include the well-known simple substitution and the less well-known homophonic substitution. Although simple substitution ciphers are indeed simple - both in terms of their use and attacks; the homophonic substitution ciphers are far more challenging to break. Even with modern computing technology, homophonic substitution ciphers remain a significant challenge. This project focuses on designing, implementing, and testing an efficient attack on homophonic substitution ciphers. We use an iterative approach that generalizes the fastest known attack on simple substitution ciphers and also employs a heuristic search technique for improved efficiency. We test our algorithm on a wide variety of homophonic substitution ciphers. Finally, we apply our technique to the “Zodiac 340” cipher, which is an unsolved ciphertext created in the 1970s by the infamous Zodiac killer."

2010

2009

  • Erickson, Derrick, and Michael Hausman. "A Dominant Gene Genetic Algorithm for a Substitution Cipher in Cryptography." (2009)
    • Abstract: "This study is about breaking the substitution cipher in cryptography. The substitution cipher replaces every letter in a document with a different letter. This makes the document unreadable unless one can find the key to decrypt the document. A genetic algorithm is a way to combine the Darwin theory and genetics to converge on the solution after many generations or iterations. This genetic algorithm will decode the message by using unigram, bigram, trigram, and four-gram statistics to build the key. These statistics will not only determine the cost of a chromosome, how "good" a solution is, but will determine whether or not a gene is dominant. The mating function focuses on building a chromosome with the dominant genes. All dominant genes are passed to the child chromosomes to quickly converge on a solution. The mutation function searches "local" solutions by manipulating genes to make the overall solution better. After many generations, the encrypted message should look close to the original message."
  • Basavaraju, Pallavi Kanagalakatte. "Heuristic Search Cryptanalysis of the Zodiac 340 Cipher." (2009).
    • Abstract: "The Zodiac 340 cipher is one of the most famous unsolved ciphers of all time. It was allegedly written by “the Zodiac”, whose identity remains unknown to date. The Zodiac was a serial killer who killed a number of people in and around the San Francisco Bay area during the 1960s. He is confirmed to have seven victims, two of whom survived [1], although in taunting letters to the news media he claims to have killed 37 people. During this time, an encrypted message known as the Zodiac 408 cipher was mailed to 3 different newspapers in the San Francisco bay area. This was a homophonic cipher and was successfully decoded. Within a few days he sent out another cipher that was 340 characters long [4]. This cipher, which is known as the Zodiac 340 cipher, is unsolved to date. Many cryptologists have tried to crack this cipher but with no success. In this project, we implemented a novel genetic algorithm in an attempt to crack the Zodiac 340 cipher. We have attacked the cipher as a homophonic cipher where each cipher symbol is mapped to only a single English letter, but each English letter can be mapped to multiple cipher symbols. In the genetic algorithm, we implemented two variants of crossover: simple and intelligent. The simple crossover looks for commonly occurring substrings, without looking for actual English words in a putative decrypt. The intelligent crossover counts the number of actual English words that can be found in a putative decrypt when evaluating each solution. We implemented a dictionary lookup for quickly identifying English words for the intelligent crossover. The genetic algorithm using a combination of simple and intelligent crossovers was able to identify many English words in various putative decrypts but no solution was found."

2008

2007

  • Dao, Thang. Analysis of the zodiac 340-cipher. Diss. San Jose State University, 2007.
    • Abstract: "The main purpose of this project is to determine whether the method used in the Zodiac 340-cipher (Z340) letter was a homophonic substitution, an improved version of the well-known simple substitution. A homophonic substitution employs a "one-to-many mapping" technique, as opposed to the "one-to-one mapping" of a simple substitution. Due to the complexity of the homophonic substitution, an exhaustive solution to the Z340 is not possible in a feasible amount of time. This research proposes an approach to implement an automated solution to a homophonic substitution based on a hill-climb technique. The software will be used to attempt to solve the Z340. Even if the software fails to solve the Z340, useful conclusions could be drawn. The objective is to reduce the number of methods that could have been used to encrypt the original message."

2006

  • Samuel, D.. "Code breaking in law enforcement: A 400-year history." Forensic Science Communications 8.2 (2006).
    • Abstract: "The introduction profiles a 2004 case in which the FBI decrypted an enciphered message a jailed man wrote to his brother, which contained incriminating references to hiding evidence and moving the victim's body. The second case involved Unabomber Theodore Kaczynski (1978-1996), who kept notebooks in which he logged his crimes in a handwritten numerical code in both English and Spanish. The decryption and translation of these notebooks sealed the case against him. The third case reported involved the Zodiac killer, who has yet to be identified. He wrote ciphers related to his serial murders for publication in newspapers. Zodiac' most famous cipher was broken within a few hours by a husband and wife team of amateur code breakers. Other Zodiac ciphers, however, remain unsolved. The fourth case mentioned is the "Hollow Nickel Case" (1953-57), which involved a newspaper boy's accidental discovery of a microphotograph of a numbered code inside a hollow nickel that split when he dropped it on a sidewalk. The numbered code was a Soviet spy's one-time pad encryption system. The code was not broken until 1957, after a Soviet KGB officer defected to the United States. This eventually led to the conviction of a Soviet spy known by his alias of Rudolf Abel. Other cases include the work of cryptanalysts William and Elizabeth Friedman; the decryption of coded telegrams related to the Teapot Dome Scandal of 1924; and ciphers used in messages between conspirators in Lincoln's assassination and the Confederate government of Jefferson Davis. Also described are the use of ciphers in communications between Mary, Queen of Scots, and her coconspirators in the plot to kill her cousin Elizabeth, Queen of England. 18 references"

2005

2000-2004

  • Delman, Bethany. "Genetic algorithms in cryptography." (2004).
    • Abstract: "Genetic algorithms (GAs) are a class of optimization algorithms. GAs attempt to solve problems through modeling a simplified version of genetic processes. There are many problems for which a GA approach is useful. It is, however, undetermined if cryptanalysis is such a problem. Therefore, this work explores the use of GAs in cryptography. Both traditional cryptanalysis and GA-based methods are implemented in software. The results are then compared using the metrics of elapsed time and percentage of successful decryptions. A determination is made for each cipher under consideration as to the validity of the GA-based approaches found in the literature. In general, these GA-based approaches are typical of the field. Of the genetic algorithm attacks found in the literature, totaling twelve, seven were re-implemented. Of these seven, only three achieved any success. The successful attacks were those on the transposition and permutation ciphers by Matthews, Clark, and Gr¨undlingh and Van Vuuren, respectively. These attacks were further investigated in an attempt to improve or extend their success. Unfortunately, this attempt was unsuccessful, as was the attempt to apply the Clark attack to the monoalphabetic substitution cipher and achieve the same or indeed any level of success. Overall, the standard fitness equation genetic algorithm approach, and the scoreboard variant thereof, are not worth the extra effort involved. Traditional cryptanalysis methods are more successful, and easier to implement. While a traditional method takes more time, a faster unsuccessful attack is worthless. The failure of the genetic algorithm approach indicates that supplementary research into traditional cryptanalysis methods may be more useful and valuable than additional modification of GA-based approaches."
    • List of attacks mentioned in the paper
  • Gester, Joe. "Solving Substitution Ciphers with Genetics Algorithm" (2003)
    • Abstract: Genetic algorithms were used in an attempt to generally solve two classes of simple substitution ciphers. First, the full key space of all possi- ble substitution ciphers was searched. When this approach was met with limited success, the simpler approach of searching the more likely used keyword generated key space was implemented. This yielded somewhat more results.
  • Pimenidis, Lexi. "HOMOPHONE KRYPTOGRAPHIE." (2002) (German-language paper. Mentions Zodiac codes.)
    • Abstract: "Homophone Substitutionsverschlusselung kann verwendet werden, wenn traditionelle Algorithmen nicht mehr genug Sicherheit bieten, sowie als Basis fur stark ere Verschlusselungen. Durch das Einbringen von Zufallselementen und die Verwendung von Mengen anstatt einzelner Zeichen, soll eine Kryptoanalyse erschwert werden. Diese Arbeit zeigt anhand von einfachen Beispielen Moglichk eiten, Grenzen und Erweiterungen von homophoner Kryptographie auf."

pre 2000

  • Jakobsen, Thomas. "A fast method for cryptanalysis of substitution ciphers." Cryptologia 19.3 (1995): 265-274.
    • Abstract: "It is possible to cryptanalyze simple substitution ciphers (both mono and polyalphabetic) by using a fast algorithm based on a process where an initial key guess is refined through a number of iterations. In each step the plaintext corresponding to the current key is evaluated and the result used as a measure of how close we are in having discovered the correct key. It turns out that only knowledge of the digram distribution of the ciphertext and the expected digram distribution of the plaintext is necessary to solve the cipher. The algorithm needs to compute the distribution matrix only once and subsequent plaintext evaluation is done by manipulating this matrix only, and not by decrypting the ciphertext and reparsing the resulting plaintext in every iteration. The paper explains the algorithm and it shows some of the results obtained with an implementation in Pascal. A generalized version of the algorithm can be used for attacking other simple ciphers as well."
  • W. T. Penzhorn. "A fast homophonic coding algorithm based on arithmetic coding" (1994)
    • We present a practical algorithm for the homophonic coding of a message source, as required for cryptographic purposes. The purpose of homophonic coding is to transform the output of a non-uniformly distributed message source into a sequence of uniformly distributed symbols. This is achieved by randomly mapping each source symbol into one of a set of homophones. The selected homophones are then encoded by means of arithmetic coding, after which they can be encrypted with a suitable cryptographic algorithm. The advantage of homophonic coding above source coding is that source coding merely protects against a ciphertext-only attack, whereas homophonic coding provides additional protection against known-plaintext and chosen-plaintext attacks. This paper introduces a fast algorithm for homophonic coding based on arithmetic coding, termed the shift-and-add algorithm, which makes use of the fact that the set of homophones are chosen according to a dyadic probability distribution. This leads to a particularly simple, efficient implementation, requiring no multiplications but only shifts and additions. The usefulness of the algorithm is demonstrated by the homophonic coding of an ASCII textfile. The simulation results show that homophonic coding increases the entropy by less than 2 bits per symbol, and also provides source encoding (data compression).
  • Forsyth, William S., and Reihaneh Safavi-Naini. "Automated cryptanalysis of substitution ciphers." Cryptologia 17.4 (1993): 407-418.
    • Abstract: "We use simulated annealing to provide an automated method for the cryptanalysis of mono-alphabetic substitution ciphers. We prove the convergence of the algorithm and study its performance for a specific cooling schedule. We discuss the merits of this approach and show that it provides a simple, fast and elegant solution to the cryptanalysis problem which is also promising for more complex types of block ciphers."
  • King, John C., and Dennis R. Bahler. "An algorithmic solution of sequential homophonic ciphers." CRYPTOLOGIA 17.2 (1993): 148-165.
    • Abstract: "REMOVE_HOMOPHONES is a new cryptanalytic algorithm for the reduction of a sequential homophonic cipher without word divisions into a simple substitution cipher [8]. Sets of homophones, defined in the cipher alphabet, are detected algorithmically, without the use of either frequency analysis or trial-and-error backtracking, in a ciphertext-only attack. Given the output of REMOVE_HOMOPHONES, a simple substitution cipher, probabilistic relaxation [9,13] can complete the algorithmic solution of sequential homophonic ciphers without word divisions."
  • Spillman, Richard, et al. "Use of a genetic algorithm in the cryptanalysis of simple substitution ciphers." Cryptologia 17.1 (1993): 31-44.
    • Abstract: "This paper considers a new approach to cryptanalysis based on the application of a directed random search algorithm called a genetic algorithm. It is shown that such a algorithm could be used to discover the key for a simple substitution cipher."
  • King, DR Bahler. "A framework for the study of homophonic ciphers in classical encryption and genetic systems." Cryptologia, 1993 - Taylor & Francis
    • Abstract: "The multiplicity of a homophonic cipher is defined ion this paper as a real number M, where 0.0≤M≤1.0. The unicity distances of homophonic ciphers, the multiplicity of historical homophonic ciphers, and the multiplicity of genes are measured and represented in this framework."
  • Hakon N. Jendal, Yves J. B. Kuhn, James L. Massey. "An Information-Theoretic Treatment of Homophonic Substitution" (1990)
    • The history of cryptology shows that most secret-key cipher systems that have been broken were broken by exploiting the departure of the plaintext statistics from those of a completely random sequence. The technique of “homophonic substitution” is an old technique for converting an actual plaintext sequence into a (more) random sequence. At EUROCRYPT ’88, Günther [1] introduced an important generalization of homophonic substitution, which we will call “variable-length homophonic substitution”. The purpose of this paper is to give an information-theoretic treatment of Günther’s type of homophonic substitution.
  • Christoph G. Günther. "A Universal Algorithm for Homophonic Coding" (1988)
    • This contribution describes a coding technique which transforms a stream of message symbols with an arbitrary frequency distribution into a uniquely decodable stream of symbols which all have the same frequency.
  • Andrea Sgarro. "Equivocations for Homophonic Ciphers" (1984)
    • Substitution ciphers can be quite weak when the probability distribution of the message letters is distinctly non-uniform. A time-honoured solution to remove this weakness is to “split” each high-probability letter into a number of “homophones” and use a substitution cipher for the resulting extended alphabet. Here the performance of a homophonic cipher is studied from a Shannon-theoretic point of view. The key and message equivocations (conditional entropies given the intercepted cryptogram) are computed both for finite-length messages and “very long” messages. The results obtained are strictly related to those found by Blom and Dunham for substitution ciphers. The key space of a homophonic cipher is specified carefully, so as to avoid misunderstandings which appear to have occurred on this subject.
  • Stahl, Fred A. "A homophonic cipher for computational cryptography." Proceedings of the June 4-8, 1973, national computer conference and exposition. ACM, 1973.
    • Abstract: "Computational cryptography deals with the storage and processing of sensitive information in computer systems by en-cipfiering. Sensitive information is information that for one reason or another must be protected from being disclosed to individuals without proper authorization. The need for systems to be secure from unauthorized access to sensitive information has been well documented. Cyrptographic techniques appear to be one of the most simple and secure methods of providing this much needed protection."

Other:

  • Language models - A list of a few papers that involve the use of probabilistic language models for cryptanalysis. (link is broken)