Search

Cryptanalysis of a British military cipher of 1759 shows the cipher to be a polyalphabetic cipher.

On Saturday March 30, 1985, we solved a cryptography puzzle that had remained unsolved for over two years. Unfortunately for us, we missed by one day the deadline for sharing what had become a $117,000 prize. This paper describes the puzzle and how we solved it. The $100,000 Decipher Puzzle consists of a simple two-sided jigsaw puzzle that contains a sequence of 376 codenumbers, ranging from 1 to 1252, which were encrypted by a multiple-substitution cipher similar to the Beale cipher. Clues state that the key was derived from some keytext in the public domain. We solved the puzzle by building a Zetalisp program that tested candidate keytexts by trying a variety of ways to extract candidate keys from each keytext and by checking the resulting candidate plaintexts for English. Our program exploited a novel “windowing” technique that detected when part of a candidate key was correct and an effective test for English based on digraph frequencies.

This article is an exposition of a pencil and paper cipher used by Soviet secret agents working inside the U. S. that successfully defied the government's computer-aided attempt at cryptanalysis for several years.

An early Indian cipher that dates perhaps as early as 4th century A.D. is described. Basically, this cipher maps numerals into consonants; the vowels between the consonants may be used freely.

A diary entry of Charles L. Dodgson, better known as Lewis Carroll, indicates that he invented two polyalphabetic ciphers in 1858. He published neither of them. In this paper we present one, a matrix based cipher, and show that it is equivalent to a Variant Beaufort cipher using a non-standard arithmetic. This is placed in historical perspective not only from the point of view of cryptography but also in regard to the state of mathematics in England in the middle of the nineteenth century. The authors have written a computer program that can be used to explore this and similar ciphers.

Hermes8 [6,7] is one of the stream ciphers submitted to the ECRYPT Stream Cipher Project (eSTREAM [3]). In this paper we present an analysis of the Hermes8 stream ciphers. In particular, we show an attack on the latest version of the cipher (Hermes8F), which requires very few known keystream bytes and recovers the cipher secret key in less than a second on a normal PC. Furthermore, we make some remarks on the cipher's key schedule and discuss some properties of ciphers with similar algebraic structure to Hermes8.

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 misunder standings which appear to have occurred on this subject.

Objectives: Computer security is all about the study of cyber attacks with a view to defend against them. Cryptography is considered to be a class of science by using the special art of transforming information in a protected way such that it can overcome the attacks. There is an immense requirement of strong cryptographic algorithms in order to withstand against the various attacks. Methods: The Kerchoff''s Principle states that the encryption and decryption algorithms are always available to anyone. The security of the cipher against any sort of attack should be depends only on the secrecy of the key. There comes the play of cryptanalysis. It is art of breaking the keys by identifying the vulnerabilities existing in the systems. This paper deals with the classical encryption schemes and their cryptanalysis. The cryptanalysis for various encryption schemes differs a lot. Various cryptanalysis like statistical analysis, frequency analysis, trial and error (brute force) are carried out in this work. Findings: The classical encryption schemes such as caesar cipher, shift cipher, vigenere cipher, affine cipher and hill cipher are discussed in the paper. A detailed analysis about the security of the above mentioned ciphers are explored. Among the ciphers it is identified that if the key varies for each plaintext to be encrypted provides added security. But the worst is the management of the huge key space. A modified algorithm is proposed which can provide a better security using simple computations. In this approach lots of keys are used but generated from a single key by using simple shift and EXOR operation. In the main stream only one key need to be exchanged between the communication entities and for that exchange we can make use of the public key cryptosystem. Application: Cryptography is considered to be an ineluctable field in era of communication. Cryptographic algorithms acts as an underpinning for lots of applications such as Anonymous Remailers, Digital Signatures, Secured Money transactions etc.

We investigate the use of Particle Swarm Optimization (PSO) in automated cryptanalysis of classical simple substitution ciphers. Based on our experimental results, PSO-based attacks proved to be very effective on various sets of encoding keys.

In this paper, we investigate the use of Ant Colony Optimization (ACO) for automated cryptanalysis of classical simple substitution ciphers. Based on our experiments, ACO-based attacks proved to be very effective on various sets of encoding keys.

This paper discusses mixing of some non-linear chaotic maps, e.g. a logistic equation and a tent mapping, as simplified method for information encryption and decryption. A ciphertext is obtained by the iteration of defined mixing chaotic maps from an initial state. Because the secure control parameters of these chaotic mappings are modulated according to currently encrypted plaintext, the proposed cipher algorithm can be treated as some homophonic substitution cipher with encryption key defined by initial state of build-in chaotic maps and some additional parameters. The resulting cipher algorithm is investigated against typical attacks on classical encryption schemes. The objective of these attacks is to recover plaintext from ciphertext or to deduce the decryption key. In this paper we study the exhaustive key search attack and find that this attack is not efficient as a practical attack on proposed cipher. Similar conclusion concerns some classical attacks, e.g.: ciphertext-only attacks and a known-plaintext attacks.

