Securely moving data without a modern computer.

[the tree]

Two kings in far away lands need to get messages from one to the other about where they are planning to invade next and what to buy thier respective wives for Christmas, they can't have these messages intercepted because that would comprimise thier plans to take over the world together, or something.

 

Messages may be transimitted as marks on paper, delivered by a messenger on horse, the messenger can remember a couple of sentances but probably wont recall the exact words and wont be impervious to torture. There are no electronic computers but both kingdoms have perfectly intelligent people with bits of paper, abacuses, decks of cards, some random books et cetera et cetera.

Given this senario what is the best way to get messages across securely?

 

One model that I thought of was that two messengers would be sent on different routes: one with the encrypted message another with instructions to decyrpt it. This would mean that if one of them got caught then the message would be lost to both friend and foe.

 

I was wondering if the concept of public/private keys would work without the aid of modern data processing. Is it possible for such a useful concept to be used in an algorythm simple enough to be done by hand?

 

Can anyone think of an even better way?

[Dak]

if they have books, then they could use a one-time key, using books and page numbers to tell each other which key to use.

 

they could also have a pre set-up code to tell each other the book/page number to use as the otk... if he's captured and tortured, then the very small sentance that he has had to have memorised will not be enough to deduce the code, and the otk encrypted message will, without powerful computers, be, at the very least, effing hard to decypher.

 

it would be possible to decypher tho, but, espescially if the decrypter didn't know about otk's, virtually impossable. if it's double-encrypted -- just a simple transpositional cypher prior to one-time-key encryption, then it'd be completely imossable to decypher.

 

with a few books, the number of possable otks would be sufficient for a unique one each time, and, like i said, with a decent code, the small phrases that would have to be remembered by the messanger would be insufficient to break the code and get the book/page, especially if the code was rotated each sending.

 

eg, you could encrypt "the bible (page) 27" as "23 thorax fish elf shoe" or "19 monkey cabbage eskimo turnip", so you can use the same book (but different pages) more than once whilst still having unique encoded messages each time.

 

or you could give him a pack of cards to deliver with the message, and use the order to dictate which key to use. the first card in the pack could be the key card (ie, which of 52 possible codes your using), the fith could be the book (so... 51 books per codes * 52 codes = lots of books), and the ninth, thirteenth and twentieth could be the page number.

[birkof]

The simplest way how to encrypt some message is to develop secret language, something like code Navaho. It´s simple, highly effective, you don´t need any secret messanger (you can write it on the billboard), etc. etc.

[bascule]

I'd say one-time pad (OTP) is by far the best approach, with a multipart pad.

 

The simplest way to think of OTP is with the answer to a yes or no question.

 

With two messengers, one could carry the pad and one carry the ciphertext. The ciphertext is the answer to a yes or no question, and the pad tells you whether yes means yes and no means no or whether no means yes and yes means no.

 

So you can capture the messenger, but without the pad you don't know whether his message is what it says or the exact opposite.

 

Now, with a multipart pad you can easily increase the security. Stack another messanger on top of there, who has another yes/no message which indicates whether the messanger who's carrying the first part of the pad really means what they say or the opposite.

 

So the ciphertext could be yes, the first part of the pad could be no, and the second part of the pad could be no. In this way, the first part of the pad actually means the opposite of what it says, which is, yes the message means what it says, and the messanger carrying the first part of the pad meant the opposite of what he sent.

 

This can be scaled up to as many messengers as you want, but you will need them all to arrive successfully to decode the message. If one is captured, you will have to start over, but at least you can ensure that they ALL must be captured for the message to be compromised.

 

In this respect, OTP has mathematically provable perfect security (provided the pad is not compromised, and has a random statistical distribution). The ciphertext is guaranteed to be at least as random as the pad, and no amount of statistical analysis will ever reveal its message.