NetNews Usenet Archive 1992 #16/NN_1992_16.iso/spool/sci/crypt/2740

Text File | 1992-07-25 | 13.1 KB | 363 lines

Path: sparky!uunet!zaphod.mps.ohio-state.edu!news.acns.nwu.edu!uicvm.uic.edu!u27239
Organization: University of Illinois at Chicago
Date: Saturday, 25 Jul 1992 14:23:18 CDT
From: Gerald Strom <[e-mail]>
Message-ID: <[e-mail]>
Newsgroups: sci.crypt
Subject:    transposition ciphers
Lines: 353

The following is a little piece I wrote recently about transposition
ciphers.  As I am far from being an expert in this field, I hope I
didn't get too much wrong and I would appreciate comments.


                   TRANSPOSITION CIPHERS

                      Gerald S. Strom
               University of Illinois at Chicago

     When Julius Caesar wanted to keep his messages from being read
by his enemies (and probably a few friends as well), he devised a simple
substitution cipher whereby one letter was replaced by another.  This
Caesar Cipher is not secure by the standards of today but interestingly,
the method used, substituting one letter or character for another in a
regular way, is still the fundamental basis for encipherment in modern
ciphers systems.  The DES system developed by the United States
government, the various public key ciphers systems, as well as the
German Enigma cipher cracked by Allen Turing during World War II
using one of the first computers are all substitution ciphers whereby
letters in the plain (or un-enciphered) text are replaced by different
letters or characters to create the cipher (or enciphered) text.
     The cipher described here differs fundamentally from the
substitution ciphers systems in that it does not rely on replacing one
letter with another.  Instead, it is a transposition cipher that relies on
scrambling the letters of the plain text in a random fashion so that the
enciphered file has the same characteristics as the plain text file.  This
makes it difficult to break because the normal statistical methods use
to break ciphers do not work.  The letter counts, for example, will be
identical in the plain and cipher text files and this means that one
cannot use letter count correlations to guess what letters may have been
substituted for another.
     How does a transposition cipher work?  After all, randomizing the
letters in a file as a means of enciphering is only useful if there is some
way that they can be unscrambled again to their original order.  This is
where one of the otherwise problematic properties of random number
generators is a great virtue.  This property is that as implemented on
modern computers, random number generators always return the same
series of quasi-random numbers if given the same seed value.  To see
how this property can be used in a cipher, consider as an example a
string of fixed length, say one made up of the first five letters of the
alphabet: a, b, c, d, and e.  Now generate five random numbers from a
given seed and number them from 0 to 4.  Now sort the random
numbers but keep the original numbering associated with each number.
These original numbering numbers are now in random order and can be
used as an string or (array) index to randomize the order of letters.  For
example, after sorting the original numbering numbers may be in the
following order (3, 1, 0, 4, 2).  If this string of numbers is placed in an
array r, then encipherment takes place according to the following
formula:
 enciphered_text[i] = original_text[r[i]] (for i = 0 to 4)
Thus the original abcde string is now dbaec in the enciphered_text
string.
     Deciphering the enciphered text is simply the reserve of the
above operation.  Generate the same sequence of random numbers with
the same seed, number them and sort them.  This will result in
obtaining the same (3, 1, 0, 4, 2) sequence as above.  Now apply the
following formula:
 restored_text[r[i]] = enciphered_text[i] (for i = 0 to 4)
The first enciphered_text character is d so for i equal to zero above the
first character will be written into the fourth (base 0 remember)
position in restored_text (r[0] = 3), which is exactly where d should be.
     Listings 1 and 2 provide a simple implementation of this cipher
in ANSI C.  The first listing enciphers a file (but does not change the
file itself) and the second listing deciphers a file.  It can be seen that
there is a great deal of redundancy in the two listings and some may
choose to combine the routines into one file capable of both
encipherment and decipherment.
     There are several things to note about the implementation in the
listings. First, fixed size blocks of size 256 are used so that the program
actually randomizes the content of a file within blocks of 256 characters.
There is no particular reason why this block size was selected and
others, even variable ones based on some algorthim using the key, could
be used.   One factor to bear in mind, however, is that the programs
need to sort to both encrypt and decrypt and the length of the block will
have a significant impact on how long these sorts take.   In general, the
longer the block used, the longer program execution will take but the
more secure the encryption.  Readers may wish to try various block sizes
with various file sizes and determine if there is a general optimal block
size.  Remember though to use the same block sizes for encrypting and
decrypting.
     Second, note that the random number generator used is the
default rand() supplied with most compilers.  Similarly, this generator
is seeded with the standard srand().  Other generators would be used
but note that the int definition for num1 in the structure needs to be
changed to float if a floating point generator is used.  Actually, using
different random generators enhances the security because different
generators produce different sequences so that two files enciphered with
the same key but different generators will be enciphered differently.
     Third, the seed for the random number generator is derived in
the listings by adding the numeric values of the letters in the key to a
predetermined value (1947 in the listings).  This is obviously not a very
original or secure method and those interested in serious
implementations will want to use their creativity here, using a non-
obvious and "hard" method of deriving the seed from the key.
     One possibility is this regard is to use a random number generator
that takes a floating point number as a seed.  By using a creative
method of converting the integer values of the key letters into a floating
point number, the possible seeds becomes effectively infinite and
precludes the possibility of a brute force attempt to find the key.
     Fourth, a routine not implemented in the listings is to waste
some predetermined number of the random numbers before saving
those that will be used in the letter randomization.  This could be done,
for example, by predetermining a fixed number of times to execute a
loop calling the random number sub-routine or by varying this number
for different files based upon the key.
     Finally, note that all files are opened for reading or writing in
binary so that it is possible to encipher text files, executable files (i.e.
.EXE and .COM files) and archive or compressed files.  In fact, by first
compressing a file and then randomizing the content of the resulting
archive significantly increases the security of the encrypted file.
                              /*  LISTING 1
                          ENCRYPTION ROUTINE  */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX         512
#define NAME_SIZE   30
#define BLOCK_SIZE  256

typedef struct {
          unsigned int num1;
          int num2;
          } rnums;

void encrypt(FILE *, FILE *);
void no_memory(void);
int comp(rnums *, rnums *);
void reorder(int, int *);
FILE *open_file(char *, char *);

void main()
{
     char *key, *filein, *fileout;
    int i, seed = 1947;
     FILE *fin, *fout;

     if ((filein = malloc(NAME_SIZE)) == NULL)
          no_memory();
     if ((fileout = malloc(NAME_SIZE)) == NULL)
          no_memory();
     if ((key = malloc(MAX)) == NULL)
          no_memory();

     fprintf(stdout, "\nEnter name of input file: ");
     scanf("%s", filein);
     fprintf(stdout, "\nEnter name for output file: ");
     scanf("%s", fileout);
     fprintf(stdout, "\nEnter encryption key (256 max; ENTER ends): ");
     scanf("%s", key);

     fin = open_file(filein, "rb");
     fout = open_file(fileout, "wb");

    for (i = 0; i < strlen(key); i++)
        seed += *(key + i);
    srand(seed);
     encrypt(fin, fout);
    fclose(fin);
    fclose(fout);
}
void encrypt(FILE *fin, FILE *fout)
{
     register int i;
     int j, block_length, *source, *rnum;

     if ((source = malloc(MAX * sizeof(int))) == NULL)
          no_memory();
     if ((rnum = malloc(MAX * sizeof(int))) == NULL)
          no_memory();

     i = 0;
     block_length = BLOCK_SIZE;
     while (!feof(fin)) {
        if ((*(source + i) = fgetc(fin)) != EOF) {
                if (++i == block_length) {
                     i = 0;
                     reorder(block_length, rnum);
                     for (j = 0; j < block_length; j++)
                         putc(*(source + *(rnum + j)), fout);
                }
          }
          else {
                reorder(i, rnum);
                for (j = 0; j < i; j++)
                     putc(*(source + *(rnum + j)), fout);
          }
     }
}
void reorder(int n, int *num)
{
     int i;
     rnums rand_struct[MAX];

     for (i = 0; i < n; i++) {
        rand_struct[i].num1 = rand();
          rand_struct[i].num2 = i;
     }
     qsort(rand_struct, n, sizeof(rnums), comp);
     for (i = 0; i < MAX; i++)
          *(num + i) = rand_struct[i].num2;

}
int comp(rnums *e1, rnums *e2)
{
     if ((e1->num1 - e2->num1)> 0)
          return 1;
     else if ((e1->num1 - e2->num1) < 0)
          return -1;
     else
          return 0;
}
FILE *open_file(char *name, char *type)
{
     FILE *fp;

     if ((fp = fopen(name, type)) == NULL) {
          fprintf(stdout, "\ncannot open %s\n", name);
          exit(1);
     }
     return fp;
}
void no_memory(void)
{
     puts("\nCannot allocate memory -- Aborting\n");
     exit(1);
}
                              /* LISTING 2
                          DECRYPTION ROUTINE  */

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