This paper presents an approach for the automated cryptanalysis of substitution ciphers based on a recent evolutionary metaheuristic called Scatter Search. It is a population-based metaheuristic founded on a formulation proposed two decades ago by Fred Glover. It uses linear combinations on a population subsets to create new solutions while other evolutionary approaches like genetic algorithms resort to randomization. First, we implement the procedures of the scatter search for the cryptanalysis of substitution ciphers. This implementation can be used as a framework for solving permutation problems with scatter search. Then, we test the algorithm and show the importance of the improvement method and the contribution of subset types. Finally, we compare its performances with those of a genetic algorithm.

Perhaps the simplest way to extend the basic monoalphabetic substitution codes is to define two cipher alphabets and use them alternately. In the example below, the first letter S of the plain message SURRENDER is replaced by D from cipher alphabet 1, but the second letter U is replaced by D from cipher alphabet 2. The same cipher letter D replaces two plaintext letters. Similarly, the two cipher letters Q and L stand for the plain letter A. This primitive polyalphabetic substitution cipher, developed by the Renaissance figure Leon Battista Alberti, is already much safer than any monoalphabetic cipher. (The same Alberti also constructed a simple cipher disk, similar to the one shown in Figure 5.1, that’s the predecessor of all the many rotor encryption machines that followed. See Section 5.1.)

We cryptanalyse some block cipher proposals that are based on dedicated hash functions SHA-1 and MD5. We discuss a related-key attack against SHACAL-1 and present a method for finding ”slid pairs” for it. We also present simple attacks against MDC-MD5 and the Kaliski-Robshaw block cipher.

The Mercy block cipher is examined, and a differential attack is shown. Using this differential, a method of distinguishing the cipher from a random permutation is given.

Although Turkish is a significant language with over 60 million native speakers, its cryptographic characteristics are relatively unknown. In this paper, some language patterns and frequencies of Turkish (such as letter frequency profile, letter contact patterns, most frequent digrams, trigrams and words, common word beginnings and endings, vowel/consonant patterns, etc.) relevant to information security, cryptography and plaintext recognition applications are presented and discussed. The data is collected from a large Turkish corpus and the usage of the data is illustrated through cryptanalysis of a mono-alphabetic substitution cipher. A new vowel identification method is developed using a distinct pattern of Turkish--(almost) non-existence of double consonants at word boundaries.

In 1915 First Lt. Joseph O. Maubourgne, later MG Maugorne and Chief Signal Officer, 1937–1941, presents a simple substitution cipher challenge to the Army Signal School. He proposes a test to determine if his new cryptosystem should replace the Cipher Disk and Playfair Cipher then in use.

We introduce a new method for cryptanalysis of DES cipher, which is essentially a known-plaintext attack. As a result, it is possible to break 8-round DES cipher with 221 known-plaintexts and 16-round DES cipher with 247 known-plaintexts, respectively. Moreover, this method is applicable to an only-ciphertext attack in certain situations. For example, if plaintexts consist of natural English sentences represented by ASCII codes, 8-round DES cipher is breakable with 229 ciphertexts only.

This paper describes a systematic procedure for decrypting simple substitution ciphers with word divisions. The algorithm employs an exhaustive search in a large on-line dictionary for words that satisfy constraints on word length, letter position and letter multiplicity. The method does not rely on statistical or semantical properties of English, nor does it use any language-specific heuristics. The system is, in fact, language independent in the sense that it would work equally well over any language for which a sufficiently large dictionary exists on-line. To reduce the potentially high cost of locating all words that contain specified patterns, the dictionary is compiled into a database from which groups of words that satisfy simple constraints may be accessed simultaneously. The algorithm (using a relatively small dictionary of 19,000 entries) has been implemented in Franz Lisp on a Vax 11/780 computer running 4.3 BSD Unix. The system is frequently successful in a completely automated mode -- preliminary testing indicates about a 60% success rate, usually in less than three minutes of CPU time. If it fails, there exist interactive facilities, permitting the user to guide the search manually, that perform very well with minor human intervention.

