📄 the des algorithm illustrated.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0035)http://www.aci.net/kalliste/des.htm -->
<HTML><HEAD><TITLE>The DES Algorithm Illustrated</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 5.50.4134.100" name=GENERATOR></HEAD>
<BODY bgColor=white><A href="mailto:orlingrabbe@orlingrabbe.com">[Email Reply]
</A>
<H2 align=center>The DES Algorithm Illustrated</H2>
<H3 align=center><I>by J. Orlin Grabbe</I></H3>
<CENTER>
<TABLE width="80%" border=0>
<TBODY>
<TR>
<TD>
<P>The DES (Data Encryption Standard) algorithm is the most widely used
encryption algorithm in the world. For many years, and among many people,
"secret code making" and DES have been synonymous. And despite the recent
coup by the Electronic Frontier Foundation in creating a $220,000 machine
to crack DES-encrypted messages, DES will live on in government and
banking for years to come through a life- extending version called
"triple-DES."
<P>How does DES work? This article explains the various steps involved in
DES-encryption, illustrating each step by means of a simple example. Since
the creation of DES, many other algorithms (recipes for changing data)
have emerged which are based on design principles similar to DES. Once you
understand the basic transformations that take place in DES, you will find
it easy to follow the steps involved in these more recent algorithms.
<P>But first a bit of history of how DES came about is appropriate, as
well as a look toward the future.
<P>
<H3 align=center>The National Bureau of Standards Coaxes the Genie from
the Bottle</H3>
<P>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.
<BLOCKQUOTE>
<P>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 treatment centers.
<P>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.
<P>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. </P></BLOCKQUOTE>
<P>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.
<P>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," <I>Computerworld</I> 14, No. 21, 95 (1980).)
<P>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.
<P>
<H3 align=center>Some Preliminary Examples of DES</H3>
<P>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".
<P>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 <I>apparently</I> 16 hexadecimal numbers long, or <I>apparently</I>
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.
<P>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".
<P>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).
<P>For example, take the message "Your lips are smoother than vaseline".
This plaintext message is 38 bytes (76 hexadecimal digits) long. So this
message must be padded with some extra bytes at the tail end for the
encryption. Once the encrypted message has been decrypted, these extra
bytes are thrown away. There are, of course, different padding
schemes--different ways to add extra bytes. Here we will just add 0s at
the end, so that the total message is a multiple of 8 bytes (or 16
hexadecimal digits, or 64 bits).
<P>The plaintext message "Your lips are smoother than vaseline" is, in
hexadecimal,
<P>"596F7572206C6970 732061726520736D 6F6F746865722074 68616E2076617365
6C696E650D0A".
<P>(Note here that the first 72 hexadecimal digits represent the English
message, while "0D" is hexadecimal for Carriage Return, and "0A" is
hexadecimal for Line Feed, showing that the message file has terminated.)
We then pad this message with some 0s on the end, to get a total of 80
hexadecimal digits:
<P>"596F7572206C6970 732061726520736D 6F6F746865722074 68616E2076617365
6C696E650D0A0000".
<P>If we then encrypt this plaintext message 64 bits (16 hexadecimal
digits) at a time, using the same DES key "0E329232EA6D0D73" as before, we
get the ciphertext:
<P>"C0999FDDE378D7ED 727DA00BCA5A84EE 47F269A4D6438190 9DD52F78F5358499
828AC9B453E0E653".
<P>This is the secret code that can be transmitted or stored. Decrypting
the ciphertext restores the original message "Your lips are smoother than
vaseline". (Think how much better off Bill Clinton would be today, if
Monica Lewinsky had used encryption on her Pentagon computer!)
<P>
<H3 align=center>How DES Works in Detail</H3>
<P>DES is a <B><I>block cipher</I></B>--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 <B><I>permutation</I></B> 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 <B>L</B> and a right half
<B>R</B>. (This division is only used in certain operations.)
<P><B>Example:</B> Let <B>M</B> be the plain text message <B>M</B> =
0123456789ABCDEF, where <B>M</B> is in hexadecimal (base 16) format.
Rewriting <B>M</B> in binary format, we get the 64-bit block of text:
<P><B>M</B> = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011
1100 1101 1110 1111<BR><B>L</B> = 0000 0001 0010 0011 0100 0101 0110
0111<BR><B>R</B> = 1000 1001 1010 1011 1100 1101 1110 1111
<P>The first bit of <B>M</B> is "0". The last bit is "1". We read from
left to right.
<P>DES operates on the 64-bit blocks using <I>key</I> sizes of 56- bits.
The keys are actually stored as being 64 bits long, but every 8th bit in
the key is not used (i.e. bits numbered 8, 16, 24, 32, 40, 48, 56, and
64). However, we will nevertheless number the bits from 1 to 64, going
left to right, in the following calculations. But, as you will see, the
eight bits just mentioned get eliminated when we create subkeys.
<P><B>Example:</B> Let <B>K</B> be the hexadecimal key <B>K</B> =
133457799BBCDFF1. This gives us as the binary key (setting 1 = 0001, 3 =
0011, etc., and grouping together every eight bits, of which the last one
in each group will be unused):
<P><B>K</B> = 00010011 00110100 01010111 01111001 10011011 10111100
11011111 11110001
<P>The DES algorithm uses the following steps:
<P>
<H2 align=center>Step 1: Create 16 subkeys, each of which is 48-bits
long.</H2>
<P>The 64-bit key is permuted according to the following table,
<B>PC-1</B>. Since the first entry in the table is "57", this means that
the 57th bit of the original key <B>K</B> becomes the first bit of the
permuted key <B>K</B>+. The 49th bit of the original key becomes the
second bit of the permuted key. The 4th bit of the original key is the
last bit of the permuted key. Note only 56 bits of the original key appear
in the permuted key.
<P><PRE> <B>PC-1</B>
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
</PRE>
<P><B>Example:</B> From the original 64-bit key
<P><B>K</B> = 00010011 00110100 01010111 01111001 10011011 10111100
11011111 11110001
<P>we get the 56-bit permutation
<P><B>K</B>+ = 1111000 0110011 0010101 0101111 0101010 1011001 1001111
0001111
<P>Next, split this key into left and right halves,
<B><I>C<SUB>0</SUB></I></B> and <B><I>D<SUB>0</SUB></I></B>, where each
half has 28 bits.
<P><B>Example:</B> From the permuted key <B>K</B>+, we get
<P><B><I>C<SUB>0</SUB></I></B> = 1111000 0110011 0010101 0101111
<BR><B><I>D<SUB>0</SUB></I></B> = 0101010 1011001 1001111 0001111
<P>With <B><I>C<SUB>0</SUB></I></B> and <B><I>D<SUB>0</SUB></I></B>
defined, we now create sixteen blocks <B><I>C<SUB>n</SUB></I></B> and
<B><I>D<SUB>n</SUB></I></B>, 1<=<B><I>n</I></B><=16. Each pair of
blocks <B><I>C<SUB>n</SUB></I></B> and <B><I>D<SUB>n</SUB></I></B> is
formed from the previous pair <B><I>C<SUB>n-1</SUB></I></B> and
<B><I>D<SUB>n-1</SUB></I></B>, respectively, for <B><I>n</I></B> = 1, 2,
..., 16, using the following schedule of "left shifts" of the previous
block. To do a left shift, move each bit one place to the left, except for
the first bit, which is cycled to the end of the block.
<P><PRE> Iteration Number of
Number Left Shifts
1 1
2 1
3 2
4 2
5 2
6 2
7 2
8 2
9 1
10 2
11 2
12 2
13 2
14 2
15 2
16 1
</PRE>
<P>This means, for example, <B><I>C<SUB>3</SUB></I></B> and
<B><I>D<SUB>3</SUB></I></B> are obtained from <B><I>C<SUB>2</SUB></I></B>
and <B><I>D<SUB>2</SUB></I></B>, respectively, by two left shifts, and
<B><I>C<SUB>16</SUB></I></B> and <B><I>D<SUB>16</SUB></I></B> are obtained
from <B><I>C<SUB>15</SUB></I></B> and <B><I>D<SUB>15</SUB></I></B>,
respectively, by one left shift. In all cases, by a single left shift is
meant a rotation of the bits one place to the left, so that after one left
shift the bits in the 28 positions are the bits that were previously in
positions 2, 3,..., 28, 1.
<P><B>Example:</B> From original pair pair <B><I>C<SUB>0</SUB></I></B> and
<B><I>D<SUB>0</SUB></I></B> we obtain:
<P><B><I>C<SUB>0</SUB></I></B> =
1111000011001100101010101111<BR><B><I>D<SUB>0</SUB></I></B> =
0101010101100110011110001111
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -