26
$\begingroup$
  • There's a person who has enough working knowledge of our current real-world methods of cryptography (e.g. knows how a few modern algorithms work and could implement one or two from scratch).
  • That person becomes a member of an alien civilization where people are generally intelligent and educated (in fields like math), but they haven't invented electricity or computers.
  • That person is willing to teach this civilization how to use cryptography and the military of that civilization is willing to learn about cryptography and apply it in order to have an advantage over a potential enemy.
  • A potential enemy could have anything between no computers at all, to computers computationally comparable to our current everyday desktops.

Could the civilization realistically implement some form of secure (probably manual) encryption of simple textual messages (or more), without access to computers? Or is it out of their league computationally to make their method cryptographically secure?

$\endgroup$
  • 15
    $\begingroup$ This entirely depends on the enemy's codebreaking resources -- what you're describing sounds awfully like WWII from a cryptographer's perspective. (save for the no-electricity part) $\endgroup$ – Shalvenay Sep 5 '16 at 19:12
  • 1
    $\begingroup$ GrinningX brings up a related point, possibly by accident, that you may want to consider as well. Different messages have different security requirements. An order to fire at a particular enemy location only needs to remain secret until it has been carried out, whereas other types of messages may need to remain secret for far longer. Pick your cipher accordingly! Just make sure to not make the same mistakes the Germans did in reencrypting and retransmitting... $\endgroup$ – a CVn Sep 5 '16 at 19:59
  • 10
    $\begingroup$ The phrase "cryptographically secure" is very context-dependent. What people mean by it now is that they're confident it can't be broken in a practical length of time, with any foreseeable resources. But that's all it means. $\endgroup$ – John Dallman Sep 5 '16 at 21:29
  • 4
    $\begingroup$ xkcd.com/505 $\endgroup$ – SOFe Sep 6 '16 at 0:02
  • 6
    $\begingroup$ Neal Stephenson's Cryptonomicon includes a description of a cipher which uses a deck of playing cards to encode the state of a CSPRNG: en.wikipedia.org/wiki/Solitaire_(cipher) $\endgroup$ – pjc50 Sep 6 '16 at 9:38

12 Answers 12

34
$\begingroup$

One time pad is 100% secure against any kind of cryptographic attack we can reasonably conceive, if used properly, and is sufficiently low tech to be used by neolithic technology level (with writing).

$\endgroup$
  • 13
    $\begingroup$ The one time pad also has massive key distribution problems, is malleable, and becomes a textbook example of how to break a trivial cipher if even a part of the key material is reused. An OTP has its applications, and military or espionage applications is one of the few situations where its properties make any real sense, but it is not the panacea it is often portrayed to be. $\endgroup$ – a CVn Sep 5 '16 at 19:39
  • $\begingroup$ @MichaelKjörling key distribution, key maintenance is general problem of any system. Weakest point is not cheaper itself but system as whole, weakest factors of all in any system are people.(at that moment at least) $\endgroup$ – MolbOrg Sep 5 '16 at 20:00
  • 5
    $\begingroup$ @MolbOrg Yes, and a big part of what modern cipher design is about is to turn the large secret (the plaintext) into a small secret (the key), based on the reasoning that it's easier to protect a small secret than a large secret. An OTP requires that the secret you are protecting is the same size as the secret it is protecting. As I said, OTPs have their uses, but a lot of people rather naiively apply them in places where they don't make sense. $\endgroup$ – a CVn Sep 5 '16 at 20:05
  • $\begingroup$ @MichaelKjörling It is not about converting large secret to small one. OTP problem is: to be secure it have to have infinite length key. Which actually can be reduced to having pseudo-random number generator mechanism - and that is actually what block chippers do - they are subset of OTP, and OTP is general/basic representation of them all, OTP is mother of them all. As key is concern - I could have 10TB key if I could or need - because I know it can't be stolen from me with my network connection, and I will notice that process. Really, OTP is mother of all ciphers, have respect, upvote. $\endgroup$ – MolbOrg Sep 5 '16 at 20:34
  • 1
    $\begingroup$ Every cryptographic problem is a key management problem. That key management may or may not be onerous is not a reason to discount its possibility, just to doubt its feasability. The question has to do with the possibility of such a system without computational power to drive it, and possible it most certainly is. I would expect the expert in this scenario would know enough to keep key use and management within useable parameters. $\endgroup$ – Lord Dust Sep 5 '16 at 23:39
