# Simplified DES¶

A simplified variant of the Data Encryption Standard (DES). Note that Simplified DES or S-DES is for educational purposes only. It is a small-scale version of the DES designed to help beginners understand the basic structure of DES.

AUTHORS:

• Minh Van Nguyen (2009-06): initial version
class sage.crypto.block_cipher.sdes.SimplifiedDES

This class implements the Simplified Data Encryption Standard (S-DES) described in [Sch1996]. Schaefer’s S-DES is for educational purposes only and is not secure for practical purposes. S-DES is a version of the DES with all parameters significantly reduced, but at the same time preserving the structure of DES. The goal of S-DES is to allow a beginner to understand the structure of DES, thus laying a foundation for a thorough study of DES. Its goal is as a teaching tool in the same spirit as Phan’s Mini-AES [Pha2002].

EXAMPLES:

Encrypt a random block of 8-bit plaintext using a random key, decrypt the ciphertext, and compare the result with the original plaintext:

sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES(); sdes
Simplified DES block cipher with 10-bit keys
sage: bin = BinaryStrings()
sage: P = [bin(str(randint(0, 1))) for i in range(8)]
sage: K = sdes.random_key()
sage: C = sdes.encrypt(P, K)
sage: plaintxt = sdes.decrypt(C, K)
sage: plaintxt == P
True


We can also encrypt binary strings that are larger than 8 bits in length. However, the number of bits in that binary string must be positive and a multiple of 8:

sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES()
sage: bin = BinaryStrings()
sage: P = bin.encoding("Encrypt this using S-DES!")
sage: Mod(len(P), 8) == 0
True
sage: K = sdes.list_to_string(sdes.random_key())
sage: C = sdes(P, K, algorithm="encrypt")
sage: plaintxt = sdes(C, K, algorithm="decrypt")
sage: plaintxt == P
True

block_length()

Return the block length of Schaefer’s S-DES block cipher. A key in Schaefer’s S-DES is a block of 10 bits.

OUTPUT:

• The block (or key) length in number of bits.

EXAMPLES:

sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES()
sage: sdes.block_length()
10

decrypt(C, K)

Return an 8-bit plaintext corresponding to the ciphertext C, using S-DES decryption with key K. The decryption process of S-DES is as follows. Let $$P$$ be the initial permutation function, $$P^{-1}$$ the corresponding inverse permutation, $$\Pi_F$$ the permutation/substitution function, and $$\sigma$$ the switch function. The ciphertext block C first goes through $$P$$, the output of which goes through $$\Pi_F$$ using the second subkey. Then we apply the switch function to the output of the last function, and the result is then fed into $$\Pi_F$$ using the first subkey. Finally, run the output through $$P^{-1}$$ to get the plaintext.

INPUT:

• C – an 8-bit ciphertext; a block of 8 bits
• K – a 10-bit key; a block of 10 bits

OUTPUT:

The 8-bit plaintext corresponding to C, obtained using the key K.

EXAMPLES:

Decrypt an 8-bit ciphertext block:

sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES()
sage: C = [0, 1, 0, 1, 0, 1, 0, 1]
sage: K = [1, 0, 1, 0, 0, 0, 0, 0, 1, 0]
sage: sdes.decrypt(C, K)
[0, 0, 0, 1, 0, 1, 0, 1]


We can also work with strings of bits:

sage: C = "01010101"
sage: K = "1010000010"
sage: sdes.decrypt(sdes.string_to_list(C), sdes.string_to_list(K))
[0, 0, 0, 1, 0, 1, 0, 1]

encrypt(P, K)

Return an 8-bit ciphertext corresponding to the plaintext P, using S-DES encryption with key K. The encryption process of S-DES is as follows. Let $$P$$ be the initial permutation function, $$P^{-1}$$ the corresponding inverse permutation, $$\Pi_F$$ the permutation/substitution function, and $$\sigma$$ the switch function. The plaintext block P first goes through $$P$$, the output of which goes through $$\Pi_F$$ using the first subkey. Then we apply the switch function to the output of the last function, and the result is then fed into $$\Pi_F$$ using the second subkey. Finally, run the output through $$P^{-1}$$ to get the ciphertext.

INPUT:

• P – an 8-bit plaintext; a block of 8 bits
• K – a 10-bit key; a block of 10 bits

OUTPUT:

The 8-bit ciphertext corresponding to P, obtained using the key K.

EXAMPLES:

Encrypt an 8-bit plaintext block:

sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES()
sage: P = [0, 1, 0, 1, 0, 1, 0, 1]
sage: K = [1, 0, 1, 0, 0, 0, 0, 0, 1, 0]
sage: sdes.encrypt(P, K)
[1, 1, 0, 0, 0, 0, 0, 1]


We can also work with strings of bits:

sage: P = "01010101"
sage: K = "1010000010"
sage: sdes.encrypt(sdes.string_to_list(P), sdes.string_to_list(K))
[1, 1, 0, 0, 0, 0, 0, 1]

initial_permutation(B, inverse=False)

Return the initial permutation of B. Denote the initial permutation function by $$P$$ and let $$(b_0, b_1, b_2, \dots, b_7)$$ be a vector of 8 bits, where each $$b_i \in \{ 0, 1 \}$$. Then

$P(b_0, b_1, b_2, b_3, b_4, b_5, b_6, b_7) = (b_1, b_5, b_2, b_0, b_3, b_7, b_4, b_6)$

The inverse permutation is $$P^{-1}$$:

$P^{-1}(b_0, b_1, b_2, b_3, b_4, b_5, b_6, b_7) = (b_3, b_0, b_2, b_4, b_6, b_1, b_7, b_5)$

INPUT:

• B – list; a block of 8 bits
• inverse – (default: False) if True then use the inverse permutation $$P^{-1}$$; if False then use the initial permutation $$P$$

OUTPUT:

The initial permutation of B if inverse=False, or the inverse permutation of B if inverse=True.

EXAMPLES:

The initial permutation of a list of 8 bits:

sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES()
sage: B = [1, 0, 1, 1, 0, 1, 0, 0]
sage: P = sdes.initial_permutation(B); P
[0, 1, 1, 1, 1, 0, 0, 0]


Recovering the original list of 8 bits from the permutation:

sage: Pinv = sdes.initial_permutation(P, inverse=True)
sage: Pinv; B
[1, 0, 1, 1, 0, 1, 0, 0]
[1, 0, 1, 1, 0, 1, 0, 0]


We can also work with a string of bits:

sage: S = "10110100"
sage: L = sdes.string_to_list(S)
sage: P = sdes.initial_permutation(L); P
[0, 1, 1, 1, 1, 0, 0, 0]
sage: sdes.initial_permutation(sdes.string_to_list("01111000"), inverse=True)
[1, 0, 1, 1, 0, 1, 0, 0]

left_shift(B, n=1)

Return a circular left shift of B by n positions. Let $$B = (b_0, b_1, b_2, b_3, b_4, b_5, b_6, b_7, b_8, b_9)$$ be a vector of 10 bits. Then the left shift operation $$L_n$$ is performed on the first 5 bits and the last 5 bits of $$B$$ separately. That is, if the number of shift positions is n=1, then $$L_1$$ is defined as

$L_1(b_0, b_1, b_2, b_3, b_4, b_5, b_6, b_7, b_8, b_9) = (b_1, b_2, b_3, b_4, b_0, b_6, b_7, b_8, b_9, b_5)$

If the number of shift positions is n=2, then $$L_2$$ is given by

$L_2(b_0, b_1, b_2, b_3, b_4, b_5, b_6, b_7, b_8, b_9) = (b_2, b_3, b_4, b_0, b_1, b_7, b_8, b_9, b_5, b_6)$

INPUT:

• B – a list of 10 bits
• n – (default: 1) if n=1 then perform left shift by 1 position; if n=2 then perform left shift by 2 positions. The valid values for n are 1 and 2, since only up to 2 positions are defined for this circular left shift operation.

OUTPUT:

The circular left shift of each half of B.

EXAMPLES:

Circular left shift by 1 position of a 10-bit string:

sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES()
sage: B = [1, 0, 0, 0, 0, 0, 1, 1, 0, 0]
sage: sdes.left_shift(B)
[0, 0, 0, 0, 1, 1, 1, 0, 0, 0]
sage: sdes.left_shift([1, 0, 1, 0, 0, 0, 0, 0, 1, 0])
[0, 1, 0, 0, 1, 0, 0, 1, 0, 0]


Circular left shift by 2 positions of a 10-bit string:

sage: B = [0, 0, 0, 0, 1, 1, 1, 0, 0, 0]
sage: sdes.left_shift(B, n=2)
[0, 0, 1, 0, 0, 0, 0, 0, 1, 1]


Here we work with a string of bits:

