The world of cryptanalysis gets ever easier to see in intuitive terms. The trick is to see the world as Turing saw it: before codes and calculating devices mechanized codes and their cryptanalysis. Folks had to learn to exploit a particular language of mathematics conceived to model the entire space of discrete calculation. Of course particular we know this as the design language of the state machine – that in its cayley graph or wavefunction forms served the early role of a software language for turing machines.
One cannot separate coding, state machines, cryptoanalysis, or turing machines. They are each a manifestation of the same thing: walking the (quantum) random walk.
– Coding takes the 1920s notion of a probability space so cleary applied to mathematical physics in the form of heisenburg or schrodinger theories. It requires the concept of a field to be represented in terms of group theory – in which the vertices, edges and invariants such as meansets of the Cayley “designer’s” graph represents the applied codeword security “rules” of the group, in a highly geometric manner.
– The notion of state require that we recognize that group actions can be expressed in such as the 2d complex plane which better characterizes the rules of possible state transitions better than does the raw presentation of the underying graph.
– Cryptanalysis recognizes that advanced, exploitable geometric properties exist between nodes in the graph when rendered on a suitable plane. There are concepts such as distance, measure, coordinates and weights. More refined and analytic than phase diagrams that express raw possibility limits of state transitions in finite dimensional worlds building upon the very idea of quantization, the weight notion capture the notion of volume of probability space carved out of highly abstract functional analysis spaces. This all builds on and up from the area of space implied by the edge-distance between some node and each of its neighboring nodes and the probability depth capturing the likelihood that a random variable model ling discrete events will have a particular graph-value.
– And turing machines are the meta-spaces that governed by meta rules focused on the inner product of correlation relations and configurations for asymptotic limiting functions that can take such as the mean set induced by a sample function and tie together the rules of the group, the constraints of the probability field, the nature of the measure or distribution of probabilities and either output a codeword consistent with the rules or analyse a ciphertext codeword to distinguish it from a random event.
To a Turing in 1939 perhaps encountering the production side of the process of spying for the first time what is not new is the theory of codes, ciphers, and cryptanalysis. For he has been studying it in its theoretical manifestation for quite some time, quite evidently, in both the us and uk. All he has to do is apply the formalism theory to the particular nature of the various enigma machines he encounters – which introduces him yet more firmly to an aspect of the puzzle he has hardly encountered to that point: the notion of complexity of the search problem that stresses the relationship between the notion of security and cryptanalysis.
Though Turing surely knows the theoretical relevancy of such as the conjugacy search problem and has embraced the idea that certain coding groups engender reverse-searching problems that so expand the search space that the time required delivers “security” (that it takes longer to search out the key by brute force methods on average than the useful lifetime of the ciphertext) he also knows that the nature of the search problem changes in the calculation complexity sense – if only you move your calculator’s workings into the complex plane supporting phase or state space. The notion of the trapdoor, due to a change of scale or rotation of coordinates is not unknown.
In state space it becomes apparent that one can approximate the “inner nature” of coding functions using frequency analysis to at least guess crypto keys. the 1960s ldpc sum/product decoding is clear a minor variant of cryptanalytica process using centers and meanset theory to reduce the search problem – based perhaps on exploiting collisions within the differentials in the functions underlying ciphers (such as suitably engineered hagelin machines).
So the hunt has to be on for transforms that easily move a problem in discrete space into frequency space – in the days before the FFT, of course. However, let us not be overwhelmed by the FFT, for we know that even back in 1945, from Tunny documentation, that folks already had a discrete form of the FFT – what we now call the WHT. It merely exploits elementary generator sets (plus and negative signs on 1), that special heisenburg relation between parity and the fourier transform, and pairwise counting that reveals kasiski style bulges in distributions/measures, long used to crack indicator systems based on vigenere squares.
And so it falls to Turing and Newman. There topology focuses on the classical case of the cayley graph where the generators are the signs +1 and -1 (so usefully applied to peano arithmetic). These elementary members of the generating set nicely enable one to approach more generally what the old timers in room 40 of the Admiralty had been doing since WWI – when breaking the vigerere square (formulate depth cages for possible codeword lengths finding which auto-correlation measure is closed to the expected value). Having found the overall distance constraint for the unique space represented by the particular ciphertext in what we would these days call either additive or multiplicative auto and cross correlation, then consider the pairwise possibilities within each column of depths. One measures them – in terms of the possibilities that things agree or disagree in terms of sign counts.
As with breaking the codeword of a vigenere square through such as the computing the index of coincidence and then performing a frequency analysis of the depths in a particular column of cipher, more generally folks learn to identify the center of a graph – as manifest by its frequency spectrum. This is that “configuration” – to use a turingesque phrase – of vertices that allows particular nodes to be the center of the distribution of the space – and whose quantization oscillator now accounts for the variance found in ciphertexts that have depths/collisions.
In some sense the (tiny amount of) variance in these particular elements ultimately accounts for all the variance of the sets that can be generated. These foundational-fluctuations are a basis for the graph’s measure, much as generators and the non commutativity properties ultimately account for the evolution and transitions in a particular cayley graph making codebooks.
We tend to think of the turing machine as having started with the intensely discrete mechanism that slowly evolves, post war, into the notion of the indeterministic machine – driven by the probabalistic oracle already outlined (and obviously classified) in Turings phd thesis. But its not clear to me that this is the correct order. It seems more likely that a Turing, having studied measure theory, started with the notion that certain configurations can, in the limit, control variance – if only the mechanizing graph can be so constrained with the likes of cutsets. And use of free groups can deliver the desired levels of control over variance – giving one an algorithm for designing configurations of graphs (to be explored by turing machine “runtimes”) leveraging underlying groups such as high dimension braid groups that enable the cryptosystem designer to distinguish different types of security protocols, including indicator protocols such as the type Turing spent so much time attacking: naval enigma.