The Book Cipher Algorithm

Implementation

To illustrate the algorithm, we wrote three programs in C—bkadd (Listing One), bkcode (Listing Two), and bkdecode (Listing Three). They use Standard C, except for processing command-line arguments with the Microsoft-specific Visual C _splitpath and _makepath functions. File processing is via the getc and putc functions, and can be improved by using buffers to increase efficiency.

Listing One

// bkadd
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>

#define MAX_WORD_LEN 100

int main(int argc, char *argv[])
{
   FILE *fp_cod, *fp_book;
   int  ch, charno;
   char word[MAX_WORD_LEN];
   int  fromstart = 1;
   int  wlen = 0;
   // Argument processing
   char code[_MAX_PATH], book[_MAX_PATH];
   char drive[_MAX_DRIVE];
   char dir[_MAX_DIR];
   char fname[_MAX_FNAME];
   char ext[_MAX_EXT];

   if (argc != 3 && argc != 4) goto error1;
   _splitpath(argv[1], drive, dir, fname, ext );
   if (strlen(ext) == 0) strcpy(ext, "cod");
   _makepath(code, drive, dir, fname, ext);

   _splitpath(argv[2], drive, dir, fname, ext );
   if (strlen(ext) == 0) strcpy(ext, "txt");
   _makepath(book, drive, dir, fname, ext);

   if (argc == 3 ||(sscanf(argv[3], "%d", &charno) != 1)
                 || (charno == 0)) charno=1;
   if (charno < 0) { fromstart = 0; charno = -charno; }

   // File opening

   if ((fp_cod  = fopen(code, "a")) == NULL) goto error2;
   if ((fp_book = fopen(book, "r")) == NULL) goto error3;

   // Main loop
   do {
      ch = getc(fp_book);
      if (isalpha(ch))
         word[wlen++] = ch;
      else {
         if (charno <= wlen)
            putc(toupper(word[fromstart ?
            (charno - 1) : (wlen - charno)]), fp_cod);
         wlen = 0;
      }
   } while (!feof(fp_book));
   // Termination
   fclose(fp_book); fclose(fp_cod); return 0;
// Error handling
error1: printf("USAGE: bkadd codfile bookfile [charno]\n"); return 1;
error2: printf("Can not open code file %s\n", argv[1]); return 1;
error3: fclose(fp_cod);
        printf("Can not open book file %s\n", argv[2]); return 1;
}

Listing Two

// bkcode

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define N_CAPITAL_LETTERS 26
#define LTRTOIDX(x) (x-'A')

int main(int argc, char *argv[])
{
    char plain[_MAX_PATH], codfile[_MAX_PATH];
    char cipher[_MAX_PATH], positions[_MAX_PATH];
    char drive[_MAX_DRIVE];
    char dir[_MAX_DIR];
    char fname[_MAX_FNAME];
    char ext[_MAX_EXT];

    FILE *fp_plain, *fp_cod, *fp_cipher, *fp_pos;
    long pos[N_CAPITAL_LETTERS];
    int  ch_plain, ch_cod;

    // Argument processing
    if (argc != 3) goto error1;
    _splitpath(argv[1], drive, dir, fname, ext );
    if (strlen(ext) == 0) strcpy(ext, "cod");
    _makepath(codfile, drive, dir, fname, ext);
    _makepath(positions, drive, dir, fname, "pos");
    _splitpath(argv[2], drive, dir, fname, ext );
    if (strlen(ext) == 0) strcpy(ext, "txt");
    _makepath(plain, drive, dir, fname, ext);
    _makepath(cipher, drive, dir, fname, "cry");

    // File opening
    if ((fp_plain  = fopen(plain, "r")) == NULL) goto error3;
    if ((fp_cod = fopen(codfile, "r")) == NULL) goto error3;
    if ((fp_cipher = fopen(cipher, "w")) == NULL) goto error3;
    fp_pos = fopen(positions, "rb+");

    // Position array intialization
    if (fp_pos == NULL) memset(pos, 0, sizeof(pos));
    else {
       fread(pos, sizeof(long), N_CAPITAL_LETTERS, fp_pos);
       fclose(fp_pos);
    }
    // Main loop
    do {
         ch_plain = toupper(getc(fp_plain));
         if (isalpha(ch_plain))
         {
            fseek(fp_cod, pos[LTRTOIDX(ch_plain)], SEEK_SET);
            do {
               ch_cod = getc(fp_cod);
            } while (!(ch_cod == ch_plain || ch_cod == EOF));
            if (ch_cod == ch_plain) {
               pos[LTRTOIDX(ch_plain)] = ftell(fp_cod);
               fprintf (fp_cipher, "%1ld ", pos[LTRTOIDX(ch_plain)]);
            } else goto error2;
         }
    } while (ch_plain != EOF);
    // Termination
    fp_pos = fopen(positions, "wb");
    fwrite (pos, sizeof(long), N_CAPITAL_LETTERS, fp_pos);
    fclose(fp_plain); fclose(fp_cod); fclose(fp_cipher); fclose(fp_pos);
    return 0;
// Error handling
error1: printf ("USAGE: bkcode codfile message\n"); return 1;
error2: printf ("Run out of letters %c!\n", ch_plain);
        fclose(fp_plain); fclose(fp_cod);
        fclose(fp_cipher); remove(cipher); return 1;
error3: printf ("Can not open files\n"); return 1;
}

Listing Three

// bkdecode
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[])
{
    char codfile[_MAX_PATH];
    char cipher[_MAX_PATH], decoded[_MAX_PATH];
    char drive[_MAX_DRIVE];
    char dir[_MAX_DIR];
    char fname[_MAX_FNAME];
    char ext[_MAX_EXT];

    FILE *fp_cipher, *fp_cod, *fp_decoded;
    long position, cod_size;

    // Argument processing
    if (argc!=3) goto error1;
    _splitpath(argv[1], drive, dir, fname, ext );
    if (strlen(ext) == 0) strcpy(ext, "cod");
    _makepath(codfile, drive, dir, fname, ext);
    _splitpath(argv[2], drive, dir, fname, ext );
    _makepath(cipher, drive, dir, fname, "cry");
    _makepath(decoded, drive, dir, fname, "txt");

    // File opening
    if ((fp_cipher  = fopen(cipher, "r")) == NULL) goto error3;
    if ((fp_cod = fopen(codfile, "r")) == NULL) goto error3;
    if ((fp_decoded = fopen(decoded, "w")) == NULL) goto error3;

    // Determine codfile size
    fseek(fp_cod, 0, SEEK_END);
    cod_size = ftell(fp_cod);

    // Main loop
    while ((fscanf(fp_cipher, "%ld", &position) != EOF)) {
        if (--position <= cod_size) {
           fseek(fp_cod, position, SEEK_SET);
           putc(getc(fp_cod), fp_decoded);
        }
        else goto error2;
    }
    // Termination
    fclose(fp_cipher); fclose(fp_cod);
    fclose(fp_decoded);
    return 0;
// Error handling
error1: printf ("USAGE: bkdecode codfile cipher \n"); return 1;
error2: printf ("Invalid ciphertext\n");
        fclose(fp_cipher); fclose(fp_cod);
        fclose(fp_decoded); remove (decoded); return 1;
error3: printf ("Can not open files\n"); return 1;
}

The idea is to create a "tank" of letters from books for each of the correspondents. Using the command bkadd allice mybook.txt 1, Bob creates the file allice.cod with the initial letters of each word in mybook.txt. The last parameter determines which letter of each word should be used—positive values 1, 2, 3, stand for the first, second, third, respectively, and setc letter, while negative values mean that letters should be counted from the last position in the word. If this parameter is omitted, the first letters are taken as the default.

Program bkcode is used to encode a message: bkcode allice message1.txt transforms message1.txt into message1.cry using letters from allice.cod. At the successful completion of the process, the program generates the file allice.pos with pointers to the positions of last used letters a, b, c, d... in allice.cod. When the next message is encoded (bkcode allice message2.txt), the search for the letters automatically continues from the previously memorized positions; no part of the (transformed) book is used twice. If the process fails (that is, if the supply of at least one of the letters in allice.cod is consumed), the appropriate message is generated and the file allice.pos is unchanged. Bob should add another book to allice.cod using the command bkadd allice myotherbook.txt 1 and repeat the bkcode command.

To decode a message, Allice uses the command bkdecode allice message1.cry, producing the message1.txt file. Figure 3 shows the complete process. In a two-way communication, by using different books, Allice should generate the file bob.cod and use it to encode messages to Bob.

[Click image to view at full size]

Figure 3: Programs and results of coding and decoding the message using the Book cipher.

Eve is welcome to intercept any of the .cry files but without knowledge of the books used, she is clueless even if her other name is "Susan Fletcher."

How Strong Is It?

Cryptanalysts mostly agree that the Book cipher, if used properly, is practically unbreakable; nearly as good as the one-time pad. Why isn't it used every day? Maybe because of that "if used properly" clause—the complete algorithm is somehow "private." The next time you bury a treasure, you can describe its location within an encrypted message and be reasonably sure that it will not be decoded for the next 150 years, but if you have to organize a secure correspondence for a web of spies all over the world, finding, deploying, and protecting adequate books might prove very difficult. By implementing the Book cipher in your applications, you don't meddle with powers you cannot comprehend—you leave the meddling to users of your software. The average user will probably go to www.gutenberg.org, download the first book, and use it as a key without even bothering to delete the copyright message (which is basically the same for every book on that site).

On the other hand, if users of your software contribute ideas of their own—using texts from the Internet instead of books, using different languages, pre-encoding messages using other algorithms, and so on—then potential attackers would be facing many groups of short messages encrypted using (at least slightly) different algorithms, which might present the ultimate challenge.

Dejan is editor-in-chief of PC Press, a personal computer magazine in Serbia and former Yugoslavia. He can be contacted at www.ristanovic.com. Jelica is a professor of computer engineering at the School of Electrical Engineering, University of Belgrade. She can be contacted at www.jeca.rs.