74
$\begingroup$

In two words: absolutely yes.

Cryptography, at its core, is not about computers at all. Sure; automated, programmable, electronic computers operating at about a gazillion instructions per millifortnight allow us to perform some pretty neat tricks that would be difficult to pull off otherwise, but there is nothing inherent about cryptography that requires electronic computers. There was serious cryptographic work being done in the 1700s and 1800s, and while those ciphers are trivially breakable with modern methods, they held up pretty well to the adversaries of the day. The Vigenère cipher is an excellent example of this.

That said, given what we know today, and within the limits of your question, your protagonist's best bet is probably (and I'll likely get shot down for this) be the German Enigma.

Yes, it was broken. But we now know quite well what allowed it to be broken, and to a large extent, what allowed breaking the Enigma was poor operating procedures. Things like reencrypting the same plaintext under multiple systems with different security properties, standard message preambles, test transmissions using real key material (the infamous LLLLL... transmission provided an invaluable crib to codebreakers in the UK), ... Really, these are things that any motivated security-inclined professional should be able to keep up with without any major difficulties. Even something as simple as starting each and every single message with a random number of letters (symbols) selected at random followed by one particular letter to mark the end of the part to be ignored, would probably be a huge improvement.

The Enigma is relatively easy to implement electromechanically (we did it with 1930s technology), and I don't think it is too much of a stretch to build one that operates purely mechanically. (Though relaxing your requirement that these aliens have not discovered electricity might make for a more believable story. You could, if you want to, make electricity very limited, and restricted to military applications, but still present in the world.)

Especially against an adversary that doesn't have computers or even electricity, the Enigma's theoretical key space is gigantic. With reasonable assumptions, Wikipedia claims that the Enigma's key space was approximately $10^{23} \approx 2^{76}$; with ideal assumptions, it had a theoretical key space of around $10^{114} \approx 2^{380}$. Make use of all of it.

By giving the aliens some Enigmas, as well as explaining to them that those have been broken, how they were broken, and how to avoid the mistakes that allowed them to be broken, your protagonist will be giving that side of a conflict a major upper hand (tentacle, or whatever) in a conflict, because for all intents and purposes, they will have the ability to keep messages secret even if messengers are intercepted or their communications are being monitored by the adversary.

Compare also How cryptographically secure was the original WW2 Enigma machine, from a modern viewpoint? on the Cryptography Stack Exchange.

