Imagine you are transported back to ~1940. What is the best (i.e. most secure, but technologically feasible) encryption you can think of for widespread (i.e. military) use? How would you implement it?
1$\begingroup$ To be clear, are you asking about how to achieve the strongest widespread encryption using strictly pre-existing WWII-era technology/practices, or are modifications of that technology using knowledge from the present era acceptable? For example, the current answer proposes a "fixed" enigma machine which clearly did not exist in 1940, but someone with knowledge of modern cryptography could design an Enigma-like device. $\endgroup$– Ella RoseAug 2, 2019 at 15:09
1$\begingroup$ Makes me wonder how tricky it would be to build a Keccak-like machine out of - let's say - K'NEX or LEGO. $\endgroup$– Ruben De SmetAug 2, 2019 at 15:09
$\begingroup$ @EllaRose: Since it's "you are transported to 1940", I feel like I can take my knowledge with me. I don't think the question is interesting otherwise. $\endgroup$– Ruben De SmetAug 2, 2019 at 15:10
I'd suggest SIGABA. I don't know about the original poster's knowledge, but my knowledge includes the demonstrated fact that one person, working alone, is highly likely to overlook attacks and produce a weak cipher. So if I'm the only one going back in time, I'm going to pick a well-proven system rather than anything I invent myself.
If I could bring a large team back, making it possible to properly test a new system, I'd be sure to bring electronics experts with me who know how to test the signal coming out of the machine for artifacts emitted by the machine which can be used to break the cipher. (These artifacts would not be part of the mathematical description of the cipher, but would be emitted nonetheless.)
$\begingroup$ @GeradAshton Nice call. $\endgroup$ Aug 4, 2019 at 14:43
$\begingroup$ The effective keyspace of the SIGABA, if its indicator was captured and understood, was 2^48.4, which was good for 1940, $\endgroup$ Aug 4, 2019 at 15:34
$\begingroup$ On SIGABA see: Mark Stamp & Wing On Chan (2007) SIGABA: Cryptanalysis of the Full Keyspace,Cryptologia, 31:3, 201-222 $\endgroup$ Aug 4, 2019 at 15:37
It depends on what you mean by widespread (military) use. The Russian VIC cipher, which used a lagged Fibonacci generator, classified as a "straddling bipartite monoalphabetic substitution superenciphered by modified double transposition," as identified by the FBI in 1953, could have been applied to widespread military intelligence use, especially for HUMINT. After all, it was not broken until 1957--with the aid of a defector. It was used in World War II, and it clearly worked.
But for moving armies that use radio communications, a one-time-pad system that actually worked in practice would have been an excellent idea. The German one-time pad GEE system was considered unbreakable, and had been in use for quite a while prior to its initial interception in 1934--used for diplomatic traffic from 1925--and continued to be heavily used in 1943, according to this declassified NSA document, but it suffered from weak key generation, according to this declassified NSA technical report. Its additive generator of wheels and switches had weaknesses which were brilliantly exploited by American analysts: the phases, cycles, potential overlaps, and limits of the keys became clear after exhaustive analysis of captured GEE one-time pads. So, the GEE system with a good TRNG, responsible cryptographic clerks, and cautious leaders, would have done the trick.
The other solution would have been to fix the weaknesses in Enigma, especially in its rotors and settings, modernize it-- see this paper by Ross Anderson-- and to improve the training of its operators, change key settings frequently, reduce predictable formatting, and not regard Enigma as an unbreakable magic box. Weaknesses in how the settings were shared over the radio were pivotal to Enigma's downfall. Or we could continue with the Rasterschlüssel 44 (RS44), a grid-based, broken double transposition that was better, in practice, than Enigma. Even so, we could tweak the RS44 and make some improvements.
Implementation is very important, as your question suggests. Procedures such as message formatting need to be emphasized. Again, weaknesses in the training of cryptographic clerks helped speed the exploitation and downfall of both GEE and Enigma--as did overconfidence, even hubris, among the leadership.
Perhaps even more important was a failure to understand some of the underlying principles of information security, the work that would soon be done by Claude Shannon.
One could implement everything according to the principles of information theory that we now know.
Edit: We should also include the Schlüsselgerät 41 (SG41), which was a rotor cipher machine similar to the Enigma--but better. It had six rotors that could move irregularly--forwards and backwards--and it was intended to replace the Enigma.
Traffic from the SG41 was almost never broken by Bletchley Park. But due to its weight (about 30 lbs; see one here) from a lack of light metal building materials, relatively few were made and then put into service (about 1500 were created in total). From the viewpoint of the frontline soldier, heavy is bad.
Both the Germans (SG41) and the Allies (SIGABA) had rotor-based encryption that worked well when used properly. Some of that equipment could have been improved for service--it was definitely good enough for the time.
If we agree that a cipher can be a symmetric key known only to the communicating parties, then the US Marines came up with a “code” the Japanese NEVER broke: the Cherokee Indian language.
They used pairs of Cherokee Indians to talk to each other to conveying military messages in their unique language. So few people in the world speak their language the Japanese were never able to “decrypt” the messages. History knows these men as “The Code Talkers”.
I guess it could be argued both ways: it’s a cipher since it was used to “encode” messages or it could be argued it’s not.