PCMania 10/Pcmania_Ep2_10_CD-01.iso/ARTICULOS/tecnologia/DLOCK2.ZIP/THESIS.TXT

Text File | 1988-11-07 | 153.3 KB | 5,185 lines

BEYOND DES:

DATA COMPRESSION AND THE MPJ ENCRYPTION ALGORITHM

by

Michael Paul Johnson

B. S., University of Colorado at Boulder, 1980









A thesis submitted to the

Faculty of the Graduate School of the

University of Colorado in partial fulfillment

of the requirements for the degree of

Master of Science

Department of Electrical Engineering

1989

Copyright (C) 1989 Michael Paul Johnson.

All Rights Reserved.

This thesis for the Master of Science degree by

Michael Paul Johnson

has been approved for the

Department of

Electrical Engineering

by




Mark A. Wickert




Charles E. Fosha, Jr.




Rodger E. Ziemer



Date

Johnson, Michael Paul (M. S., Electrical Engineering)

Beyond DES:  Data Compression and the MPJ Encryption Algorithm


Thesis directed by Assistant Professor Mark A. Wickert

Many encryption algorithms have come and gone as cryptography, cryptanalysis,
and technology have progressed.  Today's communication and computer
technologies need cryptography to truly secure data in many applications.
The demands on the cryptography needed for some commercial applications
will exceed the security offered by the National Bureau of Standards
Data Encryption Standard (DES) in the near future due to advances
in technology, advances in cryptanalysis, and the increasing rewards
for breaking such a heavily used algorithm.  To meet part of this
need, a new block encryption algorithm is proposed.  A Pascal program
to implement this algorithm is given.

One way to further increase security of encrypted data, as well as
to achieve storage and/or transmission economy, is by redundancy reduction
prior to encryption.  A linguistic approach to redundancy reduction,
together with an example computer program to implement it, is given
for this purpose.

LIST OF FIGURES    viii

I.    INTRODUCTION    1

A.  Motivation    2

B.  Approach    4

II.    HISTORY OF CRYPTOGRAPHY    6

III.    ELEMENTS OF ENCRYPTION    8

A.  Substitution    8

1.  Monoalphabetic    8

2.  Polyalphabetic    10

B.  Permutation    11

C.  Noise Addition    12

D.  Feedback & Chaining    13

1.  Plain Text Feedback    13

2.  Cipher Text Feedback    14

E.  Analog Encryption    15

IV.    FACTORS RELATED TO ENCRYPTION    17

A.  Change of Language    17

B.  Digitization    18

C.  Compression    18

D.  Multiplexing    19

V.    COMPARISON OF SELECTED ALGORITHMS    20

A.  One-Time Key Tape    20

B.  Linear Shift Register Feedback    21

C.  Exponential Encryption    22

D.  Knapsack    24

E.  Rotor Machines    24

F.  Codes    27

G.  Galois Field and Hill Cryptosystems    28

H.  DES    30

VI.    DESIGN CONSIDERATIONS FOR MPJ    33

A.  Strength Based on Key    33

B.  Usability of Random Keys    33

C.  Key Length & Block Size    34

D.  Effort Required to Break    34

E.  Computational Efficiency    35

F.  Communication Channel Efficiency    36

G.  No Back Doors or Spare Keys    36

VII.    MPJ ENCRYPTION ALGORITHM    37

A.  Description    37

1.  Overall Structure of MPJ    37

2.  Substitution Boxes    39

3.  Wire Crossings    39

4.  Key Generation    40

B.  Implementation in Pascal    44

1.  Exceptions from Standard Pascal    44

2.  Main Program    45

3.  Procedures Encrypt & Decrypt    46

4.  Procedures Permute & Ipermute    47

5.  Procedures Substitute & Isubst    47

C.  Implementation in Hardware    47

D.  Strengths & Weaknesses    48

VIII.    DATA COMPRESSION    50

A.  Purpose    50

B.  Linguistic Parsing    53

C.  Huffman Coding    55

D.  Pascal Programs    55

IX.    CONCLUSION    58

REFERENCES    59

APPENDIX

A.    MPJ in Pascal    64

B.    Linguistic Data Compression Programs    72

FIGURE

III.B    Permutation.    11

III.C.    Noise Addition    12

III.D.    Block Cipher Modes.    14

III.E.    Analog Time & Frequency Encryption    15

V.A.    One-time key tape (AKA One-time pad)    21

V.A.1    Typex Rotor Machine    25

V.E.2.    Wired Rotors    25

V.H.1.    DES Enciphering    30

V.H.2.    DES Nonlinear Function    30

V.H.3.    DES Internal Key Generation    31

VII.A.1.    Overall Structure of MPJ    38

VII.A.3.    Wire Crossings    39

I.   INTRODUCTION

The increasing proliferation of digital communication and computer
data base storage has brought with it increasing difficulty of maintaining
the privacy of that data.  There is only one effective way to protect
the privacy of communications sent over such channels as satellites,
terrestrial microwave, and cellular telephones.  This is by encryption.  It
is clearly impossible to deny unauthorized access by a determined
and knowledgeable interceptor to the communications, but it is possible
to render the communications totally unintelligible to all but the
intended receiver(s).

There are many ways to reversibly transform data from its plain form
to something that looks unintelligible, but many of these can be figured
out (broken) by someone else.  The study of how to hide secrets is
cryptology. Trying to figure out the secrets that someone else has
hidden is cryptanalysis.  These two sciences are, of course, very
much intertwined. History reveals many examples of cryptology that
worked, and that didn't [KAH]. Successful cryptanalysis depends on
taking advantage of as many of the following as are available to the
cryptanalyst: (1) taking advantage of the redundancy in any natural
language to determine the validity of assumptions, (2) clues gained
from corresponding plain and cipher text, (3) information that might
be known about the algorithm(s) used, (4) the general expected content
of the cryptograms, (5) all of the cipher text that is available in
the same system & key, (6) compromised keys, (7) as much computational
and analytical power as can be obtained, and (8) mistakes made in
the users of the cryptographic system.  The cryptographer can make
life as difficult as possible for the cryptanalyst by depriving him
of some of these things by (1) using redundancy reduction before encryption,
(2) using an algorithm that is resistant to the known plain text attack,
(3) & (4) using a strong enough algorithm that these clues aren't
really useful, (5) changing keys often and selecting them properly,
(6) guarding keys as closely as the data they protect justifies, (7)
ensuring that there aren't enough computers in the world to do a brute
force attack on the algorithm, and (8) making sure users of the system
understand how to properly use it.

This thesis proposes one solution to the above challenge by proposing
(1) an approach to linguistically based redundancy reduction, and
(2) proposing a new data encryption algorithm (MPJ) that can be used
where DES is in use now, but is more secure.

A.  Motivation

There has been a great deal of discussion of the security of DES in
the open literature.  Most of it has been favorable to DES [MEY],
but there are a few indications that it would be wise to supplement
the aging DES and eventually replace it.

DES has been in use since 1977, and has been used in a large number
of applications where people have had many possible motivations for
trying to break this cipher.  During this time, it is possible that
someone has discovered a computationally feasible method for doing
so [KRU].  Under such circumstances, it is highly unlikely that such
a discovery would be made known.  There is no way to really know this
for sure, unless you are one of the ones who has broken DES.  The
closest thing that I have found to an open admission of breaking DES
is a story of the FBI successfully decrypting a file of drug transaction
records that were encrypted on a PC using a DES board. [MCL] The DES
board that the criminal used has an algorithm to generate a key from
a word or phrase.  By an exhaustive search of an English dictionary
and key names from the criminal's family & friends using a supercomputer,
the file was solved.  This indicates some weakness in DES, but even
more weakness in the way the key was chosen. The key was not chosen
randomly, so the FBI's job was much easier.

DES is subject to attacks that require precomputation that could tie
up a supercomputer for a few years, after which it would take only
a few days to solve a DES cryptogram.  This is becoming less of a
barrier as the price of computers drops and the speed and storage
capacity of computers increase.

The U. S. National Security Agency (NSA) is acting to release some  of  its
own algorithms for ``sensitive but unclassified'' applications, such
as communications between government contractors.  The NSA also releases
some classified algorithms to chip manufacturers for use in classified
devices, but under strict controls [ULT].  This will take some of
the load off of the DES algorithm, but there is a catch.  They intend
to keep the algorithms secret and control the keys.  Since the security
of the algorithm is dependent on the key in a way that only  the NSA  knows,
this gives the NSA the exclusive ability to read everybody's' communications.  That
is not all bad, as it discourages the use of one of those systems
by someone engaged in spying or other illegal activity.  Unfortunately,
these systems are not an option for protection of a corporations proprietary
data that may have a great deal to do  with profits and  losses, but
are not really in the domain of the NSA.

There are other alternatives to DES now, but none of them in the public
domain are even as good, let alone better, for general cryptography.  For
example, RSA encryption has great advantages in the authentication
of digital signatures, but the complications of selecting good keys
and the fact that the security of RSA relies heavily on the failure
of the state of the art in mathematics to progress makes it at least
inconvenient to use and at most insecure.

Because of the above considerations, it is my intentions to suggest
a better algorithm (MPJ) for general use in the private sector.  Although
the MPJ algorithm might be useful for government applications, too,
the design requirements for the two areas of application vary [CHA]
and the latter is kept shrouded in secrecy, so we shall leave it to
the NSA.

B.  Approach

First, the problem is defined.  As explained in the above section,
the basic problem is to create an algorithm to supplement DES.  Design
criteria are then conceived such that an algorithm that meets those
criteria will solve the problem as defined.  The design criteria chosen
for the MPJ algorithm are discussed in chapter VI.  To avoid repetition
of one or more of the many mistakes that have been made throughout
history with cryptography, it is, of course, necessary to research
what was done in the past, both distant and recent.  From this, many
good ideas can be gleaned that apply to the problem at hand.  These
ideas, along with a knowledge of current technology are then applied
to design criteria with a bit of creativity and a lot of hard work
to define the new algorithm.

In the process of doing all of the above, it became apparent that
the security of encrypted data was vastly improved by first removing
as much redundancy from the data as possible.  Therefore, as sort
of a bonus, a linguistic approach to data compression is also presented
that can either be used in conjunction with the MPJ encryption algorithm,
another encryption method, or just by itself for the savings that
it gains in communications channel capacity and/or data storage space.

II.       HISTORY OF CRYPTOGRAPHY

One of the best works on the history of cryptography is <MI>The Codebreakers,
by David Kahn [KAH].  In that book, David Kahn discusses cryptography
from the prehistory to World War II.  The first codes and ciphers
were in written form, and used to protect the privacy of communications
sent by courier or mail through hostile or unknown territory.  Some
of these were reasonably good, but most were not difficult to break
using manual methods, provided that the interceptor had sufficient
cipher text and perhaps some probable text.  The use of radio, especially
by the military, increased the need for cryptography, as well as increasing
the rewards for those who could break the encryption schemes in use.  Kahn's
documentation of the efforts of those who broke some very complex
encryption schemes, like the German Enigma and the Japanese Purple
ciphers, lend great insight to the kind of process cryptanalysis really
is.

Kahn points out the kinds of mistakes the inventors and users of cryptographic
algorithms tend to make that reduce the security of their communications.  For
example, German users of Enigma tended to choose a three-letter indicator
for their messages that consisted of three consecutive letters on
the keyboard.  This substantially reduced the number of keys that
had to be searched to determine the one that they were using.  While
the designer of an algorithm may calculate the great number of combinations
of keys that there are, the cryptanalyst looks at ways to isolate
parts of the key so that the difficulty of a solution is much less
than the size of the key space indicates.  The difference in mind
set between the concealer of secrets and the one who prys into them
has caused many an inventor of an encryption algorithm to be overconfident.

The job of the cryptanalyst is a tedious one.  He tries all kinds
of things to try to unscramble the cipher text in front of him.  Sometimes
the search is fruitless.  Sometimes the search yields something that
looks like a meaningful language.  It is this ability to recognize
a meaningful message when it comes out of the various operations that
the cryptanalyst tries that makes the whole process possible.  It
is also helpful for the cryptanalyst to know some probable plain text
that is contained in a message.  This is almost always the case.  For
example, military messages even now have a very stereotyped format,
with the from, to, and date indicators in the same places in the message.
The cryptanalyst almost always knows what language to expect a message
to be written in, and this is a great help.  Natural languages contain
a great deal of redundancy.  A message that is only 90% recovered
is usually readable.  Natural languages also have very consistent
statistical properties that are very useful in cryptanalysis, especially
when the cryptanalysis is automated.  The only time that these things
don't help the cryptanalyst is in the ``one-time pad.''

III.      ELEMENTS OF ENCRYPTION

Several basic elements make up the basis of a multitude of possible
encryption algorithms, either alone or in combination [BEK][BAL].  Although
most of these elements may be used to form the basis of an encryption
method all by itself, the most secure methods of encryption will several
of them.  For example, substitution and permutation are basic elements
of both DES and MPJ encryption algorithms.  These algorithms, in turn,
are best used with some form of feedback.

A.  Substitution

A substitution cipher simply substitutes one symbol from the plain
text alphabet for another one from a cipher text alphabet.  The plain
text alphabet can be a natural language alphabet, ASCII, EBCDIC, Baudot,
the set {0,1}, or any other finite set.  Cipher text alphabets, likewise,
may be any finite set.  To be able to easily apply computer methods
to the manipulation of these alphabets, it is preferable to use alphabets
that are groups of binary digits (bits).  This is not a severe limitation,
since a correspondence can be set up between any finite set and a
set of binary numbers.

1.  Monoalphabetic

A monoalphabetic substitution cipher is one in which each letter of
the plain text alphabet is always substituted for by the same cipher
text alphabet. The cipher text alphabet need not be in any particular
order.  A subset of the monoalphabetic substitution cipher is the
Caesar cipher.  This cipher replaces each letter with a letter that
is n letters later in the alphabet.  This cipher is so named because
it was reportedly first used by Caesar. [KAH]  With only 26 possible
keys, this is obviously not very secure.  In fact, any substitution
cipher that substitutes one letter for another is vulnerable to solution
by frequency analysis, and can be solved, given enough cipher text
with the same key.  How much cipher text is enough depends on the
nature of the plain text, but for plain English, as many characters
as there are letters in the alphabet is sufficient for the probabilities
of occurrences of letters to betray enough letter identities to make
solution probable.  While ciphers of this type no longer have any
value for serious cryptography, they do make fun puzzles for elementary
school children.  For example, the following cryptogram is presented
for your solution:

UIJT JT B DBFTBS TVCTUJUVUO DJQIFS/  XPVME ZPV USVTU VPVS TFDSFST
UP JU@

Substitution ciphers can be made more secure by operating on substitutions
of more than one letter at a time.  For example, the substitution
could be made on digraphs or trigraphs (groups of two or three letters).  A
more practical example is the Data Encryption Standard.  DES is actually
a substitution cipher with an effective alphabet size of 2^64,
or about 1.84 x 10^19, and the MPJ Encryption Algorithm is a
substitution cipher with an effective alphabet size of 2^128
or about 3.4 x 10^38.   Not only is it difficult to get that
large of a sample to analyze for statistics, but the memory required
to store the substitution table is impractical even for computer systems
using large optical storage disks.

2.  Polyalphabetic

A polyalphabetic substitution cipher is one in which each letter of
the plain text alphabet may be replaced a letter from one of many
cipher alphabets. The selection of which alphabet to take the substitution
from may be determined in many ways.  The most usual method is by
selecting the cipher alphabet by a combination of a message indicator
and the number of characters from the beginning of the message.  The
classic example of this type of cipher is the rotor-based machine.  The
substitution occurs by physical wire crossings within rotors.  After
each character is enciphered, one or more rotors are rotated by a
ratchet mechanism.  The message indicator, which is part of the key,
determines the starting position of the rotors.  This effectively
allows the use of more cipher alphabets than there are letters in
the message.  Because of this, the use of statistical analysis on
any one message to guess at the substitutions is useless.  There is,
however a good way to attack this kind of cipher when it is used heavily.
This is by analyzing the statistics of the first character in each
message, then the second, etc.  This is called analyzing the messages
``in depth.''

