Encrypting maps

Question

Encrypting texts is a very old technique, which is known already from the time of the Romans, if not earlier. Now a simple text cypher is easily done with low-tech means, as long as those trying to break the code also have to rely on low tech.

Now medieval maps were often secrets. Therefore one might imagine that some medieval king wants his maps encrypted as well. Now it's of course easy to encrypt names using any text cypher, and moreover you may use non-standard symbols for landmarks. However, those would probably be easy to decode for anyone who is familiar with at least a small part of the mapped landscape. Therefore an effective encryption would need to encrypt the actual map, including the positions and relations of the landmarks to each other.

Therefore my question is: How might one encrypt a map?

The conditions are:

• Encryption/decryption should be doable with medieval means.
• For someone familiar with the encoding, it should be possible to decode the relevant features in little time, using only a minimum of tools (the map should be usable on travels).
• The encryption should be non-obvious to someone who is familiar with the mapped region, but doesn't know the encoding (that is, the encryption doesn't need to withstand modern cryptanalysis tools — the Caesar code wouldn't withstand them either — but it should not allow someone not knowing the code to look at the map and say "I recognize this region").
• In response to Keith: The map should be detailed enough that you can find your way, and can identify special spots (like the spot where you want to position your army, or the spot where you have buried the secret chest). However, the map can be amended with written information for details (for example, if it allows you roughly to get to the place of the buried chest, the exact placement could be written in a text referring to the landmarks around), so there's no need for extreme precision.

Answer 1

Folding.

Make a large map with large erroneous portions that become hidden with proper folding. This will confound even someone familiar with the area. "That looks like such and such river, but it doesn't have this adjacent mountain range..."

Yes, creasing could give it away, so the solution there is to use separate pieces of different maps which, when layered and oriented properly, reveal the real map. The cipher would be something akin to overlapping the dot marking certain towns or geographical landmarks.

Basically this is a map made of a collage of maps. I can't find a proper example, because maps aren't usually designed to do this, but it might look something like this when the erroneous sections are folded away:

Folding is preferred for the single or separate maps to produce the final map. Otherwise you just have the complete map cut into pieces. The maps can otherwise contain many folds to hide the proper ones and be flattened when not in use to avoid capture of the proper folding. Adding other maps which play no part in the final map will serve to further confuse anyone who captures them.

Answer 2

You could always do it the way Robert Baden-Powell (the founder of the Scout Movement) did when he was posted to Malta as a spy, Draw maps as butterflies or some other animal. This does not require any special tools to decrypt other than to merely look at it. Those unfamiliar with the concept will see only an image of an animal / bug. In theory this could still be used today depending on how many people know what you are up to. In particular, in the included image you can note that "secret spots" (in this case gun emplacements) are marked on the wings of the butterfly as patterns further hiding the real intentions behind the image. Essentially if you could produce a convincing enough image of an animal that could have features that stand out only to the recipient or those knowing the code, you would have both an alibi for carrying a "map", as well no real proof that what you are holding is a map.

Links to Sources:

http://publicdomainreview.org/2013/07/10/robert-baden-powells-entomological-intrigues/ http://pinetreeweb.com/bp-adventure02.htm

Answer 3

Anamorphic drawing

uses a reflecting surface to draw/view a scene (or a map)

The shape of the reflecting surface is the cryptographic "key" that would allow the information to be extracted, while hiding it from anyone lacking the correct reflector.

Answer 4

Encryption requires a key to decrypt. Lets work with that assumption.

Draw a full map to act as the "key", and cut holes and lines and shapes in it that ruin it. Draw a second full map by first overlaying the cut out pieces of the key on top of the second map. For each section that is not covered, draw fake details and information into it. Then, remove the covered sections and replace it with legitimate information.

Now, only when you have both the key and the map are you able to make any sense of the two - the key is full of holes and as such unusable by itself, and the map is full of fake sections that are covered up by the key when applied correctly.

Answer 5

Color Encoding

