Suppose you were able to go back in time, to an era before computers, and give someone contemporary cryptography. Encryption methods that are essentially unbreakable now would certainly be unbreakable then. But there’s a catch: not only do attackers not have computers, neither do users.
Manual cryptography
If you told someone about RSA encryption, for example, you’d lose them right after you said “First you find a couple 1000-digit primes.” But there’s no need for using 1000-digit primes if no attacker has a computer. You could use 100 digit primes. Could you use 10 digit primes? If you chose primes just big enough to make the method unbreakable by hand, could someone implement it by hand?
Kirchoff’s principle says the strength of an encryption method should depend only on keeping the key secret, not the method. If you could keep the method secret, RSA would be unbreakable because nobody thought of anything like it before computers. But to make our thought experiment more interesting, let’s suppose that an enemy has also traveled back in time. If you tell your side about RSA, he can tell his side about it as well. So we’re back to Kirchoff’s principle.
An encryption method combinining substitution and permutation would have been practical to carry our manually. The ADFGVX cipher from 1918 was a start in this direction. That idea could been extended further, with a larger substitution set and longer permutations, and with more than one round of substitution and permutation, approaching what would be come the approach used in modern symmetric encryption. Such a method might have been manually implementable without being manually breakable.
Mechanized cryptography
World War II was a time of transition from manual cryptography to computerized cryptography. Encryption machines were attacked by cryptanalysis machines, though these machines were general-purpose computers. If you could implement a symmetric encryption method like AES in a mechanical device, no mechanical device could break it.
You could use something like DES, simpler than AES but still unbreakable at the time. DES is considered broken because now you could throw enough compute power at it to break it by brute force, but that would not be possible with only mechanical devices.
My hunch is that the best approach would be stream ciphers. Maybe it would be practical to implement one of these by hand or with the aid of simple calculating machines. Something like PCG, which is not cryptographically secure today [1], would have been then, though I don’t know how practical it would have been to carry out PCG, say, in the 1940s.
More pre-computer cryptography
[1] In 2020, Charles Bouillaguet, Florette Martinez, and Julia Sauvage were able to break PCG using 20,000 CPU-hours. See their paper Practical seed-recovery for the PCG Pseudo-Random Number Generator. IACR Transactions on Symmetric Cryptology. ISSN 2519-173X, Vol. 2020, No. 3, pp. 175–196.
There’s also Solitaire: https://en.wikipedia.org/wiki/Solitaire_(cipher)
John, KNOWING WHAT WE KNOW TODAY: the answer to your question is an ENHANCED GALOIS FIELD-BASED Affine Hill Cipher with 3×3 or 4×4 matrix keys.
The original Hill Cipher used mod 26 arithmetic (for the letters “A” through “Z” only), but we would use prime modulus 97, which allows us to add the ten decimal digits, punctuation, and homophonic mapping of each plaintext letter into (at least) two numbers. Using mod 97 makes all plaintext and ciphertext into consistent two-digit numbers.
In Shannon’s terms, plaintext “AAA” yields 8 different numeric vectors, and “AAAA” yields 16.
The Affine Vector (V): Adding a constant shift vector (C = KP + V mod p) destroys the linear homogeneity property of C = KP. This means a plaintext of all zeros does not map to a ciphertext of all zeros.
Especially with pre-calculated (laminated) lookup tables, I believe that this is relatively easy to implement and use by hand, but unbreakable by hand.
A 3×3 matrix and vector in mod 97 has a keyspace of 79 key bits!
A 4×4 matrix and vector in mod 97 has a keyspace of even larger 132 bits!
[extending my prior reply with more details of enhancing the cryptographic strength]
John, and if you consider that rather than mapping the letters statically, as Lester Hill did in his 1929 and 1931 papers, (for example A=1, B=2), each plaintext letter/digit/punctuation gets randomly mapped into one of two plaintext numbers (for the vector), we are talking about an additional 587 bits to describe this permutation.
The permutation process is equivalent to reaching into a bag of 96 numbered balls and drawing them out sequentially in 48 pairs to assign two unique numerical codes to each of the 48 plaintext symbols, establishing one specific mapping layout out of more than 2^587 possible combinatorial arrangements.
An attacker attempting a known-plaintext or chosen-plaintext attack hits a brick wall because of this two-part layering:
1. The Matrix Obscuration: Even if they know a segment of plaintext, they cannot isolate the specific homophone chosen for a specific character because it is bound up in a system of equations governed by the secret matrix M *AND* vector V.
2. The Doubled Ambiguity: Not only does the matrix mix the values, but the fact that any given plaintext character could have come from one of two different homophones means every plaintext-ciphertext equation has multiple valid pre-image branches at the input stage.
It seems to me that more detail is needed in the problem specification. Specifically, what is the communications problem? For example, is it (1) one secret agent who has to memorize the code used to communicate with his home base or (2) dozens of entities that need to communicate with one another? Similarly, how much traffic is involved—a single 200-word message each day or thousands of messages each day?
Relatedly, what resources does the opponent have? Is the opposing analytic force two clerks or a dozen PhD mathematicians?
If the problem is a single secret agent without too much traffic and who can bring supplies along, a one-time pad would provide security. Dozens or hundreds of entities could use a strip cipher with a library of say 500 paper strips of which a random 36 would be used each day or for each message. See M-138A or the Jefferson/Bazeries wheel cipher.