Forgetting old ideas and trying to invent the “old wheel”

From the history of US cryptography

At the end of the 18th century, cryptography was enriched with a remarkable invention — the Jefferson coder , named after a statesman, first secretary of state, and then president of America Thomas Jefferson. Jefferson himself called his system "disk cipher." Such a device was implemented by a well-known multi-alphabet substitution cipher.

The encoder was a wooden cylinder, which was cut into 36 discs (although the number of discs could be different), which were mounted on one axis so that they independently rotate around it. On the side surfaces of the disks in free order - all the letters of the English alphabet.


')
Parallel to the axis of the disk on the surface of the cylinder line stood out. The plain text was divided into groups of 36 characters, the first letter of the group was recorded by the position of the first disk along the selected line, the second one of the second disk, etc. The cipher text was read from any line parallel to the selected one. To decrypt, on a similar device, the resulting ciphertext was written out by rotating the disks along a dedicated line, and the plaintext was searched among the lines parallel to it by a meaningful reading of possible options.



Replica Jefferson disk encoder made of plastic. It has only 10 disks, not 36, but it is well suited to demonstrate the operation of this encoder:







Jefferson's invention was a precursor to the appearance of disk encoders, which were used in developed countries in the twentieth century. Oddly enough, during the life of the creator the fate of this device was unsuccessful. Jnfferson himself was wary of the encoder and continued to use nomenclators.

For the period from about 16 to 19 centuries. typical was the so-called. a nomenclator is a cipher, which is a combination of a replacement cipher and a small code. The nomenclator usually contained the code equivalents of the letters of the alphabet and the most common syllables, words and phrases, as well as a number of special characters. Most often, it met characters specially created for this purpose, but astrological and occult symbols were also often used. The nameclator was designed as an encryption system that was best adapted to the most common methods of cryptanalysis at that time, which usually included counting the frequency of occurrence in the text of each cipher symbol and search in the text of words and expressions containing character combinations specific to the language. The method of frequency analysis of letters is based on the fact that in any language some letters are more common than others. In English, for example, the letter E is more often found. Other most common letters are T, A, O, N, R and S. (The whole group of letters is easy to remember as the word "SENORITA".) And the letters J, K X and Z are rare in English. Since the frequency of a letter does not change during the replacement operation, the key to unraveling the true meaning of a cipher-character is sometimes to count the frequency of its appearance in the ciphertext. Likewise, the simple replacement operation does not change the combinations of letters (letter models). For example, the word ATTACK, being encrypted, can take the form XJJXBU. Despite the fact that the meanings of the letters changed, the literal model of the word (namely, two identical letters, framed on the left and right by the same letter, followed by two other different letters) remained unchanged.

The ancient Romans also called the nomenclator a slave, whose duties included knowing and telling his master the names of the citizens of the city and all the slaves in the house, as well as to proclaim the names of the food served. But now is not about that. Nomenclatures were the standard for diplomatic correspondence, spyware, and were the primary means of antipolitical conspiracy from the beginning of the fifteenth century to the end of the eighteenth century.

Jefferson was very cautious about his invention and consulted about it with the mathematician R. Patterson. As a result of this exchange of information, Patterson offered his own cipher, which he said was more reliable, such a cipher was a vertical permutation with the introduction of "dummies", although it was significantly inferior to the Jefferson cipher.

In patterson cipher, the message must be written from top to bottom and from left to right. Then it should be split into several sections of no more than nine lines. The lines in each section are numbered and jumbled in random order. The order of the lines in the section will give the first half of the key, for example: 5-1-3-2-4-7-6-8 for a section of eight lines.

Then at the beginning of each line, you can insert from 0 to 9 random letters. The resulting sequence gives the second half of the key, for example, 1-7-9-3-3-2-1-7 (1 letter was inserted into the first line, 7 letters into the second line, and so on). The message will have a ragged right edge — you can add some more meaningless letters to the end to align it.