When the map is made, add landmarks and terrain features using a specific color. Accompany the resulting map with a set of glasses with color-filtering lenses designed specifically for that map. Medieval techniques would cause each map and each set of glasses to be slightly different, making perfect decoding of unassociated map-glasses pairs to be difficult and/or confusing.

Image Distortion

Instead of using color filtration, the maps could be made using image-distorting lenses, much in the same way as the mirrors at a fun house. If the cartographer makes unimportant/important parts of the map using lenses that make everything wavy, the resulting hodgepodge of real and wavy parts can easily cause confusion.

Answer 6

You could draw parts of the map on pieces of thin paper. The pieces would need to be folded and stacked in a specific way. Then, the map is lit from the back somehow (sunlight, sky or firelight). This reveals the map.

If you've seen the original Iron Man, Tony Stark uses a method like this (without the folding) to disguise his plans for the first Iron Man suit he made in the cave when he was captured. When the pieces were arranged correctly, it showed the full suit, but otherwise they just looked like random drawings. (Sorry, couldn't find the link..)

Answer 7

Hide the map in what looks like a coded message of text.

For instance, take the following text with various capital letters:

AT VEro eos et accusamus et iusto odio dignissimos ducimus qui bLAnditiis praesentium volupTAtum deleniti atque corrupti quos dOLores et quas molestias EXCEpturi Sint occaecati cupiditate non proVIDENT, SIMIlique sunt IN cULpa Qui OFficia DEserunt mollitia animi, id est laboRUm et doloRum fuGA. et haRUm qUIDEM rerum facilis est et expeDITa distinctio. Nam liberO tEMporE, cum soluta nobis est eligENDI OPtio cumque nihil iMPEdit qUO minus id quod mAXIME placeat facerE Possimus, omnis vOluptas Assumenda est, omniS dolOr repellendus. tEmporibus autem quibusdaM Et aut officiis DebitIs aut rerum necesSITatibus saepe eveniet ut et voluptateS REPUdiandae sint et molESTiae non recusandae. itaque earum rerum hic tenetur a sapiente dElectus, ut aut reiciendis voluptatibus maiores alias consequatUR AUt perferendis doloribus asperiores repellat.

Apply the cypher which says to split lines after a certain number of characters at the nearest space:

AT VEro eos et accusamus et iusto odio dignissimos ducimus 
qui bLAnditiis praesentium volupTAtum deleniti atque corrupti 
quos dOLores et quas molestias EXCEpturi Sint occaecati cupiditate 
non proVIDENT, SIMIlique sunt IN cULpa Qui OFficia DEserunt mollitia 
animi, id est laboRUm et doloRum fuGA. et haRUm qUIDEM rerum 
facilis est et expeDITa distinctio. Nam liberO tEMporE, cum 
soluta nobis est eligENDI OPtio cumque nihil iMPEdit qUO minus 
id quod mAXIME placeat facerE Possimus, omnis vOluptas Assumenda 
est, omniS dolOr repellendus. tEmporibus autem quibusdaM Et aut 
officiis DebitIs aut rerum necesSITatibus saepe eveniet ut et 
voluptateS REPUdiandae sint et molESTiae non recusandae. itaque 
earum rerum hic tenetur a sapiente dElectus, ut aut reiciendis 
voluptatibus maiores alias consequatUR AUt perferendis doloribus 
asperiores repellat.

Throw away lower case letters and replace them with spaces, replace the capital letters with some character.

XXXXX                                                 
     XX                         XX                    
      XX                       XXXX    XX             
       XXXXXXXXXXX           XXX  XX  X XX      XX    
                 XX          X     XXXX  XX   XXXXX   
                  XXX               X     XX XX   XX  
                    XXXXXXX                XXX     XX 
         XXXXXX            XXX              X       X 
         X    X               X                     XX
         X    X                XXX                     
         XXXXXX                  XXX                  
                                   X                  
                                   XXXXX              

The simple map is revealed. Meanwhile any captured documents would have enemy spies trying to decipher some encoded message, when no such message exists.