#define MAX         512
#define NAME_SIZE   30          /* In case anyone has a long path */
#define BLOCK_SIZE  256

typedef struct {
          unsigned int num1;
          int num2;
          } rnums;

void decrypt(FILE *, FILE *);
void plant_seed(char *);
void no_memory(void);
int comp(rnums *, rnums *);
void reorder(int, int *);
FILE *open_file(char *, char *);

void main()
{
     char *key, *filein, *fileout;
    int i, seed = 1947;
     FILE *fin, *fout;

     if ((filein = malloc(NAME_SIZE)) == NULL)
          no_memory();
     if ((fileout = malloc(NAME_SIZE)) == NULL)
          no_memory();
     if ((key = malloc(MAX)) == NULL)
          no_memory();

     fprintf(stdout, "\nEnter name of input file: ");
     scanf("%s", filein);
     fprintf(stdout, "\nEnter name for output file: ");
     scanf("%s", fileout);
     fprintf(stdout, "\nEnter encryption key (256 max; ENTER ends): ");
     scanf("%s", key);

     fin = open_file(filein, "rb");
     fout = open_file(fileout, "wb");

    for (i = 0; i < strlen(key); i++)
        seed += *(key + i);
    srand(seed);
    decrypt(fin, fout);
    fclose(fin);
    fclose(fout);
}
void decrypt(FILE *fin, FILE *fout)
{
     register int i;
     int j, block_length, *source, *destination, *rnum;

     if ((source = malloc(MAX * sizeof(int))) == NULL)
          no_memory();
     if ((destination = malloc(MAX * sizeof(int))) == NULL)
          no_memory();
     if ((rnum = malloc(MAX * sizeof(int))) == NULL)
          no_memory();

     i = 0;
     block_length = BLOCK_SIZE;
     while (!feof(fin)) {
        if ((*(source + i) = fgetc(fin)) != EOF) {
                if (++i == block_length) {
                     i = 0;
                     reorder(block_length, rnum);
                     for (j = 0; j < block_length; j++)
                          *(destination + *(rnum + j)) = *(source + j);
                     for (j = 0; j < block_length; j++)
                          putc(*(destination + j), fout);
                }
          }
          else {
              reorder(i, rnum);
              for (j = 0; j < i; j++)
                *(destination + *(rnum + j)) = *(source + j);
              for (j = 0; j < i; j++)
                putc(*(destination + j), fout);
          }
     }
}
void reorder(int n, int *num)
{
     int i;
        rnums rand_struct[MAX];

     for (i = 0; i < n; i++) {
        rand_struct[i].num1 = rand();
          rand_struct[i].num2 = i;
     }
     qsort(rand_struct, n, sizeof(rnums), comp);
     for (i = 0; i < MAX; i++)
          *(num + i) = rand_struct[i].num2;

}
int comp(rnums *e1, rnums *e2)
{
     if ((e1->num1 - e2->num1)> 0)
          return 1;
     else if ((e1->num1 - e2->num1) < 0)
          return -1;
     else
          return 0;
}
FILE *open_file(char *name, char *type)
{
     FILE *fp;

     if ((fp = fopen(name, type)) == NULL) {
          fprintf(stdout, "\ncannot open %s\n", name);
          exit(1);
     }
     return fp;
}
void no_memory(void)
{
     puts("\nCannot allocate memory -- Aborting\n");
     exit(1);
}