Although the rotor-based polyalphabetic ciphers used by Germany and
Japan in World War II contributed greatly to their losses because
their messages were read regularly by the allies, it is possible to
create a more secure polyalphabetic substitution with computer technology.
The primary weakness of the mechanical rotor machines was the infrequent
changing of many of the parts of the key such as rotor wiring and
ratchet construction.  A more general method of using a different
set of alphabets for each message would be very secure.  Unfortunately,
it would result in keys larger than the message.  Since the minimum
key length for absolute, provable cryptographic security, as determined
by C. E. Shannon [SHA], is exactly the length of the message, this
solution is not very efficient with respect to key management.

B.  Permutation

Permutation is taking the same symbols and writing them in a different
order to confuse an interceptor.  There are many ways of doing this
geometrically. For example, words may be written vertically then transcribed
horizontally, or they may be written on a strip of paper wrapped along
the length of a rod of a given diameter, then unwrapped for delivery.

In general, a permutation operation may be considered as an operation
on a block of symbols, where each symbol's position is changed to
another position within the block according to some rule.  The blocks
may overlap each other if the permutation is undone from the end of
the message to the beginning.

The rule(s) determining how the permutation is done may be fixed,
or they may depend in some way on a key.  Although historical permutation
ciphers tended to be rather simple, computer methods allow them to
be potentially rather complex, especially if the symbols that are
scrambled are individual bits.

Permutation, when used in combination with substitution, is very useful
in further increasing the complexity of a cipher, since the two algorithms
act in different ways to baffle the interceptor.  This is significant,
since it is not possible to actually increase the security of a substitution
cipher by simply repeating the same thing with a different key.  The
result in such a case would be another substitution cipher with the
same complexity.

C.  Noise Addition

Noise addition can either be a way of enhancing another encryption
scheme, or of hiding the very existence of a message.  For example,
a grid can be set up on a piece of paper where only certain positions
are significant.  These positions are then concatenated together to
reveal the secret message.  The rest of the paper is then filled with
something that uses those characters, but contains something different,
like a letter to someone's mother.  The same thing can be done electronically,
by defining a block of bits with only part of the bits significant.  The
rest of the bits are then filled with truly random noise, like the
output of a Geiger counter.  This method can be very effective, especially
if the position of the information-bearing bits vary from block to
block in a pseudorandom manner, and if there is a relatively large
proportion of truly random noise.  The obvious disadvantage to this
kind of scheme is that it makes very poor use of communications channels
and data storage facilities.

One useful variation on the noise addition method is to multiplex
several encrypted streams of data (encrypted with another method)
together with some pseudorandom interleaving.  Since the other encrypted
streams of data act like the random noise added to any one stream
of data, this is a good way to improve security when a large volume
of encrypted data must be sent through the same channel.

D.  Feedback & Chaining

A block cipher like DES or MPJ, when applied directly to an input
file with a highly repetitive structure (i. e., lots of spaces between
columns) will also display some of that structure.  Although it may
not be possible to determine the exact contents of what has been encrypted,
it may be rather easy to determine something about the nature of what
has been encrypted.  To deny the interceptor even this information,
and to further increase the complexity of the encrypted information,
feedback and chaining may be used.  Chaining refers to making the
results of the encryption of one block dependent on previous results.  This
is usually done in one of two ways.  One is by adding the plain text
from the last block to the cipher text of this block, modulo two.  The
other is by adding the cipher text from the preceding block to the
cipher text of the current block, modulo two.  These are referred
to as plain text feedback and cipher text feedback, respectively.

1.  Plain Text Feedback

Plain text feedback has the property that any errors in transmission
get propagated clear through the rest of the message.  This may be
a desirable property if it is necessary to detect any tampering with
the message, but it makes it difficult to use real (error-prone) channels.  If
it is necessary to have the property of error propagation to detect
tampering and to use real channels, then the message should be transmitted
using an error detection and correction protocol of some sort.

2.  Cipher Text Feedback

Cipher text feedback also causes some error propagation, but not clear
through to the end of a message.  An error in one block will cause
an error in that block in the bit positions where the error occurred
and in all of the next block, but the receiving station can recover
all subsequent error-free blocks.  This method is a good compromise
between security and error recovery.  It is still desirable to wrap
encrypted data in an error detection and correction protocol to avoid
having a one bit error wipe out many bits.

E.  Analog Encryption

There are several methods of analog encryption.  None of them are
as secure as digital methods can be.  Analog encryption is generally
based on spectrum inversion, spectrum scrambling, time slice scrambling,
and (for video signals) suppression of synchronization information.  These
elements are also used in combination [LOD].  These methods are commonly
used by cable TV companies (and sometimes on satellite channels) to
ensure that people only get the programming that they have paid for.  Articles
on how to build devices to defeat some of these things appear periodically
in electronic hobbyist magazines.

The state of the art in current use for protection of satellite TV
signals is the General Instruments Video Cipher II.  This device used
digital (DES) encryption of the audio information and a partially
analog encryption of the video signal.  This device is a deterrent
to those who receive satellite TV without paying a cable TV operator,
but it has been broken by a hacker who figured out that it was possible
to modify the microcode in the device so that a key purchased for
one machine would work on all of them with modified code.  This is,
of course, illegal, but it allows one person to pay for a service
and many people to use it for free [DOH].  The problem here is not
one of the encryption algorithm, but in the key management.

IV.       FACTORS RELATED TO ENCRYPTION

A.  Change of Language

Although it is not really encryption, the use of a different language
from what the interceptor is likely to know does increase the difficulty
of cryptanalysis.  For example, I know that it would be far more difficult
for me to solve even a simple Caesar substitution cipher in Chinese
than in English, Spanish, or German.  This principal was used effectively
by the United States against Japan in World War II by using the Navajo
language for spoken radio communications [KAH].  Since the Navajo
language had no written form, and was only spoken by a small group
of Native Americans, there were no Japanese who knew the language.  The
Japanese never did figure that ``code'' out.  Thus, the Navajo ``Code
Talkers'' made a great contribution to their country.

Part of the reason for the success of the Navajo Code Talkers was
that the Japanese had no idea what was going on.  Since this success
is now well known, it is difficult to determine the potential success
of a repeat of this kind of approach.  There are still some languages
that are spoken only by a very few people in the world, some of which
have no written form.  These could be used to increase the effective
``key space.''

Although a change of language was a great victory for the Navajo People
and the United States of America during World War II, it is difficult
to adapt this success to computerized communication methods.

B.  Digitization

The very act of digitizing an audio or video signal provides some
protection from the casual eavesdropper.  Although this provides no
protection against a determined snooper, it is an appropriate level
of additional security for protecting the privacy of things like mobile
telephone conversations.  Of course, once an analog signal is digitized,
there is a wide range of digital encryption methods available.  Of
course, some methods would be overkill, since the same communication
would probably be transmitted in the clear over wire and/or microwave
channels as well as by radio between the car and the stationary cellular
transceiver.

Although there has been some ill-conceived efforts by the mobile telephone
industry to legislate privacy for such applications by saying that
it is illegal to listen to someone else's phone calls around 800 MHz
(where cellular phones usually operate), this kind of thing is unenforceable.
Worse yet, such legislation provides a false sense of security in
a world where scanners and other receivers that operate in that range
are readily available.

C.  Compression

Data compression itself tends to obscure things by taking, for example,
and ASCII text file in English and reducing it to a binary file that
is not as easy to read.  There is a more important effect of data
compression, however. The removal of the natural redundancy of the
plain text data before encrypting it with some kind of encryption
algorithm makes it much more difficult to cryptanalyze the cipher
text.  In the extreme case where all of the redundancy of a message
is removed, all messages of a given length would be meaningful, and
it would be impossible for the cryptanalyst to determine which one
was intended.

D.  Multiplexing

Multiplexed signals are less readable to the casual observer, but
standard multiplexing offers no real increase in cryptographic strength.  It
can, however, increase the strength of multiple streams of encrypted
data when the multiplexing is done with a pseudorandom interleave
(as discussed above under noise addition).   This makes the multiplexing
and demultiplexing processes more complex with respect to synchronization
and timing, and is likely to introduce more delay into the system
than more straight forward multiplexing arrangements.

V.   COMPARISON OF SELECTED ALGORITHMS

A.  One-Time Key Tape

The one-time key tape, also called the one-time pad, has a tremendous
advantage.  It is the only commonly used encryption method that is
provably secure.  Proving the security of most other systems generally
reduces to an impossible negative proof <197> an attempt to prove
the lack of a method to defeat it.

The way the one-time key tape works is to add each character of the
message to a character of the key modulo the alphabet size.  When
working with any binary stream of data, this is easy to implement
by exclusive-oring the input stream with the key stream.  At the receiving
end, the same thing is done to decrypt the data.  Since P + K + K
= P (modulo 2), the original stream is recovered.

As implied by the name, it is important that each key be used only
once.  If it were used more than once, then the system would be vulnerable
to attack with the known cipher text and corresponding plain text
attack.  The key is obtained from the boolean identity:  K = (P +
K) + P, where K is the key, P is the plain text, P + K is the cipher
text, and all additions are modulo the alphabet size (usually 2).  The
key thus recovered would then be used to decipher the next message
that used it.

According to C. E. Shannon [SHA], for a cipher to be provably secure,
the number of keys must be as great as the number of potential messages.  The
number of keys he refers to, of course, is the number of keys that
yields a distinctly different transformation of the message text into
cipher text.

This method of encryption is provably secure, since an exhaustive
search of the keys applied to any cipher text of a given length will
yield all possible plain text messages of the same length.  Since
there are many messages of the same length that make sense, many of
which have totally contradictory or unrelated meanings, the cryptanalyst
has no way of knowing which one was intended unless he has the key.

Naturally, any method of encryption this secure has a price.  The
price is the sheer volume of keying material that must be kept secure
and managed.  For any communication network or data storage system
that handles large amounts of data, key management becomes a nightmare
with this system.

B.  Linear Shift Register Feedback

Linear shift registers with selected feedback taps are commonly used
to generate pseudorandom sequences for such things as spread spectrum
communications.  They could be (and are, in some cases) applied to
cryptography by exclusive-oring the pseudorandom stream with the plain
text stream.

The main weakness to this approach is the cipher text with corresponding
plain text attack.  If the cryptanalyst obtains the plain text that
came from a certain cipher text, then he can recreate a portion of
the pseudorandom stream by exclusive-oring the two together.  The
linear shift register feedback function can then be expressed as a
system of linear boolean equations that will solve the portion of
the cycle that was received.  A solution of this system of equations
is possible with only enough bits to be a few times as long as the
shift register at the most [DEN].  Since this amount of plain text
required to break the cipher is so much less than the length of the
pseudorandom sequence, it is likely that this solution can then be
applied to additional cipher text to recover it, too.

C.  Exponential Encryption

The classic algorithm of this type is the RSA algorithm, which is
named after the initials of its creators (R. L. Rivest, A. Shamir,
and L. Aldeman).  The security of this algorithm rests on the
fact that even with supercomputers, it is very difficult to factor
the product of two very large prime numbers.  The RSA algorithm has
a unique property in that the key has two parts, one of which may
be made public.  This makes this algorithm very well suited to the
use of digital signatures.

The RSA algorithm defines the relationships between the plain text
message, the cipher text, and the elements of the key as follows [JAC]:

C = P^e mod m

P = C^d mod m

m = pq
where C = Cipher text, P = Plain text, e = encryption key, d = private
decryption key, m = public modulus, and p and q are randomly chosen
large (> 150 digits each) prime numbers.  The receiver chooses a private
key d and calculates a public key e.  d must be relatively prime to
(p - 1) and (q - 1).  The algorithm works because ed = 1 mod
the least common multiple of (p - 1)(q - 1).  The algorithm
is only secure if very large prime numbers are used.  A number of
100 digits is too small - this size of number can be factored
now with a multiprocessor technique developed by Arjen K. Lenstra
of the University of Chicago and Mark Manasse of Digital Equipment
Corporation [COS].

The key generation for RSA is a bit nasty, but is reasonable using
Rabin's test for primality:  Let n = 2^rd+1, where d is odd.
Choose a at random from 1 < a < n - 1.  Accept n as prime if either
a^d = 1 mod n or a^2jd = -1 mod n for some j such that
0 <= j < r, otherwise reject it.

RSA is excellent for public key and authentication use, but it does
have certain disadvantages for general encryption use.  The processing
time required for key generation and for the encryption/decryption
process makes it a poor choice for use with high data rates, although
there are some reasonably efficient ways to do the exponentiation
[CHI].  The complexity of the algorithm makes it more difficult to
implement than many others [VAN].  The worst problem, though is the
way that the complexity of solving the algorithm could be reduced
by several orders of magnitude by mathematical research.  For example,
J. Sattler and C. P. Schnorr recently published some algorithms that
would appear to reduce the complexity of solving an RSA key by a factor
of about 10^4 [SAT].  Granted that we are talking about taking
9 x 10^8 years instead of 1.5 x 10^13 years, but it is
the potential for other discoveries that may drastically reduce this
time even further that is the real threat.

D.  Knapsack

A knapsack or trapdoor algorithm is one that is relatively easy to
perform, but which is very difficult to invert.  The RSA algorithm
is one such algorithm.  Another one, proposed by Ralph C. Merkle,
uses the following vector operation:  given an integer s and an integer
vector a = a1, a2, ..., an find a vector k
= x1, x2, ..., xn where xi is in {0,1}
such that s = x * a. (* denotes dot product.)  [MER]  This
algorithm is referred to in another paper as having been broken [VAN].  Another
algorithm using matrix operations is suggested by H. Retkin [RET].  This
algorithm may be good, but it is not obvious to me that no one will
come up with a good solution to breaking it, too.  Therefore, I prefer
to use encryption algorithms that have simple brute force solutions
that are well understood, but just take too long to perform to be
of concern.

E.  Rotor Machines

Rotor machines were once the state of the art in cryptography.  They
are a way to form a polyalphabetic solution automatically.  An excellent
history of these machines is contained in [KAH], [DEA], and [KOZ].  Although
they are obsolete now due to the superiority of many computer algorithms,
they played a major role in the history of cryptography.

There were many different variations on the rotor machine, but the
main principle of each of them was that the input, which is normally
a indicated by one of 27 (or whatever the alphabet size in use is)
wires is connected to a voltage level by a keyboard.  This wire is
then connected via rotary contacts to a rotor that physically permutes
the position of the wire.  This causes a simple substitution for each
character, or a poly alphabetic substitution. The output is taken
from rotary contacts on the other side of the rotor. Several of these
rotors are placed in series.  After each character is encrypted, one
or more of the rotors is moved to a new position by a ratchet mechanism.  The
net effect is a different simple substitution for each letter in the
message.  Common additions to this scheme are a plugboard style permutation
performed before or after the rotors and the addition of a reflecting
rotor to run the signal back through the rotors in the opposite direction,
using each rotor twice.

The key used is a combination of several things:  (1) the permutation
performed by each rotor (changed by rewiring it), (2) the order in
which the rotors were assembled, (3) the starting position of the
rotors, (4) the plugboard connections, (4) the number of rotors used,
and (5) the ratchet arrangement.  Taken all together, these form a
large key space.  If the entire key space is varied simultaneously
and for every message, then this polyalphabetic substitution is very
secure.  Due to the construction of these machines, some of the variables
were not as easy to change as others. Therefore in practical use,
the variables were not changed all at once.  For example, the number
of rotors and the ratchet arrangement would probably be fixed for
the life of the machine.  Therefore, if this portion of the key is
solved for once, that is enough until a new kind of machine replaces
it, perhaps years later.  The rotor wiring is tedious to change, and
therefore unlikely to be changed very often.  The order of the rotors
might be changed periodically, but during heavy use, the only thing
that was changed for each message is usually the starting position
of the rotors.

Using an alphabet size of 26 and five rotors, varying only the starting
position of the rotors provides a key space of less than 12 million,
which is within the range of possibility of solution by mechanical
computer, and a quick task for one of today's PCs.  With many messages
encrypted with the same rotors, the rotor wiring can be solved by
frequency analysis ``in depth.''  In other words, the permutation
applied to the first letter of each message can be solved by determining
the frequency of occurrence of each code letter and comparing that
with the language of the source language.  This can be done for each
position in the message.  From these substitutions, the rotor wiring
and plugboard connections may be reduced.  This is a more lengthy
process than solving for the rotor starting position, but once done
the solution is likely to be good for a while.  Using this kind of
approach, isolating the parts of the key, the Allies read many German
and Japanese messages during World War II.