Answer 8

We can make some sort of jigsaw puzzle with square pieces without holes and pinches from map.

And put special symbol on the bottom side of the map. Let us consider the "MAP_OF_CITY" is the key. So, the first piece is the one with "M1" on bottom, the next is "A1", third is "P1" and so on, than, after "Y1", the "M2", than "A2" and so on. Of course we have pieces that are fake (for example, with letter of "W1","W2" and so on).

So, the map can be assembled quite fast, and pieces can be quite small for images to be usefull.

Also the map can be something, that do not looks like a map - like Ammassalik wooden maps

Answer 9

Create a map grid with letters on one axis and numbers on the other, ex: A through Z on top, 1-26 on the left.

If you need finer details, you can increase that, say A through AZ and 1-52.

Now turn your map into a written description:

The river is an eighth of a mile wide and runs from A3 to E7 to M6. It widens around L6 and there is a crossable ford at D5. The trade road runs from A5 through...

Now you have a written description, and you can use standard encryption techniques on that. You have two options with that:

1. Encrypt all of the text. This is the most secure, but takes the longest to decrypt.
2. Only encrypt the coordinates. This is less secure, because people will be able to gather rough details without the code. But it also makes it much faster to decode and reverse to the correct coordinates and recreate the map.

Answer 10

Love this question, and there are some ingenious answers already.

I haven't checked the engineering on whether this would be possible, but I'm thinking a Pantograph with custom geometry to transform the map outlines; the transforming element could be replaceable for different encodings.

So, General 1 creates his master map. It is transformed onto another sheet, which is given to Disposable Soldier 1 to take to General 2, who uses the previously agreed upon pantograph element to reconstruct the original.

Doable with some bits of wood and a charcoal stick; although the transforming element may have to be more accurately made.

Answer 11

Invisible ink

It is is not exactly cryptography, but steganography, but you are using an innocent looking sheet of paper and paint the map in invisible ink which will be visible if heated. The idea is already known in the time of the old Greeks.

Grille

Use a Fleißner Grill. Draw the map, divide it in equal parts divisible by four and create a template where one fourth of entries are open. Look at the windows, enumerate the parts on the back, rotate the grille and continue. In this case the map must not have shared lines or features on their borders because then it is a jigsaw puzzle which can be solved..

Answer 12

Excellent question. I don't know if it has ever been done.

Substitution and Transposition

First, re-arranging map elements, such as a mountain-replaced-by-a-body-of-water. But this is recognizable to someone familiar with your region.

Next, re-assembly of the mapped region by squares of, say 500m x 500m, so that there is a distortion that only your readers can understand how to re-assemble it.

Smooth out the features so that they blend together and you have a map of an un-recognizable region with features that are not familiar to anyone from 'round here.

Your readers then take up the scissors and re-assemble and re-substitute. Feel free to throw in classic cryptography of the names of features or strategic positions after that.

Answer 13

One idea which can be combined with the others is to have a stack of decoys. Following the wrong one can be expensive or dangerous, if it includes things like safe reef passages and mountain passes.

You have to know which parts of which sheets are right, as well as how to fold/mask/layer them properly.

The cost of brute-forcing the key could then be higher than the value of the map.

Some specific details might be practically coded as plain text, which is then encrypted in a conventional manner. For example, a shoreline can be covered with numbered points, and the safe way through the rocks/reefs is encoded as a list of waypoints in a separate document.

Answer 14

Visual Cryptography provides a very nice approach:

The advantage is that if done right, each share has exactly zero information. Suppose that you convert the map into grayscale "pixels". You take a transparent sheet and for each pixel, fill half of the pixel at a random orientation. This is the key.

Now you take another transparent sheet, put it on top of the key sheet, and start drawing the map by filling exactly half of each pixel again, but at such an orientation that combined with the underlying key it will either result in a fully black pixel, a half-black pixel, or anywhere inbetween.

Very simple, completely secure (zero information in each share separately), and does not require a computer to create. (though admittedly transparent sheets might be difficult to come by in those times)