$\endgroup$
  • 6
    $\begingroup$ I think I agree about Enigma, other than the minor detail that we don't know if the opponent has access to modern computers. If your opponent has literally 20 orders of magnitude more computing power than you have (which is possible given the OP's setting) you really don't want to be relying much on algorithmic strength. That being said, I'd love to see someone take you up on the idea of a mechanically operated Engima which, instead of wires, had plastic tubes and you encoded a letter by pouring liquid into one letter and seeing which letter it came out if! $\endgroup$ – Cort Ammon Sep 5 '16 at 22:11
  • 2
    $\begingroup$ It's also great from a storytelling perspective, because there is a vast body of resources on how the Enigma was broken, so you would never run out of source material! $\endgroup$ – Cort Ammon Sep 5 '16 at 22:12
  • 2
    $\begingroup$ I did a little sleuthing, and it looks like 80 bit is considered just barely secure at the moment. It looks like The bitcoin mining community is cracking about 2^85 SHA-1 hashes per year, so if the whole bitcoin community were to focus on brute forcing Enigma codes, it could probably break 2^76 in few hours (Enigma's encryption does take less calculation than SHA-1). It woudl be interesting, however, to see if you could operate in a way that... $\endgroup$ – Cort Ammon Sep 6 '16 at 13:57
  • 2
    $\begingroup$ ... let you use the rest of the keyspace. Much of that keyspace comes from the assumption that your rotors can be rewired. The Germans never did this, but it'd be interesting to see what you could pull off. I guess the real unknown is whether the adversary just has a few desktop computers, or has the NSA on their side! $\endgroup$ – Cort Ammon Sep 6 '16 at 13:58
  • 5
    $\begingroup$ @nijineko "It was encoded (translated), and decoded (interpreted)" No. That's not what those words mean. Encode means 'to turn into code'. The Navajo language is not a code. It is a language. You can't use those terms interchangeably. The key difference is that, with a language, if someone who happens to know the language reads a translated text, they will know what the text contains. OTOH, even if I know what algorithm was used to encode a text, without the key, I can't read it. $\endgroup$ – Shane Sep 6 '16 at 20:25
16
$\begingroup$

Yes. Look at the Caesar Cipher (dating back to Julius Caesar) or the Vigenere Cipher (more modern and more secure) as examples. Neither are considered "strong" encryption being primarily based on replacing one letter with another (or combinations of letters, which is stronger), but if neither side has computers and the encryption does not have to last terribly long they can be very handy.

Another option would be to use something like Navajo codetalkers, as occurred in WWII. By translating a message into a complete but very difficult to decipher language you have very little risk of it being translated by your enemy (unless they also have people who speak that language). That survived the advanced decryption efforts of the Germans, who also employed early computers.

$\endgroup$
  • $\begingroup$ Correct. But those were weak because the people back then had neither the knowledge nor the computational power required to make something cryptographically secure. I'm talking about a scenario where they know the math but lack the computational power. $\endgroup$ – Sigma Ori Sep 5 '16 at 19:34
  • 1
    $\begingroup$ The code talkers are only a viable option if a language already exists and is spoken by some people. If you need to develop a language then teach it to people before you can use that technique, that program will likely be infiltrated. $\endgroup$ – Shane Sep 6 '16 at 21:00
  • $\begingroup$ @Shane - Yes, absolutely. I should have specified that rather than taking it as assumed knowledge. $\endgroup$ – GrinningX Sep 6 '16 at 21:29
  • 1
    $\begingroup$ Code talkers are not cryptography, they're obfuscation. The key difference being that crypto assumes the listener knows the method being used, only the key needs to be hidden. Whereas obfuscation relies on hiding the method or simply making it difficult, but once you know the method all communication is vulnerable. $\endgroup$ – Schwern Sep 7 '16 at 7:11
5
$\begingroup$

Yes - Again

While historical references do exist, as the OP added they are not long-term secure and can be broken. If the OP is looking for something "harder", then yes, people could manually construct short messages using current encryption schemes. It would be bloody long work, but it could certainly be done.

Take a look at this paper on how AES works for example. In this paper the author walks through how AES encryption works. As you can see from the example it would take a considerable amount of manual work, but you could perform manual AES encryption after exchanging a secret key.

The major defects of this type of operation however are threefold:

1. The key must remain secret If the other side obtains your secret key, you're toast. So you wouldn't want to tell too many people what that key was unless they're all willing to take it to their grave even under torture.

2. It's extremely labor-intensive Encrypting small and extremely important messages is feasible with enough people on board, but you couldn't relay dozens/hundreds/thousands of messages a day with such a system. If you wanted to - and you generally would want to during a war scenario - then you would be back to the aforementioned caesar/vigenere ciphers.

3. Modern encryption was built for computers Systems such as AES were built when computers were in-use and well understood. You will often see references to the binary system and will need to translate letters back to ASCII. But that will be the case when trying to use any computer-level encryption in a manual-only world.

Note: I created a different entry because the OP clarified on my first one, which used real-life examples of ciphers which were used successfully in areas where computers did not exist. This answer is fundamentally different and discusses modern encryption using entirely manual concepts, based on OP comments.

Edit: Technically you could perform asymmetric encryption, which would remain useful if any outpost's secret key was compromised. But even using so-called "suite B" encryption protocols to reduce computational burden while maintaining integrity (based on more advanced math) they are still SIGNIFICANTLY more labor-intensive than symmetric algorithms like AES. I would wager it's still basically possible - we did build pyramids without wheels after all - but probably very difficult and certainly much more time consuming. You could have your protagonist use the same ideas that underly asymmetric encryption to create a less vigorous algorithm however, and that may make it more realistic while still remaining unlikely to be broken manually. Just make sure to stipulate that rooms full of people were working on it :)

