1. Home
  2. The DES cryptosystem
  3. The protocol explained

The Data Encryption Standard (DES)

Try a demo of the protocol

The math and definitions explained

Encoding schemes: From characters to integers and bits

In cryptography, we often encrypt and sign messages that contain characters. However, asymmetric key cryptosystems (where Alice and Bob use different keys), such as RSA and ElGamal, are based on arithmetic operations on integers. Symmetric key cryptosystems (where Alice and Bob use the same key), such as DES and AES, are based on bitwise operations on bits (a bit is either 0 or 1 and is an abbreviation for binary digit). Therefore, we must convert characters into integers or bits before applying the cryptosystem to the message.

Because a computer can only handle bits, there already exists a method for converting characters into integers or bits, which uses the ASCII (American Standard Code for Information Interchange) table. A part of the ASCII table from Wikipedia is shown in the following table (note that the binary representation on the Wikipedia site uses only seven bits, but we use eight bits by prepending an extra 0):

Character Decimal Hexadecimal Binary
(space) 32 20 00100000
! 33 21 00100001
\( \vdots \) \( \vdots \) \( \vdots \) \( \vdots \)
A 65 41 01000001
B 66 42 01000010
\( \vdots \) \( \vdots \) \( \vdots \) \( \vdots \)
a 97 61 01100001
b 98 62 01100010
\( \vdots \) \( \vdots \) \( \vdots \) \( \vdots \)

For example, if Alice wants to send the message "Hey Bob!" encrypted to Bob using a symmetric key cryptosystem, she first converts it into its integer representation and then into its binary representation:

\( \eqalign{ H &\rightarrow 72 &&\rightarrow 01001000 \\ e &\rightarrow 101 &&\rightarrow 01100101 \\ y &\rightarrow 121 &&\rightarrow 01111001 \\ &\rightarrow 32 &&\rightarrow 00100000 \\ B &\rightarrow 66 &&\rightarrow 01000010 \\ o &\rightarrow 111 &&\rightarrow 01101111 \\ b &\rightarrow 98 &&\rightarrow 01100010 \\ ! &\rightarrow 33 &&\rightarrow 00100001 } \)

That is, the message "Hey Bob!" is represented with integers as "72 101 121 32 66 111 98 33" and in binary as "01001000 01100101 01111001 00100000 01000010 01101111 01100010 00100001".

While ASCII is sufficient for basic English text, modern cryptographic applications often need to handle international characters. Unicode standards like UTF-8 extend ASCII and can encode virtually all characters from all writing systems. In UTF-8, ASCII characters still use a single byte, while other characters may use 2-4 bytes.

Modern cryptographic algorithms typically operate on bytes (8-bit units) or words (groups of bytes). The binary representation shown above organizes characters into bytes, which serve as the fundamental unit for cryptographic operations in algorithms like AES, where data is processed in 128-bit (16-byte) blocks.

Notice the relationship between the different representations:

  • The decimal form is what computers process mathematically
  • The hexadecimal form (base 16) provides a more compact representation where each hex digit represents exactly 4 bits
  • The binary form (base 2) shows the actual bit pattern stored in memory

It's important to note that encoding (converting characters to numbers or binary) is not the same as encryption. Encoding is a standardized, reversible process with no secret key. Anyone knowing the encoding scheme can decode the message. Encryption, on the other hand, requires a key to reverse the process, providing actual security.

Related Encoding Schemes in Cryptography

Several other encoding schemes are commonly used in cryptographic applications:

  • Base64: Often used to encode binary data (like encryption keys or encrypted messages) into ASCII text for safe transmission over text-based channels
  • Hex encoding: Frequently used to represent hashes, keys, and other binary values in a human-readable format
  • Block padding: Many cryptographic algorithms operate on fixed-size blocks (e.g., AES uses 128-bit blocks), requiring messages to be padded to the appropriate length

Bitwise operators

