Purple Encryption Machine
During the Second World War, Japanese experts worked on the development of encryption systems, the names of which were given by color shades. In the mid-30s, American intelligence revealed a secret cipher - the "purple" code. As a result of the work of a special team, headed by the famous American cryptographer William Frederick Friedman, it was found that the Japanese are using a new encryption machine. Friedman diligently engaged in deciphering the "purple" code - one of the most complex. And in 1940, the work gave results, the code was cracked, and its algorithm was published. Hacking a Japanese cipher helped US intelligence gain access to secret diplomatic correspondence.
As for the encryption device, the Americans initially assumed that they were dealing with one of the versions of Enigma. But it was soon discovered that the "purple" code belongs to the Japanese encryption machine, code-named Purple. In Japan, it is known as Alphabet Type 97 Typewriter (original 九七 式 文 印字 機) or Type B Type Coding Machine (original 暗号 機 イ プ). Purple replaced the Red encoders, which were used by the Ministry of Foreign Affairs of Japan.
')
The device consisted of a combination of cables and a contact panel, thanks to which it was possible to create a wide variety of ciphers. In order to encrypt the message, the corresponding key was selected and installed. After that, text was entered through the keyboard of an electronic typewriter. Having passed through the interlacing of contact devices and cables, the message was printed out in encrypted form.
In Purple, instead of scramblers, telephone switches or step finders were used. What made the machine more complicated than other similar encryption devices. Also used hundreds of different fonts, which further complicated the already difficult work of American cryptanalysts. But apparently, despite all the efforts of the Japanese, the "purple" code was cracked.
In 1940, Friedman managed to recreate a copy of the Purple encryption machine, which significantly helped in deciphering the subsequent encoded messages of the Japanese.
William Frederick Friedman (1891 - 1969)
William Frederick Friedman - American cryptographer, is considered one of the founders (father) of American cryptology. He began to use the terms cryptanalysis (cryptanalysis) and cryptology (cryptology). He organized and became the first director of the American Radio Intelligence Service.
Three textbooks on military cryptography, many scientific works on the analysis of code and ciphers belong to Friedman’s authorship. He was one of the first to use statistical methods in cryptanalysis, developed nine encryption machines. His name is immortalized in the US Military Intelligence Hall of Fame and the National Security Agency's Hall of Fame.
Purple is one of the first machines built on finite automata. For the first time, the concept of a finite automaton as a discrete converter with a finite number of possible states as information coding and decoding schemes was considered in the article by Claude Shannon (1948).
A simpler and more understandable description of the Purple machine is made precisely in finite automaton terms.
For simple replacement of symbols of plaintext and ciphertext, in addition to the input and output switching panel, blocks L, M, R, S and stepping are used , which are final cryptoautomatic machines, L = M = R. The first four automata acting as converters have purely initializing keys. The last (stepping) is a combinational cryptoautomatic machine, used as a controlling automaton, which determines the order of state changes in the first three. The states in the L, M, R, S automata are 0, 1, ..., 24 ; in each of them, under the action of the input symbol, the state q can either be preserved or change to the state q + 1 mod 25 . In accordance with the cipher key, the crypto automatic machines L, M, R are divided into “fast” - f, “medium” - m and “slow” - s . The state S is affected by each input symbol. Among L, M, R, only one does this, which is selected by a crypto-automatic stepping depending on the state of S and m so that f changes its state every time. But there are two exceptions:
- if S is in state 24 , then the state changes m ;
- if S is in state 23 , and m is in 24 , then the state changes s .
Purple encryption scheme
All communication channels between the components of the machine are divided into information and control. Information transmit Latin alphabet characters (cipher alphabet). Controls transmit state symbols from L, M, R, S to stepping and logical 0, 1 from stepping to L, M, R.
The last two characters are taken arbitrarily and are taken to designate control commands "save state", "change state". Information channels related to S , transmit vowel Latin letters, and related to L, M, R transmit Latin letters. The function of the information output of each automaton-converter at any fixation of its state acts as a certain bijection on the corresponding information alphabet.
Arkady Dmitrievich Zakrevsky (1928 - 2014)
Arkady Dmitrievich Zakrevsky, an outstanding cybernetics expert in the field of discrete mathematics, algorithmic and logical design, in his manuscript (1959) proposed a version of a symmetric finite automaton cipher.
The cipher is initialized by the key by a crypto-automatic machine C = <X, Q, Y, K, ψ, ϕ> , in which the set of keys K = Q × K 0 is such that Υ = {C k = <X, Q, Y, k , ϕ k >: k ∈ K} is the set of all strongly connected automata with fixed alphabets X, Q, Y and bijective functions ϕ kq : X → Y , defined for any k ∈ K and q ∈ Q as ϕ kq (x) = ϕ ( k, x, q) for all x ∈ X. On the key k = (q 0 , k 0 ) ∈ K, the message α ∈ X * is encrypted by the automaton C k from the “key” (defined by the key k) initial state q 0 ∈ Q to the cryptogram β = ¯ϕ k (α, q 0 ) ∈ Y * , which is decoded into a message α = ¯ϕ 0 k (β, q 0 ) by the automaton D k = <Y, Q, X, ψ 0 k, ϕ 0 k> , where the functions ψ 0 k and ϕ 0 k are defined according to the rule: if ψ k (x, q) = s and ϕ k (x, q) = y, then ψ 0 k (y, q) = s and ϕ 0 k (y, q) = x for all x ∈ X, y ∈ Y, q ∈ Q.
Let in C here | X | = | Y | = m and | Q | = n . Then it is directly calculated that | Υ | > n (m − 1) n n m !
Two keys k and k ' in K are called equivalent if the automata C k , C k' in Υ perform the same mapping from X * to Y * from their “key” initial states q 0 , q ' 0 ∈ Q, respectively, that is, if ϕ¯ k, q0 = ¯ϕ k ', q'0 . Let κ denote the number of all equivalence classes of keys in K , or, equivalently, the number of all pairwise nonequivalent keys of the cipher in question.
As for the encryption device, the Americans initially assumed that they were dealing with one of the versions of Enigma. But it was soon discovered that the "purple" code belongs to the Japanese encryption machine, code-named Purple. In Japan, it is known as Alphabet Type 97 Typewriter (original 九七 式 文 印字 機) or Type B Type Coding Machine (original 暗号 機 イ プ). Purple replaced the Red encoders, which were used by the Ministry of Foreign Affairs of Japan.
')
The device consisted of a combination of cables and a contact panel, thanks to which it was possible to create a wide variety of ciphers. In order to encrypt the message, the corresponding key was selected and installed. After that, text was entered through the keyboard of an electronic typewriter. Having passed through the interlacing of contact devices and cables, the message was printed out in encrypted form.
In Purple, instead of scramblers, telephone switches or step finders were used. What made the machine more complicated than other similar encryption devices. Also used hundreds of different fonts, which further complicated the already difficult work of American cryptanalysts. But apparently, despite all the efforts of the Japanese, the "purple" code was cracked.
In 1940, Friedman managed to recreate a copy of the Purple encryption machine, which significantly helped in deciphering the subsequent encoded messages of the Japanese.
William Frederick Friedman (1891 - 1969)
William Frederick Friedman - American cryptographer, is considered one of the founders (father) of American cryptology. He began to use the terms cryptanalysis (cryptanalysis) and cryptology (cryptology). He organized and became the first director of the American Radio Intelligence Service.
Three textbooks on military cryptography, many scientific works on the analysis of code and ciphers belong to Friedman’s authorship. He was one of the first to use statistical methods in cryptanalysis, developed nine encryption machines. His name is immortalized in the US Military Intelligence Hall of Fame and the National Security Agency's Hall of Fame.
The cipher built on finite automata
Purple is one of the first machines built on finite automata. For the first time, the concept of a finite automaton as a discrete converter with a finite number of possible states as information coding and decoding schemes was considered in the article by Claude Shannon (1948).
A simpler and more understandable description of the Purple machine is made precisely in finite automaton terms.
For simple replacement of symbols of plaintext and ciphertext, in addition to the input and output switching panel, blocks L, M, R, S and stepping are used , which are final cryptoautomatic machines, L = M = R. The first four automata acting as converters have purely initializing keys. The last (stepping) is a combinational cryptoautomatic machine, used as a controlling automaton, which determines the order of state changes in the first three. The states in the L, M, R, S automata are 0, 1, ..., 24 ; in each of them, under the action of the input symbol, the state q can either be preserved or change to the state q + 1 mod 25 . In accordance with the cipher key, the crypto automatic machines L, M, R are divided into “fast” - f, “medium” - m and “slow” - s . The state S is affected by each input symbol. Among L, M, R, only one does this, which is selected by a crypto-automatic stepping depending on the state of S and m so that f changes its state every time. But there are two exceptions:
- if S is in state 24 , then the state changes m ;
- if S is in state 23 , and m is in 24 , then the state changes s .
Purple encryption scheme
All communication channels between the components of the machine are divided into information and control. Information transmit Latin alphabet characters (cipher alphabet). Controls transmit state symbols from L, M, R, S to stepping and logical 0, 1 from stepping to L, M, R.
The last two characters are taken arbitrarily and are taken to designate control commands "save state", "change state". Information channels related to S , transmit vowel Latin letters, and related to L, M, R transmit Latin letters. The function of the information output of each automaton-converter at any fixation of its state acts as a certain bijection on the corresponding information alphabet.
Code Zakrevskogo
Arkady Dmitrievich Zakrevsky (1928 - 2014)
Arkady Dmitrievich Zakrevsky, an outstanding cybernetics expert in the field of discrete mathematics, algorithmic and logical design, in his manuscript (1959) proposed a version of a symmetric finite automaton cipher.
The cipher is initialized by the key by a crypto-automatic machine C = <X, Q, Y, K, ψ, ϕ> , in which the set of keys K = Q × K 0 is such that Υ = {C k = <X, Q, Y, k , ϕ k >: k ∈ K} is the set of all strongly connected automata with fixed alphabets X, Q, Y and bijective functions ϕ kq : X → Y , defined for any k ∈ K and q ∈ Q as ϕ kq (x) = ϕ ( k, x, q) for all x ∈ X. On the key k = (q 0 , k 0 ) ∈ K, the message α ∈ X * is encrypted by the automaton C k from the “key” (defined by the key k) initial state q 0 ∈ Q to the cryptogram β = ¯ϕ k (α, q 0 ) ∈ Y * , which is decoded into a message α = ¯ϕ 0 k (β, q 0 ) by the automaton D k = <Y, Q, X, ψ 0 k, ϕ 0 k> , where the functions ψ 0 k and ϕ 0 k are defined according to the rule: if ψ k (x, q) = s and ϕ k (x, q) = y, then ψ 0 k (y, q) = s and ϕ 0 k (y, q) = x for all x ∈ X, y ∈ Y, q ∈ Q.
Let in C here | X | = | Y | = m and | Q | = n . Then it is directly calculated that | Υ | > n (m − 1) n n m !
Two keys k and k ' in K are called equivalent if the automata C k , C k' in Υ perform the same mapping from X * to Y * from their “key” initial states q 0 , q ' 0 ∈ Q, respectively, that is, if ϕ¯ k, q0 = ¯ϕ k ', q'0 . Let κ denote the number of all equivalence classes of keys in K , or, equivalently, the number of all pairwise nonequivalent keys of the cipher in question.
Source: https://habr.com/ru/post/275347/
All Articles