Tree structures have been proposed for both the construction of block ciphers by Kam and Davida (1979), and self-synchronous stream ciphers by Kuhn (1988). Attacks on these ciphers have been given by Anderson (1991), and Heys and Tavares (1993). Here the authors demonstrate that a more efficient attack can be conducted when the underlying Boolean functions for the cells are known. It is shown that this attack requires less than one third of the chosen ciphertext of Anderson's original attack on the Kuhn cipher.

Cryptanalysis of the stream cipher 'Labyrinth', a cipher recently proposed by Lin and Shepherd (1997), is performed. Given only 2/sup 30/ known bits of keystream, the 119 bit key of Labyrinth is recovered in under a second of computation using a DEC Alpha.

We present a cryptographic scheme for encrypting 2-D gray scale images by using a large family of fractals. This scheme is based on a transposition of the image elements implemented by a generator of 2-D hierarchical scanning patterns producing a large subset of the (n2)! possible orders defined on a 2-0 image of n x n elements. Each pattern defines a distinct order of pixels and can be described by an expression, which is considered as the key of the transposition. This transposition cipher can easily be combined with various substitution ciphers, producing efficient product ciphers operating on pictorial data. Two such ciphers are constructed and their effects on real gray value images are shown. Encryption and decryption algorithms are derived from a parailel algorithm implementing the creation of the family of scanning patterns.

This paper presents a non-numerical polygraphic substitution cipher which appears more efficient than Hill's algebraic system. For instance, by using the same number of “operations” per message as a 6-graphic algebraic substitution cipher, the present cipher can achieve 4096-graphic substitution. Less dramatically, a 16-graphic application of the present cipher requires only one-eighth as many operations as a 16-graphic algebraic cipher. The source of the greater efficiency of the proposed cipher is that the number of letters which can be jointly enciphered is exponential, rather than linear, with respect to the number of operations performed.

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 plaintext 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 applied successfully to two examples.

Correlation of relative information content of spacing interval distributions is defined. A procedure is outlined which achieves significant improvement in vowel identification for blocks of simply substituted text as short as 20 letters.

Evidence is presented which tends to indicate that the possible interpretations of very short simple substitution cipher are few in number. If “side information” is available, that is, if the analyst can correctly recognize topic, style, content, or completeness of thought, then simple substitution ciphers shorter in length than the unicity distance can readily be solved. Such results provide a theoretical basis for cryptanalytic methods which begin initially with very short segments of text.

The equivocation of the key for a simple substitution cipher is upper and lower hounded, when the message source is memoryless. The hounds are shown to be exponentially tight. The results are compared with random ciphering. It is observed that the exponential behavior of the equivocation of the key is not determined by the redundancy in the message source, but by the symbol probabilities which are closest in a certain sense. The title is incorrect in the IEEE version. The first word is Bounds, not Sounds.

Probabilistic relaxation estimates the probabilities of the potential labelings of the nodes of a multigraph. The constraints used are limited to those nodes which are connected by arcs in this multigraph. A multiplicative formula called the product rule is introduced for combining the estimates of several nodes. This formula is then shown to correspond to a discrete relaxation operator. Experiments were made using the product rule to break a substitution cipher and to disambiguate the semantic labeling of the pixels of a color image of a house. The experiments showed that in some applications, the product rule converges more rapidly to estimates that permit making reasonable decisions than did a previous formula using arithmetic averaging. The experiments also suggested ways to refine the relaxation formulas to produce more precise estimates.

This paper shows how a single message in the Gromark cipher, a system which uses a pseudo-random decimal key, can be broken, and investigates some variations of the basic scheme and the properties of the keys.

This paper reports an extension of work published in 1986 by Carroll and Martin [1,2]. The earlier work automatically solved simple substitution ciphers in a cryptotext-only attack. It used a computer program written in the artificial intelligence language Prolog. The Prolog data base contained 1084 rules. The work reported here reduces the running time required to break simple substitution ciphers and breaks polyal-phabetic ciphers as well. Results suggest that the only inherent limitations on the ability to break ciphers as the number of crypto alphabets increases reside in the speed of computation and the availability of cryptotext.

A cipher used by the astronomer Aryabhata (c. 500 A.D.) is described. It converts numbers into letter sequences and a number can be represented by many different cipher sequences. The cipher can be viewed as an example of an encryption paradigm where the encryption is defined by a key class rather than a single key. By defining an extremely large set of keys, the task of the cryptanalyst can become well nigh impossible.

This article reports the last of a series of experiments performed between 1984 and 1988 to explore the limits of artificial intelligence (AI) techniques in the automated solution of ciphers in crypt-text-only attacks. We started with simple substitution ciphers and went on to solve polyalphabetic ciphers, geometric transposition ciphers, and product ciphers that combined the last two techniques.