The key itself is recorded as a two-digit number, where tens are the digit from the first half, and units are the number of meaningless letters added to the beginning. It is enough for the decoder to subtract from each line by the specified number of letters and rearrange them in the correct order (in Patterson's time, you had to arm yourself with scissors and re-paste the cut lines onto a sheet of paper). The message is decrypted, it can again be read from top to bottom, and just ignore the nonsense at the right edge.

Only in the 20th century was the high resilience of the Jefferson cipher recognized; it was later used to encrypt messages by the American army during World War II, and the inventor himself was called the father of the “American cipher case”.



Throughout history, there have been several attempts to re-invent the long-forgotten wheel of Jefferson. At the beginning of the 20th century, Parker Hitt (again, the United States) wrapped the Jefferson cipher in a “strip cipher”, which is much simpler to make. Stripes with a double alphabet, were fixed in a frame, which was more technologically advanced than wooden discs with the alphabet. The meaning of encryption and decryption remains the same, but complex discs were replaced with easily reproducible “strips” of hard material (for example, cardboard, metal). The significance of this invention is not in the emergence of new cryptographic ideas, but in the technological simplicity of their implementation. At the end of 1937, the Japanese carried out a secret excavation in the building of the American consulate in Kobe (Japan) and re-photographed the American embassy
strip cipher. However, they could not effectively use this mining, since the cipher strength was determined by the key system, which, in addition to the “strips”, also included their choice and location on the tablet. The strips were replaceable, there were up to hundreds of them, and the choice of thirty active strips was set by the key table.

Later, in the 20s of the last century, Jefferson’s cipher was “invented” once again. After this, the cryptanalysts came to the conclusion that, despite its simplicity, this cipher is strong enough. As a result, the US Army adopted it and, as it is believed, the use of this cipher led to the appearance of the first complex electromechanical devices.

Long tape method

On an early December morning in 1917, a handsome young man quickly swept between the massive columns of the lobby of the American Telephone and Telegraph building (AT & T) located in downtown New York. He ran into the elevator and climbed it to the 17th floor, where there was a telegraph office of the company, which was part of its research department. This branch, in which several of the most talented engineers worked, has been engaged in a year in bringing to mind the latest advances in the field of telegraphy - a direct-printing telegraph, which the branch has called the teletype.

The young man's name was Gilbert Vernam, and he was always a little late. Colleagues considered Vernama a very intelligent engineer and capable inventor. There were rumors among them that every evening, stretching out on the sofa, he asked himself out loud: “What else could I invent?” Vernama had a rare mindset that allowed him to invent an original electrical circuit and then transfer it to a drawing canvas without reproducing all the required connections using wires. A great idea had already matured in his head. Vernam rather timidly expressed his idea to his colleagues, who immediately found it worthy of special attention.

Work on a secret project began in the summer, a few months after the United States declared war on Germany. Parker instructed several of his subordinates to investigate the possibility of keeping secret messages transmitted by teletype.

It turned out that the oscillations of the current in the communication line could be recorded with an oscilloscope and then easily converted into the letters of the transmitted message. Therefore, it was decided to make changes to the connections of the wires of the teletype printing mechanism. As a result, the message text was encrypted using a one-alphabetic replacement method. In the telegraph office they understood that such protection was too weak, but they could not think of anything else and stopped dealing with this problem until Vern told them about his idea.

Vernam worked in the telegraph office and called his cipher the "long tape teletype method." The essence of the Vernam cipher is simple: the telegraph message, represented as a bitstream, was modulated with a tape, onto which a random stream of bits of unlimited duration was stored. That is, the gamming cipher was transferred to electric ground. There were only two requirements for the cipher, the gamma should have been random and the gamma tape could be used only once (from here the name OTP - One Time-Pad, OTK - One-Time-Key; OTT - One-Time-Tape) . For encryption, a gamma punched tape with random signs was prepared in advance, after which its pulses with impulses of plaintext characters were electromechanically folded. The amount received was a ciphertext. At the receiving end, the pulses received via the communication channel were added to the pulses of the same binary scale, as a result of which the original message pulses were restored.

Vernam proposed to use the features of the teletype code, in which the encoded sign was expressed in the form of five elements. Each of these elements symbolized the presence (“plus”) or absence (“minus”) of the electric current in the communication line. Thus, there were 32 different combinations of “pluses” and “minuses”. 26 of them were assigned to letters, and the remaining 6 denoted “service combinations” (space between words, switching from letters to numbers and punctuation marks, reverse switching from numbers and punctuation marks to letters, returning the print device carriage, switching to a new line and idling). For example, the letter "A" was expressed by the combination "+ + - - -", the letter "N" corresponded to "- - + + -", and the transition to numbers and punctuation marks was given through "+ + - + +". The coded message was stuffed on a punched tape: “pluses” seemed like holes, and “minuses” - with their absence. When reading punched tape metal probes passed through the holes, closed the electrical circuit and sent current pulses through the wires. And where the “minus” was on the punched tape, the paper did not allow these probes to close the circuit, and as a result the current pulse was not transmitted.






Vernam designed a special device consisting of magnets, relays and collector plates in order to electrically add pulses during encryption. Since the decryption procedure was completely analogous to the encryption procedure, the same device was used for decryption. The pulses entered the summation device from two readers: one read the “gamma” and the other read the plaintext. The resulting “pluses” and “minuses” could be transmitted like a regular teletype message. At the receiving end, a device invented by Vernam added pulses that were read from an identical “gamma” tape and restored the original plaintext pulses.



The single-tape electromechanical cipher machine was created in the USA around 1933 by the Western Union Telegraph Company. A limited number of such machines were produced, based on the Varnam cipher.

Even if the message was intercepted, without a scale it was impossible to decipher it, because the enemy saw only a random sequence, which meant nothing to him. Information that was available to the enemy, only the length of the message. In its original form, the Varnam system was vulnerable because the key punched tape was made in the form of a ring and was used again after its completion. Vernam managed to merge two processes together - encryption and message transfer. He created what was later called linear encryption.

Only after the First World War, Vernam received a patent for his invention, which soon overtook, for a while, the fate of the Jefferson disc coder.

However, although the device invented by Vernam was undoubtedly a valuable fruit of the creative engineering of a talented inventor, in commercial terms it suffered a complete failure. Telegraph companies and commercial firms, which, according to AT & T, were to buy Varnam’s patented cipher extensions to their teletypes in mass quantities, preferred old-fashioned codes that significantly reduced the length of messages, thereby reducing telegraph costs and at the same time providing at least some , albeit small, the safety of correspondence. After the end of the First World War, the budgets of the armed forces of all countries were reduced to a minimum. The lack of funds and the lack of material resources forced the army telecommunications operators to return to combining two relatively short tapes with the “gamma”, and the weak persistence of such a “gamma” generation system shown by military cryptanalyst led to the fact that Vernam's cipher system was forgotten for some time.

As for Varnam himself, he continued his research work at AT & T. He improved his cipher system a bit, and also invented a device for automatic encryption of handwritten text during its transmission by photo-telegraph. In 1929, Vernama was transferred with a significant increase to one of the branches of AT & T. However, four months later, a financial crisis broke out in the United States, and since Vernam had not yet had enough time to earn enough seniority at a new place, he was soon fired. He went to work at another large company, but the abrupt change in his personal fate apparently had a depressing effect on him. Every year less and less was heard about Vernam, until finally, on February 7, 1960, the person who automated the encryption process died completely obscene at home.

Vernam's cipher (One-time pad) in PHP

Here is the implementation in php:

<?php /** *   *   php */ function shifrVernam($oStr,$key='') { $len = mb_strlen($oStr, 'utf-8'); //   $shStr = ''; //  if($key == '') for($i = 0; $i < $len; $i++)//     $key .= mb_substr(md5(mt_rand(1,mt_getrandmax())),0,1,'utf-8'); for($i = 0; $i < $len; $i++) //  $shStr .= $oStr[$i]^$key[$i]; echo "<br> : '$oStr'", //    "<br>: '$key'", "<br> : '$shStr'<br>"; return array($key => $shStr); } header('Content-type: text/html; charset=utf-8'); //     $crypt = shifrVernam("Hello word!"); /*:  : 'Hello word!' : 'c462031ba7e'  : '+QZ^_ F SD' */ //      foreach($crypt as $key => $shr) shifrVernam($shr,$key);/*:  : '+QZ^_ F SD' : 'c462031ba7e'  : 'Hello word!' */ 

Major Joseph Moborna was an outstanding cryptanalyst. He thoroughly studied cryptanalysis in the army school of communication and was well acquainted with the latest achievements in this field. Moborne took up the further refinement of the Werman method. He combined the randomness of gamma with the rule of a one-time cipher block note. Now there were three limitations: the encryption was implemented as an encryption gamma, equal in length or exceeding the encrypted message; gamma signs were completely random or equiprobable; each scale was used once and only once, after which it was destroyed by the transmitting or receiving correspondent. There was also an additional rule: only two copies of the cipher key were made, one copy for the sender, the second copy for the receiving correspondent.



Three sheets of one-time cipher note, each of which is a possible key for a cipher. The message is encrypted using sheet 1

As a result, an absolutely persistent ciphering system, a one-time cipher block note is absolutely persistent both in theory and in practice, no matter how long the intercepted ciphertext is, no matter how much time is spent on his research, the cryptanalyst will never be able to open the one-time cipher block used to obtain this ciphertext, it simply does not have a starting point for its research, since in a one-time cipher system the gamma contains no repetitions, is not used more than once, is not a coherent text and has no internal structural patterns. Therefore, all methods of decryption, to some extent based on these characteristics, do not give any results. And here - the cryptanalyst comes to a standstill.



The perfect encryption method did not “deserve” universal use because of the huge amount of gamma that is required when using it. In wartime, it was necessary to encrypt hundreds of thousands of words during the day, and for this you would need to make millions of gamma signs. And since the gamma for each message had to be one and only, its total volume is equivalent to the volume of all correspondence during the warriors, which is simply impossible in rapidly changing military conditions.