In mathematics, we are all familiar with arithmetic operations such as addition, subtraction, multiplication, and division. However, computers work with bit strings — that is, sequences of 0s and 1s — and therefore require similar operations that act on two bit strings. The most important bitwise operations are NOT, AND, OR, and XOR. Below, we show the results of these operations with one or two bits as input.

The NOT operation is often represented as !:

  • \( !0 = 1\)
  • \( !1 = 0\)

The AND operation is represented as \( \wedge \):

  • \( 0 \wedge 0 = 0\)
  • \( 1 \wedge 0 = 0\)
  • \( 0 \wedge 1 = 0\)
  • \( 1 \wedge 1 = 1\)

The OR operation is represented as \( \vee \):

  • \( 0 \vee 0 = 0\)
  • \( 1 \vee 0 = 1\)
  • \( 0 \vee 1 = 1\)
  • \( 1 \vee 1 = 1\)

The XOR (exclusive OR) operation is represented as \( \oplus \):

  • \( 0 \oplus 0 = 0\)
  • \( 1 \oplus 0 = 1\)
  • \( 0 \oplus 1 = 1\)
  • \( 1 \oplus 1 = 0\)
Operations on Multi-Bit Values

These operations work on each bit position independently when applied to longer bit strings. Let A = 10110110 and B = 11001101:

Operation Bit Values Description
NOT A NOT 10110110 = 01001001 Each bit flipped
A AND B 10110110 AND 11001101 = 10000100 Bitwise AND of each position
A OR B 10110110 OR 11001101 = 11111111 Bitwise OR of each position
A XOR B 10110110 XOR 11001101 = 01111011 Bitwise XOR of each position
Common Notations

These operations are represented differently across contexts:

  • Mathematical notation: ! (NOT), \(\wedge\) (AND), \(\vee\) (OR), \(\oplus\) (XOR)
  • Programming notation: ~ (NOT), & (AND), | (OR), ^ (XOR)
  • Boolean logic: NOT, AND, OR, XOR
Importance in Cryptography

Bitwise operations are fundamental to modern cryptography:

  • XOR is especially important because it forms the basis of the one-time pad and is used extensively in stream ciphers and block cipher modes
  • AND and OR are commonly used in hash functions and S-box implementations
  • Bit permutations (rearrangements) combined with these operations create diffusion and confusion in many algorithms
Key Properties of XOR

XOR has special properties that make it valuable in cryptography:

  • Self-inverse: A \(\oplus\) A = 0 (XORing any value with itself gives zero)
  • Identity element: A \(\oplus\) 0 = A (XORing with zero leaves the value unchanged)
  • Associative: A \(\oplus\) (B \(\oplus\) C) = (A \(\oplus\) B) \(\oplus\) C
  • Commutative: A \(\oplus\) B = B \(\oplus\) A

These properties allow operations like: C = P \(\oplus\) K (encryption), P = C \(\oplus\) K (decryption)

Additional Bitwise Operations

Other important operations in cryptography include:

  • Shift operations (left << and right >>): Move bits to the left or right, filling with zeros
  • Rotate operations (ROL and ROR): Similar to shifts but wrap the bits around
  • Bit permutation: Rearranging bits according to a fixed pattern

These operations are fundamental components in many encryption algorithms and hash functions.

PRF and CPA Security of Symmetric Key Cryptosystems

Types of Attacks on Symmetric Cryptosystems

Alice and Bob's adversary, Eve, can attempt the following types of attacks on a symmetric key cryptosystem such as DES or AES:

  • Ciphertext-only attack: Eve tries to guess the key used to encrypt an observed ciphertext sent between Alice and Bob.
  • Known-plaintext attack: Eve somehow knows the plaintext corresponding to an observed ciphertext sent between Alice and Bob and tries to guess the key.
  • Chosen-plaintext attack (CPA): Eve tricks Alice or Bob into encrypting a message of her choice. Using her knowledge of the resulting ciphertext and plaintext, she tries to guess the key used.
  • Chosen-ciphertext attack (CCA): Eve can send a ciphertext to Alice or Bob, who then return the decrypted message. With her knowledge of the ciphertext and plaintext, she tries to guess the key used.