Answer 15

How about drawing the maps on the glass of a set of lamps. When you want to see the map, you can set the lamps up at a certain distance and angle to a screen (this would be the key). You then setup a screen of some sort (like the wall of a tent, or other flat, lightly colored surface) When you light all the lamps, the map is projected onto the screen. If you don't want the maps captured, smash them.

It would look like this, except the pictures would be parts of a map, and overlapping. Also, you could have a more complicated shade or blown glass cover for the lamp to distort or mask things for more secrecy.

Answer 16

Use stack of transparent papers

Each paper consists of patches of real and fake parts of a map drawn on them (with solid background), but it is mostly transparent. When stack in the correct order, all fake pieces are hidden under the real ones, revealing the true map. Every paper is numbered from 1 to N, giving N! different arrangements. The decryption key is a sequence of numbers in which they need to be stacked. Papers are randomly shuffled before storing the map. This map is easy to decrypt and read and decrypting doesn't require any additional items. In addition the map can be split between multiple parties. Also pieces that contain only fake patches can be added to increase the difficulty.

Edit: In addition every piece can be stack in obverse or reverse giving you total of N!*2^N possibilities

Answer 17

Use a one-time pad with XOR.

To encrypt

1) Draw your map as a black and white grid of squares (bitmap) made up of filled and empty squares (plaintext)

_________
|_|_|_|_|
|_|X|X|X|
|_|X|_|_|
|_|X|_|_|

obviously you can make this as big as you want.

2) Draw another bitmap with squares filled in randomly (key)

_________
|X|_|X|X|
|X|_|X|_|
|_|X|_|X|
|_|X|X|_|

3) Draw your encrypted map with the following rules: For each square compare the contents of 1) and 2) and colour in only the squares that are different (black in one, but not the other)

_________
|X|_|X|X|
|X|X|_|X|
|_|_|_|X|
|_|_|X|_|

---

To decrypt:

Take 3) and 2) For each square compare the contents of and colour in only the squares that are different (black in one, but not the other) Voila, you get 1) back.

_________
|X|_|X|X|
|X|X|_|X|
|_|_|_|X|
|_|_|X|_|


_________
|X|_|X|X|
|X|_|X|_|
|_|X|_|X|
|_|X|X|_|

=> original

_________
|_|_|_|_|
|_|X|X|X|
|_|X|_|_|
|_|X|_|_|

Provided you filled in 2) randomly then there is no way of breaking this encryption unless you have the key. Also you should only use 2) once and not for a set of maps.

Answer 18

Similar to what Mnementh suggested.

Start with a large piece of high quality leather. Leave large top and bottom margins and draw the map in between. Full width but only the middle part vertically.

Now divide the map into vertical strips of width suitable for a belt with a marker. From these strips mark a belt length portion that covers the map containing but has a different top and bottom margins, start and end points for each strip. Belt holes and buckles should also go to the unmarked part. Cut off the strips, fill the unmarked parts with fake map lines, and turn the strips into belts. The belt decoration on the other side should tell with some code the strip ordering and the top margins used.

Anyone who knows the same code of markings to order and margin can reassemble the map. Presuming that they use same measures for the margins... Each belt can be given to different person and aged to different degree.

Answer 19

I'm most familiar with the encryption of numbers, so I came at this from a numbers angle.

Maps can be numbers, most usually in a grid. These numbers can either represent geographical features, topography, or something else entirely.

Features grid visually represented (screenshot of Advance Wars on GBA):

Topography:

Now, since we're using numbers, we can use classic encryption methods. You'd have your original map, and you'd have a key, a grid of random numbers. You could then add/etc. the respective numbers on both grids to form the encrypted map. As long as the recipient had the key, they could reverse calculate the original map, and it would be impossible for anybody without a key to decrypt it, as there could feasibly be a key that would generate any possible map.

Answer 20

An idea is having longer stripes of paper. Lets say you have six of these stripes (ABCDEF). Some of them you can now lay horizontal, some vertical, lets say:

AAA
BBB
CCC

DEF
DEF
DEF

Now you lay the stripes over each other in a pattern, so that some parts are hidden by others:

AEA
DBF
CEF

On the parts that are hidden in the final layout paint some fake map to distract people.

Answer 21

Well it seems to me that any kind of direct-placement of symbols on a page wouldn't work, simply because it doesn't matter what the symbols are -- anyone familiar with the area could infer meaning from them, and deduce an "unusual" one to be more important.

Instead, some means of scrambling the actual data seems in order. That's rather challenging to do with a single, homogeneous page, as there is no easy way to un-scramble paper, except with cutting and rearranging, as @Mikey suggests.

I'd imagine some kind of tool or "key" used to encode and decode the map. Such as a specially-shaped glass lens. Place it on top of the map, and it de-encrypts it. Or blue-glass filter, and multi-color paper. Hard to see the real data without it. Or a chemical added to it, which only reacts with another chemical.

Answer 22

The requirement that the map can be used while on a journey, presumably under Medieval conditions, is a tough condition. I can think of all sorts of ways of encrypting a map using technology available in the Middle Ages, but most of the ideas I come up with would require considerable time to decrypt, tools that might not be so convenient to lug around, etc.

But here are two ideas that I can suggest:

1. Cut the map into pieces, with each piece being too small to be of practical value. Write some code number of symbols on each piece that can be used to put them back together correctly. Note the symbol must be in code: obviously if the pieces are simply labeled with grid co-ordinates, anyone could quickly figure this out and put them together. But there are any number of routine cyphers available to encrypt the grid co-ordinates.

Combine this with encrypting any text on the map, so that an unauthorized person can't use place names as clues to figuring out the proper arrangement.

Deliberately mis-align things that cross the borders between sections slightly. You don't want someone to be able to re-arrange the pieces by lining up roads and rivers, or you just turn the cypher into a jigsaw puzzle. So if, say, a road crosses from tile A4 to tile E6, move the road just slightly to the north on the edge of A4 and slightly to the south on the edge of B6 so it doesn't line up.

2. Use conventional map symbols, but use them randomly for the wrong things. Like on one part of the map a blue line may be a river like we would expect, but elsewhere it is a road, and yet somewhere else it is a mountain range. Coded text on the map tells which it is in each case. The text is encrypted by conventional means. So if I see what looks like a mountain range, and it's labeled "Fwghthrnbr", and I decrypt this and it turns out to mean "Rhine River", then I know this mountain range really represents a river.

Hmm, if we use a system to encrypt the text that doesn't look like code but like plausible names, like we encrypt "Rhine River" as "Harold's Mountains", then to someone trying to read the map, it might look like an ordinary map, and he just can't figure out where this place is. If he doesn't realize it's in code, he won't try to crack the code. It would be easy enough to have some substitution cypher that treats common terrain names, like "River", "City", "Bridge", etc, as units that are transformed into each other according to some set and reversible rules. Like arrange them in a list and then go up or down so many slots in the list based on the position of the word on the map or other words around it.

Answer 23

Usability may depend on intentions. Assume you want to transfer a map from A to B once, with the risk of being intercepted. Shave the head of a messenger. Tattoo the map on his skalp. Wait for his hair to grow. Send the messenger (with a fake map for distraction). At the destination shave hime again.

Answer 24

Draw a normal and usable map but include some extra points (like trees with n branches or letters with a special shape..) in it. To decipher the secrets one would have to connect the extra points.. The crossing of two or more connectors are the hidden places..

Answer 25

Don't make a map, make directions

Think about what a map really is. A map is a visual display of local geography. It shows rivers, hills, roads and towns. The biggest reason a map is used is to figure out directions to get to a certain place. Therefore, instead of encrypting the map, cut out the middleman and just give directions.

Make the directions harder to follow for those that must not know

Instead of using official names for villages, use codewords that include minor events from villages. Refer to villages not by the village name, but by the name of a local dignitary. Most people don't know the name of the dignitaries a village over. Hell, most people don't even know the names for their own village dignitaries.

Answer 26

How about having a Mirror Key for your encoded map?

You place the mirror at a certain location on the map with a certain orientation, then look at it from a certain point and the map will come into focus.

Notes:

• The mirror key doesn't need to be a perfect mirror, but instead just reflective enough to make out the image. Polished metal would work and would be consistent with medieval times
• As you are drawing your encoded map you need to replicate the same setup as when you'll read it later, and then draw it based on the reflected image you want (I'm sure that will take a LOT of patience and practice).
• You can also have "dark" places that won't show up in your reflected image. This will let you add in features to the map that don't belong.
• You can vary several things to make it difficult to read the map even if someone finds the mirror and the map together:
  • Where you put the mirror in relation to the map
  • What side of the mirror is up
  • What angle to hold the mirror at
  • Where you look at the image from
  • How the map is folded
• The mirror will take some experimentation to get right. For example, you may find that some setups won't work because the places you'll need to draw will overlap. Probably the easiest would be to cut flat pieces and have them at different planned angles to avoid this. However, curved pieces would add an extra layer of distortion (and complexity!)

Answer 27

Encrypt the text-based instructions necessary for creating the map

for example, take a chess game and imagine the board as a map - most commonly, the board arrangement is determined by walking through how the pieces got there rather than giving each piece a coordinate

so for example, you could have instructions to place a city in the dead center, then a mountain range from east to west just north of the city, an enemy city a quarter of the map away to the north-east on the other side of the mountain range, and then an equal amount away but to the north-west have a hidden cave with the treasure, that will be visible only by the last light of Durin's Day, etc.

Answer 28

Up is down.

(I can't make comments yet)

---

*sigh*

Ok, this is a map featured in the third Pirates of the Caribbean movie. It consist of several Annulus of different sizes, with a circle in the center of them all.

I think this could be done with thin wood by attaching the circle and the outer annulus to other, more stable surface (like another piece of thin wood, either circular or square). Or, maybe it doesn't have to be attached at all; by leaving the pieces separated (and maybe split in several parts) they can be carried easily and add other level of difficulty to this. It could also be done in paper, though.

Since the pieces can be rotated, the key is the relative position of all the pieces.

If the annulus are split in several parts, its pieces have many ways to be put together as long as there are no recognizable "outlines" (as stated below), but that could be solved by adding fake ones. Each piece could have some sort of identifier, like signs, letters or numbers (don't have to be sequential, it may be "1", "-8", "Pi" for example), so one can remember their relative order.

All locations don't have to be real, only the relevant one. The rest can be fake to make it harder to solve the puzzle.

Annotations could be made like in the film (between one annulus and other, as seen in the pic), or inside of them.

You could use one key for the map in question, and other key for the annotations.

The downside of this is that it has to be a map of either many outlined parts (as is the case of the movie with islands), or a map of a zone with no recognizable outlines (e.g. a river). If it contains a river, the solution would be make only one part of the river "real" (the most relevant) and then complete it with fake splits, if possible in other part of the map but that, when using a certain key ("position") the fake river matches with the real (i.e. a "collision" in the "output").

Answer 29

As an extension to Andrew's answer, quickly generating pseudorandom binary strings for the one time pad by hand can done in the following way:

• Take a number and transform it into binary.
• Add a 0 to the end of the bit string.
• Remove the first bit from the string.
• XOR this string with the previous string.
• This is your random string.
• Repeat.

This is based on the Xorshift algorithm.

This algorithm will generate $2^n$ random numbers for a seed of length n. It is not secure, but it eliminates the need to share a large amount of random numbers.

An Example:

11011 (The start number) - First Number - 27.

110110 (Add a zero.)

10110 (Remove the first bit.)

01101 (XOR with previous result) - Second number - 21.

...

A simple implementation in Python:

def random(seed):
    seed ^= seed << 1
    yield seed