sage: S = "1000001100"
sage: L = sdes.string_to_list(S)
sage: sdes.left_shift(L)
[0, 0, 0, 0, 1, 1, 1, 0, 0, 0]
sage: sdes.left_shift(sdes.string_to_list("1010000010"), n=2)
[1, 0, 0, 1, 0, 0, 1, 0, 0, 0]

list_to_string(B)

Return a binary string representation of the list B.

INPUT:

• B – a non-empty list of bits

OUTPUT:

The binary string representation of B.

EXAMPLES:

A binary string representation of a list of bits:

sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES()
sage: L = [0, 0, 0, 0, 1, 1, 0, 1, 0, 0]
sage: sdes.list_to_string(L)
0000110100

permutation10(B)

Return a permutation of a 10-bit string. This permutation is called $$P_{10}$$ and is specified as follows. Let $$(b_0, b_1, b_2, b_3, b_4, b_5, b_6, b_7, b_8, b_9)$$ be a vector of 10 bits where each $$b_i \in \{ 0, 1 \}$$. Then $$P_{10}$$ is given by

$P_{10}(b_0, b_1, b_2, b_3, b_4, b_5, b_6, b_7, b_8, b_9) = (b_2, b_4, b_1, b_6, b_3, b_9, b_0, b_8, b_7, b_5)$

INPUT:

• B – a block of 10-bit string

OUTPUT:

A permutation of B.

EXAMPLES:

Permute a 10-bit string:

sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES()
sage: B = [1, 1, 0, 0, 1, 0, 0, 1, 0, 1]
sage: sdes.permutation10(B)
[0, 1, 1, 0, 0, 1, 1, 0, 1, 0]
sage: sdes.permutation10([0, 1, 1, 0, 1, 0, 0, 1, 0, 1])
[1, 1, 1, 0, 0, 1, 0, 0, 1, 0]
sage: sdes.permutation10([1, 0, 1, 0, 0, 0, 0, 0, 1, 0])
[1, 0, 0, 0, 0, 0, 1, 1, 0, 0]


Here we work with a string of bits:

sage: S = "1100100101"
sage: L = sdes.string_to_list(S)
sage: sdes.permutation10(L)
[0, 1, 1, 0, 0, 1, 1, 0, 1, 0]
sage: sdes.permutation10(sdes.string_to_list("0110100101"))
[1, 1, 1, 0, 0, 1, 0, 0, 1, 0]

permutation4(B)

Return a permutation of a 4-bit string. This permutation is called $$P_4$$ and is specified as follows. Let $$(b_0, b_1, b_2, b_3)$$ be a vector of 4 bits where each $$b_i \in \{ 0, 1 \}$$. Then $$P_4$$ is defined by

$P_4(b_0, b_1, b_2, b_3) = (b_1, b_3, b_2, b_0)$

INPUT:

• B – a block of 4-bit string

OUTPUT:

A permutation of B.

EXAMPLES:

Permute a 4-bit string:

sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES()
sage: B = [1, 1, 0, 0]
sage: sdes.permutation4(B)
[1, 0, 0, 1]
sage: sdes.permutation4([0, 1, 0, 1])
[1, 1, 0, 0]


We can also work with a string of bits:

sage: S = "1100"
sage: L = sdes.string_to_list(S)
sage: sdes.permutation4(L)
[1, 0, 0, 1]
sage: sdes.permutation4(sdes.string_to_list("0101"))
[1, 1, 0, 0]

permutation8(B)

Return a permutation of an 8-bit string. This permutation is called $$P_8$$ and is specified as follows. Let $$(b_0, b_1, b_2, b_3, b_4, b_5, b_6, b_7, b_8, b_9)$$ be a vector of 10 bits where each $$b_i \in \{ 0, 1 \}$$. Then $$P_8$$ picks out 8 of those 10 bits and permutes those 8 bits:

$P_8(b_0, b_1, b_2, b_3, b_4, b_5, b_6, b_7, b_8, b_9) = (b_5, b_2, b_6, b_3, b_7, b_4, b_9, b_8)$

INPUT:

• B – a block of 10-bit string

OUTPUT:

Pick out 8 of the 10 bits of B and permute those 8 bits.

EXAMPLES:

Permute a 10-bit string:

sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES()
sage: B = [1, 1, 0, 0, 1, 0, 0, 1, 0, 1]
sage: sdes.permutation8(B)
[0, 0, 0, 0, 1, 1, 1, 0]
sage: sdes.permutation8([0, 1, 1, 0, 1, 0, 0, 1, 0, 1])
[0, 1, 0, 0, 1, 1, 1, 0]
sage: sdes.permutation8([0, 0, 0, 0, 1, 1, 1, 0, 0, 0])
[1, 0, 1, 0, 0, 1, 0, 0]


We can also work with a string of bits:

sage: S = "1100100101"
sage: L = sdes.string_to_list(S)
sage: sdes.permutation8(L)
[0, 0, 0, 0, 1, 1, 1, 0]
sage: sdes.permutation8(sdes.string_to_list("0110100101"))
[0, 1, 0, 0, 1, 1, 1, 0]

permute_substitute(B, key)

Apply the function $$\Pi_F$$ on the block B using subkey key. Let $$(b_0, b_1, b_2, b_3, b_4, b_5, b_6, b_7)$$ be a vector of 8 bits where each $$b_i \in \{ 0, 1 \}$$, let $$L$$ and $$R$$ be the leftmost 4 bits and rightmost 4 bits of B respectively, and let $$F$$ be a function mapping 4-bit strings to 4-bit strings. Then

$\Pi_F(L, R) = (L \oplus F(R, S), R)$

where $$S$$ is a subkey and $$\oplus$$ denotes the bit-wise exclusive-OR function.

The function $$F$$ can be described as follows. Its 4-bit input block $$(n_0, n_1, n_2, n_3)$$ is first expanded into an 8-bit block to become $$(n_3, n_0, n_1, n_2, n_1, n_2, n_3, n_0)$$. This is usually represented as follows

$\begin{split}\begin{tabular}{c|cc|c} n_3 & n_0 & n_1 & n_2 \\ n_1 & n_2 & n_3 & n_0 \end{tabular}\end{split}$

Let $$K = (k_0, k_1, k_2, k_3, k_4, k_5, k_6, k_7)$$ be an 8-bit subkey. Then $$K$$ is added to the above expanded input block using exclusive-OR to produce

$\begin{split}\begin{tabular}{c|cc|c} n_3 + k_0 & n_0 + k_1 & n_1 + k_2 & n_2 + k_3 \\ n_1 + k_4 & n_2 + k_5 & n_3 + k_6 & n_0 + k_7 \end{tabular} = \begin{tabular}{c|cc|c} p_{0,0} & p_{0,1} & p_{0,2} & p_{0,3} \\ p_{1,0} & p_{1,1} & p_{1,2} & p_{1,3} \end{tabular}\end{split}$

Now read the first row as the 4-bit string $$p_{0,0} p_{0,3} p_{0,1} p_{0,2}$$ and input this 4-bit string through S-box $$S_0$$ to get a 2-bit output.

$\begin{split}S_0 = \begin{tabular}{cc|cc} \hline Input & Output & Input & Output \\\hline 0000 & 01 & 1000 & 00 \\ 0001 & 00 & 1001 & 10 \\ 0010 & 11 & 1010 & 01 \\ 0011 & 10 & 1011 & 11 \\ 0100 & 11 & 1100 & 11 \\ 0101 & 10 & 1101 & 01 \\ 0110 & 01 & 1110 & 11 \\ 0111 & 00 & 1111 & 10 \\\hline \end{tabular}\end{split}$

Next read the second row as the 4-bit string $$p_{1,0} p_{1,3} p_{1,1} p_{1,2}$$ and input this 4-bit string through S-box $$S_1$$ to get another 2-bit output.

$\begin{split}S_1 = \begin{tabular}{cc|cc} \hline Input & Output & Input & Output \\\hline 0000 & 00 & 1000 & 11 \\ 0001 & 01 & 1001 & 00 \\ 0010 & 10 & 1010 & 01 \\ 0011 & 11 & 1011 & 00 \\ 0100 & 10 & 1100 & 10 \\ 0101 & 00 & 1101 & 01 \\ 0110 & 01 & 1110 & 00 \\ 0111 & 11 & 1111 & 11 \\\hline \end{tabular}\end{split}$

Denote the 4 bits produced by $$S_0$$ and $$S_1$$ as $$b_0 b_1 b_2 b_3$$. This 4-bit string undergoes another permutation called $$P_4$$ as follows:

$P_4(b_0, b_1, b_2, b_3) = (b_1, b_3, b_2, b_0)$

The output of $$P_4$$ is the output of the function $$F$$.

INPUT:

• B – a list of 8 bits
• key – an 8-bit subkey

OUTPUT:

The result of applying the function $$\Pi_F$$ to B.

EXAMPLES:

Applying the function $$\Pi_F$$ to an 8-bit block and an 8-bit subkey:

sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES()
sage: B = [1, 0, 1, 1, 1, 1, 0, 1]
sage: K = [1, 1, 0, 1, 0, 1, 0, 1]
sage: sdes.permute_substitute(B, K)
[1, 0, 1, 0, 1, 1, 0, 1]


We can also work with strings of bits:

sage: B = "10111101"
sage: K = "11010101"
sage: B = sdes.string_to_list(B); K = sdes.string_to_list(K)
sage: sdes.permute_substitute(B, K)
[1, 0, 1, 0, 1, 1, 0, 1]

random_key()

Return a random 10-bit key.

EXAMPLES:

The size of each key is the same as the block size:

sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES()
sage: key = sdes.random_key()
sage: len(key) == sdes.block_length()
True

sbox()

Return the S-boxes of simplified DES.

EXAMPLES:

sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES()
sage: sbox = sdes.sbox()
sage: sbox; sbox
(1, 0, 3, 2, 3, 2, 1, 0, 0, 2, 1, 3, 3, 1, 3, 2)
(0, 1, 2, 3, 2, 0, 1, 3, 3, 0, 1, 0, 2, 1, 0, 3)

string_to_list(S)

Return a list representation of the binary string S.

INPUT:

• S – a string of bits

OUTPUT:

A list representation of the string S.

EXAMPLES:

A list representation of a string of bits:

sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES()
sage: S = "0101010110"
sage: sdes.string_to_list(S)
[0, 1, 0, 1, 0, 1, 0, 1, 1, 0]

subkey(K, n=1)

Return the n-th subkey based on the key K.

INPUT:

• K – a 10-bit secret key of this Simplified DES
• n – (default: 1) if n=1 then return the first subkey based on K; if n=2 then return the second subkey. The valid values for n are 1 and 2, since only two subkeys are defined for each secret key in Schaefer’s S-DES.

OUTPUT:

The n-th subkey based on the secret key K.

EXAMPLES:

Obtain the first subkey from a secret key:

sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES()
sage: key = [1, 0, 1, 0, 0, 0, 0, 0, 1, 0]
sage: sdes.subkey(key, n=1)
[1, 0, 1, 0, 0, 1, 0, 0]


Obtain the second subkey from a secret key:

sage: key = [1, 0, 1, 0, 0, 0, 0, 0, 1, 0]
sage: sdes.subkey(key, n=2)
[0, 1, 0, 0, 0, 0, 1, 1]


We can also work with strings of bits:

sage: K = "1010010010"
sage: L = sdes.string_to_list(K)
sage: sdes.subkey(L, n=1)
[1, 0, 1, 0, 0, 1, 0, 1]
sage: sdes.subkey(sdes.string_to_list("0010010011"), n=2)
[0, 1, 1, 0, 1, 0, 1, 0]

switch(B)

Interchange the first 4 bits with the last 4 bits in the list B of 8 bits. Let $$(b_0, b_1, b_2, b_3, b_4, b_5, b_6, b_7)$$ be a vector of 8 bits, where each $$b_i \in \{ 0, 1 \}$$. Then the switch function $$\sigma$$ is given by

$\sigma(b_0, b_1, b_2, b_3, b_4, b_5, b_6, b_7) = (b_4, b_5, b_6, b_7, b_0, b_1, b_2, b_3)$

INPUT:

• B – list; a block of 8 bits

OUTPUT:

A block of the same dimension, but in which the first 4 bits from B has been switched for the last 4 bits in B.

EXAMPLES:

Interchange the first 4 bits with the last 4 bits:

sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES()
sage: B = [1, 1, 1, 0, 1, 0, 0, 0]
sage: sdes.switch(B)
[1, 0, 0, 0, 1, 1, 1, 0]
sage: sdes.switch([1, 1, 1, 1, 0, 0, 0, 0])
[0, 0, 0, 0, 1, 1, 1, 1]


We can also work with a string of bits:

sage: S = "11101000"
sage: L = sdes.string_to_list(S)
sage: sdes.switch(L)
[1, 0, 0, 0, 1, 1, 1, 0]
sage: sdes.switch(sdes.string_to_list("11110000"))
[0, 0, 0, 0, 1, 1, 1, 1]