Deterministic vs. Probabilistic Encryption

Symmetric key cryptosystems can be divided into two groups: deterministic and probabilistic cryptosystems. A deterministic cryptosystem, such as DES or AES, uses no randomness during encryption; that is, encrypting the same plaintext twice with the same key always produces the same ciphertext (which can be observed by Eve). This issue can be addressed with a probabilistic cryptosystem, such as the various modes of operation for DES and AES, which use randomness in the form of an initialization vector.

In a good deterministic cryptosystem, there should be no discernible relationship between the plaintext and ciphertext when the key is unknown. In other words, encryption in a deterministic cryptosystem should behave like a truly random function. If this is the case, we say that the encryption function is a pseudo-random function (PRF), and the cryptosystem is PRF-secure if Eve's advantage in correctly guessing in the following game is negligible:

Eve sends a message \( m \) to an oracle, which returns a ciphertext \( c \). Here, \( c \) is either an encryption of \( m \) using the cryptosystem's encryption function or an encryption of \( m \) using a truly random function. Eve then tries to guess which encryption function the oracle used.

PRF Security Model

With a probabilistic cryptosystem, we can achieve higher security compared to a deterministic cryptosystem. Therefore, we require that Eve cannot distinguish between a real encryption of her message \( m \) and an encryption of a random message unrelated to \( m \). We say that a probabilistic cryptosystem is CPA-secure if Eve's advantage in correctly guessing in the following game is negligible:

Eve sends a message \( m \) to an oracle, which returns a ciphertext \( c \). Here, \( c \) is either an encryption of \( m \) or a random message of the same length as \( m \). Eve then tries to guess what \( c \) is an encryption of.

Hence, if a probabilistic cryptosystem is CPA-secure, the only information that a ciphertext reveals is the length of the encrypted message.

Formally, Eve's "advantage" in these security games is defined as the absolute difference between 1/2 and the probability that Eve correctly distinguishes the scenarios: |Pr[Eve guesses correctly] - 1/2|. We say this advantage is "negligible" if it decreases faster than any polynomial in the security parameter (typically the key length).

Block Cipher Modes of Operation

The security properties of symmetric ciphers depend heavily on their modes of operation:

  • ECB (Electronic Codebook): The simplest mode, but not CPA-secure as identical plaintext blocks produce identical ciphertext blocks
  • CBC (Cipher Block Chaining): CPA-secure when used with a random IV
  • CTR (Counter): CPA-secure with a unique nonce, effectively turning a block cipher into a stream cipher
  • GCM (Galois/Counter Mode): Provides both confidentiality (CPA-security) and authenticity

The initialization vector (IV) or nonce is crucial for providing the randomness needed for CPA security.

Semantic Security and Indistinguishability

CPA security is often referred to as "semantic security" or "indistinguishability under chosen plaintext attack" (IND-CPA). These terms all describe the same fundamental security property: an adversary cannot extract meaningful information about the plaintext from the ciphertext, even when they can obtain encryptions of chosen messages.

Practical Implications

These security definitions have important practical consequences:

  • Systems using ECB mode can reveal patterns in the data (e.g., the famous "ECB penguin" demonstration)
  • Reusing the same IV/nonce in CBC or CTR mode can completely break the security
  • Many real-world attacks target implementation flaws rather than the algorithms themselves
  • Modern systems typically require authenticated encryption (combining confidentiality with integrity)

The cryptography explained

Historical Background

The Data Encryption Standard (DES) cryptosystem was developed by IBM in the early 1970s in association with the United States National Security Agency (NSA) as a modification of an earlier cryptosystem called Lucifer. In 1977, DES was adopted as a government standard and was initially expected to serve as a standard for only 10-15 years; however, it remained a standard until 1999 when development of its replacement, the Advanced Encryption Standard (AES), had begun.

