Tech Note #35: How Encryption and Digital Signatures Work

©

1999 Bionic Buffalo Corporation; All Rights Reserved.

19 May 1999

http://www.tatanka.com

Page

3 of 10

There is a second kind of cryptosystem, which uses one key to encrypt, and a different key to

decrypt. Such a system is called an *asymmetric* cryptosystem. It has the advantage that many

people can use the encryption key to encrypt messages for a recipient, but only the recipient

who has the decryption key can read and understand them. When the encryption key is

published for anyone to use, then this is called a *public key* cryptosystem, since one of the two

keys is public.

DES: An Example of a Symmetric Cryptosystem

One of the most common symmetric encryption mechanisms is DES (Data Encryption

Standard), which is a U S Government standard widely used in financial and many other

applications. DES uses a 56-bit key to scramble and unscramble messages. Messages are

encrypted or decrypted 64 bits at a time. Encryption is done in 18 steps: an initial permutation,

16 operations called *rounds*, and a final permutation.

The initial permutation is a simple rearrangement of the bits in the input.

Each of the rounds is the same, except for the inputs. The output of one round becomes the

input for the next round. Each round has seven steps:

1.

The 56-bit key is shifted and permuted, and 48 bits are selected.

2.

The right half of the 64-bit output of the previous round is permuted and expanded, and 48

bits are selected.

3.

The 48 bits from Step 1 are XORed with the 48 bits from Step 2.

4.

The result of Step 3 is divided into 8 different 6-bit numbers. Each of these numbers is used

to index into a table to produce 8 new 4-bit numbers. The indexing operation is not simple,

and this step and the design of the tables (called *S-boxes*) are crucial to the strength of the

encryption.

5.

The 32 bits produced by Step 4 are rearranged again. (This permutation is called the *P-*

box.)

6.

The left half of the 64-bit output of the previous round is XORed with the output of Step 5,

to become the right half of the output of this round.

7.

The right half of the 64-bit output of the previous round becomes the left half of the output

of this round.

The final permutation is another rearrangement of the input bits, and is the simple inverse of the

initial permutation.

Decrypting a DES message is almost the same as encrypting it, except that the selection of the

48 key bits for each round is done so that the 16 rounds see the key selections in reverse order.