A RAPID YES-NO COMPUTER-AIDED COMMUNICATOR

Abstract

When attacking the German Enigma cipher machine during the 1930s, the Polish mathematician Marian Rejewski developed a catalog of disjoint cycles of permutations generated by Enigma indicators. By comparing patterns that resulted from message indicators with his catalog, Rejewski was able to determine the ground settings. Well, not quite—the mapping from the disjoint cycles to the ground settings is not one-to-one. Rejewski's catalog no longer exists. This article reports on the output of a program that “recreates” the catalog and answers the question “How far from being one-to-one is the mapping?”     

Recovering the military Enigma using permutations—filling in the details of Rejewski's solution

During the last few months of 1932, the Polish mathematician Marian Rejewski solved the problem of finding the internal connections of the rotors and reflector of the Enigma cipher machine used by the German army at that time. This allowed the Polish Cipher Bureau to construct an analogue of the machine, and subsequently to find effective methods for deciphering secret messages. Rejewski performed this feat virtually alone using cryptographic material provided by the Polish secret services. His knowledge of the theory of permutation groups was essential in solving this problem.

This article describes in detail how to find the complete wiring of the rotors and reflector of Enigma, as well as other specifics, using data that Rejewski had at his disposal, by systematically presenting the resolution of all cases that could have been encountered. Similarly, we complete those stages of the procedure that were only outlined by Rejewski.     

RECOVERING THE WIRING OF ENIGMA'S UMKEHRWALZE A

Umkehrwalze A was the original reflector used in the version of the Enigma machine employed by the German armed services. Its wiring was originally deduced by the Polish cryptanalyst Marian Rejewski in December 1932 or January 1933, but details of the wiring have not previously been published. Sufficient information to recover the wiring analytically is provided in a wartime document by Alan Turing, and other sources have been found to confirm the solution. This paper presents the wiring, along with alternative methods of recovering it from Turing's data.     

REVIEW OF THINGS CRYPTOLOGIC

Abstract

Sets out, with comments, an account by A. G. Denniston (the operational head of the British Government Code and Cypher School in 1939) of the meeting near Pyry, Poland, in July 1939, when Polish cryptanalysts revealed how they broke Enigma, and a letter by Dillwyn Knox on the meeting's outcome.     

Cryptanalysis of Enigma double indicators with hill climbing

The Enigma machines were a series of electromechanical rotor cipher machines developed in Germany and used in the first half of the twentieth century to protect commercial, diplomatic, and military communications. Until 1938, the German Army used the so-called double-indicator procedure to transmit Enigma-encoded messages. It was replaced in September 1938 by a new procedure also involving double indicators. Both procedures enabled a team of mathematicians from the Polish Cipher Bureau to recover the wiring of the rotors and to develop cryptanalytic methods for the recovery of the daily keys. The double-indicator procedure was discontinued by the German Army in May 1940, and new methods were developed by the British at Bletchley Park, who were assisted by the knowledge transferred to them by the Polish cryptanalysts. In this article, the authors introduce two new algorithms that build on the historical cryptanalytic attacks on the two variants of the double-indicator procedures. Those attacks are based on hill climbing, divide-and-conquer, and specialized scoring functions, and they can recover the daily key using a number of indicators significantly smaller than the number of indicators required for the historical methods. Unlike the historical methods, the new algorithms produce unique and unambiguous results, including for scenarios with turnover of the middle rotor, and they also fully recover the plugboard settings. With these algorithms we won an international Enigma contest organized in 2015 by the City of Poznan, in memory of the Polish Cipher Bureau mathematicians.     

Modern breaking of Enigma ciphertexts

“Breaking German Army Ciphers” is the title of a Cryptologia article from 2005, describing the lucky survival of several hundred authentic Enigma messages of World War II, and an account of a ciphertext-only cryptanalysis of a large number of these messages, leaving only a few (mostly short messages) unbroken. After reviewing the work done, and investigating the reasons for both lucky breaks and close misses, the modern ciphertext-only attack on Enigma messages is improved, especially on genuine ones with short lengths and/or many garbles. The difficulties of a proper measure for the candidate’s closeness to a plaintext are clarified. The influence on the decryption process of an empty plugboard and one with only a few correct plugs is examined. The method is extended by a partial exhaustion of the plugboard combined with an optimized hillclimbing strategy. The newly designed software succeeds in breaking formerly unbroken messages.     

A new theorem in threshold logic and its application to multioperand binary adders

We present a new theorem in Threshold Logic which is a generalization of Mezei's theorem. We demonstrate one of its applications, i.e., the optimization of the size of depth-2 Multioperand Binary Adders. By applying this theorem, the weight complexity of the gates in the second layer of a previous construction is reduced from O(m·2 ⁿ ) to O(1), where m is the number of operands and n is the number of bits.     

NAVAL ENIGMA: M4 AND ITS ROTORS

The wiring of rotors in the naval version of Enigma is given (including that of beta and gamma) and events leading to the introduction of Triton, a cipher for Atlantic U-boats, are described. It is shown that an alpha rotor did not enter service, and that Triton became operational in October 1941.     

The Turing Bombe Victory and the first naval Enigma decrypts

Victory was the name of the first prototype Bombe that was developed for breaking the German Enigma messages of World War II. It lacked the diagonal board and simultaneous scanning that was provided for all the later models, but these disadvantages were overcome by the ingenious use of a column menu (a special Bombe menu where the Enigma fast rotors are all in the same position) to break six days of naval traffic, 22–27 April 1940, following the pinch of material from an armed trawler Schiff 26 (Polares). These were the first naval decrypts of the War, and their solution took several months to complete. No further naval breaks occurred until November. This article examines the decryption process in some detail in order to explain the difficulties, highlight the role of Victory in this process, and provide detailed workings of the processes. It also sheds some light on the early development of the British Bombe.     

Breaking “Tirpitz”: Cryptanalysis of the Japanese-German joint naval cipher

This article gives the solutions of the only four messages known to still exist from the previously unbroken Japanese-German joint naval radio communications traffic in the system known as “Tirpitz,” which used the specially-designed model T Enigma machine. It also explains the methods used by the author to break the messages, and gives some background on the model T Enigma and its usages.     

G-312: AN ABWEHR ENIGMA

G-312, an Abwehr Enigma in the collection of The Bletchley Park Trust is presented together with details of its internal mechanism and wheel wiring.     

NEEDLES AND HAYSTACKS: THE SEARCH FOR ULTRA IN THE 1930'S (AN EXCERPT)

This thesis traces the efforts in the 1930's of the Polish, French, and British Intelligence Services to break the German Enigma ciphering machine, efforts which led to the Bletchley Park Ultra operations of World War II. The cooperation, and lack thereof, among the intelligence services is discussed, with the conclusion that more cooperation sooner would have better served the individual national interest of each.     

The number of spanning trees of the regular networks

The classic theorem on graphs and matrices is the Matrix-Tree Theorem, which gives the number of spanning trees t(G) of any graph G as the value of a certain determinant. However, in this paper, we will derive a simple formula for the number of spanning trees of the regular networks.     

THE MARKET FOR ENCRYPTION

Abstract

In 1942, the United States Navy recognized that in the ranks of newly-enlisted WAVES lay the potential for much-needed assistance in processing German Navy Enigma messages that had been intercepted and deciphered. This is the improbable story of one of those WAVES.     

Doubling the Degree of Precision Without Doubling the Grid When Solving a Differential Equation with a Pseudo-Spectral Collocation Method

In the conventional pseudo-spectral collocation method to solve an ordinary first order differential equation, the derivative is obtained from Lagrange interpolation and has degree of precision N for a grid of (N+1) points. In the present, novel method Hermite interpolation is used as point of departure. From this the second order derivative is obtained with degree of precision (2N+1) for the same grid as above. The associated theorem constitutes the main result of this paper. Based on that theorem a method in put forward in which the differential equation and the differentiated differential equation are simultaneously collocated. In this method every grid point counts for two. The double collocation leads to a solution accuracy which is superior to the precision obtained with the conventional method for the same grid. This superiority is demonstrated by 3 examples, 2 linear problems and a non-linear one. In the examples it is shown that the accuracy obtained with the present method is comparable to the solution accuracy of the standard method with twice the number of grid points. However, the condition number of the present method grows like N ³ as compared to N ² in the standard method.     

Robust stability of a family of disc polynomials

In his well-known theorem, V. L. Kharitonov established that Hurwitz stability of a set f1 of interval polynomials with complex coefficients (polynomials where each coefficient varies in an arbitrary but prescribed rectangle of the complex plane) is equivalent to the Hurwitz stability of only eight polynomials in this set. In this paper we consider an alternative but equally meaningful model of uncertainty by introducing a set fD of disc polynomials, characterized by the fact that each coefficient of a typical element P(s) in fD can be any complex number in an arbitrary but fixed disc of the complex plane. Our result shows that the entire set is Hurwitz stable if and only if the ‘center’ polynomial is stable, and the H _∞-norms of two specific stable rational functions are less than one. Our result can be readily extended to deal with the Schur stability problem and the resulting condition is equally simple.     

A new lower bound on the monotone network complexity of Boolean sums

Summary Neciporuk [3], Lamagna/Savage [1] and Tarjan [6] determined the monotone network complexity of a set of Boolean sums if each two sums have at most one variable in common. By this result they could define explicitely a set of n Boolean sums which depend on n variables and whose monotone complexity is of order n ^3/2. In the main theorem of this paper we prove a more general lower bound on the monotone network complexity of Boolean sums. Our lower bound is for many Boolean sums the first nontrivial lower bound. On the other side we can prove that the best lower bound which the main theorem yields is the n ^3/2-bound cited above. For the proof we use the technical trick of assuming that certain functions are given for free.     

A General Decomposition Theorem for the k-Server Problem

The first general decomposition theorem for the k-server problem is presented. Whereas all previous theorems are for the case of a finite metric with k+1 points, the theorem given here allows an arbitrary number of points in the underlying metric space. This theorem implies O(polylog(k))-competitive randomized algorithms for certain metric spaces consisting of a polylogarithmic number of widely separated subspaces and takes a first step toward a general O(polylog(k))-competitive algorithm. The only other cases for which polylogarithmic competitive randomized algorithms are known are the uniform metric space and the weighted cache metric space with two weights.     

UMKEHRWALZE D: ENIGMA'S REWIRABLE REFLECTOR - PART III

Umkehrwalze D was a field-rewirable reflector for the German service Enigma machine, introduced primarily on German Air Force cipher networks late in the Second World War. This article discusses the history of the device and the various techniques and machines developed by the British and American signals intelligence agencies to deal with it.