9
$\begingroup$

I've seen ciphers (usually in spy drama shows) that involve taking a book and writing down an index to individual characters. Essentially it's a keyed substitution cipher, where the key is the name and exact edition number of the book.

Example:

Imagine a book that has 500 pages, with approximately 60 lines per page and 80 characters per line. We might write 238:4:64 to specify that we're on the 238th page, 4th line, 64th character. A five character message might be encrypted into 114:25:22 374:41:46 182:17:62 63:53:8 50:8:18.

Without knowing what the book is, I would imagine this is provably secure as long as the person encrypting never re-used an index. Am I correct in this assumption?


For fun, you could try this out: 12:9:3 183:15:7 238:14:11 310:9:38 194:11:17 7:1:1

I'm using a page:line:character format, ignoring titles, spaces and punctuation. The book is Charles Darwin's On The Origin of Species, 6th edition.

N.B: I'm not trying to get you to crack this, just adding it because it nicely demonstrates the way this works :)

$\endgroup$
20
$\begingroup$

Using the book as a key is relatively similar to one-time pad, insofar as the book can be considered as a random stream of characters. But that's true only to some extent: a book consists of words, with meaning, which implies that characters which may appear at position 321:42:35 are not uncorrelated with characters which appear at positions 321:42:34 and 321:42:36. Therefore, merely not reusing exact index values is not sufficient; you should refrain from using two index values from the same word. This reduces the lifetime of a given book as a cipher key.

Another problem is in the "random choice". When you want to encrypt a letter, you must choose one of the index values in the book which correspond to that letter. Human beings are very bad at making random choices in their head. But non-random choices can exhibit biases. So the encryption process is important, and not completely described. An unbiased process would have you use dice to select at random the page, line and column; and if that does not correspond to your target letter, try again. That's tedious.

Also, in order to avoid reusing a given index, you must keep a list of the index places you have used, e.g. by marking the already used letters in the book. The book then ceases to be an inconspicuous object: instead of a brain-only key ("use this book"), you have a physical key ("use this, I mean that specific printed instance, book").

And, of course, anybody who has scanned millions of book and extracted the text into searchable computer structures, can easily try all existing books in a few minutes, and report a hit when the decryption result appears to look like meaningful words. So you are at the mercy of Google (and of whoever acquires Google's services).

$\endgroup$
  • 6
    $\begingroup$ Right, I would say that the main difference between this and a one-time pad is that: a one time pad's security is based on all possible pads that could be created, whereas a book cipher's security is based on all possible books that have been created. $\endgroup$ – John Gietzen Nov 25 '11 at 20:31
7
$\begingroup$

An obstacle to proving that a book cipher is secure is that the letters in (most) books are not chosen independently at random. Thus, in principle, if two indices are chosen too close to each other, an adversary could deduce some statistical information about how the corresponding plaintext letters may be correlated.

As a toy example, suppose that an adversary has already deduced (e.g. from known plaintext) that the indices 123:7:41 to 123:7:46 spell out E-N-C-R-Y-P. It's then not much of a leap of deduction to guess that index 123:7:47 probably denotes a T.

A more realistic case might be one where the book used as a key happens to be e.g. a collection of statistical tables, in which some pages consist mostly of text and others mostly of numbers. A clever attacker might then be able to deduce (again e.g. by comparing ciphertext with known plaintext) which pages are which, and thus be able to tell with fairly high accuracy which ciphertext indices denote numbers.

Also worth noting is that the keyspace, i.e. the number of distinct usable books, is not as large as one might think. Especially in the modern era of computers, it would not be hard to write a program to try to decrypt a message repeatedly using each of a collection of digitized books as keys, and to apply a statistical test to the output to see how random it looks. Indeed, with enough known plaintext, one could even make the test robust against changes in pagination and other minor differences between editions.

And, of course, a major weakness of a book cipher is that one must carry the book around as a key (or otherwise obtain repeated access to it, e.g. by regularly visiting a library). If one had captured some messages that one suspected of being encrypted with a book cipher, and had a hunch about the identity of the sender, some simple old-fashioned surveillance (and perhaps burglary) would narrow down the possible keyspace significantly.

$\endgroup$
  • 1
    $\begingroup$ Interesting. Given an attacker with moderate resources (i.e. one that doesn't have access to the entire world's literature) it seems that it would be secure as long as the pages, lines and letter offsets were chosen with reasonably random distribution. $\endgroup$ – Polynomial Nov 24 '11 at 12:42
4
$\begingroup$

NO, that book cipher is not provably secure. Much to the contrary, it miserably fails a basic security criteria in modern cryptography: ciphertext indistinguishability under chosen plaintext.

Assume one plaintext consists of many x, the other of as many j. Count, in the corresponding two ciphertexts, the number of letters coded with the third number equal to 1 (designating a character at start of a line); or, for long-enough text, with the last two numbers both equal to 1 (designating a character at start of a page); both hinting at the first letter of a word.

The lowest number obtained is likely to be for the plaintext with the many x, based on that table of frequency of characters in English words, and in the first letter of English words, sorted by decreasing ratio of the two:

                    frequency
letter   frequency   as first     ratio
                      letter
x         0.15%       0.02%       8.82
e        12.70%       2.01%       6.33
r         5.99%       1.65%       3.62
n         6.75%       2.37%       2.85
z         0.07%       0.03%       2.18
u         2.76%       1.49%       1.85
d         4.25%       2.67%       1.59
v         0.98%       0.65%       1.51
l         4.03%       2.71%       1.49
k         0.77%       0.59%       1.31
y         1.97%       1.62%       1.22
o         7.51%       6.26%       1.20
i         6.97%       6.29%       1.11
g         2.02%       1.95%       1.03
h         6.09%       7.23%       0.84
s         6.33%       7.76%       0.82
c         2.78%       3.51%       0.79
p         1.93%       2.55%       0.76
a         8.17%      11.60%       0.70
f         2.23%       3.78%       0.59
q         0.10%       0.17%       0.55
m         2.41%       4.38%       0.55
t         9.06%      16.67%       0.54
w         2.36%       6.75%       0.35
b         1.49%       4.70%       0.32
j         0.15%       0.60%       0.26

It is easy to make sensible-looking plaintext that can be reliably distinguished using this method. One can even build protracted use cases where that might be an operational problem.

If spaces are considered, and assuming spaces do not occur at start of line/page in books (or such line is discarded as leading to ambiguous character count), then things get worse.

Ultimately (especially with use of space), I believe that occurrence and location of a long enough fragment of known text could be detected from ciphertext, with fair reliability, without knowledge of the book used.

$\endgroup$
2
$\begingroup$

hummm... some thoughts about it:

  1. I think that it could be secure depending on what you want to hide. The bigger and the more "real world words" you want to protect, the easier it gets to crack. Why? Because in books, in general, you'll only have letters, few numbers, and that's only. Ok, so I know your transmitting one or more words. By the size of the index you provide, I know how long it should be.

  2. Knowing that, I can easily write some program to use it in a large collection of books. And since I know what to look for (look for letters that will make regular words), it's easy to reduce the search (this book is just giving trash? skip to the next one)

  3. How many books are there in the world? This site, citing google, says: 129,864,880. So I would have so search your index in the 130 million books. Not that hard. Ok, perhaps hard for me to have all that, but Google, perhaps government, already have all them.

  4. That will procuce some false positives. Ok, just check all them out.

  5. Remember "The Bible Code" ? Looking for secret codes / informations that could be revealed if you applied some search using constant search rules. Ex.: look for every 1004th letter of the Bible. It's how the false positives can be produced.

  6. So, it all depends on what you want to hide, from who you want to hide, and what would happen to you if someone find out your secret.

  7. Using different books on each message would help a bit. Using some "encoding" inside your code could help more: for example, the person who knows how to decrypt the message have to put the letters in the correct order, that only he knows. That avoids / slows down the brute-force search-in-every-book. But not that much, since any word not having a vowel indicates that the book is the wrong one. Perhaps using some Ceaser cipher could help.

$\endgroup$
  • 3
    $\begingroup$ +1 for the 130 million figure. That's not really all that much; we're talking about the equivalent of a 27-bit keyspace. $\endgroup$ – Ilmari Karonen Nov 24 '11 at 12:57
  • 3
    $\begingroup$ That number of 130 million books can be narrowed down further. First of all, we can discard all books not having enough pages to contain the highest page number used. But we can do better than that. Using the solution to the German tank problem, we can estimate the number of pages of the book and discard even more books. Similar techniques can be used on the number of lines per page and the number of characters per line, although those will vary less than the number of pages. $\endgroup$ – SQB Nov 15 '16 at 10:08
-1
$\begingroup$

If the book cipher refers to words as opposed to letters then the book cipher could be made more secure by the different ciphers refering to the same word. Therefore where a word appears more than once in the book likely use a different reference to it.

Another way of making it more secure is not to use a book in your native language for example an English Langauge speaker using a book in French.

$\endgroup$
  • $\begingroup$ Of course, if the book cipher refers to words, you're stuck with the words found in the book. If you're book is French, that means that you're stuck with French vocabulary... $\endgroup$ – poncho Jul 3 '15 at 20:43
-1
$\begingroup$

There are a very large number of books that have never been scanned, and most of those which have are full of garbage characters and/or are usually scanned into pdf as images, which makes them unusable.

If I used an unusual book, transcribed it in text, and wrote a program which took each letter of each word and put them into a numbered database, and then used the database to encrypt a message - also making sure no number was used more than once, it would be very difficult to decrypt without having the book. For instance, using the first paragraph of this reply 3, 5, 8, 11, etc. all represent the letter "e". So the program would pick one at random, say "5", for the first "e" in the message, then eliminate it from further use, maybe picking "11" the next time "e" occurred.

Decryption would require either the book or the database derived from the book. The program would take the number and search the database for the letter corresponding to it.

Probably the database would use numbers with the same number of digits, like "000001" for "1", and "000090" for "90", to make it easier, then all the numbers could be run together without spaces, making it harder to figure out what it was to begin with.

$\endgroup$
  • 2
    $\begingroup$ How is this an answer to the question? $\endgroup$ – poncho Jul 19 '15 at 3:08
-3
$\begingroup$

Create your own "book". Write a program that fills out pages of cells, divided into columns and rows, with randomly generated letters. Then print out 600 such pages. This "book" becomes your key that the NSA does not have a copy of....

$\endgroup$
  • 1
    $\begingroup$ If anyone writes such a program or knows of one in existence. I would like to hear about it. It would beat the hell out of creating it by hand. $\endgroup$ – InalienableWrights Mar 19 '17 at 16:00
  • 1
    $\begingroup$ This does not answer the question, which was whether a book cipher is provably secure. $\endgroup$ – otus Mar 20 '17 at 14:19

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