$\endgroup$
  • $\begingroup$ ASCII is merely one mapping between binary and text. (Also, one that's increasingly rarely used these days, except as a tribute of UTF-8 to its heritage.) For a cipher like AES, you can just treat each block as 128 choices of "on or off", and map those to symbols in any way you want. If all you need is, say, the English alphabet, then you can encode that using five or at most six of those; using six, you get some extra whitening potential, and 21 symbols per block (plus a spare bit). $\endgroup$ – a CVn Sep 5 '16 at 20:02
  • $\begingroup$ Good point. That's certainly one option. The only reason I was leaning towards maintaining binary usage is that it at least lends itself towards analogue/mechancial calculators, which could save some time depending on implementation. But assuming entirely manual labor it may be easier to work with a different character set. $\endgroup$ – GrinningX Sep 5 '16 at 20:15
  • $\begingroup$ FWIW, this is what posting multiple answers is good for: offering different alternative answers that have very little or nothing to do with each other. $\endgroup$ – a CVn Sep 6 '16 at 13:59
  • $\begingroup$ For asymmetric encryption. Choose a symmetric key, asymmetric encypt it at the start of the message. Now you have told the reciever and only them the symmetric key for the rest of the msg. $\endgroup$ – Catprog Sep 7 '16 at 6:34
5
$\begingroup$

This website (Articles on Historical Cryptography) has pages and pages on historical ciphers and codes. and a basic Ottendorf cipher can remain unsolved for some time if the writings used are obscure enough.

$\endgroup$
  • $\begingroup$ You provided nice link. $\endgroup$ – MolbOrg Sep 6 '16 at 21:23
  • $\begingroup$ +1 upon the realisation that if the books used are unavailable to whoever is trying to break the cipher (entirely possible for alien civilisations), they're going to have a hard time of it $\endgroup$ – Mithrandir24601 Sep 6 '16 at 21:28
4
$\begingroup$

Read Quicksilver by Neal Stephenson. He dissects how codes were used in the 17th century for secure communications as all letters were read by governments. In one example the Duchess of Qwghlm (A fictional country with a 16 letter alphabet) communicates securely using needlepoint where stitches make an "X", if the low left to high right is above the low right high left then it is a "1", otherwise it a "0". Four stitches can then represent all the letters in the Qwghlm alphabet (like hexadecimal). For further security you had to know Qwghlm to be able to read it! Also read his book Cryptonomicon. It is about Cyphers in WW2 and the 90's. the main character used church organ pipes and resonance to make a sound based computer to crack the Japanese code. It's one of my favorite books!

$\endgroup$
  • 2
    $\begingroup$ Came here to mention Cryptonomicon. In it we also have the Solitaire cipher, implemented using... a deck of cards. en.wikipedia.org/wiki/Solitaire_(cipher) $\endgroup$ – MichaelK Sep 6 '16 at 12:19
  • $\begingroup$ A code, however, becomes worthless the moment it is cracked. With a good cipher, all you have to do is change the key and redistribute all key material; a major hassle, but not a total break. $\endgroup$ – a CVn Sep 6 '16 at 12:23
1
$\begingroup$

I'm surprised that no one has mentioned Beale ciphers. There, the vulnerabilities lie in 1) knowing which book is being used to do the encoding, and 2) whether different editions (versions) of that book are different enough to resist easy decoding.

$\endgroup$
0
$\begingroup$

No, not in any meaningful sense of cryptography that includes safety against an attacker who does discover scalable math/computation. This is very over-simplified, but cryptography generally relies on math that's polynomial (usually sub-quadratic) time to compute in one direction but exponential time to reverse. However, in order to make the exponential-time calculations infeasible, you still need big numbers. 2n is pretty damn small in the big scheme of things until n gets fairly big. And once n gets big, the forward operation is costly to do without a high-speed computer. Just try doing 2048-bit RSA on a 1 MHz cpu if you don't believe me.

Keep in mind that even without "computers" in the sense of high-speed electronic devices, an attacker with resources could simply employ or enslave tens of millions of people to perform a few huge computations each. The original meaning of "computer" was a human who performed large computations, not a machine.

$\endgroup$
  • 2
    $\begingroup$ Training and coordinating tens of millions of people to do anything is not "simple", especially without modern telecommunications. If it was, the Allies would have "simply" employed tens of missions of people to crack Engima. $\endgroup$ – Schwern Sep 7 '16 at 7:16
  • 1
    $\begingroup$ A one-time pad does not need any high-tech. The agent encodes using a sheet from the pad and then destroys the sheet. The coded message can be decrypted only by obtaining the recipient's other copy of the pad. Alternatively the pad can be "hidden in plain sight", being derived from letters from loved ones, estate accounts, etc. No amount of maths can decode something cyphered with an OTP. Its weakness is if the enemy can obtain a copy of the pad. $\endgroup$ – nigel222 Sep 7 '16 at 12:07
  • 1
    $\begingroup$ Bruce Schneier proved this claim false by designing a cryptosystem that can be performed without a computer but that is resistant to computerised cracking. The system was published in Neal Stephenson's Cryptonomicon. I'm not sure whether the particular system has entirely stood up to scrutiny, but the basic observation is that you can implement an S-box without a computer using cards, because they are easy to manually permute. Of course this is "easy" in the sense that it takes all evening to encrypt a message and one mistake ruins the whole thing. It's no good for a real-time conversation. $\endgroup$ – Steve Jessop Sep 7 '16 at 15:28
  • $\begingroup$ ... but the key space in that system is 52! (or maybe 54! -- IIRC it used jokers but I can't remember what for), which is bigger than many symmetric ciphers actually in use. $\endgroup$ – Steve Jessop Sep 7 '16 at 15:32
  • $\begingroup$ @Schwern: Hierarchical coordination of training and supervision is efficient and ancient technology. $\endgroup$ – R.. Sep 7 '16 at 20:11
0
$\begingroup$

Since I can't comment, I will just provide a some example without it the answer will be incomplete. Remember https://en.wikipedia.org/wiki/The_Adventure_of_the_Dancing_Men ? Although Sherlock Holmes could understand the cipher, certainly it goes beyond of cryptography where you are trying just decode sequences of bits. Images, and sounds can be another interesting part of cryptography. No secret that many CAPTHCA which human can read easily, bring computers in complete stuck.

$\endgroup$
  • $\begingroup$ No, it doesn't. A human just replaces images with letters, and then computer breaks substitution cipher in a glimpse of an eye. And that's not even mentioning computer vision and machine learning that are already more powerful than human. $\endgroup$ – polkovnikov.ph Sep 7 '16 at 15:38
0
$\begingroup$

Absolutely yes. In addition to everything that was said already: The Cryptonomicon by Neal Stephenson, contains a complete cryptographic algorithm using standard playing cards, with the required math being simple enough that with some training it can be done in the head.

$\endgroup$
0
$\begingroup$

One fairly significant consideration is that - if there is no electricity - then (short of some sort of semaphore system) messages will have to be hand-delivered. With the sort of time-scale that this implies, the disadvantage of taking several minutes to manually decode a single sentence will be much less marked; if a message takes two days to reach the recipient then several minutes or even hours to decode will not seem quite such an issue.

$\endgroup$
  • $\begingroup$ I'm not clear whether you're saying this is a reason they can have encryption, or a reason they won't want it, or what. And why do you immediately rule out semaphore (it immediately made me think of Terry Pratchett's "clacks network")? $\endgroup$ – IMSoP Sep 7 '16 at 17:00
  • $\begingroup$ I'm suggesting that it would be a reason for encryption, as it would make little practical difference and would protect against the message's being intercepted. I didn't rule out semaphore (hence why I mentioned it); but it would be an incredibly expensive system to operate especially in any environment where visibility would be sometimes limited - realistically it would be feasible for communicating for large population centres that are close together (say London to Birmingham) but less so in other environments. $\endgroup$ – Matt Bowyer Sep 8 '16 at 11:39
-1
$\begingroup$

Do you really need caligraphy?

Are you just interested in passing secret messages? If so, look into steganography, et al.

My favo(u)rite story of passing a secret message is this ...

According to Herodotus, Histiaeus was unhappy having to stay in Susa, and made plans to return to his position as tyrant of Miletus by instigating a revolt in Ionia.

In 499 BC, he shaved the head of his most trusted slave, tattooed a message on his head, and then waited for his hair to grow back.

The slave was then sent to Aristagoras, who was instructed to shave the slave's head again and read the message, which told him to revolt against the Persians.

$\endgroup$
  • $\begingroup$ Any explanation for the downvote? Or is it just the usual SE anonymous cowardry? $\endgroup$ – Mawg Apr 23 '17 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.