Historical timeline:

  • Early 1970s: IBM develops DES based on earlier Lucifer cipher
  • 1977: Adopted as government standard
  • 1990s: Vulnerabilities become apparent due to key size
  • 1999: Development of AES begins to replace DES
Cipher Structure & Properties

DES is a special type of iterated cipher called a Feistel cipher because the encryption and decryption algorithms are almost identical. The only difference is that during decryption, the round keys are used in reverse order compared to encryption.

In DES, Alice and Bob use the same 56-bit key \( K \) (the key is actually 64-bit, but 8 bits are used to validate the key) for both encrypting and decrypting, where plaintexts and ciphertexts are 64-bit. Because Alice and Bob use the same key, DES is called a symmetric cryptosystem where, for example, Alice sends the key to Bob with an asymmetric cryptosystem such as RSA or ElGamal. The reason why symmetric key cryptosystems are used when they first have to use an asymmetric cryptosystem to exchange the key is because they are much faster than asymmetric cryptosystems.

A key difference between the following description of DES and asymmetric cryptosystems is that we will operate with bits and their bitwise operations instead of integers and their arithmetic operations. Consequently, plaintexts and ciphertexts are sometimes referred to as blocks in symmetric cryptosystems because they are bitstrings.

Key DES Properties:

  • Block size: 64 bits
  • Key size: 56 bits (effectively) + 8 parity bits
  • Structure: 16-round Feistel network
  • Operations: Bitwise XOR, permutations, substitutions
Algorithm Overview

As previously described, DES is based on the iterated Feistel cipher where the block (the plaintext or ciphertext) in each round (iteration) is divided into two halves \( L^{i} \) and \( R^{i} \) of equal length. Then in each round, \( L^{i} \) and \( R^{i} \) are computed as:

\( \eqalign{ L^{i} &= R^{i-1} \\ R^{i} &= L^{i-1} \oplus f(R^{i-1}, K^{i}) } \)

where \( f \) is called the round function and is given the right half of the previous block \( R^{i-1} \) and the current round key \( K^{i} \) as input.

The encryption and decryption algorithm in DES is the above round repeated 16 times as illustrated in Figure 1 (see below) where the block \( x \) (the plaintext or ciphertext) is first permuted according to the initial permutation \( IP \). The output is the two halves \( L^{0} \) and \( R^{0} \) (each 32-bit) which are used in the first round, i.e., \( IP(x) = L^{0}R^{0} \). After the 16 rounds, the block is again permuted according to the inverse initial permutation \( IP^{-1} \) where the output \( y \) is either the ciphertext (encryption) or the plaintext (decryption), i.e., \( y = IP^{-1}(R^{16}L^{16}) \) (notice that the two halves \( L^{16} \) and \( R^{16} \) are swapped before the inverse permutation is applied). The two permutations \( IP \) and \( IP^{-1} \) are fixed and have no cryptographic influence.

As illustrated in Figure 1, each round uses a 48-bit round key \( K^{i} \), but as previously described, Alice and Bob only agree on a single 56-bit key \( K \). To solve this problem, they use a key schedule which derives the 16 round keys \( K^{1}, K^{2}, \dots, K^{16} \) from the 56-bit key \( K \), where each \( K^{i} \) is a certain permuted selection of bits from \( K \).

Figure 1: The DES algorithm
Figure 2: The \( f \) function
Core Operations

The round function \( f \) is illustrated in Figure 2 and executes the following steps:

  1. First, the right half \( R^{i-1} \) is expanded from 32-bit to 48-bit with the expansion function \( E \) by repeating 16 of the bits.
  2. The expanded result \( E(R^{i-1}) \) is then XORed with the round key \( K^{i} \) and the result is divided into eight 6-bit blocks, i.e., \( B = E(R^{i-1}) \oplus K^{i} \) where \( B=B_{1}B_{2} \dots B_{8} \).
  3. Each of the 6-bit blocks \( B_{i} \) is then substituted with a 4-bit block \( C_{i} \) using an S-box \( S_{i} \), i.e., \( C_{i} = S_{i}(B_{i}) \).
  4. Finally, the 32-bit string \( C = C_{1}C_{2} \dots C_{8}\) is permuted according to the permutation \( P \), and \( P(C) \) is the output of the function \( f \).
