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

Bases: sage.structure.sage_object.SageObject

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, ΠF the permutation/substitution function, and σ the switch function. The ciphertext block C first goes through P, the output of which goes through Π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 Π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, ΠF the permutation/substitution function, and σ the switch function. The plaintext block P first goes through P, the output of which goes through Π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 Π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 (b0,b1,b2,…,b7) be a vector of 8 bits, where each bi∈{0,1}. Then

P(b0,b1,b2,b3,b4,b5,b6,b7)=(b1,b5,b2,b0,b3,b7,b4,b6)

The inverse permutation is P−1:

P−1(b0,b1,b2,b3,b4,b5,b6,b7)=(b3,b0,b2,b4,b6,b1,b7,b5)

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=(b0,b1,b2,b3,b4,b5,b6,b7,b8,b9) be a vector of 10 bits. Then the left shift operation Ln 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 L1 is defined as

L1(b0,b1,b2,b3,b4,b5,b6,b7,b8,b9)=(b1,b2,b3,b4,b0,b6,b7,b8,b9,b5)

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

L2(b0,b1,b2,b3,b4,b5,b6,b7,b8,b9)=(b2,b3,b4,b0,b1,b7,b8,b9,b5,b6)

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 P10 and is specified as follows. Let (b0,b1,b2,b3,b4,b5,b6,b7,b8,b9) be a vector of 10 bits where each bi∈{0,1}. Then P10 is given by

P10(b0,b1,b2,b3,b4,b5,b6,b7,b8,b9)=(b2,b4,b1,b6,b3,b9,b0,b8,b7,b5)

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 P4 and is specified as follows. Let (b0,b1,b2,b3) be a vector of 4 bits where each bi∈{0,1}. Then P4 is defined by

P4(b0,b1,b2,b3)=(b1,b3,b2,b0)

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 P8 and is specified as follows. Let (b0,b1,b2,b3,b4,b5,b6,b7,b8,b9) be a vector of 10 bits where each bi∈{0,1}. Then P8 picks out 8 of those 10 bits and permutes those 8 bits:

P8(b0,b1,b2,b3,b4,b5,b6,b7,b8,b9)=(b5,b2,b6,b3,b7,b4,b9,b8)

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 ΠF on the block B using subkey key. Let (b0,b1,b2,b3,b4,b5,b6,b7) be a vector of 8 bits where each bi∈{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

ΠF(L,R)=(L⊕F(R,S),R)

where S is a subkey and ⊕ denotes the bit-wise exclusive-OR function.

The function F can be described as follows. Its 4-bit input block (n0,n1,n2,n3) is first expanded into an 8-bit block to become (n3,n0,n1,n2,n1,n2,n3,n0). 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=(k0,k1,k2,k3,k4,k5,k6,k7) 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 p0,0p0,3p0,1p0,2 and input this 4-bit string through S-box S0 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 p1,0p1,3p1,1p1,2 and input this 4-bit string through S-box S1 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 S0 and S1 as b0b1b2b3. This 4-bit string undergoes another permutation called P4 as follows:

P4(b0,b1,b2,b3)=(b1,b3,b2,b0)

The output of P4 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 ΠF to B.

EXAMPLES:

Applying the function Π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[0]; sbox[1]
(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 (b0,b1,b2,b3,b4,b5,b6,b7) be a vector of 8 bits, where each bi∈{0,1}. Then the switch function σ is given by

σ(b0,b1,b2,b3,b4,b5,b6,b7)=(b4,b5,b6,b7,b0,b1,b2,b3)

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]