16-08-2012, 01:18 PM
The DES Algorithm Illustrated
The DES Algorithm Illustrated.pdf (Size: 87.86 KB / Downloads: 58)
The National Bureau of Standards Coaxes the Genie from the
Bottle
On May 15, 1973, during the reign of Richard Nixon, the National Bureau of Standards
(NBS) published a notice in the Federal Register soliciting proposals for cryptographic
algorithms to protect data during transmission and storage. The notice explained why
encryption was an important issue.
Over the last decade, there has been an accelerating increase in the
accumulations and communication of digital data by government, industry
and by other organizations in the private sector. The contents of these
communicated and stored data often have very significant value and/or
sensitivity. It is now common to find data transmissions which constitute
funds transfers of several million dollars, purchase or sale of securities,
warrants for arrests or arrest and conviction records being communicated
between law enforcement agencies, airline reservations and ticketing
representing investment and value both to the airline and passengers, and
health and patient care records transmitted among physicians and
The DES Algorithm Illustrated
treatment centers.
The increasing volume, value and confidentiality of these records
regularly transmitted and stored by commercial and government agencies
has led to heightened recognition and concern over their exposures to
unauthorized access and use. This misuse can be in the form of theft or
defalcations of data records representing money, malicious modification of
business inventories or the interception and misuse of confidential
information about people. The need for protection is then apparent and
urgent.
It is recognized that encryption (otherwise known as scrambling,
enciphering or privacy transformation) represents the only means of
protecting such data during transmission and a useful means of protecting
the content of data stored on various media, providing encryption of
adequate strength can be devised and validated and is inherently integrable
into system architecture. The National Bureau of Standards solicits
proposed techniques and algorithms for computer data encryption. The
Bureau also solicits recommended techniques for implementing the
cryptographic function: for generating, evaluating, and protecting
cryptographic keys; for maintaining files encoded under expiring keys; for
making partial updates to encrypted files; and mixed clear and encrypted
data to permit labelling, polling, routing, etc. The Bureau in its role for
establishing standards and aiding government and industry in assessing
technology, will arrange for the evaluation of protection methods in order
to prepare guidelines.
NBS waited for the responses to come in. It received none until August 6, 1974, three
days before Nixon's resignation, when IBM submitted a candidate that it had developed
internally under the name LUCIFER. After evaluating the algorithm with the help of the
National Security Agency (NSA), the NBS adopted a modification of the LUCIFER
algorithm as the new Data Encryption Standard (DES) on July 15, 1977.
DES was quickly adopted for non-digital media, such as voice-grade public telephone
lines. Within a couple of years, for example, International Flavors and Fragrances was
using DES to protect its valuable formulas transmitted over the phone ("With Data
Encryption, Scents Are Safe at IFF," Computerworld 14, No. 21, 95 (1980).)
Meanwhile, the banking industry, which is the largest user of encryption outside
government, adopted DES as a wholesale banking standard. Standards for the wholesale
banking industry are set by the American National Standards Institute (ANSI). ANSI
X3.92, adopted in 1980, specified the use of the DES algorithm.
The DES Algorithm Illustrated
Some Preliminary Examples of DES
DES works on bits, or binary numbers--the 0s and 1s common to digital computers. Each
group of four bits makes up a hexadecimal, or base 16, number. Binary "0001" is equal
to the hexadecimal number "1", binary "1000" is equal to the hexadecimal number "8",
"1001" is equal to the hexadecimal number "9", "1010" is equal to the hexadecimal
number "A", and "1111" is equal to the hexadecimal number "F".
DES works by encrypting groups of 64 message bits, which is the same as 16
hexadecimal numbers. To do the encryption, DES uses "keys" where are also apparently
16 hexadecimal numbers long, or apparently 64 bits long. However, every 8th key bit is
ignored in the DES algorithm, so that the effective key size is 56 bits. But, in any case,
64 bits (16 hexadecimal digits) is the round number upon which DES is organized.
For example, if we take the plaintext message "8787878787878787", and encrypt it with
the DES key "0E329232EA6D0D73", we end up with the ciphertext
"0000000000000000". If the ciphertext is decrypted with the same secret DES key
"0E329232EA6D0D73", the result is the original plaintext "8787878787878787".
This example is neat and orderly because our plaintext was exactly 64 bits long. The
same would be true if the plaintext happened to be a multiple of 64 bits. But most
messages will not fall into this category. They will not be an exact multiple of 64 bits
(that is, an exact multiple of 16 hexadecimal numbers).
How DES Works in Detail
DES is a block cipher--meaning it operates on plaintext blocks of a given size (64-bits)
and returns ciphertext blocks of the same size. Thus DES results in a permutation among
the 2^64 (read this as: "2 to the 64th power") possible arrangements of 64 bits, each of
which may be either 0 or 1. Each block of 64 bits is divided into two blocks of 32 bits
each, a left half block L and a right half R. (This division is only used in certain
operations.)
Cracking DES
Before DES was adopted as a national standard, during the period NBS was soliciting
comments on the proposed algorithm, the creators of public key cryptography, Martin
Hellman and Whitfield Diffie, registered some objections to the use of DES as an
encryption algorithm. Hellman wrote: "Whit Diffie and I have become concerned that
the proposed data encryption standard, while probably secure against commercial
assault, may be extremely vulnerable to attack by an intelligence organization" (letter to
NBS, October 22, 1975).