The S-Boxes

In DES, there are eight S-boxes, and each S-box is a look-up table with 4 rows and 16 columns where each row contains the numbers 0 to 15 permuted in a specific order (the permutations were chosen to prevent certain types of attacks, see below). Given the 6-bit string \( B_{i} = b_{1}b_{2}b_{3}b_{4}b_{5}b_{6} \) and the S-box \( S_{i} \), the result \( C_{i} \) is computed as follows: The two bits \( b_{1}b_{6} \) determine the binary representation of the row \( 0 \leq r_{i} \leq 3 \) in \( S_{i} \), and the four bits \( b_{2}b_{3}b_{4}b_{5} \) determine the binary representation of the column \( 0 \leq c_{i} \leq 15 \) in \( S_{i} \). The entry at position \( (r_{i},c_{i}) \) in \( S_{i} \), which is a number between 0 and 15, is then converted to a binary number and becomes \( C_{i} \).

To clarify the use of the S-boxes, we show how to compute the output \( C_{1} \) when given the input \( B_{1} = 011011 \) and the S-box \( S_{1} \):

  • Row selection: \( b_{1}b_{6} = 01 \) (binary 1)
  • Column selection: \( b_{2}b_{3}b_{4}b_{5} = 1101 \) (binary 13)
  • Output: S-box entry at position (1,13) which is \( 5 \) (binary 0101)
  • Therefore: \( C_{1} = 0101 \)
The S-box \( S_{1} \)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
Security Properties & Analysis

The S-boxes were designed to prevent certain types of attacks, especially a method called differential cryptanalysis which was discovered by IBM in the 1970s but kept secret for almost 20 years until it was rediscovered by Biham and Shamir in the early 1990s. Therefore, at the time DES was proposed, some people suggested that the S-boxes might contain hidden trapdoors which would allow the NSA to decrypt messages while claiming that DES was secure. But when Biham and Shamir (re)discovered differential cryptanalysis, it became clear that the S-boxes were designed to prevent this type of attack and not to make DES insecure.