Rotor machines can be simulated in a computer program with more flexibility
than in mechanical hardware, with many improvements.  There are, however,
better methods to use in computer algorithms that were not easy to
use in mechanical devices.  Therefore, rotor machines are interesting
to study for historical value, but they are obsolete at a time when
computers are becoming almost as common as televisions.

F.  Codes

Codes, as opposed to ciphers, operate on linguistic units like words,
phrases, and sentences, rather than directly on the units of the alphabet.  Codes
have the advantage that they generally compress the message.  For
example, the codeword ``APPLE'' might mean ``The supplies will be
shipped on Monday via private courier'' and ``GRAPE'' might mean ``The
bid is too high.  Reduce it by 10%.''  If there are only a few different
messages that might be encoded, a substantial savings in space can
be realized.

Codes are useful for compression of information, even when no encryption
is intended.  For example, the Uniform Commercial Code, used for telegraphy
saves on tolls, even though it is published and gives no real security.  Another
example is the use of Q signals on amateur radio, where encryption
is illegal but brevity is important, especially when using a slower
mode of communication like Morse Code.  There QST means ``The following
is a message of interest to all Amateurs'' and QSL means ``My location
is _____.''

When used to hide the meaning of the message, the code must be changed
often. This is much more difficult to do than to change the key to
an encryption algorithm.  Therefore, this technique has limited value
except for some diplomatic and military codes.  For commercial applications
where brevity and security are both required, it is easier to first
encode the plain text with a fixed code to reduce its size, then to
encrypt the encoded text with an encryption algorithm whose key can
be easily changed.  This technique is more secure than the use of
the encryption algorithm alone, even if the code used is widely known.  See
chapter VIII for more on the effects of data compression when used
with encryption.

G.  Galois Field and Hill Cryptosystems

A Galois Field cryptosystem is one in which the letters of the encryption
alphabet are assigned arbitrarily to the integers from 0 to p^n,
where p is prime and n is an integer.  These integers are then operated
on in blocks of m letters by matrix multiplication with a matrix that
represents monic irreducible polynomials of order m - 1.  All operations
are done modulo p^n.  To decrypt the data, the ciphertext is
multiplied in the same manner by the inverse of the encryption matrix
(obtained using the same modulo arithmetic).  The resulting numbers
are then substituted back for the letters they represent.

The Hill cryptosystem is similar, except that n is fixed at one, and
that p need not be absolutely prime as long as several integers less
than p are relatively prime to it.  For more details on how these
cryptosystems work, see the articles by Hill, Cooper, and Patti [HIL]
[HLL] [COO] [PAT].

Both of these systems are based on linear algebra over a limited field
of integers.  Therefore, they are subject to solution of the key in
use by linear algebra if enough cipher text and corresponding plain
text is available.  If the permutation of the encryption alphabet
in use is known, then the amount of corresponding plain and cipher
text needed for a solution is merely the key length.  If the permutation
of the encryption alphabet in use is not known then there must be
a sufficient quantity to also perform statistical analysis attacks
on the alphabet in use.  Therefore, I do not recommend the use of
these systems for serious encryption because of these vulnerabilities.  Not
only are they less secure than their key length (the combined length
of the coefficients of their matrices) would indicate, they are computationally
less efficient than DES and MPJ.  Key generation for these systems
becomes increasingly complex as the size of the key grows, too, because
the probability of coming up with a valid set of monic irreducible
polynomials that form an invertible matrix decreases rapidly with
matrix size.

These cryptosystems, do, however, provide interesting mathematical
illustrations on what can be done with Galois Fields.  They also provide
adequate security for cases where the information being secured is
not of great commercial value, and is therefore unlikely to be cryptanalyzed.

H.  DES

The National Bureau of Standards (now known as NITS) Data Encryption
Standard (DES) was published in the Federal Information Processing
Standards Publication Number 46, dated January 15, 1977 (FIPS PUB
46) [DES].  For details, please refer to that publication.  A summary
of the algorithm follows.

Encryption consists of an initial permutation, sixteen rounds of encryption,
then an inverse of the initial permutation.  Each of the sixteen rounds
of encryption consist of taking the right half of the input block
(32 of the 64 bits) and running it through a nonlinear function of
the 32 bits and an internal key, then adding this result to the left
half of the input modulo two.  This 32 bit answer becomes the next
round's right half block.  The next round's left half becomes the
right half block without modification.  The nonlinear function used
consists of a bit selection E that selects 48 bits from the input
of 32 (several of the bits are repeated).  These 48 bits are added
modulo 2 to the round key of 48 bits.  The result of that operation
are then fed six bits each into eight substitution boxes.  Each of
the eight substitution boxes are different, but the same set of eight
boxes are used for each round.  Each substitution box gives an output
of 4 bits.  The output of these boxes are fed into a permutation P
that rearranges the output in a fixed manner.

The sixteen internal keys are generated from the 56 bit input key
by feeding the input key into a fixed permutation that rearranges
the order of the key bits.  The key is then split into left and right
halves called C and D.  Each half is shifted left one or two times
(according to a fixed table) before generating each internal key.  Each
of the sixteen internal keys is generated by taking the two halves
of the key as shifted and permuting them in a fixed manner.

The key and the resulting internal keys are the only things that vary
in this algorithm.  The initial and final permutations and the contents
of each of the substitution boxes are constant.  The two permutations
used in generating the internal keys are constant.  The bit selection
and permutation used within the nonlinear function are constant.

The strengths of the DES is that its cryptographic strength depends
only on the key, that the algorithm is easy to implement in a single
IC, that it has been well tested an no one has publicly announced
a solution, that hardware and software that uses it is readily available,
and that the algorithm places very few restrictions on key generation
so that random numbers may be generated by the users for use as keys.

The weaknesses of the DES are that the key is too short for security
in the face of anticipated increases of computing power, that it is
old enough that it is likely that someone has broken it (found a short-cut
solution), that hardware implementations of the DES are too slow for
some applications, and that it limits itself to be simpler than is
really necessary with current technology.

VI.  DESIGN CONSIDERATIONS FOR MPJ

The following paragraphs describe the design considerations that I
used in creating the MPJ Encryption Algorithm, and the reasons for
each.

A.  Strength Based on Key

The strength of the system must rely on the security of the key only.  It
cannot depend on the algorithm being kept secret, because the algorithm
will be published.  Even if the algorithm were not published, it would
probably be reverse engineered from software implementations of the
algorithm.  The algorithm must be constructed in such a way that there
is no computationally feasible way to derive the key from samples
of corresponding plain text and cipher text.

B.  Usability of Random Keys

The key selection should be as easy as the random selection of a number
in a given range.  Selecting a very secure key should be no more difficult
than flipping a coin once for each bit of the key, or generating keys
using a pseudorandom sequence combined with random events such as
timing of keystrokes on a computer.  A one bit change in the key should
provide a drastically different transformation, so that a potential
cryptanalyst has no idea when a key that he guesses might be ``close''
to the right one.

C.  Key Length & Block Size

The key length should be significantly longer than the DES 56 bit
size.  A key size of 128 bits (sixteen 8-bit bytes) was chosen as
being very manageable, yet highly secure even when attacked by multiple
array supercomputers.  The block size was also chosen as 128 bits
(twice the size of DES) to provide a significant increase in complexity
of the encryption.

D.  Effort Required to Break

The effort required to break the algorithm by any method should be
so great as to make such a task unfeasible even if significant advances
are made in computer technology.

This requirement is intimately linked to the choice for key size and
block size.  For example, if one thousand keys could be tried every
nanosecond (10^12 attempts per second), an exhaustive key search
that resulted in success after only testing one millionth of the possible
keys (extremely good luck) would take 2^128/((10^12)(10^6))
= 3.4 x 10^20 seconds = 1 x 10^13 years.  If someone figured
out a computational method or weakness in the algorithm that reduced
the complexity by a factor of a million, and that someone also figured
out how to compute the solution a thousand times faster, and they
still believed in one in a million chances at good luck, they could
possibly come up with a solution in only 10,000 years. By way of contrast,
testing keys at the rate of 10^12 per second for DES with its
56 bit key, all of the keys can be tested in 7.2 x 10^4 seconds,
or about 20 hours.  While trying a trillion keys a second is not realistic
with current general purpose computers, current technology could be
applied to dedicated, highly parallel encryption/decryption engines
that could approach that speed - at a cost that would be prohibitive
for all but large governments at today's prices.

Other than time, the other main measure of complexity of an algorithm
is the storage capacity required to implement a lookup table attack.  Suppose
a lookup table were to be constructed that contained the encrypted
version of just one block of cipher text corresponding to a very common
block of plain text (such as 16 ASCII spaces) for every key possible.  For
the MPJ algorithm, this would take 2^128 x 128 = 4.356 x 10^40
bits.  If this memory were constructed with some kind of device that
could store one bit per atom of silicon, this would take 4.356 x 10^40
bits x 28.086 amu/atom x 1.660531 x 10^-24 grams/amu x 10^-6
metric tons/gram = 2.03 x 10^12 metric tons of silicon.  That
is about one thousandth of the mass of Deimos, the smaller of Mars'
two moons.  [CRC]  For DES, the same table would only require about
215 micrograms of silicon.  Nobody has come up with memory that dense,
and fundamental physical limits make such a task difficult, indeed.  It
is not difficult to conceive of some breakthroughs in optical storage
technology coming close, say using a thousand molecules of something
per bit. Under those circumstances, DES would be vulnerable to such
an attack, where MPJ would still be safe.

E.  Computational Efficiency

The MPJ encryption algorithm must be computationally efficient enough
to be implemented in software on a standard IBM PC or compatible (or
on an Apple computer of comparable power), and fast enough to handle
at least 10 megabits per second when implemented in dedicated hardware.  Note
that this is less restrictive with respect to the hardware for DES,
which was required to be simple enough to implement on a single chip
using 1970s technology.

F.  Communication Channel Efficiency

The MPJ encryption algorithm must not significantly increase the size
of the plain text when encrypting it.  This precludes the use of noise
addition as a technique to be used.

G.  No Back Doors or Spare Keys

While it may be impossible to guarantee that no ``back doors'' or  ways
to decipher a message without the key exist, the algorithm should  be
sufficiently complex combination of simple, well-understood operations  that
no help is offered to the cryptanalyst from the structure of  the
algorithm. Spare keys (the situation where more than one unique  key
will decipher a message) are avoided by making the number of keys  possible
much less than the number of possible transformations that can be
done  on a set of blocks.  This is true for MPJ because 2^128
<< 2^128!.

VII.      MPJ ENCRYPTION ALGORITHM

A.  Description

The MPJ Encryption Algorithm can be looked at from the outside like
a rather large electronic codebook that operates on 128 bit blocks.  The
algorithm may be used in several modes.  It can be used directly in
electronic codebook mode, in block chaining with ciphertext feedback
mode, in block chaining with plain text feedback mode, and in stream
cipher generation mode.

Given a 128 bit key, instructions to encrypt or decrypt, and a 128
bit input block, a unique 128 bit output block comes out. Encryption
and decryption are inverse operations that can be done in either order.  For
example, if P is the plain text block, C is the cipher text block,
EK1 is encryption with key 1, and DK1 is decryption
with key 1, then C = EK1(P); P = DK1(P).  A different
cipher text results if the plain text is decrypted first, but DK1(EK1(P))
= P = EK1(DK1(P)).  Multiple encryption can be done
with several keys, as in these examples with three:

C = EK1(EK2(EK3(P))); P = DK1(DK2(DK3(C)))
or a different method:

C1 = EK1(DK2(EK3(P))); P = DK1(EK2(DK3(C)))

1.  Overall Structure of MPJ

Before encryption or decryption occurs, the substitution boxes are
filled based on the input key.

To encrypt a 128 bit input block, it is run sequentially through ten
rounds of substitution.  Each round of substitution operates on the
16 eight-bit bytes that make up the input block individually.  In
between each round of substitution is a round of permutation, for
a total of 9 rounds of permutation.  The permutation operation is
identical each time.  Each operation (substitution and permutation)
has an inverse operation.  Decryption is done by running the inverse
operation of each of the above steps in the opposite order.

After one round of permutation, each bit in the output block depends
on every bit in the byte that it is in and on eight bits of the key.  After
a round of permutation and the second round of substitution, each
bit in the block depends on eight bytes of the input block and on
eight bytes in the key.  After the third round of substitution, each
bit in the block is functionally dependent on 15 of the input bytes
and on 15 bytes of the key.  After the fourth round of substitution,
each bit in the block is functionally dependent on every bit of the
input block and on each bit of the key.  After the tenth round of
substitution the functional dependence on every bit of the key and
the input block is so complex that it would be infeasable to determine
the key used, even if the cryptanalyst has known corresponding plain
and cipher text and knows the algorithm used.  Because the substitution
boxes are totally nonlinear functions, the problem of finding each
of the 40,960 internal key bits is a tough one, indeed.  It would
be easier to find the original key of only 128 bits by brute force
- something that is difficult, indeed.

2.  Substitution Boxes

The substitution boxes are designed to be big enough to provide a
large number of possible arrangements, but small enough to still fit
comfortably within the memory of an MS-DOS computer.  Each substitution
box is therefore a collection of 16 substitution boxes that operate
on only 8 bits at a time, with a total of 256 entries.  The substitution
boxes may be an array or look-up table in a computer, or they may
be implemented in hardware using RAM.

The substitution boxes are filled during the internal key generation
process with a permutation of numbers that depends on the main key
in a different way for each substitution box.

3.  Wire Crossings

The wire crossings serve to extend the functional dependence of the
output block on the input block across the internal byte boundaries.  This
is done by making each byte of the output of the permutation to contain
one bit from each of eight different bytes.  The selection of bits
was chosen to make a computer implementation fairly efficient.  A
pure hardware implementation of this operation is, of course, much
faster, since it involves only the propagation delay of the signal
from one end of a short wire to the other.  The input block bit positions
are numbered from left to right (MSB to LSB) as 127 down to 0, then
the new positions those bits occupy after the wire crossing are (MSB
to LSB):

55, 46, 37, 28, 19, 10, 1, 120, 111, 102, 93, 84, 75, 66, 57, 48,
39, 30, 21, 12, 3, 122, 113,  104, 95, 86, 77, 68, 59, 50, 41, 32,
23, 14, 5, 124, 115, 106, 97,  88, 79, 70, 61, 52, 43, 34, 25, 16,
7, 126, 117, 108, 99, 90, 81, 72, 63, 54, 45, 36, 27, 18, 9, 0

4.  Key Generation

Internal key generation in the MPJ encryption algorithm consists of
filling all of the substitution boxes (arrays in software or RAM in
hardware).  There are 16 substitution boxes used for each of 10 rounds.  Each
substitution box contains 256 entries of 8 bits each.  Therefore,
the actual internal keys have a combined length of 16 x 10 x 256 x
8 = 327,680 bits.  These are obtained by manipulation of the 128 input
key bits.  Note that trying to attack the MPJ encryption algorithm
by brute force trial and error using internal keys instead of using
the 128 input key bits is ridiculous.  The calculations given above
indicate how difficult even a 128 bit random key is to solve by brute
force.  The only way that an attack on internal keys is useful is
if there are parts of the internal keys that can be solved for separately,
without having to solve for as many as 128 bits at once.

Attacks against the internal key structure are made computationally
intractable in three ways.  First, the smallest chunk of the internal
key that could be meaningfully solved for is the contents of one of
the substitution boxes.  Each of these contain 256 bytes, or 16 times
the length of the input key. Remember that the addition of each bit
doubles the complexity of the solution, so this is not attractive
compared to solving for the input key.  The second impediment to this
attack is to make the relationship between the contents of the substitution
boxes and the input key quite nonlinear.  The way this is done is
by using a combination of rotating bit selection and the use of the
last substitution box filled to compute the contents of the next one.  The
third line of defense against the solution of internal keys is the
use of ten nonlinear rounds of encryption to make any attempt at constructing
a system of linear equations to solve for the internal key given known
plain text and corresponding cipher text infeasable.  Note that each
round of encryption in MPJ causes the whole 128 bit block to be changed,
where each of the rounds in DES only modifies half of its 64 bit block.  Therefore
the internal structure of MPJ is very difficult to solve for, with
each bit of the output having a nonlinear functional dependence on
every bit of the input and on the contents of 1 + 8 + 15 + (7 x 16)
= 136 of the substitution boxes, containing a total of 34,816 bits.  If
the substitution boxes were linear, this solution would be possible,
but there is no method I know of to solve such a system of nonlinear
equations, either here or the simpler case of the DES internal structure.

To find the inverse of the substitution box functions, separate inverse
substitution boxes are formed that place each address of a substitution
box at the address of the data contained in the substitution box.  For
example, if the contents of the first substitution box in the first
round of encryption for the input value of 1 is 219, then the contents
of the first inverse substitution box in the last round of decryption
for the input of 219 will be 1.  In equations, SI[i, j, S[i, j, k]]
= k for all i, j, k, where the first index of the array is the round
of encryption, numbered from 0 to 9, or the round of decryption, numbered
from 9 to 0 (defined differently for programming convenience); the
second index is the position of the 8 bits that the substitution applies
to in the input block, numbered from 0 to 15, left to right; and the
third index is the value of the 8 bits input to the block.

The actual algorithm for substitution box filling consists of three
main parts.  The first one is a nested loop to fill one substitution
box, permute the key with the same permutation used for the encryption
operation, then to run each byte of the key through the substitution
box that was just filled. This is done for each round of encryption,
from 0 to 9, with each substitution box used in one round of encryption,
from left to right, done within each of these rounds.  In other words,
the index of the three dimensional array that selects the position
of the substitution box within each array varies faster than the index
that selects the number of the round of encryption that the box uses.

The second algorithm is the one that fills each substitution box based
on the contents of the input key, as modified by the previous steps.  This
algorithm uses bit selection and rotation to determine where each
value of the output of the substitution box goes.  To be an invertable
function, each of the possible output values from 0 to 255 must appear
exactly once somewhere within the array with 256 possible slots, numbered
from 0 to 255.  The first number placed in the array is 255, and there
are 256 possible places to put it.  The second one is 254, with 255
places to put it.  This is continued until the last value, 0 is placed
in the one remaining slot.  For the first half of the values, the
formula pos = (n * m) div 255 is used to determine which of the unfilled
slots (counting in index order from 0 to n) is to be used to contain
n.  The variable pos is the position (counting only unfilled slots),
* denotes multiplication, and div is the integer division operator
(remainders are ignored).  The variable m is determined for the first
value of n (255) by selecting one bit from each byte of the key, starting
with the least significant bit from the least significant byte of
the key.  The next bit (place value of 2) is selected from the next
most significant bit of the key, and so on until m has eight bits.  For
the next value of n (254), the same thing is done, except that the
bit selected is one bit position to the left of the one selected last
time.  The place value of the bit selected is the same in m as it
is in the byte it came from.  The bit to the left of the MSB in a
byte is the LSB of the byte to the left of it.  The byte to the left
of the most significant byte is the least significant byte.  For the
values of n from 127 to 0, then the same thing is done, except that
only seven bits are selected for m, and the position is determined
from pos = (n * m) div 127. For a more concise explanation of this
process, see the commented pascal procedure makesbox in the program
in appendix A.

The third algorithm used in internal key generation is the generation
of inverse substitution boxes.  This is done with a simple nested
loop that fills the inverse substitution boxes according to the formula
si[i, j, s[i, j, k]] for i from 0 to 9, j from 0 to 15, and k from
0 to 255.  The array si is the collection of inverse substitution
boxes, and the array s is the collection of substitution boxes filled
by the above two algorithms.  Filling of inverse substitution boxes
is only needed for decryption mode.

B.  Implementation in Pascal

Pascal source code for a program to implement the MPJ Encryption Algorithm
is given in Appendix A.

1.  Exceptions from Standard Pascal

This program was written for MS-DOS computers and compiled using Borland
Turbo Pascal 5.0.  To adapt this program for use on another system,
note that the following features of Turbo Pascal that do not conform
to the ANSI/IEEE770X3.97-1983 Standard Pascal were used in this program:

(i)  The assign procedure is used to associate an operating system
file name with a Pascal file name.

(ii)  The nonstandard file handling procedures blockread, blockwrite,
close, and seek, were used.  The nonstandard function filepos was
used.

(iii)  The type longint (a 32 bit integer) was used for input handling
to allow range checking without invoking a system error for a number
that was only slightly out of range.  A 16 bit integer could be used
instead.

(iv)  A generic file type was used, which is not defined in ANSI Pascal.

(v)  The nonstandard operators shl and xor were used.  The shl could
be replaced with integer division by 2 (div 2), and the xor could
be replaced by expressions of the form ((A and (not B)) or ((not A)
and B)).

(vi)  Logical operators (and, or, not, xor) were used with integers
to perform bit-wise operations.

(vii)  The + operator was used to concatenate strings.

(viii)  The uses clause links in separately compiled units.

(ix)  The include comment {$I filename} includes additional source
code to be compiled with the current file.

(v)  Additional nonstandard features were used in writing startup  and
the file handling functions that are unique to MS-DOS.  These functions
would best be rewritten for a different target system.

2.  Main Program

The main program calls startup to initialize variables, get the key
from the user, and determine which files are to be encrypted or decrypted.
It then calls makesbox to generate the internal keys (fill the substitution
boxes). If the decryption mode is to be used, it calls makesi to fill
the inverse substitution boxes.  It then does the actual encryption
or decryption.

The main program allows for the encryption of multiple files (specified
using MS-DOS wildcards), and passes these files to the encryption
routine one block at a time.  To provide additional security, files
are encrypted in place, with each block of output overwriting the
corresponding input block in the same place on the disk.  If it is
desired to keep a copy of both encrypted and plain text versions of
the file, the input file should be copied before running this program.

Because this program uses block chaining with ciphertext feedback,
only the encryption mode of the MPJ algorithm is used, the source
of the feedback (input or output) being determined by the decryption
boolean variable.  This mode is used because (1) it obscures repetitive
patterns in the source file that the electronic codebook mode might
not hide, (2) it accommodates files of any number of bytes (including
a short block at the end) with no complications and results in an
output file that is the same length as the input file, and (3) it
is slightly faster in operation because the procedure makesi does
not have to be called.  This mode does require an initialization vector,
but since the initialization vector is encrypted before use, a constant
initialization vector may be used.

To use the electronic codebook mode, delete the for statement following
the calls to encrypt, replace one call to encrypt with a call to decrypt,
and remove the comment delimiters from around the call to makesi.

3.  Procedures Encrypt & Decrypt

