with the strongest line of data file and message encryption software available.


          1. INTRODUCTION

               There have been many cryptographic methods invented since writing
          itself was developed.  This overview is designed to give prospective users
          of a cryptographic system a broad idea of where their system fits into the
          whole spectrum of cryptographic methods and algorithms.  It also can give
          them an idea of how strong a particular method might be in relation to
          other methods, and a general concept of how the strength of a cryptographic
          system can be judged.

               We have tried to write this overview using a minimum of math, so that
          non-technical readers can understand most or all of the material.  None of
          the subjects is covered to any depth, in the hope that the entire survey
          can be read in less than 1 hour.

               This treatment deals only with the different kinds of algorithms or
          methods used in cryptography.  There are many other considerations that go
          into choosing a cryptographic algorithm.  Most older methods are intended
          only for sending hand-written messages.  Among modern methods, some are
          best-suited for protecting files on a computer, others are suited for
          encrypting messages, while others are specialized for exchanging
          cryptographic keys.

               These issues are considered elsewhere on this website.  See
          www.mastersoftware.biz/crypt-ch.htm for example.


          1. INTRODUCTION

            2.1. Secret Method Cryptography
            2.2. Inherent Key Cryptography
            2.3. Hidden Key Cryptography
              2.3.1. No key required

            3.1. Substitution Ciphers
              3.1.1. Data Encryption Standard (DES)
              3.1.2. Advanced Encryption Standard (AES)
              3.1.3. GK-Crypt
              3.1.4. Linearity
            3.2. Transposition Ciphers
            3.3. Stream Ciphers
              3.3.1. Random numbers
              3.3.2. One-time pad
              3.3.3. OP-Crypt




               Most cryptographic methods, from ancient to modern, fall into a few
          broad classes:

               Secret method
               Inherent key
               Hidden key
               Secret key
               Public key
               Private key

               In secret method cryptography the strength of the cipher comes from
          keeping the method itself secret.  Most of the encryption methods of
          ancient times, such as the atbash cipher mentioned in "The DaVinci Code,"
          were secret method ciphers.

               Inherent key methods rely on a secret key that is built right into the
          device, or right into the software.  The scytale or skytale used by the
          pharaohs of ancient Egypt was an inherent key device; the diameter of the
          cylinder was the key.  Some of the machine ciphers used during World War II
          were of this type.  The machine would be constructed using a moving chain
          with lugs, or a turning wheel with pins that drove the mechanism.  The
          chain or wheel could have billions of possible settings.  When the
          government bought the machine, technicians would set the lugs or pins to
          some fixed arrangement before issuing the machines to the field.  All of
          the machines in use would be fixed at the same setting.

               Hidden key methods depend on hiding the key for their strength.  The
          most common method is to hide the key within the message itself.  For
          example, it might be agreed that the fifth block of the message would
          contain the key.  A more sophisticated variant is to combine the
          information hidden in the message with some other information, such as the
          date when the message was sent, to form the key.  In modern computer file
          encryption programs, the key is sometimes placed in a key file which may be
          encrypted with some inherent key method.  A slightly stronger version uses
          a control file which contains the name of the key file, so the user can
          give the key file any desired name, for example an innocent-sounding name
          like chicken_recipe.

               Secret key methods get their strength from a secret key that is shared
          by the sender and the receiver of the message.  Users may try to keep the
          method secret, but they don't rely on that.  The strength rests in the key,
          which must be carefully chosen.  Secret key methods are sometimes called
          symmetric because the sender and the receiver use the same key.

               Public key methods rely on mathematical functions which are called
          one-way functions because they are easy to compute, but very difficult to
          reverse.  One example is multiplying two large prime numbers.  (Prime
          numbers are numbers that cannot be formed by multiplying two other numbers
          that are both greater than 1.  So 2, 3, 5, 7, 11 and 13 are prime, but
          4=2x2, 6=2x3 and 9=3x3 are not prime.)  It is easy for a computer to
          multiply two 100-digit primes to get a 200-digit product, but very hard to
          find those 100-digit primes if you are given the 200-digit product.  Each
          user of the public key system will have a public key, known to everyone,
          that people can use to send messages, and a private key that is used to
          read the messages.  Public key methods are sometimes called asymmetric
          methods because the sender and receiver use different keys.

               Private key cryptography is the newest form.  In private key methods,
          the sender and the receiver each have a separate private key, known only to
          themselves, and not known to each other.  The sender encrypts the message
          with the sender's private key.  Then certain mathematical functions are
          used to change the message so that the sender's private key is removed and
          replaced by the receiver's private key.  This allows the receiver to
          decrypt and read the message.

               You can imagine the message as a jewel in a strongbox with two locks.
          First the sender's lock is placed on the box, then the receiver's lock is
          added.  When the sender's lock is removed the receiver can remove his own
          lock to obtain the jewel.  The NK-Crypt and N2-Crypt encryption packages
          use mathematical functions that can accomplish this securely.

               The following sections will discuss these classes of encryption
          methods in more detail.

          2.1. Secret Method Cryptography

               In Secret Method cryptography, the method, and often the fact that
          cryptography is being used, are kept secret.  This is its only source of
          security.  One example is a cipher designed for young children where A is
          represented by a picture of an apple or an ape, B is represented by a bird
          or a boat, C by a carrot or a cat, and so forth.  A message is a series of
          such pictures.  The method is useful for teaching children the sounds of
          the letters, but offers no secrecy.

               Secret method cryptography is primarily of historic interest.  In
          ancient times, the message might be worked into the design on the
          messenger's clothing, or written on the messenger's shaved scalp.  In the
          weeks it took to deliver the message, the hair would grow back and conceal
          the message.  A modern analogue would be the hidden patterns on the backs
          of marked playing cards.

               Secret method cryptography, no matter how clever, is not considered
          safe because anyone who learns the method or obtains a copy of the device,
          can read all of the messages, both past and future.

               Unfortunately, some of the computer encryption methods in use today
          are still of this type.  For example, one method is to exclusive-or
          (combine) the contents of each computer file with its file name, scrambled
          in a fixed manner, over and over.  For such weak secret key methods, simply
          obtaining a single message and its translation would allow an opponent to
          break the system.  Once broken, a secret method is broken forever, since
          there are no keys the users can change to prevent reading future messages.

               These methods are still occasionally used either because the maker is
          not aware of the danger, or because secret method encryption is both easy
          to implement and easy to use.  If an encryption product says that no keys
          are needed, and no secret files are used, then it is a good bet that it is
          a secret method product.

          2.2. Inherent Key Cryptography

               Inherent Key methods rely on a secret key that is built right into the
          device, or right into the software.  The turning grille cipher, which was
          used from the 17th through the early 20th centuries was an inherent key
          device.  It used a thin square metal sheet with holes cut in it at various
          spots.  The sender would place the grille over a sheet of paper, and write
          one letter of the message through each hole.  When all of the holes had
          been used, the grille would be turned and letters would be written through
          the holes in their new positions.  The receiver would read the message the
          same way.

               The positions of the holes constitute the secret key.  Since the holes
          cannot be moved, the key is inherent in the device itself.

               Inherent key cryptography is nearly as weak as secret method
          cryptography.  It is not considered safe because anyone who obtains a copy
          of the same software, or the same device, can read all of your messages,
          both past and future.  Thus the vendor, any government agency, and even any
          other purchaser could read your files.

               Some inherent key software products are distributed with a different
          key built into each copy of the program, just as combination locks are sold
          with different settings.  This is better, but anyone who copies the
          software from your computer, or from a backup disk, or from your online
          backup service, can read all of your files or messages.

               Since inherent key cryptographic products are generally produced by
          people with little knowledge of cryptography, the built-in keys and the
          encryption method are also likely to be weak.

               Once again, if the product says that no keys or passwords are
          required, be very wary.  It is not likely to be a strong product.

          2.3. Hidden Key Cryptography

               Hidden Key methods depend on hiding the cryptographic key for their
          strength.  It is like people hiding the keys to their home under the
          doormat, on the lintel, or inside a fake stone in a flowerpot.

               Hidden key cryptographic software is now very popular with the
          less-experienced suppliers of privacy products.  It offers the user the
          convenience of not needing to enter a password or keyword each time the
          software is used, but this convenience comes with the price of reduced

               These products typically keep the key in a file that is itself
          encrypted with an inherent key that is built into the program.  Anyone who
          gets access to your computer, or to your backup disks, can copy that key
          file, and then can read your files or your messages.

               There is nothing inherently wrong with the idea of storing file keys
          or message keys in a key file, sometimes called a master file.  Many of the
          best encryption products also do this.  But the master file must itself be
          protected with a strong key, sometimes called a master key, otherwise the
          file keys are vulnerable.  The master key must not be an inherent key (see
          the preceding section) or a hidden key, but must be a secret key kept by
          the user.

               Some products will take the hidden key idea several steps.  They will
          have separate key files, which are encrypted with key file superkeys kept
          in a superkey file, which is encrypted with a master key stored in a hidden
          file whose name is stored in a control file which is encrypted with an
          inherent key.  This is still not safe!!  Someone who gets access to your
          computer, or to some other computer on your local network, can use the
          encryption software on your computer to read your files.  They don't need
          any keys or special knowledge to do this, because the encryption software
          already has that ability built in.

               As long as the top-level key is kept on your computer, whether it is
          in a key file or built into the encryption software, someone can find that
          key and use it to read your files.

          2.3.1. No key required

               The same blanket warning applies equally to all cryptographic packages
          that can be run without entering a key or password.  These products may use
          secret method cryptography, inherent key cryptography, or hidden key
          cryptography.  Use caution.  If the product says that no keys or passwords
          are required, then you are taking a serious risk.  If the product allows
          only a short password, then you are taking a serious risk.  If the product
          allows long passwords, but you choose a short simple password, then you are
          taking a serious risk.

               The risk is present even when a very strong encryption algorithm is
          being used.  For example, a disk encryption product may use 256-bit AES
          encryption, and automatically produce the 256-bit key using the latest
          random-number generating techniques, but if the user can access the
          contents of the disk without a password, or by using at most a simple
          password, then the product is not safe.


               Nearly all of the cryptographic methods developed over the past 400
          years are secret key methods.  Nearly all of the cryptographic methods in
          use today by govermments, and especially by the military, are secret key

               Secret key methods generally fall into two classes, block ciphers and
          stream ciphers.  Block ciphers are further divided into substitution
          ciphers and transposition ciphers.

               Substitution ciphers take blocks of one or more characters at at time
          and replace them with other blocks according to some fixed rule.  The most
          common example is the simple substitution cipher, often found on newspaper
          puzzle pages, where each letter of the alphabet is consistently replaced by
          a different letter of the alphabet.  A slightly more complex example might
          use a table of 2-letter or 3-letter combinations, and use that table to
          substitute for 2 or 3 letters of the message at a time.

               Transposition ciphers change the order of the characters in a message.
          A simple example is where the letters of the message are written into a
          rectangular grid going left to right across the rows.  Then the letters are
          taken out of the grid going top to bottom down the columns.  As a general
          rule, ciphers that use only transposition, no matter how complex, are not
          considered secure.  The transposition must be combined with other
          encryption steps to be secure.

               Stream ciphers generate a stream of keys, such as letters or numbers.
          Each key in the stream is used to encrypt one character of the message.  In
          classical methods the key stream was simply some key word or key phrase
          repeated over and over for the length of the message.  The most common
          modern method is to use a random number generator to produce the stream of
          keys.  As a general rule, the random number generators used in most
          statistical applications are not strong enough to produce a secure

          3.1. Substitution Ciphers

               Substitution ciphers generally take one character or block of
          characters at a time and replace it with another.  The simplest form of
          substitution cipher uses a table in which all of the blocks of a given size
          appear in scrambled order.  You replace a given block with the
          corresponding block from the table.  For example, using blocks of 3
          uppercase letters (trigrams), you might have

               AAA  WCY
               AAB  GNR
               AAC  TDW
               AAD  ZOF

          Various methods are used to make this type of substitution depend upon the
          key.  For example the key could be used to scramble the order of the blocks
          in either or both of the lists.

               The table method becomes impractical for blocks of more than 3
          characters, especially on computers, where there are 256 different
          characters rather than 26.  A table of 4-character blocks would contain
          256x256x256x256 entries, or about 4.3 billion entries, each containing 4

               For larger blocks of characters the substitution is usually
          accomplished by doing a series of operations on single characters or pairs
          of characters within the block.  A simple example using blocks of N
          characters would use a table of pairs.  First the pair 1,2 is substituted,
          then the pair 2,3, and so forth.  When the end of the block is reached, it
          would wrap around using pair N,1.  This method starts to be secure when at
          least 5 complete cycles are taken, particularly if a different pair
          substitution table is used for each round.  Here is an example of one round

               COMPUTER      CO becomes XM
               XMMPUTER      MM becomes KD
               XKDPUTER      DP becomes RH
               XKRHUTER      HU becomes FL
               XKRFLTER      LT becomes BC
               XKRFBCER      CE becomes WT
               XKRFBWTR      TR becomes SV
               XKRFBWSV      VX becomes LD

          3.1.1. Data Encryption Standard (DES)

               Some modern block substitution ciphers are the Data Encryption
          Standard (DES), the Advanced Encryption Standard (AES), and the newer
          GK-Crypt algorithm.  The Data Encryption Standard treats each block of 8
          bytes, or 64 bits, as 16 units of 4-bits each.  (4-bit units are sometimes
          called nibbles or nybbles.)  The left half of the block is used to generate
          eight 4-bit quantities.  These 32 bits are permuted (shuffled) in a fixed
          manner and then exclusive-ored (combined) with the right half.  Then the
          left and right halves are swapped, and this operation is repeated for 16
          rounds.  (There are also some bit permutations at the beginning and end,
          but they add no strength.  They are there to make the encryption hard to
          simulate in software.)

               The DES was state-of-the-art for the mid-1970's, but its small 56-bit
          key size made it obsolete by about 1990.  The trend has been away from
          bitwise hardware-oriented encryption.

          3.1.2. Advanced Encryption Standard (AES)

               The Advanced Encryption Standard (AES) is also a block cipher, using a
          block size of 16 bytes, or 128 bits, and a key size of 128 bits in current
          implementations.  The key may be increased to 192 bits or 256 bits in the
          future, when 128 becomes inadequate.  The first step in AES is to expand
          the key to 128 bytes, to make 10 round keys of 16 bytes each.  This is done
          by performing repeated substitution and exclusive-or operations on the key

               The 10 round keys are then used to perform 10 rounds of encryption.
          Each round consists of 3 steps.  First the message is combined with the key
          using an exclusive-or operation.  In the second step the 16-byte message is
          considered as 4 words of 4 bytes each.  These 4 words are shifted left by
          1, 2, 3 and 4 byte positions, respectively.  In the third step each column
          of the 4x4 block of bytes is mixed using a linear transformation, that is,
          each column vector is multiplied by certain matrix of values.

               This last step is called a Hill cipher for Lester Hill who invented it
          around 1920.  It was used by both the US and Russian military in the period
          between the two World Wars.  Methods for breaking the Hill cipher were
          developed by Jack Levine at UNC Raleigh.

               Some features of the AES are (1) it has a fixed block size, (2) it
          uses the same key for every block, (3) it uses the same permutation in
          every round, (4) the permutations are simple shifts applied within a single
          4-byte word.

          3.1.3. GK-Crypt

               The new GK-Crypt encryption algorithm is also a block cipher, using 9
          rounds of substitution and permutation.  Version 1 of GK-Crypt uses
          16-byte, or 128-bit blocks, and 80-byte, or 640-bit keys.  Version 2 of
          GK-Crypt uses variable-length blocks of 16 to 32 bytes, or 128 to 256 bits,
          and 640-bit keys.  The first step in GK-Crypt is to expand the key from 80
          bytes to 360 bytes for version 1, or to 690 bytes for version 2.

               Like the DES and the AES, each round of GK-Crypt begins by combining
          the message with the key for that round.  Then each byte of the message is
          combined with another message byte.  In version 1 of GK-Crypt, this is done
          in a fixed way, which is the same for every round.  In version 2 of
          GK-Crypt, the choices of which bytes to combine depend on the key for each
          round.  Finally, the message block is permuted (shuffled).  Unlike both DES
          and AES, this is done in a key-dependent way, and is different for each

               After each block has been encrypted, a new key is generated for the
          next block.  This process also uses a sequence of substitutions and
          key-dependent permutations.  A separate portion of the key is set aside for
          generating the next key, and this portion is also changed for each new
          block.  This means that not only is the key for the next block different,
          but the transformation to generate the next key is also different.

               GK-Crypt is much stronger than AES, or even quadruple AES, because (1)
          it has a variable block size, (2) it uses a different key for every block,
          (3) it uses a different permutation in every round, (4) it permutes the
          entire block in a complex way.

          3.1.4. Linearity

               Linearity is an important concept in the design of all substitution
          ciphers.  It can be illustrated by the familiar process of flipping a coin.
          Suppose that you flip a fair coin 100 times, and you get 56 heads.  You
          immediately know that you got 44 tails, because the number of heads plus
          the number of tails always add up to the total number of flips.  Addition
          is a linear function.

               The exclusive-or operation which is widely used in computer
          cryptography is also a linear function.  When a message byte and a key byte
          are exclusive-ored, the bits of each byte are lined up.  Everywhere that
          there is a 1 in the key byte, the corresponding bit of the message is
          inverted.  That is, if the message bit was a 0 it becomes a 1, and if it
          was a 1 it becomes a 0.  Everywhere there is a 0 in the key, the
          corresponding bit of the message stays unchanged.

               Message  0 0 0 0 1 1 1 1
               Key      0 1 1 0 1 0 0 1
               Result   0 1 1 0 0 1 1 0

               For cryptography, linear functions are the weakest kind.  Systems of
          linear equations are easy to solve.  The methods have been known for
          hundreds of years.  (Notice that the matrix multiplication step of the AES
          is a purely linear operation.)  Therefore, if an encryption method can be
          described by linear equations, and a few characters of the message are
          known, it is easy to solve the linear equations and determine the key.
          That let's you find the rest of the message.

               When one bit of the key in a linear system changes, a fixed set of
          bits in the message will all change simultaneously.  This is a weakness
          which is easy to exploit.  For example, if the same message has been
          encrypted with 2 different keys, an attacker can look at which bits are the
          same in each message, and which bits are different, and determine a good
          deal about the keys.

               The ideal in cryptography is to have a perfectly non-linear system.
          In such a system, when one bit of the key changes, or any combination of
          key bits change, each bit of the cipher message will have exactly a 50-50
          chance of changing.

               A perfect non-linear substitution is not possible, but every
          well-designed encryption system tries to make its substitutions as
          non-linear as possible.  The 8 S-boxes (substitution functions) in DES are
          highly non-linear.  The substitution table in AES has been mathematically
          designed to be highly non-linear.  However, this mathematical regularity
          means that the substitution can be described by a mathematical function,
          which is itself a weakness.

               GK-Crypt strikes a balance between strong non-linearity and
          mathematical regularity.  GK-Crypt uses 3 substitution tables.  One is
          highly structured, similar to the AES table, and the other two are somewhat
          random.  All 3 tables were constructed to be strongly non-linear.  They
          have been chosen so that they are also as independent as possible from one
          another.  That is, there are no strong linear relationships between the 3
          tables.  Such relationships might also weaken the encryption.

          3.2. Transposition Ciphers

               The best-known transposition ciphers are the route ciphers.  In a
          typical route cipher, the letters of the message are written into a
          rectangular grid one at a time, going across the rows, something like this

               T H I S I S A
               R O U T E C I
               P H E R

          Then the letters will be read out of the grid in a different order, for
          example, reading down the columns


          or diagonally


          or reading alternately up and down the columns


               The Union used these types of route ciphers in the US Civil War, and
          it is believed that they were never broken by the Confederacy.  Today,
          these simple route transpositions make fairly elementary hobbyist ciphers,
          easily solved by paper and pencil methods.

               In the late 19th century the first transposition cipher utilizing a
          key was developed.  It is called a columnar transposition, or more
          precisely, a complete columnar transposition if all of the columns are the
          same length, and an incomplete columnar transposition otherwise.  The
          letters of the message are written into a rectangular grid, as before, but
          this time the columns are numbered in some order.  This numbering of the
          columns is the key.

               3 7 1 6 4 8 2 5
               T H I S I S A C
               O L U M N A R T
               R A N S P O S I
               T I O N

          The letters are read out of the grid by reading down the columns, but the
          columns are taken out in the order specified by the key.  In this example,
          the column numbered 1 is read out first, IUNO, then the column numbered 2,
          ARS, and so forth.


          This is a major improvement over the route transposition, but this type of
          cipher can still be solved by skilled hobbyists using paper and pencil

               Double columnar transposition was used by the US, Germany, and other
          nations from about 1900 to 1945.  The message was scrambled by a columnar
          transposition, and that message was scrambled again by a second columnar
          transposition, usually using the same key for both steps.  The French broke
          the German version, but it is believed that the Germans did not break the
          American version.  Today advanced hobbyists routinely solve such messages
          using paper and pencil.

               In general, a transposition cipher by itself, no matter how
          sophisticated, is not secure.  However, in the 1890's a French
          cryptographer named Etienne Bazeries showed that even a simple
          transposition cipher combined with a simple substitution cipher could
          provide a decent degree of security.  This fact is at the heart of most
          modern block ciphers, including the AES and GK-Crypt.

          3.3. Stream Ciphers

               The basic idea in a stream cipher is that each character in a message
          is enciphered using one character of the key.  The first stream ciphers,
          which were called polyalphabetic ciphers, were developed in the 16th to
          18th centuries.  They used a short key, such as a single word, which was
          repeated as many times as needed for the length of the message.  Typically,
          the key word would be written across the top of the page during encryption,
          and the message would be written in columns beneath it, leaving blank lines
          for writing in the encrypted message.

               Most of these classical stream ciphers used a substitution table, or
          tableau.  For English this is normally a 26x26 grid of letters.  Each of
          the 26 rows contains the 26 letters of the alphabet in some order.  For the
          simpler ciphers, the letters might be the normal alphabet shifted by one
          position, left or right for each successive row, or written backwards and
          shifted.  For the more sophisticated versions, each row might be scrambled.
          To encrypt one letter of the message, the letter would be found on the top
          row of the grid, and the key letter would be found along the left column of
          the grid.  The letter lying in the same column as the message letter, on
          the row corresponding to the key letter would be the enciphered letter.

               Decryption would be the reverse process.  The key letter would be
          found along the left edge, and the encrypted letter would be found in the
          corresponding row.  Then the letter at the top of that column would be the
          letter from the original message.

               Slightly more complex variations of these classical ciphers would have
          the message letter written on an index row above the top row of the grid,
          and the key letters written in an index column to the left of the grid.
          This provided for more keying possibilities because different index rows
          and columns could be used with any grid.

               Most modern stream ciphers are simply elaborations on these
          principles.  The message is combined character-by-character with the key
          stream to produce the encrypted message.  In some of the oldest and weakest
          systems, the key stream was produced by taking the keyword and cycling the
          bits around.  That is, the leftmost bit of a character would be moved to
          the righthand end, and the rest of the bits would be moved left one
          position.  This would form the next character of the key stream.

               One of the simplest techniques was to use the file name, followed by
          the file name with each character cycled 1 bit position, then 2 bit
          positions, etc., until, after 8 shifts, it was back to the original file
          name.  This produced a repeating key that was 8 times as long as the file
          name.  This method is scarcely any stronger than the 16th century method of
          repeating the keyword over and over.

          3.3.1. Random numbers

               Far more common is to use a random number generator to produce the key
          stream.  The two most common forms of random number generators, more
          properly called pseudorandom number generators, are linear congruential and
          linear feedback generators.  These will be described briefly, since a more
          detailed treatment would require deeper math.

               There is one basic mathematical concept that needs to be introduced in
          order to understand linear congruential generators.  This is the idea of
          modular division.  If n and p are positive integers, then the residue of n
          modulo p means the remainder when n is divided by p.  For example, if n is
          42 and p is 10, then the residue of n modulo p is 2.  This is denoted 42 =
          2 (mod 10).

               The basic idea in a linear congruential generator is that you start
          with some number, called the seed, then you multiply this number by a fixed
          multiplier, add a fixed constant, and then take the residue of this
          quantity modulo a fixed divisor.  The result is the next random, or
          pseudorandom, number.  This number becomes the next seed, and the process
          can be repeated to get a sequence of pseudorandom numbers.

               The process can be denoted as

               mr + c (mod d).

          Here m is the multiplier, r is the last random number, c is the constant,
          and d is the divisor.  The operation mod indicates the modular division or
          remainder operation.

               There are two types linear congruential generators that are most
          commonly used in practice.  The most common type uses a prime number as the
          modular divisor.  This prime is usually made as large as one computer word
          can hold.  When the divisor is a prime the constant c is usually 0.

               As a simple example, let d be 7, let m be 2, and let c be 0.  Start
          with a seed value of 1.  The next term will be 2x1(mod 7), or 2(mod 7),
          which is just 2.  The third term will be 2x2(mod 7), which is 4.  The
          fourth term is 2x4(mod 7), or 8(mod 7), which is 1.  Since the first and
          fourth terms are the same, the sequence will repeat.  We say that the
          period of the sequence is 3, since it contains just 3 numbers 1, 2, 4 that
          repeat endlessly.  When 7 is the divisor 2 is not a good choice for the
          multiplier, since the period is only 3.  If 3 were chosen as the
          multiplier, then the sequence would be 1, 3, 2, 6, 4, 5 with a period of 6.
          So 3 is a better choice.

               The second common type of linear congruential generator uses a power
          of 2 as the divisor.  In this case c must be an odd number, and the
          multiplier m must be one of the numbers 5, 9, 13, etc.  This type of
          generator is faster than the prime generators because the modular division
          can be done very fast with a power of 2.

               The values of m, c and d must be carefully chosen so that the
          generator will have good random properties, and will have a long period,
          that is, will generate many numbers before repeating.  There are many
          statistical tests that can be used to test the random properties of such a
          generator.  Random number generators of this type generally have good
          distribution properties, but do poorly on what is called the runs-up test.
          They tend to produce sequences of increasing numbers, such as 2, 19, 31,
          177, 2161, 327648, 471255, etc., that are too long for real randomness.

               More importantly, linear congruential generators are not
          cryptographically strong.  Each term in the sequence is determined from
          just the one term before, and that term fits within a single computer word,
          usually no more than 32 bits.  It is easy for an attacker to try all 232
          values until the correct seed is guessed.

               The data which is used to calculate the terms in the sequence is
          called the internal state of the generator.  With a 32-bit computer 1 bit
          is used for the sign of the number and the other 31 bits

               In order to achieve today's standard of 128-bit security, it is
          necessary to add together the outputs of at least 5 linear congruential
          generators.  These 5 generators may all use the same value of p, but they
          must use different values of m.  Naturally, using 5 generators takes 5
          times as long to compute each random number.

               Another type of random number generator is the linear feedback random
          number generator.  This type of generator uses a larger seed of k computer
          words, x1, x2, x3, ..., xk.  Each new term in the sequence is generated by

               xn = xn-a $ xn-b $ xn-c $ ... $ xn-k

          Here $ represents some combining operation, usually addition or
          exclusive-or.  The terms xn-a, xn-b, etc., represent one or more of the
          last k terms of the sequence.

               Sometimes a more general linear function is used, such as

               xn = c1xn-1 + c2xn-2 + ... + ckxn-k

          where c1, c2, etc. are integer coefficients (multipliers).  Usually most of
          these coefficients will be 0 for the sake of speed.

               The problem with all of the linear feedback generators is that the
          random numbers can be expressed by linear equations, and linear equations
          are easy to solve.  Given a small amount of known, or guessed text, an
          attacker can solve the equations to determine the seeds.  Once the seeds
          are known, the entire random key stream is known, so the entire message can
          be read.

               The bottom line is that neither type of random number generator is
          safe.  Linear congruential generators have small seeds which can be
          exhaustively tried.  Linear feedback generators have large seeds, but lead
          to simple equations that are easily solved.

          3.3.2. One-time pad

               The original One-Time Pad was an encryption method where each
          character of the message was combined with a separate character from the
          keystream.  It is called "one-time pad" because secret agents were actually
          sent into the field with pads of special water-soluble paper on which
          hundreds of completely random characters were written.  These characters
          were used as keys which could be used for encrypting a message by the
          tableau method described above.  After each message was sent, the agent
          would flush away that sheet.  The person receiving the message would use an
          identical sheet, perhaps a carbon copy, to decipher the message.

               The key to the success of this method is that the keys have to be
          completely random.  During World War II the British actually had a woman
          draw lettered balls out of a Bingo cage, while the Germans used a system
          with a swinging pendulum.

               With true random keys, any character of the message can become any
          other character in the encrypted message with equal likelihood.  This can
          be formally proven to be perfectly secure.  That is why so many encryption
          products claim to be like the one-time pad, regardless of whether they are
          similar or not.  To achieve this absolute security, each character of the
          random key must be completely independent of any other character, and no
          part of the random key stream can ever be used again.  This cannot be done
          using pseudorandom numbers.

               Most products on the market today that claim to use the One-Time Pad
          use a pseudorandom number generator as described in the preceding section.
          Such systems are insecure because pseudorandom numbers eventually repeat,
          because they can be determined by exhaustive trial, and/or they are
          generated by simple linear relationships that can be solved easily.

          3.3.3. OP-Crypt

               The OP-Crypt package makes several improvements over other products
          which claim to use the one-time pad.  Data is not encrypted one character
          at a time.  It is encrypted in blocks using a block cipher stronger than
          AES (the Advanced Ecryption Standard).  If an opponent knew some of the
          message, they could not determine the key that was used to produce the
          encrypted message.  Therefore they could not determine any part of the

               The key stream is not generated by a linear mathematical function,
          which can be guessed or solved.  The key stream is generated from true
          random data derived from random physical processes such as gamma rays and
          solar flares.  Each user is furnished with more than 10,000,000 characters
          of such true random data.  The key for each message is obtained by
          encrypting randomly chosen portions of the already-random key data with a
          different encryption key for each block.

               There are actually 4 keys for each block of the message, two
          key-encrypting keys which encrypt two separate portions of the random data
          to obtain two message-encrypting keys.  Each message block is encrypted
          twice, making it impossible for an attacker to determine the two message
          keys.  Of course the user need not be aware of any of this.  All of the
          keys are generated internally by the software, and the user never sees


               Public Key cryptography is a relatively new idea, dating back only to
          the 1970's.  The basic idea is that each party has two functions, E to
          encrypt a message, and D to decrypt the message.  The function E is known
          to everyone.  It is publicly available, either by asking the person with
          whom you wish to communicate, or by some kind of key-distributing network.

               The leading method for public key cryptography uses two large prime
          numbers, say two 150-digit primes.  Each user of the system secretly
          chooses two such primes, and forms their 300-digit product.  This product
          is made public along with a large number E.  Whenever a person wants to
          send a message to the receiver, they treat the message as a series of
          300-digit numbers.  They then encrypt each block by raising the number to
          the E power modulo that 300-digit product.  (See the discussion of modular
          division in the section on random numbers.)

               The receiver, who knows the two primes, can easily calculate the
          secret decrypting number D.  The receiver raises each encrypted block of
          the message to the D power modulo the 300-digit product, and gets back the
          original message.  A third party who wanted to read the encrypted message
          would need to factor the 300-digit product to determine the two primes in
          order to calculate D.  Factoring large numbers can be very difficult and
          can take massive amounts of computing time.

               There are two drawbacks to this form of public key cryptography.
          First, it is very slow.  Raising a large number to a large power modulo a
          large number takes a lot of time, even with the most sophisticated methods.
          This is why some public key software packages include data compression

               Second, improvements in factoring algorithms may make this form of
          encryption insecure.  Some years ago mathematicians learned how to use
          elliptic curves to factor large numbers.  Suddenly all of the public key
          messages that had been sent using 50-digit or 100-digit primes were no
          longer secure.  People who had collected and recorded such messages could
          now read them, and learn the secrets they contained.  People who were using
          public key cryptography had to switch to 150-digit or 200-digit primes if
          they wanted security.


               The newest form of encryption is Private Key Cryptography.  In this
          form, each party has a private key which nobody else knows.  The private
          key is never shared with other parties, so there is no need for any form of
          key exchange or key distribution.

               The great advantage of private key cryptography is that any two
          parties anywhere who have the private key software can securely exchange
          messages without having to make any prior arrangements.  No third party who
          intercepts the messages can read them, even if the third party also has the
          same private key software.

               The method is to treat each message as a series of numbers.  The
          sender performs a mathematical encryption operation on each block of the
          message using the sender's encryption key.  The receiver then performs a
          second mathematical encryption operation on each block of the message using
          the receiver's encryption key.  These mathematical operations are chosen so
          that they commute, that is you would get the same result if you did the two
          encryptions in the opposite order.  For example, ordinary addition
          commutes, so that 2+5 gives the same result as 5+2.

               This makes it possible for the sender to remove the first encryption
          by decrypting the message using the sender's decryption key.  That leaves
          the message encrypted only with the receiver's key.  So now the receiver
          can decrypt the message using the receiver's own decryption key.

               The disadvantage, of course, is that the message must be transmitted 3
          times so that the sender and receiver can perform their respective
          encryption and decryption steps.  For many applications, however, the
          advantage of not needing to exchange encryption keys outweighs this


© Copyright 2005-2024 Frank Rubin