Expert systems programmed in artificial intelligence languages can break simple substitution ciphers by capturing and employing knowledge about the relative frequencies of single letters and certain combinations of letters in certain positions. These techniques can be extended to fixed-key polyalphabetic ciphers after using regression analysis to separate out the segments of text enciphered in each component alphabet.

A cipher based on word block lengths interpreted as base N numbers, and converted to base M numbers is described. The advantage is that the ciphertext length can be chosen to be greater or less than the plaintext length, even though word divisions are maintained. This gives a very high resistance to Probable Word searches. In its simplest form, however, the number of possible keys is limited, reducing the security of the cipher once the basis is guessed.

Finding the keylength is the essential step in breaking periodic substitution ciphers. However, the well-known Index of Coincidence technique becomes less reliable as the keylength increases. We describe an empirical method, based on regression analysis of frequency counts from a sample of ciphertexts, which is more reliable, yet easier to use.

The Beale Treasure Cipher (Bl) has withstood the attacks of several generations of amateur and professional cryptanalysts. This paper reports a statistical anomaly in Bl which suggests that it may be a hoax.

The cipher presented here is trigraphic, because triples of letters are mapped into triples of letters, and it is truly tri-graphic because all three letters of the triple are treated in the same fashion. The key consists of a square or rectangular array of letters (like that used for the Playfair), which must have an odd number of rows and an odd number of columns. The cipher is a very simple algebraic cipher, but it is suitable for hand ciphering and deciphering. It is believed to be almost as easy to use as a Play-fair or Delastelle, and possibly more secure against cryptanalysis.

A substitution cipher consists of a block of natural language text where each letter of the alphabet has been replaced by a distinct symbol. As a problem in cryptography, the substitution cipher is of limited interest, but it has an important application in optical character recognition. Recent advances render it quite feasible to scan documents with a fairly complex layout and to classify (cluster) the printed characters into distinct groups according to their shape. However, given the immense variety of type styles and forms in current use, it is not possible to assign alphabetical identities to characters of arbitrary size and typeface. This gap can be bridged by solving the equivalent of a substitution cipher problem, thereby opening up the possibility of automatic translation of a scanned document into a standard character code, such as ASCII. Earlier methods relying on letter n-gram frequencies require a substantial amount of ciphertext for accurate n-gram estimates. A dictionary-based approach solves the problem using relatively small ciphertext samples and a dictionary of fewer than 500 words. Our heuristic backtrack algorithm typically visits only a few hundred among the 26! possible nodes on sample texts ranging from 100 to 600 words.

For simple substitution ciphers an exact expression and bounds are derived for the message equivocation in terms of the key equivocation. It is established that the message equivocation approaches the key equivocation exponentially fast for discrete memoryless sources. It is observed that the exponential behavior of the message equivocation is not determined by redundancy in the message source but by either the symbol probabilities which are closest in a certain sense or the sum of the two smallest symbol probabilities.

At the SAC'96 the iterated block cipher, Akelarre, was proposed. Akelarre uses components of the block ciphers RC5 and IDEA and is conjectured strong with four rounds. This paper shows that Akelarre with any number of rounds is weak even under a ciphertext only attack. This illustrates that mixing two (presumably) strong ciphers is not always a good idea.

Cryptography is one of the most popular fields of study these days as it is necessary to maintain the confidentiality of the data which is sent over the network. There are various cipher techniques available for encrypting the messages such as vernam cipher, mono-alphabetic cipher, poly-alphabetic cipher, etc. One of the most popular cipher techniques is the vigenere cipher. It is a poly-alphabetic cipher technique which uses the vigenere table for the process of encryption of alphabets. This paper extends the vigenere table by including numerical data, so that the numbers can also be encrypted using this technique. It combines the encryption process of vigenere and Caesar cipher for getting the cipher text from the given plaintext and key.

This paper introduces an applied problem-solving task, set in the context of cryptography and embedded in a network of computer-based tools. This designed learning environment engaged students in a series of collaborative problem-solving activities intended to introduce the topic of functions through a set of linked representations. In a classroom-based study, students were asked to imagine themselves as cryptanalysts, and to collaborate with the other members of their small group on a series of increasingly difficult problem-solving tasks over several sessions. These tasks involved decrypting text messages that had been encrypted using polynomial functions as substitution ciphers. Drawing on the distinction between viewing functions as processes and as objects, the paper presents a detailed analysis of two groups’ developing fluency with regard to these tasks, and of the aspects of the function concept underlying their problem-solving approaches. Results of this study indicated that different levels of expertise with regard to the task environment reflected and required different aspects of functions, and thus represented distinct opportunities to engage those different aspects of the function concept.