These procedures directly reflect the overall structure of MPJ.  The
are simply calls to the routines that perform the substitutions and
permutations, calling them in the proper order and passing a parameter
to the substitution routines that select the right set of substitution
(or inverse substitution) boxes for the operation being done.  The
procedure encrypt makes 10 calls to substitute, with 9 calls to permute
(one call to permute between each pair of calls to substitute.  The
procedure decrypt makes 10 calls to isubst, with 9 calls to ipermute,
done in the inverse order of encryption.

4.  Procedures Permute & Ipermute

Permute just scrambles the order of the bits in the 128 bit block
in such a way as to maximize the dependence of each byte on every
other byte of the input.  Each byte is formed by selecting the least
significant bit from the least significant bit of the corresponding
input byte, then the next most significant bit from the next byte
to the left, and so on.  The least significant byte is considered
to be to the left of the most significant byte. Ipermute is just the
inverse of this permutation, with bytes being selected to the right
instead of the left.

5.  Procedures Substitute & Isubst

These procedures are simple array lookups in which each byte of the
input block is used as the third index of the array s for the procedure
substitute or si for the procedure isubst.  The output is the contents
of the array.  The first index is the round of encryption or decryption
(counting backwards if it is decryption), and the second index of
the array is the byte position (0 to 15) within the input and output
blocks.

C.  Implementation in Hardware

For use with high data rates (greater than 10 Megabits per second),
it is desirable to implement the MPJ algorithm directly in hardware.
This also provides the advantage of greater security against tampering
than a program on a general purpose computer might be subject to.

The hardware implementation consists of six basic elements:  (1) Key
generation, (2) serial to parallel conversion, (3) substitution, (4)
wire crossings, (5) parallel to serial conversion, and (6) timing
control.  The key generation is done by a program running in a microprocessor.  This
program takes the key as input and fills the substitution boxes, which
are simply static RAM chips. Serial to parallel conversion and parallel
to serial conversion is done with shift registers.  The wire crossings
are done with physical wire crossings (or printed circuit board trace
crossings) - a technique that is hard to beat for speed.  Timing
control is done with a sequential circuit that is synchronized to
the incoming data stream.

The output data stream will, of necessity, be delayed by at least
the block size of 128 bits, and some kind of protocol must be used
to synchronize the blocks at the sending and receiving ends.

The following diagram shows a block diagram of a hardware implementation
of the MPJ Encryption Algorithm.  There are, of course, many variations
possible.  For example, block chaining could be used with hardware
exclusive-or gates to do the modulo 2 addition and flip-flops for
unit delays.

D.  Strengths & Weaknesses

The main strengths of the MPJ encryption algorithm are:

It is much more secure than DES.

When used in conjunction with data compression, MPJ is probably
more secure than many of the best military and diplomatic codes &
ciphers.

It is easy to generate a key for MPJ.

It is capable of high data rates when implemented in hardware.

It will run on a personal computer.

It takes more time to generate internal keys from an external
key than to actually encrypt or decrypt data, making exhaustive key
search attack more difficult than normal use.

The algorithm is published and may be freely used for any
legal purpose.

There has not been a lot of time for anyone to search for
a short-cut solution to MPJ, nor the volume of sensitive material
to motivate such a search as DES has had.

The main weaknesses of the MPJ encryption algorithm are:

The key and block sizes are fixed (optimized for the memory
and processing power of the IBM PC), so it doesn't take very good
advantage of more powerful computers other than running faster.

The software implementation isn't very fast.

There is no way to prove that there is no short-cut solution
to MPJ (or DES, or almost any encryption algorithm except for the
one-time key tape).

Since the MPJ encryption algorithm is my own invention,
I could possibly be blind to some weakness that it might contain.

VIII.     DATA COMPRESSION

A.  Purpose

Data compression has two obvious purposes:  to save on communication
channel capacity required to send a message and to save on media capacity
required to store a message.  The third purpose for data compression,
pointed out by C. E. Shannon, is to make decryption of a message more
difficult [SHA].  In reading through the history of cryptanalysis,
it became very obvious to me that the one thing that all cryptanalysis
relies on the most is the presence of a great deal of redundancy present
in natural languages.  This is especially true for messages that the
cryptanalyst already has something of an idea of what the message
is about.  It is this redundancy that enables the cryptanalyst to
tell which of several possible solutions is the right one - the
one that ``makes sense.''  For example, if the message is between
English-speaking parties, then the of the possible messages ``ACCEPT
THE PROPOSAL,'' ``A;LSDI FUPE ZAARED,'' and ``XXDKFJ DDDLKJDJFFZA,''
the first message is instantly recognized as the only one that makes
sense.  The reason that this is so obvious is because of the redundancy
of natural languages.  If all of the redundancy of a message is removed,
then there is no criteria to select one possible answer over another,
and the cryptanalyst is left baffled.

The task at hand is to try to eliminate or at least reduce the amount
of redundancy in a message before encryption, then restore the message
to its original meaning after decryption.  If all of the redundancy
of a message is removed, it means that all possible messages that
can be constructed from an alphabet have meaning, and that the length
of a message is inversely proportional to its probability.  This ideal
can probably be achieved only for special circumstances with very
limited messages.  For use with general correspondence in a natural
language, however, it is not practical to totally remove the redundancy
from all messages.  In fact, it is very difficult to even measure
redundancy or entropy in a natural language.  The concepts of redundancy
and entropy (as defined in communication theory texts) are useful
for comparisons of various methods of redundancy reduction.

Most existing methods of redundancy reduction use either a manually
constructed code like the amateur radio operator's Q-signals or an
automatic method that operates on either the alphabet or some groupings
of alphabet symbols, like trigraphs.  Manual techniques are fine for
their intended application, but automatic methods that are well-suited
for computer implementation are better for use with encryption.  Automatic
methods are likely to achieve good results with much greater ease
of use and less opportunities for errors.

The probability of occurrence of various letters in most natural languages
are fairly constant over a wide range of types of text, and have been
studied and published many times.  These probabilities for English
letters are published in several of the texts on cryptography listed
in the references section of this thesis.  Probabilities of digraphs
(groups of two letters) and trigraphs (groups of three letters) have
likewise been studied, and are fairly constant for a given language.  Just
changing the representation of trigraphs to variable length codes
that are shorter for more common trigraphs and longer for less common
trigraphs results in a substantial savings in length of an English
message.

There are many such methods for compressing data that are fairly straight
forward.  This and other methods, many of which are discussed by James
Storer in his book on data compression [STO].  There are also several
public domain and share-ware programs that are available on many bulletin
boards that perform data compression.  My favorite is PKARC, written
by Phil Katz.  It dynamically analyzes each input file to determine
which one of five compression methods or storing with no compression
results in the smallest file.  The compression methods used by PKARC
are repetition coding, Huffman encoding, Ziv-Lempel-Welch compression,
and two different variations on Dynamic Ziv-Lempel-Welch compression
[KAT].  PKARC also has an option that allows a rather crude encryption
of the archive files with a password. Although this doesn't provide
strong cryptographic security, it does help to obscure the redundancy
that PKARC adds back in, in the form of cyclic redundancy checks on
files and file headers.  The CRC checks and file headers would be
a good point of vulnerability when trying to cryptanalyze an archived
(compressed) file.

My feeling was that it was possible to compress natural language text
even more than was commonly being done by using linguistic parsing
of the text to form a dictionary.  I was partially right.  My method
does remove more redundancy and make most text files smaller and more
secure.  It won't win any speed contests with PKARC, however, which
I recommend that you use if speed is of great importance or if you
are going to compress binary files (such as executable programs).

In comparing the performance of SQUEEZE with PKARC, I compressed a
4,316,030 byte ASCII text file (the King James Version of the Holy
Bible) to 1,312,493 bytes with a language code file of 163,236 bytes.  PKARC
compressed the same file to 1,779,184 bytes.  This is a removal of
69.6% of the redundancy for SQUEEZE (or 65.8% if you add the size
of the language code file), compared with a redundancy reduction of
only 58.8% for PKARC.  This may not seem like much of a difference,
but the smaller compressed file fits on a 1.44 Megabyte 3 1/2 inch
floppy disk, and the other one doesn't.  This would be more of a significant
achievement if SQUEEZE weren't so slow.  It took well over two hours
to do this running on one of the fastest PC's available (25 MHz 80386),
while PKARC worked for about a minute on the task.  I believe that
both the speed and amount of redundancy reduction can be improved
upon.  I am therefore publishing the source code for what I did in
Appendix B, so that someone else may be able to build upon this idea.

B.  Linguistic Parsing

Instead of developing a Huffman code based on trigraphs or other such
arbitrary chunks of fixed length, why not develop a Huffman code based
on the way people read words?  Letter combinations made from statistically
properly distributed trigraphs will probably contain a lot of valid
English words, but they will contain a lot of garbage, too.  If, however,
all symbols correspond to English words (or punctuation), then a collection
of random symbols will look a lot more like English.  Of course, the
arrangement of words will probably not make sense in either group,
but an intuitive analysis indicates that a code based on linguistic
parsing of words will contain a lot less redundancy than will a fixed-length
code.

To define linguistic symbols, I called any grouping of alphabetic
symbols unbroken by non-alphabetic symbols a word symbol.  I called
any group of contiguous spaces a space symbol.  I called a carriage
return + line feed combination a new line symbol.  Any other punctuation
and numbers were called symbols themselves.  There may be more efficient
ways to split up text into symbols, since, for example, words are
almost always followed by a space.  I also counted upper and lower
case words different symbols.  It may have been more efficient to
use a modifier symbol to indicate that the following word is capitalized
or written in all capitol letters.  Of course, if all of the input
text is all upper case, as would be the case for some telegraphic
type communications systems, this is not a concern.

Once a linguistic symbol is detected in the input text, it is encoded
with its corresponding Huffman code representation.  This is then
decoded at the other end of the communications link or after retrieving
the data from storage, using the same Huffman code.

So that the Huffman code generation does not have to be done each
time a file is compressed, an escape code that meant ``the following
symbol of ____ bits is not in the code, and is to be interpreted directly''
is used.  For these symbols, a simple suppression of the most significant
bit is used, resulting in a savings of one out of eight bits.

C.  Huffman Coding

Given a set of symbols and their associated probabilities of occurrence,
a Huffman code for those symbols is constructed by generating a tree.  Start
with a set of symbols as individual nodes.  While there are still
separate nodes, combine the two nodes with the lowest probability
(resolve ties arbitrarily) into a new node with a probability equal
to the sum of the probabilities of the two nodes that were combined.  Attach
one of the nodes to the new node via a 1 and the other node via a
0.  After all of the nodes are combined, the code for each symbol
is the sequence of ones and zeroes assigned to the branches of the
tree starting at the root and ending at the symbol. [STO]

Note that this algorithm results in a very similar code to a Shannon-Fanno
code (which generates the tree by starting at the root and building
out to the leaves), but it is computationally more efficient to implement.

D.  Pascal Programs

The pascal programs that implement this linguistic file compression
are in appendix B.  The first one, COUNT, merely counts the frequency
of occurrence of words in sample text.  It is not necessary that the
text analyzed be the same text to be compressed, just that it be similar.  For
example, better compression would be expected when using a code based
on personnel records when using that code to compress personnel records
than when compressing medical discussions.  However, the significant
gains made in compressing the more common words in the code offset
the lesser compression (or even possible expansion) encountered when
words not in the code are encountered.  It is also desirable to COUNT
a large sample of text to ensure accurate word frequencies.

The second program, MAKETREE takes the frequency data from the output
file generated by COUNT and generates a Huffman code from it.  It
then writes this tree out into a file that is used by SQUEEZE.  To
get reasonable speed from this program, it uses as much memory as
MS-DOS will let it for the more frequently accessed information, and
uses a temporary file for the rest of the information.  The program
runs significantly faster if this temporary file is on a RAM disk
in extended or expanded memory (beyond the basic 640 KBytes of the
MS-DOS domain).

SQUEEZE, the third program, does the squeezing and unsqueezing of
files based on the output file of MAKETREE.  The same Huffman coding
tree can be used for many different input text files, because the
statistics of English (especially when the same types of text, such
as all business letters or all technical reports) remain fairly constant
even when the content of the text conveys different meanings.  SQUEEZE
handles words not in its dictionary in stride, but highlights them
as they scroll across the screen in processing so that the user can
get a feel for how well the text is matched to the code tree in use.
If only a few proper names and such are highlighted, then the code
in use is a good one to use.  If not, then perhaps a regeneration
of the code would be in order.  Note that the code file used to SQUEEZE
a file must be identical to the one used to unSQUEEZE it, so it must
either be stored or sent with the file, or sent in advance and agreed
upon by communicating parties.

After testing these programs on various ASCII text files, it can be  seen that
significant compression can be obtained, and that the compressed  files can be
recovered reliably.  There is, however, room for improvement  in the exact way
that text is parsed and in the speed of the implementation.  Nevertheless,
when maximum security is desired, I recommend first compressing an  ASCII text
file with SQUEEZE, then encrypting it with CRYPTMPJ.  The  code file
(LANGUAGE.COD) used by SQUEEZE and the encryption key should  be sent by a
separate, secure channel to the receiving party (or stored  in a physically
secure location for data storage) in advance of the  message.  The combination
of minimal natural redundancy in the message  sent and the use of a good
encryption algorithm should be difficult  to crack.

IX.       CONCLUSION

The MPJ Encryption algorithm provides an alternative to DES that is
more secure, providing that the software and/or hardware does not
get corrupted or tampered with, and providing that the keys are managed
effectively.  I have implemented and tested the algorithm in software
for the IBM PC and compatible machines.  The algorithm may be implemented
directly in hardware for faster data rates.  The MPJ Encryption Algorithm
may be used by itself, or it may be improved upon by compressing the
data before encryption.

The use of data compression in conjunction with any encryption algorithm
drastically increases the security of the encrypted data.  For natural
language text, one approach that yields improved compression over
the compression of constant size blocks of data is the compression
of linguistic units, such as words.  I have achieved reversible compression
of such files to less than 35% of their original size using linguistic
parsing and a Huffman code. For binary data, such as computer programs,
the use of existing techniques, such as those in PKARC, written by
Phil Katz and available on most computer bulletin boards, are recommended.

It is hoped that the MPJ encryption algorithm, as well as some of
my ideas on data compression, will make a positive contribution towards
data security, communications privacy, and efficiency of data storage
and transmission.  May God prosper those who use this knowledge and
build upon it for good.

REFERENCES

[ALB]  Douglas J. Albert and Stephen P. Morse,``Combating
Software Piracy by Encryption and Key Management,''Computer,
Vol. 21, No. 5, April 1984, pp. 68-73 Los Alamitos, CA: IEEE Computer
Society.

[AME]  Stanley R. Ames, Jr., Morrie Gasser, and Roger
R. Schell, ``Security Kernel Design and Implementation:  An Introduction,''
Computer, Vol. 16, No. 7, July 1983, pp. 14-22 Los Alamitos,
CA: IEEE Computer Society.

[BAL]  W. W. Rouse Ball & H. S. M. Coxeter, Mathematical
Recreations & Essays.  New York:  The MacMillan Company, 1962.

[BAU]  Friedrich L. Bauer, ``Cryptology - Methods
and Maxims,'' in Proceedings of the Workshop on Cryptography at
Burg Feuerstein, Germany, March 29-April 2, 1982, Berlin, Heidelberg,
New York: Springer-Verlag, 1983.

[BEK]  H. J. Beker, ``A Survey of Encryption Algorithms,''
in International Conference on Secure Communication Systems,
22-23 February 1984, London, New York: Institute of Electrical
Engineers, 1984. TK5102.5.I519.1984

[BET]  Thomas Beth, Introduction to Proceedings of
the Workshop on Cryptography at Burg Feuerstein, Germany, March 29
- April 2, 1982, Berlin, Heidelberg, New York: Springer-Verlag,
1983.

[BON]  D. J. Bond, ``Practical Primality Testing,'' in
International Conference on Secure Communication Systems, 22-23
February 1984, London, New York: Institute of Electrical Engineers,
1984. TK5102.5.I519.1984

[BRO]  C. B. Brookson and S. C. Serpell, ``Security on
the British Telecom Satstream Service'' in International Conference
on Secure Communication Systems, 22-23 February 1984, London,
New York: Institute of Electrical Engineers, 1984. TK5102.5.I519.1984

[BUR]  Dave Bursky, ``Protect Your EEPROM Data and Gain
More Flexibility,'' Electronic Design, 26 May 1988, pp.43-48.
Waseca, MN:  Brown Printing Co.

[CHA]  Leslie S. Chalmers, ``An Analysis of the Differences
Between the Computer Security Practices in the Military and Private
Sectors,'' in Proceedings of the IEEE 1986 Symposium on Security
and Privacy, Oakland, CA, April 7-9, 1986. QA76.9.A25.595.1986

[CHI]  H. R. Chivers, ``A Practical Fast Exponentiation
Algorithm for Public Key,'' in International Conference on Secure
Communication Systems, 22-23 February 1984, London, New York:
Institute of Electrical Engineers, 1984.  TK5102.5.I519.1984

[COO]  R. H. Cooper, ``Linear Transformations in Galois
Fields and their Application to Cryptography,'' Cryptologia Magazine,
Volume 4, Number 3, July 1980, pages 184-188.  Republished electronically
by Tony Patti.

[COS]  Terry Costlow, ``Global Computer Network Cracks
Cryptographic Mathematics Barrier,'' Electronic Engineering Times,
Issue 508, 17 October 1988, p. 14, Manhasset, NY:  CMP Publications,
Inc.

[CRC]  Handbook of Chemistry and Physics, 53rd
Edition, Cleveland, OH: The Chemical Rubber Company, 1972.

[DEA]  Cipher A. Deavers and Louis Kruh, Machine
Cryptography and Modern Cryptanalysis, Norwood, MA: Artech House,
Inc., 1985.  Z103.D43.1985

[DEN]  Dorothy Elisabeth Robling Denning, Cryptography
and Data Security, Reading, MA; Menlo Park, CA; London; Amsterdam;
Don Mills, Ontario; Sydney: Addison-Wesley Publishing Company, 1982.
QA76.9.A25.D46.1982

[DES]  National Bureau of Standards, Federal Information
Processing Standards Publication Number 46 Dated 15 January 1977.

[DOH]  Richard Doherty, ``FBI Nabs Pirated VCII,'' Electronic
Engineering Times, Manhasset, N. Y.:  CMP Publications, Inc., Issue
500, August 22, 1988.

[EET]  ``NSA OKs Decryption Unit,'' Electronic Engineering
Times, August 29, 1988, Manhasset, N. Y.: CMP Publications, Inc.

[FRA]  Ole Immanuel Franksen, Mr. Babbage's Secret
- The Tale of a Cipher and APL, Englewood Cliffs, NJ: Prentice-Hall,
1985. Z103.B2.F72.1985

[FRI]  H. J. Beker, J. M. K. Friend, and P. W. Halliden,
``Simplifying Key Management in Electronic Fund Transfer Point of
Sale Systems,'' in International Conference on Secure Communication
Systems, 22-23 February 1984, London, New York: Institute of
Electrical Engineers, 1984.  TK5102.5.I519.1984

[FRM]  Lester J. Fraim, ``Scomp: A Solution to the Multilevel
Security Problem,'' Computer, Vol. 16, No. 7, July 1983,pp.
26-34, Los Alamitos, CA: IEEE Computer Society.

[GOO]  G. Goos and J. Hartmans, Lecture Notes in
Computer Science.  Z102.5.W67.1982

[GOR]  J. A. Gordon and H. Retkin, ``Are Big S-Boxes
Best?'' in Proceedings of the Workshop on Cryptography at Burg
Feuerstein, Germany, March 29-April 2, 1982, Berlin, Heidelberg,
New York: Springer-Verlag, 1983.

[HAE]  D. G. Haenshke, D. A. Kettler, and E. Oberer,
``Network Management and Congestion in the U. S. Telecommunications
Network,'' IEEE Transactions on Communications, volume COM-29,pp.
376-385, April 1981.

[HEL]  Gilbert Held and Thomas R. Marshall, Data
Compression, Second Edition; Chichester, New York, Brisbane,Toronto,
Singapore: John Wiley & Sons, 1987.  QA76.9.D33.H44.1987

[HIL]  Lester S. Hill, ``Cryptography in an Algebraic
Alphabet,'' American Mathematical Monthly, June 1929, pages
306-312, the American Mathematical Society.  Republished electronically
by Tony Patti by permission.

[HLL]  Lester S. Hill, ``Concerning Certain Linear Transformation
Apparatus of Cryptography,'' American Mathematical Society,
March 1931, pages 135-154.  Republished electronically by Tony Patti
by permission.

[JAC]  A. M. Jackson, N. A. McEvoy, and B. B.Newman,
``Project Universe Encryption Experiment'' in International Conference
on Secure Communication Systems, 22-23 February 1984, London,
New York: Institute of Electrical Engineers, 1984. TK5102.5.I519.1984

[KAH]  David Kahn, The Codebreakers - The Story
of Secret Writing, New York: The MacMillan Company, 1987. Z103.K28

[KRU]  Cipher A. Deavers, David Kahn, Louis Kruh, Greg
Mellen, and Brian Winkel, Cryptology Yesterday, Today and Tomorrow,
Norwood, MA: Artech House, Inc., 1987.  Z103.C76.1987

[LAN]  Carl E. Landwehr, The Best Available Technologies
for Computer Security,'' Computer, Vol. 16, No. 7, July 1983,pp.
86-100, Los Alamitos, CA: IEEE Computer Society.

[KAT]  Phil Katz, PKARC FAST! Archive Create/Update
Utility Version 3.5 04-27-87, published electronically in PKX35A35.EXE.

[KON]  Alan G. Konheim, Cryptography:  A Primer,
New York: John Wiley & Sons.  Z103.K66

[KOZ]  Wladyslaw Kozaczuk, Enigma - How the German
Machine Cipher was Broken and How it was Read by the Allies in World
War Two, University Publications of America, Inc., 1984.D810.C88.K6813.1984

[LIN]  Christer Lind<130>n, ``Electronic Seal for Protection
of Electronic Money in Sweden, Finland, and Norway'' in Proceedings
of 1986 International Carnahan Conference on Security Technology:
Electronic Crime Countermeasures, August 12-14, 1986. QA76.9.A25.C41.1986

[LOD]  N. Lodge, B. Flannaghan, and R. Morcom,``Vision
Scrambling of C-MAC DBS Signals,'' in International Conference
on Secure Communication Systems, 22-23 February 1984, London,
New York: Institute of Electrical Engineers, 1984. TK5102.5.I519.1984

[LU]  W. P. Lu and M. K. Sandareshan, ``A Hierarchical
Key Management Scheme for End-to-End Encryption in Internet Environments''
in Proceedings of the IEEE 1986 Symposium on Security and Privacy,
Oakland, CA, April 7-9, 1986.  QA76.9.A25.595.1986

[MCL]  Vin McLellan, ``Drugs and DES:  A New Connection,''
Digital Review, August 24, 1987.

[MER]  Ralph C. Merkle, Secrecy, Authentication,
and Public Key Systems, Ann Arbor, MI: UMI Research Press,1982.  QA76.9.A25M47.1982

[MEY]  Carl H. Meyer & Stephen M. Matyas,Cryptography:  a
New Dimension in Computer Data Security - A Guide for the Design
and Implementation of Secure Systems, New York, Chichester, Brisbane,
Toronto, Singapore: John Wiley & Sons, 1982.  Z103.M55.1982

[MIT]  C. J. Mitchell, ``A Comparison of the Cryptographic
Requirements for Digital Secure Speech Systems Operating at Different
Bit Rates,'' in International Conference on Secure Communication
Systems, 22-23 February 1984, London, New York: Institute of
Electrical Engineers, 1984.  TK5102.5.I519.1984

[PAT]  Tony Patti, A Galois Field Cryptosystem,
1986. Published electronically by Tony Patti, editor of Cryptosystems
Journal, 9755 Oatley Lane, Burke, VA 22015.

[PIP]  Fred Piper, ``Stream Ciphers,'' in Proceedings
of the Workshop on Cryptography at Burg Feuerstein, Germany, March
29-April 2, 1982, Berlin, Heidelberg, New York: Springer-Verlag,
1983.

[PER]  Tekla S. Perry and Paul Wallich, ``Can Computer
Crime be Stopped?,''  IEEE Spectrum, May, 1984, pp.34-49.  New
York, NY: The Institute of Electrical and Electronic Engineers, Inc.

[RET]  H. Retkin, ``Multi-Level Knapsack Encryption,''
in International Conference on Secure Communication Systems,
22-23 February 1984, London, New York: Institute of Electrical
Engineers, 1984. TK5102.5.I519.1984

[SAT]  J. Sattler and C. P. Schnorr, ``Ein Effizienzvergleich
Der Faktorisierungsverfahren von Morrison-Brillhart und Schroeppel,''
in Proceedings of the Workshop on Cryptography at Burg Feuerstein,
Germany, March 29-April 2, 1982, Berlin, Heidelberg, New York:
Springer-Verlag, 1983.

[SCH]  C. P. Schnorr, ``Is the RSA Scheme Safe?'' in
Proceedings of the Workshop on Cryptography at Burg Feuerstein,
Germany, March 29-April 2, 1982, Berlin, Heidelberg, New York:
Springer-Verlag, 1983.

[SHA]  C. E. Shannon, ``Communication Theory of Secrecy
Systems,'' Bell System Technical Journal, Volume 28, 1949.

[STO]  James A. Storer, Data Compression Methods
and Theory.  Rockville, MD:  Computer Science Press, 1988. QA76.9.D33S76

[TIL]  Henk C. A. van Tilborg, An Introduction to
Cryptology, Boston, Dordrecht, Lancaster: Kluwer Academic Publishers,
1988.  Z103.T54.1987

[RET]  H. Retkin, ``Multi-Level Knapsack Encryption,''
in International Conference on Secure Communication Systems,
22-23 February 1984, London, New York: Institute of Electrical
Engineers, 1984. TK5102.5.I519.1984

[ULT]  Ultron Labs Corporation, ``Crypto Module Processes
TOP SECRET Data,'' EE Product News, October 1988, p. 16, Overland
Park, KS: Intertec Publishing.

[VAN]  J. Vandewalle, R. Govaerts, W. De Becker, M. Decroos,
& G. Speybrouk, ``RSA-Based Implementation of Public Key Cryptographic
Protection in Office Systems'' in Proceedings of 1986 International
Carnahan Conference on Security Technology:  Electronic Crime Countermeasures,
August 12-14, 1986.  QA76.9.A25.C41.1986

APPENDIX A.  MPJ in Pascal

{$R-}    {Range checking off}

{$S-}    {Stack checking off}

{$I+}    {I/O checking on}

{$N-}    {Don't use 80x87 numeric coprocessor}

program cryptmpj;

{ Encryption designed to exceed DES in security value and be implementable
on

  an IBM PC compatible machine. }



Uses Crt, Dos;  { Include screen handling & MS DOS interface functions.
}



const maxinbuffer = 16;

      ap = #39;                            { Apostrophe for write
statements. }



type blocks = array[0..15] of byte;             { 16 byte (128 bit)
blocks. }

     stype = array[0..9,0..15,0..255] of byte;  { Holds substitution
boxes. }

     ptrstype = ^stype;  { Dynamic variable required to get beyond
64K limit. }

     string80 = string[80];                     { Long character strings.
}

     string15 = string[15];                     { Short character
strings. }



var initial,                  { Initialiazation vector. }

    feedback,                 { Chaining feedback array. }

    key,                      { Encryption/decryption key. }

    buffer, outbuf:  blocks;  { File read/write buffers. }

    s,                        { Substitution boxes. }

    si: ptrstype;             { Inverse substitution boxes. }

    bytesdone,                { Number of bytes done. }

    number: longint;          { Used to read in key & initialization
vector. }

    que,                      { Position in file specification que.
}

    i, j, k,                  { Iteration & array indexes. }

    actualread: integer;      { Actual number of bytes read in from
file. }

    inputfile: file;          { File to encrypt or decrypt in place.
}

    keyfile: text;            { External key file. }

    intkeyfile: file of stype; {Holds s and si. }

    keyname,                  { Name of external key file. }

    intkeyname,               { Name of internal key file. }

    path,                     { Used in parsing file specification.
}

    temp: string[255];        { Used in determining encrypt/decrypt
option. }

    inputfilename,            { MS-DOS name of inputfile. }

    filespec: string80;       { File specification that may include
wild cards}

    fileque: array[0..15] of string80; { Names of multiple file specifications}

    name: string15;           { Name of next file to process. }

    decryption,               { True iff decryption is desired. }

    filefound: boolean;       { At least one file was found to process.}

    ch: char;                 { Character input. }

    search: searchrec;        { Used in finding matches to wild cards.
}



procedure permute(x: blocks; var y: blocks);

{ This procedure is designed to make each bit of the output dependent
on as

  many bytes of the input as possible, especially after repeated application.

  Each output byte takes its least significant bit from the corresponding

  input byte.  The next higher bit comes from the corresponding bit
of the

  input byte to the left.  This is done until all bits of the output
byte

  are filled.  Where there is no byte to the left, the byte at the
far right

  is used. }



  begin

    y[0] := (x[0] and 1) or (x[1] and 2) or (x[2] and 4) or

            (x[3] and 8) or (x[4] and 16) or (x[5] and 32) or

            (x[6] and 64) or (x[7] and 128);

    y[1] := (x[1] and 1) or (x[2] and 2) or (x[3] and 4) or

            (x[4] and 8) or (x[5] and 16) or (x[6] and 32) or

            (x[7] and 64) or (x[8] and 128);

    y[2] := (x[2] and 1) or (x[3] and 2) or (x[4] and 4) or

            (x[5] and 8) or (x[6] and 16) or (x[7] and 32) or

            (x[8] and 64) or (x[9] and 128);

    y[3] := (x[3] and 1) or (x[4] and 2) or (x[5] and 4) or

            (x[6] and 8) or (x[7] and 16) or (x[8] and 32) or

            (x[9] and 64) or (x[10] and 128);

    y[4] := (x[4] and 1) or (x[5] and 2) or (x[6] and 4) or

            (x[7] and 8) or (x[8] and 16) or (x[9] and 32) or

            (x[10] and 64) or (x[11] and 128);

    y[5] := (x[5] and 1) or (x[6] and 2) or (x[7] and 4) or

            (x[8] and 8) or (x[9] and 16) or (x[10] and 32) or

            (x[11] and 64) or (x[12] and 128);

    y[6] := (x[6] and 1) or (x[7] and 2) or (x[8] and 4) or

            (x[9] and 8) or (x[10] and 16) or (x[11] and 32) or

            (x[12] and 64) or (x[13] and 128);

    y[7] := (x[7] and 1) or (x[8] and 2) or (x[9] and 4) or

            (x[10] and 8) or (x[11] and 16) or (x[12] and 32) or

            (x[13] and 64) or (x[14] and 128);

    y[8] := (x[8] and 1) or (x[9] and 2) or (x[10] and 4) or

            (x[11] and 8) or (x[12] and 16) or (x[13] and 32) or

            (x[14] and 64) or (x[15] and 128);

    y[9] := (x[9] and 1) or (x[10] and 2) or (x[11] and 4) or

            (x[12] and 8) or (x[13] and 16) or (x[14] and 32) or

            (x[15] and 64) or (x[0] and 128);

    y[10] := (x[10] and 1) or (x[11] and 2) or (x[12] and 4) or

            (x[13] and 8) or (x[14] and 16) or (x[15] and 32) or

            (x[0] and 64) or (x[1] and 128);

    y[11] := (x[11] and 1) or (x[12] and 2) or (x[13] and 4) or

            (x[14] and 8) or (x[15] and 16) or (x[0] and 32) or

            (x[1] and 64) or (x[2] and 128);

    y[12] := (x[12] and 1) or (x[13] and 2) or (x[14] and 4) or

            (x[15] and 8) or (x[0] and 16) or (x[1] and 32) or

            (x[2] and 64) or (x[3] and 128);

    y[13] := (x[13] and 1) or (x[14] and 2) or (x[15] and 4) or

            (x[0] and 8) or (x[1] and 16) or (x[2] and 32) or

            (x[3] and 64) or (x[4] and 128);

    y[14] := (x[14] and 1) or (x[15] and 2) or (x[0] and 4) or

            (x[1] and 8) or (x[2] and 16) or (x[3] and 32) or

            (x[4] and 64) or (x[5] and 128);

    y[15] := (x[15] and 1) or (x[0] and 2) or (x[1] and 4) or

            (x[2] and 8) or (x[3] and 16) or (x[4] and 32) or

            (x[5] and 64) or (x[6] and 128);

  end;



procedure ipermute(x: blocks; var y: blocks);

{ This is the inverse of the procedure permute. }



  begin

    y[0] := (x[0] and 1) or (x[15] and 2) or (x[14] and 4) or

            (x[13] and 8) or (x[12] and 16) or (x[11] and 32) or

            (x[10] and 64) or (x[9] and 128);

    y[1] := (x[1] and 1) or (x[0] and 2) or (x[15] and 4) or

            (x[14] and 8) or (x[13] and 16) or (x[12] and 32) or

            (x[11] and 64) or (x[10] and 128);

    y[2] := (x[2] and 1) or (x[1] and 2) or (x[0] and 4) or

            (x[15] and 8) or (x[14] and 16) or (x[13] and 32) or

            (x[12] and 64) or (x[11] and 128);

    y[3] := (x[3] and 1) or (x[2] and 2) or (x[1] and 4) or

            (x[0] and 8) or (x[15] and 16) or (x[14] and 32) or

            (x[13] and 64) or (x[12] and 128);

    y[4] := (x[4] and 1) or (x[3] and 2) or (x[2] and 4) or

            (x[1] and 8) or (x[0] and 16) or (x[15] and 32) or

            (x[14] and 64) or (x[13] and 128);

    y[5] := (x[5] and 1) or (x[4] and 2) or (x[3] and 4) or

            (x[2] and 8) or (x[1] and 16) or (x[0] and 32) or

            (x[15] and 64) or (x[14] and 128);

    y[6] := (x[6] and 1) or (x[5] and 2) or (x[4] and 4) or

            (x[3] and 8) or (x[2] and 16) or (x[1] and 32) or

            (x[0] and 64) or (x[15] and 128);

    y[7] := (x[7] and 1) or (x[6] and 2) or (x[5] and 4) or

            (x[4] and 8) or (x[3] and 16) or (x[2] and 32) or

            (x[1] and 64) or (x[0] and 128);

    y[8] := (x[8] and 1) or (x[7] and 2) or (x[6] and 4) or

            (x[5] and 8) or (x[4] and 16) or (x[3] and 32) or

            (x[2] and 64) or (x[1] and 128);

    y[9] := (x[9] and 1) or (x[8] and 2) or (x[7] and 4) or

            (x[6] and 8) or (x[5] and 16) or (x[4] and 32) or

            (x[3] and 64) or (x[2] and 128);

    y[10] := (x[10] and 1) or (x[9] and 2) or (x[8] and 4) or

            (x[7] and 8) or (x[6] and 16) or (x[5] and 32) or

            (x[4] and 64) or (x[3] and 128);

    y[11] := (x[11] and 1) or (x[10] and 2) or (x[9] and 4) or

            (x[8] and 8) or (x[7] and 16) or (x[6] and 32) or

            (x[5] and 64) or (x[4] and 128);

    y[12] := (x[12] and 1) or (x[11] and 2) or (x[10] and 4) or

            (x[9] and 8) or (x[8] and 16) or (x[7] and 32) or

            (x[6] and 64) or (x[5] and 128);

    y[13] := (x[13] and 1) or (x[12] and 2) or (x[11] and 4) or

            (x[10] and 8) or (x[9] and 16) or (x[8] and 32) or

            (x[7] and 64) or (x[6] and 128);

    y[14] := (x[14] and 1) or (x[13] and 2) or (x[12] and 4) or

            (x[11] and 8) or (x[10] and 16) or (x[9] and 32) or

            (x[8] and 64) or (x[7] and 128);

    y[15] := (x[15] and 1) or (x[14] and 2) or (x[13] and 4) or

            (x[12] and 8) or (x[11] and 16) or (x[10] and 32) or

            (x[9] and 64) or (x[8] and 128);

  end;



procedure makesbox(key: blocks);

{ This procedure generates internal keys by filling the substitution
box array

  s^ based on the external key given as input. }

  var i, j, k: integer;

  procedure makeonebox(i, j: integer; key: blocks);

    var pos, m, n, p, startbit, bitmask, startbyte, keybyte: word;

        empty: array[0..255] of boolean;

    begin

      for m := 0 to 255 do    { The empty array is used to make sure
that }

        empty[m] := true;     { each byte of the array is filled only
once. }

      startbit := 1;

      startbyte := 0;

      for n := 255 downto 128 do  { n counts the number of bytes left
to fill }

        begin

          keybyte := startbyte;

          bitmask := startbit;

          m := 0;

          for p := 0 to 7 do   { m is obtained by bit selection on
the key }

            begin

              m := m or (key[keybyte] and bitmask);

              bitmask := bitmask shl 1;

              if bitmask > 128 then

                begin

                  bitmask := 1;

                  inc(keybyte);

                  if keybyte > 15 then keybyte := 0;

                end;

            end;

          pos := (n * m) div 255;  { pos is the position among the
UNFILLED }

          m := 0;                  { components of the s^ array that
the    }

          p := 0;                  { number n should be placed.  }

          while m < pos do

            begin

              inc(p);

              if empty[p] then inc(m);

            end;

          while not empty[p] do inc(p);

          s^[i, j, p] := n;

          empty[p] := false;

          startbit := startbit shl 1;  { The starting position of
the bit  }

          if startbit > 128 then       { selection for the key is
rotated  }

            begin                      { left one bit for the next
n.      }

              startbit := 1;

              inc(startbyte);

              if startbyte > 15 then startbyte := 0

            end;

        end;

      startbyte := 0;

      startbit := 1;

      for n := 127 downto 1 do         { This half of the algorithm
is the   }

        begin                          { same as the upper half, except
that }

          keybyte := startbyte;        { only 7 bits are selected
for m.     }

          bitmask := startbit;

          m := 0;

          for p := 0 to 6 do

            begin

              m := m or (key[keybyte] and bitmask);

              bitmask := bitmask shl 1;

              if bitmask > 64 then

                begin

                  bitmask := 1;

                  keybyte := keybyte + 3;

                  if keybyte > 15 then keybyte := keybyte - 16;

                end;

            end;

          pos := (n * m) div 127;

          m := 0;

          p := 0;

          while m < pos do

            begin

              inc(p);

              if empty[p] then inc(m);

            end;

          while not empty[p] do inc(p);

          s^[i, j, p] := n;

          empty[p] := false;

          startbit := startbit shl 1;

          if startbit > 64 then

            begin

              startbit := 1;

              inc(startbyte);

              if startbyte > 15 then startbyte := 0

            end;

        end;

      p := 0;

      while not empty[p] do

        inc(p);

      s^[i,j,p] := 0;

    end;



  begin

    new(s);

    for i := 0 to 9 do

      for j := 0 to 15 do

        begin

          write(#13,'Filling substitution boxes for round ',i+1,'
of 10, byte ',

                j+1,' of 16.  ');

          makeonebox(i, j, key);

          permute(key, key);            { Shuffle key bit positions.        }

          for k := 0 to 15 do           { Run key through last s-box
before }

            key[k] := s^[i, j, key[k]]; { making the next s-box.            }

        end;

    writeln;

  end;



procedure makesi;

{ This procedure fills the inverse substitution box array si^.  It
is not

  necessary to call this procedure unless the decryption mode is used.  }

  var i, j, k: integer;

  begin

    new(si);

    for i := 0 to 9 do

      for j := 0 to 15 do

        for k := 0 to 255 do

          si^[i, j, s^[i, j, k]] := k;

  end;



{$I CRYPTINC.PAS}   { Include additional file handling & user interface.
}



procedure substitute(round: integer; x: blocks; var y: blocks);

var i: integer;

begin

  for i := 0 to 15 do

    y[i] := s^[round,i,x[i]];

end;



procedure isubst(round: integer; x: blocks; var y: blocks);

var i: integer;

begin

  for i := 0 to 15 do

    y[i] := si^[round,i,x[i]];

end;



procedure encrypt(x: blocks; var y: blocks);

{ Encrypt a block of 16 bytes. }

var z: blocks;

begin

  substitute(0, x, y);

  permute(y, z);

  substitute(1, z, y);

  permute(y, z);

  substitute(2, z, y);

  permute(y, z);

  substitute(3, z, y);

  permute(y, z);

  substitute(4, z, y);

  permute(y, z);

  substitute(5, z, y);

  permute(y, z);

  substitute(6, z, y);

  permute(y, z);

  substitute(7, z, y);

  permute(y, z);

  substitute(8, z, y);

  permute(y, z);

  substitute(9, z, y);

end;



procedure decrypt(x: blocks; var y: blocks);

{ Decrypt a block of 16 bytes. }

var z: blocks;

begin

  isubst(9, x, y);

  ipermute(y, z);

  isubst(8, z, y);

  ipermute(y, z);

  isubst(7, z, y);

  ipermute(y, z);

  isubst(6, z, y);

  ipermute(y, z);

  isubst(5, z, y);

  ipermute(y, z);

  isubst(4, z, y);

  ipermute(y, z);

  isubst(3, z, y);

  ipermute(y, z);

  isubst(2, z, y);

  ipermute(y, z);

  isubst(1, z, y);

  ipermute(y, z);

  isubst(0, z, y);

end;



begin

  startup;  { Initialize files, call makesbox (and makesi if required).
}

  que := 0;

  while (que < 16) and (fileque[que] <> '') do

    begin

      filespec := fileque[que];

      inputfilename := filespec;

      path := '';

      repeat

        i := pos('\',inputfilename);

        if i > 0 then

          begin

            path := path + copy(inputfilename, 1, i);

            inputfilename := copy(inputfilename, i+1, length(inputfilename));

          end;

      until i = 0;

      findfirst(filespec, $22, search);

      while doserror = 0 do

        begin

          inputfilename := path + search.name;

          assign(inputfile, inputfilename);

          reset(inputfile,1);

          filefound := true;

          bytesdone := 0;

          for i := 0 to 15 do

            feedback[i] := initial[i];

          if decryption then

           begin

            writeln('Decrypting ',inputfilename);

            while not eof(inputfile) do

              begin

                blockread(inputfile,buffer,maxinbuffer,actualread);

                encrypt(feedback,outbuf);

                { Note that decrypt is not ever called when using
block

                  chaining with ciphertext feedback.  It would be
called

                  if the electronic codebook mode were used, instead.
}

                for i := 0 to 15 do

                  begin

                    outbuf[i] := outbuf[i] xor buffer[i];

                    feedback[i] := buffer[i]

                  end;

                seek(inputfile, filepos(inputfile) - actualread);

                blockwrite(inputfile, outbuf, actualread);

                bytesdone := bytesdone + actualread;

                write(#13, bytesdone:9,' bytes decrypted. ');

              end;

            writeln(#13, bytesdone:9,' bytes decrypted.  ');

           end

          else

           begin

            writeln('Encrypting ',inputfilename);

            while not eof(inputfile) do

              begin

                blockread(inputfile,buffer,maxinbuffer,actualread);

                encrypt(feedback,outbuf);

                for i := 0 to 15 do

                  begin

                    outbuf[i] := outbuf[i] xor buffer[i];

                    feedback[i] := outbuf[i]

                  end;

                seek(inputfile, filepos(inputfile) - actualread);

                blockwrite(inputfile, outbuf, actualread);

                bytesdone := bytesdone + actualread;

                write(#13, bytesdone:9,' bytes encrypted.  ');

              end;

            writeln(#13, bytesdone:9,' bytes encrypted.  ');

           end;

          close(inputfile);

          findnext(search);

        end;

      inc(que);

    end;

  if not filefound then writeln('No matching files found.');

  writeln('Done.');

end.

APPENDIX B.  Linguistic Data Compression Programs

program count;

{Program to count the probability of occurances of words in text.}



uses dos, crt;

const maxbuf = 4096;

      maxstr = 15;

      ap = #39;



type wd = string[maxstr];

     ptr = ^entry;

     yarn = string[80];

     entry = record

               wrd:  wd;        {Linguistic word}

               count: longint;  {How many times this word was found}

               next: ptr;       {Next record in sequence}

             end;



var outfile,             {File with output report}

    infile: text;        {File with input text to be analyzed}

    bottom,              {Last entry record}

    newbuf,              {New entry record}

    prev: ptr;           {Previous entry record}

    buffer,              {Current entry record}

    top: array[1..255] of ptr;  {First entry record}

    words: wd;           {Word under construction}

    temp,

    path,                    {Path of input file}

    filemask,                {File name mask}

    filespec,                {Path + name (including wild cards)}

    inname,                  {Name of input file}

    outname: yarn;           {Name of output file}

    ch: char;

    i, j, cmdparameter, topindex: integer;

    cnt: longint;

    filefound: boolean;

    inbuf, outbuf: array[1..maxbuf] of byte;

    s: searchrec;           {Record fill: array[1..21] of byte;attr:byte;time,

                              size:longint;name: string[12]}



function exist(filename: wd): boolean;

{Returns TRUE iff the file exists.}

var f: file;

begin {exist}

  assign(f,filename);

  {$I-}

  reset(f);

  {$I+}

  if IOresult = 0 then

    begin

      exist := true;

      close(f)

    end

  else

    exist := false;

end;  {exist}



function punct(ch: char): boolean;

{TRUE iff ch is not a letter or chr(255).}

  var c:  integer;

  begin

    c := ord(ch);

    if ((c > 10) and (c <= 64)) or ((c >= 91) and (c <= 96))

    or ((c >= 123) and (c <= 254)) or ((c > 0) and (c < 10)) then

      punct := true

    else

      punct := false;

  end;



function letter(ch: char): boolean;

{TRUE iff ch is a letter A-Z or a-z.}

  var c: integer;

  begin

    c := ord(ch);

    if ((c >= 65) and (c <= 90)) or ((c >= 97) and (c <= 122)) then

      letter := true

    else

      letter := false;

  end;



procedure parse(var words: wd; var ch: char);

{Extracts a word or item of punctuation from input file.}

  begin  {parse}

    words := '';

    while not (letter(ch) or punct(ch) or eof(infile)) do

      begin

        read(infile,ch);

      end;

    if punct(ch) then

      begin

        if ord(ch) = 13 then

          begin

            words := chr(255)+chr(255);

            if not eof(infile) then read(infile, ch);

          end

        else

          if ch = ' ' then

            begin

              words := ch;

              while (not eof(infile)) and (ch = ' ') and (length(words)
< maxstr) do

                begin

                  read(infile,ch);

                  if ch = ' ' then words := words + ch;

                end;

              if (length(words) = maxstr) and (not eof(infile)) then

                read(infile,ch);

            end

          else

            begin

              words := ch; {return one punctuation character}

              if not eof(infile) then read(infile, ch);

            end;

      end

    else

      begin

        if letter(ch) then

          begin

            words := ch;

            while (not eof(infile)) and letter(ch) and (length(words)
< maxstr) do

              begin

                read(infile,ch);

                if letter(ch) then words := words + ch;

              end;

            if (length(words) = maxstr) and (not eof(infile)) then

              read(infile,ch);

          end;

      end;

  end;  {parse}



procedure update(words: wd);

{Increments the count associated with a word.}

  begin

    topindex := ord(words[1]);

    buffer[topindex] := top[topindex];

    {Find record that matches word, if it exists.}

    while (buffer[topindex]^.wrd < words) and (buffer[topindex]^.next
<> nil) do

      begin

        prev := buffer[topindex];

        buffer[topindex] := buffer[topindex]^.next

      end;



    if buffer[topindex]^.wrd = words then

      {Increment count on word that already exists}

      inc(buffer[topindex]^.count)

    else

      begin  {Add word to middle of list with count of one}

        new(newbuf);

        newbuf^.wrd := words;

        newbuf^.count := 1;

        newbuf^.next := prev^.next;

        prev^.next := newbuf;

      end;

  end;



procedure report;

{Produces a report file.}

  var total: longint;

  begin

    assign(outfile, paramstr(1));

    rewrite(outfile);

    total := 0;

    for topindex := 1 to 255 do

      begin

        buffer[topindex] := top[topindex];

        while (buffer[topindex]^.next <> nil) do

          begin

            buffer[topindex] := buffer[topindex]^.next;

            if buffer[topindex]^.count > 0 then

              begin

                writeln(outfile,buffer[topindex]^.wrd);

                writeln(outfile,buffer[topindex]^.count);

                total := total + buffer[topindex]^.count;

              end;

          end;

      end;

    writeln(outfile, chr(255));

    writeln(outfile, '1');

    writeln(outfile, 'Total count:  ',total);

    close(outfile);

  end; {report}



begin

  clrscr;

  writeln('  This program counts words in a set    This program may
be copied freely ');

  writeln('  of input files to determine their     for educational
use or to try it  ');

  writeln('  frequency of occurance.  This data    out.  If you like
it, donations   ');

  writeln('  is then stored in a file for use by   will be accepted
by the author.   ');

  writeln('  MAKETREE, which constructs a code     This program is
believed to be    ');

  writeln('  tree with the Huffman algorithm.      reliable, but it
is the user',ap,'s    ');

  writeln('  The code tree is used by SQUEEZE.     responsibility
to determine its   ');

  writeln('                                        fitness for use.  No
liability    ');

  writeln('  Mike Johnson                          will be assumed
by the author.    ');

  writeln('  P. O. Box 1151                        Copyright (C) 1988
Mike Johnson.  ');

  writeln('  Longmont, CO 80502-1151               All rights reserved.              ');

  if paramcount < 2 then

    begin

      writeln;

      writeln('Syntax: COUNT outputfilename inputfilename[s]');

      writeln('        input file names may include * and ?');

      writeln('        Input files are assumed to be ASCII text.');

      writeln;

      writeln('If a previous COUNT ouput file named LANGUAGE.OUT exists,
then new counts');

      writeln('will be added to the counts in LANGUAGE.OUT.');

      writeln('Maximum effectiveness will be obtained if the nature
of the files COUNTed');

      writeln('is similar to the nature of the files to be compressed
with SQUEEZE.');

    end

  else

    begin

      filefound := false;

      new(bottom);

      bottom^.wrd := chr(255);

      bottom^.count := 0;

      bottom^.next := nil;

      for topindex := 1 to 255 do

        begin

          new(top[topindex]);

          top[topindex]^.wrd := chr(1);

          top[topindex]^.count := 0;

          top[topindex]^.next := bottom;

          buffer[topindex] := top[topindex];

        end;

      ch := chr(0);

      words := '                              ';



      if exist('LANGUAGE.OUT') then

        begin

          assign(infile,'LANGUAGE.OUT');

          reset(infile);

          writeln('Reading in existing LANGUAGE.OUT.');

          while (not eof(infile)) and (words <> chr(255)) do

            begin

              readln(infile,words);

              if words <> chr(255) then

                begin

                  topindex := ord(words[1]);

                  readln(infile,cnt);

                  new(newbuf);

                  newbuf^.wrd := words;

                  newbuf^.count := cnt;

                  newbuf^.next := bottom;

                  buffer[topindex]^.next := newbuf;

                  buffer[topindex] := newbuf;

                  write(#13,words,'            ');

                end;

            end;

          close(infile);

          writeln;

        end;



      {Initialize input files.}

      for cmdparameter := 2 to paramcount do

        begin

          filespec := paramstr(cmdparameter);

          filemask := filespec;

          path := '';

          repeat

            i := pos('\',filemask);

            if i > 0 then

              begin

                path := path + copy(filemask, 1, i);

                filemask := copy(filemask, i+1, length(filemask));

              end;

          until i = 0;

          findfirst(filespec, readonly + hidden + archive, s);

          while doserror = 0 do

            begin

              filefound := true;

              inname := path + s.name;

              assign(infile, inname);

              reset(infile);

              words := '                              ';

  writeln('>>>>>>>>>>>>>>>>>>>>> Processing ',inname);

              while (not eof(infile)) and (words <> '') and (not keypressed)
do

                begin

                  parse(words,ch);     {Find word or punctuation}

                  if words = chr(255)+chr(255) then

                    writeln

                  else

                    write(words);

                  if length(words) > 0 then

                    update(words);     {Increment word counter}

                end;

              close(infile);

              findnext(s);

            end;

        end;



      if not filefound then writeln('No matching files found.');

      report;

    end;

end.

{$R+}

{$M 3072,4096,655360}

program maketree;



uses crt;

const maxstr = 15;

      ap = #39;



type wd = string[maxstr];

     yarn = string[80];

     mem = ^mementry;

     entry = record

               wrd:  wd;        {Which linguistic word in input file}

               memory: mem;     {Corresponding mementry.}

             end;



     mementry = record

                  count: longint; {Word count.}

                  onezero: byte;  {Is this record pointed to by 1
or 0?}

                  root,           {Position of record nearer root.}

                  next:  mem;     {Position of next record.}

                end;



var temp: file of entry; {Temporary file}

    infile: text;        {File with input text to be analyzed}

    buffer,              {Current entry record}

    newbuf: entry;       {New entry record}

    mtop,

    mbottom,

    mbuffer,

    mnewbuf,

    mprev: mem;

    inname,              {Name of input file}

    outname,             {Name of output file}

    words: wd;           {Word under construction}

    ch: char;

    cnt1,

    cnt2,

    cnt:  longint;

    i, j: integer;

    tempname: yarn;



function exist(filename: wd): boolean;

{Returns TRUE iff the file exists.}

var f: file;

begin {exist}

  assign(f,filename);

  {$I-}

  reset(f);

  {$I+}

  if IOresult = 0 then

    begin

      exist := true;

      close(f)

    end

  else

    exist := false;

end;  {exist}



procedure fanno;

  begin

    cnt1 := 0;

    repeat



      {Find smallest two records.}

      mprev := mtop^.next;

      mbuffer := mprev^.next;



      {Combine lowest 2 probabilities of counts.}

      mtop^.next := mbuffer^.next;

      new(mnewbuf);

      mnewbuf^.count := mbuffer^.count + mprev^.count;

      mnewbuf^.onezero := 2;

      mnewbuf^.root := nil;

      mprev^.root := mnewbuf;

      mprev^.onezero := 1;

      mbuffer^.root := mnewbuf;

      mbuffer^.onezero := 0;



      {Place combined entry in proper place in chain.}

      mbuffer := mtop;

      repeat

        mprev := mbuffer;

        mbuffer := mbuffer^.next;

      until (mnewbuf^.count <= mbuffer^.count);

      mprev^.next := mnewbuf;

      mnewbuf^.next := mbuffer;



      {Check for completion.}

      inc(cnt1);

      write(#13,cnt1,' nodes combined.  ');

    until (cnt1 >= cnt2);

  end;  {fanno}



procedure placeit;

  begin

        write(#13,cnt:11,' ',words,'          ');

        mbuffer := mtop;

        repeat

          mprev := mbuffer;

          mbuffer := mbuffer^.next;

        until mbuffer^.count >= cnt;

        new(mnewbuf);

        newbuf.wrd := words;

        newbuf.memory := mnewbuf;

    write(temp,newbuf);

        mnewbuf^.count := cnt;

        mnewbuf^.onezero := 2;

    mnewbuf^.root := nil;

        mnewbuf^.next := mbuffer;

        mprev^.next := mnewbuf;

  end;



procedure filegen;

var cod: file of byte;

    ascnum: yarn;

    c: char;

    b, d: byte;

    i, shifter: integer;



  begin

    assign(cod,outname);

    rewrite(cod);

    reset(temp);

    repeat

      read(temp,buffer);

      mbuffer := buffer.memory;

      if buffer.wrd <> '' then

    begin

          for i := 0 to length(buffer.wrd) do

            begin

              b := ord(buffer.wrd[i]);

              write(cod,b);

            end;

          ascnum := '';

          while (mbuffer^.root <> nil) do

            begin

              if mbuffer^.onezero = 0 then

                ascnum := ascnum + '0'

              else

                ascnum := ascnum + '1';

              mbuffer := mbuffer^.root;

            end;

          d := ord(ascnum[0]);

          write(cod,d);

          shifter := 1;

          b := 0;

          for i := d downto 1 do

            begin

              if ascnum[i] = '1' then b := b + shifter;

              shifter := shifter shl 1;

              if shifter >= 256 then

                begin

                  write(cod,b);

                  b := 0;

                  shifter := 1

                end;

            end;

          if shifter > 1 then write(cod,b);

          write(#13,buffer.wrd:maxstr,' = ',ascnum,'                           ');

        end;

    until eof(temp);

    close(cod);

    close(temp);

    erase(temp);

  end;



begin

  clrscr;

  writeln('  MAKETREE takes the word count         This program may
be copied freely ');

  writeln('  data created by COUNT and creates     for educational
use or to try it  ');

  writeln('  a code tree using the Huffman         out.  If you like
it, donations   ');

  writeln('  algorithm.  The resulting code tree   will be accepted
by the author.   ');

  writeln('  is used by SQUEEZE when it            This program is
believed to be    ');

  writeln('  compresses ASCII text files.          reliable, but it
is the user',ap,'s    ');

  writeln('                                        responsibility
to determine its   ');

  writeln('                                        fitness for use.  No
liability    ');

  writeln('  Mike Johnson                          will be assumed
by the author.    ');

  writeln('  P. O. Box 1151                        Copyright (C) 1988
Mike Johnson.  ');

  writeln('  Longmont, CO 80502-1151               All rights reserved.              ');

  if paramcount < 2 then

    begin

      writeln('Syntax: MAKETREE infile outfile [tempfile]');

      writeln('                 infile is input file name (generated
by COUNT)');

      writeln('                 outfile is output file name to be
used by SQUEEZE');

      writeln('                 tempfile is filename to use for temporary
file');

      writeln('The temporary file is best put on a RAM disk in extended
or expanded memory,');

      writeln('but a hard disk or even a floppy will do if that is
the fastest you have.');

      writeln('Don',ap,'t use a RAM disk in conventional (lower 640K)
memory, as this program');

      writeln('already uses most of that in generating the coding
tree.');

    end

  else

    begin

      inname := paramstr(1);

      outname := paramstr(2);

      if exist(inname) then

        begin

          assign(infile,inname);

          reset(infile);

        end

      else

        begin

          writeln('Unable to open ',inname);

          exit

        end;

      if paramcount > 2 then

        tempname := paramstr(3)

      else

        tempname := 'ZYXWVUTS.$$$';

      assign(temp,tempname);

      {$I- }

      rewrite(temp);

      {$I+ }

      if ioresult <> 0 then

        begin

          writeln('I/O error attempting to open temporary file ',tempname);

          halt;

        end;

      new(mtop);

      new(mbottom);

      mtop^.count := -1;

      mtop^.onezero := 2;

      mtop^.root := nil;

      mtop^.next := mbottom;

      mbottom^.count := 2147483647;

      mbottom^.onezero := 2;

      mbottom^.root := nil;

      mbottom^.next := nil;

      cnt2 := 2;

      writeln('Reading in and sorting word frequency data.');

      repeat

        readln(infile,words);

        readln(infile,cnt);

        placeit;

        inc(cnt2);

      until (words = chr(255)) or eof(infile);

      close(infile);

      words := chr(255) + chr(255);

      placeit;

      words := words + chr(255);

      placeit;

      words := words + chr(255);

      placeit;

      writeln(#13,cnt2,' nodes to add to Huffman coding tree.                  ');

      fanno;

      writeln;

      writeln('Writing output file.');

      filegen;

      writeln(#13,'Done.                                          ');

    end;

end.

{$R+}

{$M 2048,4096,655360}

program squash;



uses dos, crt;



const maxbuf = 4096;

      maxstr = 15;

      ap = #39;



type wd = string[maxstr];

     yarn = string[80];

     ptr = ^entry;

     entry = record

               wrd:  wd;        {Linguistic word}

               count:  byte;    {How many bits in code}

               code: longint;   {Code (right justified in 4 byte integer)}

               next: ptr;       {Pointer to next entry}

             end;



var outfile,                 {File with output report}

    infile: file;            {File with input text to be analyzed}

    temp,

    path,                    {Path of input file}

    filemask,                {File name mask}

    filespec,                {Path + name (including wild cards)}

    inname,                  {Name of input file}

    outname: yarn;           {Name of output file}

    words: wd;               {Word under construction}

    ch: char;

    top,

    bottom: array[1..32] of ptr;

    last,

    newbuf,

    newline,

    endfile,

    buf: ptr;

    mask,

    masked,

    place,

    long,

    cd,

    cnt:  longint;

    infilepos,              {Current position in input file buffer}

    inbitpos,               {Current bit mask in input file buffer}

    inbytes,                {Actual number of bytes read}

    outfilepos,             {Current position in output file buffer}

    outbitpos,              {Current bit mask in output file buffer}

    outbytes:  word;        {Actual number of bytes to write}

    cmdparameter,           {Command line parameter number}

    start,                  {Starting point for command line file
name scan}

    strlen,

    bite,

    b, i, j, k, m: integer;

    squish, filefound, done: boolean;

    outbite:  byte;

    inbuf,

    outbuf: array[1..maxbuf] of byte;

    s: searchrec;           {Record fill: array[1..21] of byte;attr:byte;time,

                              size:longint;name: string[12]}



function exist(filename: yarn): boolean;

{Returns TRUE iff the file exists.}

var f: file;

begin {exist}

  assign(f,filename);

  {$I-}

  reset(f);

  {$I+}

  if IOresult = 0 then

    begin

      exist := true;

      close(f)

    end

  else

    exist := false;

end;  {exist}



procedure getbit(var b: integer);

begin

  if infilepos = 0 then

    begin

      if eof(infile) then

        done := true

      else

        begin

          blockread(infile, inbuf, maxbuf, inbytes);

          infilepos := 1;

          inbitpos := 1;

        end;

    end;

  if not done then

    begin

      b := inbuf[infilepos] and inbitpos;

      if b > 0 then b := 1;

      inbitpos := inbitpos shl 1;

      if inbitpos > 128 then

        begin

          inbitpos := 1;

          inc(infilepos);

          if infilepos > inbytes then infilepos := 0;

        end;

    end;

end;



procedure getbite(var b: integer);

begin

  if infilepos = 0 then

    begin

      if eof(infile) then

       begin

        done := true;

        b := 0

       end

      else

        begin

          blockread(infile, inbuf, maxbuf, inbytes);

          infilepos := 1;

        end;

    end;

  if not done then

    begin

      if inbitpos > 1 then

        begin

          inc(infilepos);

          writeln('Bit sync error in getbite!')

        end;

      b := inbuf[infilepos];

      inbitpos := 1;

      inc(infilepos);

      if infilepos > inbytes then infilepos := 0;

    end;

end;



procedure putbit(b: integer);

begin

  if (b > 1) or (b < 0) then writeln('Bad data passed to putbit.');

  outbite := outbite or (outbitpos * b);

  outbitpos := outbitpos shl 1;

  if outbitpos > 128 then

    begin

      inc(outfilepos);

      outbuf[outfilepos] := outbite;

      outbite := 0;

      outbitpos := 1;

      if outfilepos >= maxbuf then

        begin

          blockwrite(outfile, outbuf, maxbuf, outbytes);

          if outbytes < maxbuf then

            begin

              writeln('Disk full error.');

              done := true;

            end;

          outfilepos := 0;

        end;

    end;

end;



procedure putbite(b: integer);

begin

  if (b > 255) or (b < 0) then writeln('Bad data passed to putbite.');

  outbite := b;

  inc(outfilepos);

  outbuf[outfilepos] := outbite;

  outbite := 0;

  outbitpos := 1;

  if outfilepos >= maxbuf then

    begin

      blockwrite(outfile, outbuf, maxbuf, outbytes);

      if outbytes < maxbuf then

        begin

          writeln('Disk full error.');

          done := true;

        end;

      outfilepos := 0;

    end;

end;



procedure flushbit;

begin

  if outbitpos > 1 then

    begin

      inc(outfilepos);

      outbuf[outfilepos] := outbite;

    end;

  blockwrite(outfile, outbuf, outfilepos, outbytes);

  outbite := 0;

  outbitpos := 1;

  outfilepos := 0;

end;



function punct(ch: char): boolean;

{TRUE iff ch is not a letter or chr(255).}

  var c:  integer;

  begin

    c := ord(ch);

    if ((c > 10) and (c <= 64)) or ((c >= 91) and (c <= 96))

    or ((c >= 123) and (c <= 254)) or ((c > 0) and (c < 10)) then

      punct := true

    else

      punct := false;

  end;



function letter(ch: char): boolean;

{TRUE iff ch is a letter A-Z or a-z.}

  var c: integer;

  begin

    c := ord(ch);

    if ((c >= 65) and (c <= 90)) or ((c >= 97) and (c <= 122)) then

      letter := true

    else

      letter := false;

  end;







procedure parse(var words: wd; var ch: char);

{Extracts a word or item of punctuation from input file.}

  var byt: integer;

  begin  {parse}

    words := '';

    while not (letter(ch) or punct(ch) or done) do

      begin

        getbite(byt);

        ch := chr(byt);

      end;

    if punct(ch) then

      begin

        if ord(ch) = 13 then

          begin

            words := chr(255)+chr(255);

            if not done then begin getbite(byt); ch := chr(byt) end;

          end

        else

          if ch = ' ' then

            begin

              words := ch;

              while (not done) and (ch = ' ') and (length(words) < maxstr) do

                begin

                  getbite(byt);

                  ch := chr(byt);

                  if ch = ' ' then words := words + ch;

                end;

              if (length(words) = maxstr) and (not done) then

                begin

                  getbite(byt);

                  ch := chr(byt)

                end;

            end

          else

            begin

              words := ch; {return one punctuation character}

              if not done then begin getbite(byt); ch := chr(byt) end;

            end;

      end

    else

      begin

        if letter(ch) then

          begin

            words := ch;

            while (not done) and letter(ch) and (length(words) < maxstr)
do

              begin

                getbite(byt);

                ch := chr(byt);

                if letter(ch) then words := words + ch;

              end;

            if (length(words) = maxstr) and (not done) then

              begin

                getbite(byt);

                ch := chr(byt)

              end;

          end;

      end;

  end;  {parse}



begin

  clrscr;

  writeln('  SQUEEZE is designed to remove         This program may
be copied freely ');

  writeln('  redundancy from ASCII text files,     for educational
use or to try it  ');

  writeln('  making them smaller for transmission  out.  If you like
it, donations   ');

  writeln('  and storage.  It also improves the    will be accepted
by the author.   ');

  writeln('  security of files encrypted after     This program is
believed to be    ');

  writeln('  SQUEEZING.  It uses LANGUAGE.COD,     reliable, but it
is the user',ap,'s    ');

  writeln('  created with COUNT and MAKETREE.      responsibility
to determine its   ');

  writeln('                                        fitness for use.  No
liability    ');

  writeln('  Mike Johnson                          will be assumed
by the author.    ');

  writeln('  P. O. Box 1151                        Copyright (C) 1988
Mike Johnson.  ');

  writeln('  Longmont, CO 80502-1151               All rights reserved.              ');

  if (paramcount < 3) then

    begin

      writeln;

      writeln('Syntax: SQUEEZE a|s|u|x outputfile inputfile(s)');

      writeln('a and s both mean add or squash, u and x both mean
unsquash or extract.');

      writeln('Input and output files must be different.');

      writeln('Input file name(s) may include wild cards.');

      writeln('LANGUAGE.COD  (made with MAKETREE) must be in default
directory.');

    end

  else

    begin

      {Read in language code dictionary.}

      assign(infile,'LANGUAGE.COD');

      reset(infile,1);

      infilepos := 0;

      inbitpos := 1;

      done := eof(infile);

      newline := nil;

      last := nil;

      endfile := nil;

      if paramcount >= 1 then

        temp := paramstr(1)

      else

        temp := 'X';

      temp := upcase(temp[1]);

      if (temp = 'A') or (temp = 'S') then

        squish := true

      else

        squish := false;

      writeln('Reading in LANGUAGE.COD.');

      for i := 1 to 32 do

        begin

          new(top[i]);

          top[i]^.wrd := '';

          top[i]^.count := 0;

          top[i]^.code := 0;

          top[i]^.next := nil;

          bottom[i] := top[i];

        end;

      last := nil;

      while not done do

        begin

          new(newbuf);

          newbuf^.wrd := '';

          getbite(strlen);

          if not done then

            begin

              for i := 1 to strlen do

                begin

                  getbite(bite);

                  newbuf^.wrd := newbuf^.wrd + chr(bite);

                end;

              getbite(bite);

              newbuf^.count := bite;

              getbite(bite);

              newbuf^.code := bite;

              if newbuf^.count > 8 then

                begin

                  getbite(bite);

                  long := bite;

                  newbuf^.code := newbuf^.code + (long shl 8);

                  if newbuf^.count > 16 then

                    begin

                      getbite(bite);

                      long := bite;

                      newbuf^.code := newbuf^.code + (long shl 16);

                      if newbuf^.count > 24 then

                        begin

                          getbite(bite);

                          long := bite;

                          newbuf^.code := newbuf^.code + (long shl
24);

                        end;

                    end;

                end;

              newbuf^.next := nil;

              if newbuf^.wrd = chr(255) then

                begin

                  last := newbuf;

                end

              else

                if newbuf^.wrd = chr(255) + chr(255) then

                  newline := newbuf

                else

                  if newbuf^.wrd = chr(255) + chr(255) + chr(255)
then

                    endfile := newbuf;

              if squish then

                begin

                  if ord(newbuf^.wrd[1]) > 107 then

                    i := length(newbuf^.wrd) + 15

                  else

                    i := length(newbuf^.wrd)

                end

              else

                i := newbuf^.count;

              bottom[i]^.next := newbuf;

              bottom[i] := newbuf;

              write(#13,newbuf^.wrd,'                     ');

            end;

        end;

      if newline = nil then

        writeln('Error:  newline symbol not in LANGUAGE.COD! ');

      writeln;

      close(infile);



      {Initialize input & output files and global variables.}

      outname := paramstr(2);

      filefound := false;

      assign(outfile,outname);

      if exist(outname) then

        begin

          reset(outfile,1);

          seek(outfile,filesize(outfile))

        end

      else

        rewrite(outfile,1);



      outfilepos := 0;

      outbitpos := 1;

      outbite := 0;

      if squish then start := 3 else start := 2;

      for cmdparameter := start to paramcount do

        begin

          filespec := paramstr(cmdparameter);

          filemask := filespec;

          path := '';

          repeat

            i := pos('\',filemask);

            if i > 0 then

              begin

                path := path + copy(filemask, 1, i);

                filemask := copy(filemask, i+1, length(filemask));

              end;

          until i = 0;

          findfirst(filespec, readonly + hidden + archive, s);

          while doserror = 0 do

            begin

              filefound := true;

              inname := path + s.name;

              assign(infile, inname);

              reset(infile,1);

              infilepos := 0;

              inbitpos := 1;

              done := eof(infile);



              {Perform compression on input file(s).}

              if squish then

               begin

                writeln('Compressing ',inname);

                ch := chr(0);

                while not done do

                  begin

                    parse(words,ch);     {Find word or punctuation}

                    if length(words) > 0 then

                      begin

                        if ord(words[1]) > 107 then

                          buf := top[length(words) + 15]

                        else

                          buf := top[length(words)];

                        mask := 1;

                        while (buf^.wrd <> words) and (buf^.next <>
nil) do

                          buf := buf^.next;

                        if buf^.wrd <> words then

                          begin

                            highvideo;

                            if words = chr(255) + chr(255) then

                              writeln('Newline code not found in tree!
')

                            else

                              write(words);

                            for i := 1 to last^.count do

                              begin

                                masked := last^.code and mask;

                                mask := mask shl 1;

                                if masked = 0 then

                                  putbit(0)

                                else

                                  putbit(1);

                              end;

                            for i := 0 to length(words) do

                              begin

                                for j := 0 to 6 do

                                  begin

                                    b := (ord(words[i]) shr j) and
1;

                                    putbit(b)

                                  end;

                              end;

                          end

                        else

                          begin

                            for i := 1 to buf^.count do

                              begin

                                masked := buf^.code and mask;

                                mask := mask shl 1;

                                if masked = 0 then

                                  putbit(0)

                                else

                                  putbit(1);

                              end;

                            lowvideo;

                            if words = chr(255) + chr(255) then

                              writeln

                            else

                              write(buf^.wrd);

                          end;

                    end;

                  end;

                mask := 1;

                for i := 1 to endfile^.count do

                  begin

                    masked := endfile^.code and mask;

                    mask := mask shl 1;

                    if masked = 0 then

                      putbit(0)

                    else

                      putbit(1);

                  end;

               end

              else



                {Decompress input file.}

                begin

                  writeln('Decompressing ',inname);

                  cd := 0;

                  mask := 1;

                  cnt := 0;

                  while not done do

                    begin

                      getbit(b);

                      if b > 0 then cd := cd or mask;

                      mask := mask shl 1;

                      if mask <= 0 then writeln('Error: code too long.');

                      inc(cnt);

                      buf := top[cnt];

                      while (buf^.next <> nil) and

                            ((cnt <> buf^.count) or (cd <> buf^.code))
do

                        buf := buf^.next;

                      if (cnt = buf^.count) and (cd = buf^.code) then

                        begin

                         if buf = endfile then

                          done := true

                         else

                          if buf^.wrd = chr(255) then

                            begin

                              j := 0;

                              for k := 0 to 6 do

                                begin

                                  getbit(b);

                                  j := j + (b shl k);

                                end;

                              for i := 1 to j do

                                begin

                                  m := 0;

                                  for k := 0 to 6 do

                                    begin

                                      getbit(b);

                                      m := m + (b shl k)

                                    end;

                                  putbite(m);

                                  highvideo;

                                  write(chr(m));

                                end;

                            end

                          else

                           if buf^.wrd = chr(255) + chr(255) then

                            begin

                             writeln;

                             putbite(13);

                             putbite(10);

                            end

                           else

                            begin

                              for i := 1 to length(buf^.wrd) do

                                begin

                                  b := ord(buf^.wrd[i]);

                                  putbite(b)

                                end;

                              lowvideo;

                              write(buf^.wrd)

                            end;

                          cd := 0;

                          cnt := 0;

                          mask := 1;

                        end;

                    end;

                end;



              {Finish up or loop back for more work to do.}

              flushbit;

              close(infile);

              findnext(s);

            end;

        end;



      if not filefound then writeln('No matching files found.');

      flushbit;

      close(outfile);

    end;

end.



{That's all, folks!}