Another property of the S-boxes that is vital to the security of DES is that the S-boxes are the only non-linear function in DES (the linear functions are the permutation \( P \) and the expanding function \( E \)). A cryptosystem that is only based on linear functions is easy to break with, e.g., a known plaintext attack (given a plaintext and its corresponding ciphertext it's easy to compute the secret key).

A function \( g \) is linear if it satisfies that \( g(A \oplus B) = g(A) \oplus g(B) \) for two bitstrings \( A \) and \( B \).

For example, let \( A = 101000 \) and \( B = 011011 \). We now want to show that the permutation \( P \) and the expanding function \( E \) are linear, but the S-boxes \( S_{i} \) are non-linear. Assume that the permutation is given as \( P(X) = x_{2}x_{4}x_{1}x_{3}x_{5}x_{6} \):

\( \eqalign{ P(A) \oplus P(B) &= P(101000) \oplus P(011011) = 001100 \oplus 100111 = 101011 \\ P(A \oplus B) &= P(101000 \oplus 011011) = P(110011) = 101011 } \)

i.e. \( P(A \oplus B) = P(A) \oplus P(B) \) and the permutation is a linear function. Now assume the expanding function is given by \( E(X) = x_{1}x_{2}x_{3}x_{4}x_{3}x_{4}x_{5}x_{6} \), i.e. it expands 6-bit to 8-bit:

\( \eqalign{ E(A) \oplus P(B) &= E(101000) \oplus E(011011) = 10101000 \oplus 01101011 = 11000011 \\ E(A \oplus B) &= E(101000 \oplus 011011) = E(110011) = 11000011} \)

i.e. \( E(A \oplus B) = E(A) \oplus E(B) \) and the expanding function is linear. Finally for the S-boxes we use the S-box \( S_{1} \):

\( \eqalign{ S_{1}(A) \oplus S_{1}(B) &= S_{1}(101000) \oplus S_{1}(011011) = 1101 \oplus 0101 = 1000 \\ S_{1}(A \oplus B) &= S_{1}(101000 \oplus 011011) = S_{1}(110011) = 1011 } \)

i.e. \( S_{1}(A \oplus B) \neq S_{1}(A) \oplus S_{1}(B) \) and the S-boxes are non-linear functions.

DES Variants & Limitations

A serious flaw of DES is its short 56-bit keys, and already in the 1990s it became feasible to break DES by a brute-force attack. That is, given an input block \( x \) and an output block \( y \), we run the DES algorithm \( DES \) with different keys until \( y = DES_{K}(x) \), and hence we have found the used key \( K \).

One solution to this problem is to use DES multiple times. The most used method is called Triple DES and runs the DES algorithm three times using different keys:

\( y = TDES_{K_{1},K_{2},K_{3}}(x) = DES_{K_1}(DES_{K_2}(DES_{K_3}(x))) \)

Notice that \( K_{1} \), \( K_{2} \), and \( K_{3} \) are not the 48-bit round keys but 56-bit main keys.

A variant of Triple DES replaces the middle DES encryption with a DES decryption, i.e., the middle DES algorithm runs with the round keys in reverse order. Now, if we choose the keys in this version as \( K_{1} = K_{2} = K_{3}\), it's the same as running the DES algorithm once because we first encrypt and then decrypt the message (which has no influence) and finally encrypt the message again. Another variant chooses the keys as \( K_{1} = K_{3} \), which reduces the key size. Finally, a variant called DES-X uses a single DES encryption combined with the input block \( x \) XORed with \( K_{1} \) and the output block \( y \) XORed with \( K_{3} \):

\( y = XDES_{K_{1},K_{2},K_{3}}(x) = DES_{K_2}(x \oplus K_{1}) \oplus K_{3} \)

The protocol

Key exchange
Alice and Bob agree on the 56-bit key \( K \).
Encryption
Alice:
  1. Uses the key \( K \) in the key schedule to generate the 16 48-bit round keys \( K^{1}, K^{2}, \dots, K^{16} \).
  2. Uses the round keys in the order \( K^{1}, K^{2}, \dots, K^{16} \) in the DES algorithm \( DES \) to encrypt the message \( m \) by \( c = DES_{K}(m) \).
Alice sends the 64-bit ciphertext \( c \) to Bob.
Decryption
Bob:
  1. Uses the key \( K \) in the key schedule to generate the 16 48-bit round keys \( K^{1}, K^{2}, \dots, K^{16} \).
  2. Uses the round keys in the reverse order \( K^{16}, K^{15}, \dots, K^{1} \) in the DES algorithm \( DES \) to decrypt the ciphertext \( c \) by \( m = DES_{K}(c) \).

Try a demo of the encryption scheme here.

Example

Alice wants to send an encrypted message \( m \) to Bob. They first agree on a 56-bit key \( K = 10101001 \dots\) and both generate the 16 48-bit round keys with the key schedule:

\( \eqalign{ K^{1} &= \dots 10001000 \\ K^{2} &= \dots 11110001 \\ &\vdots \\ K^{16} &= \dots 00000000 } \)

Alice then encrypts the 64-bit message \( m = 10110011 \dots\) using the round keys in the order \( K^{1}, K^{2}, \dots K^{16} \) and sends the 64-bit ciphertext \( c = DES_{K}(m) = 10101011 \dots \) to Bob.

Bob decrypts the received ciphertext with the round keys in the reverse order \( K^{16}, K^{15}, \dots K^{1} \) by computing \( m = DES_{K}(c) = 10110011 \dots \).

Home   Contact   Sitemap

Copyright © 2025 cryptographyacademy.com
Developed by fogbunzel.dk

Back to top