Starting from:
$20
Project 1 Simplified DES Solution
Description:
Create a program to encrypt and decrypt binary files using S-DES (Simplified DES) in the Cipher Block Chaining mode. The program takes the input of an initial key and an initial vector, reads the plaintext or ciphertext from a file, conducts the encryption or decryption, and writes the resulting ciphertext or plaintext into a second file.
This is a group project with no more than two students in a group. You can use any of your preferred programming languages and operating systems. The code must be welldocumented for easy understanding.
Input Format:
The program should take a command in the following format.
(java) mycipher -m mode -k initial_key -i initial_vector -p plaintext_file -c ciphertext_file
mode: can be only encrypt or decrypt
initial_key: 10-bit initial key
initial_vector: 8-bit initial vector
plaintext_file: a binary (not text) file to store the plaintext
ciphertext_file: a binary (not text) file to store the ciphertext
Output Format:
The program should print output in the following format.
k1=subkey 1
k2=subkey 2
plaintext=all bytes of the plaintext separated by blanks, starting from the first byte
ciphertext= all bytes of the ciphertext separated by blanks, starting from the first byte
Sample Screen Shot:
Sample Test Cases:
java mycipher -m encrypt -k 0111111101 -i 10101010 -p f1 -c f3
k1=01011111
k2=11111100
plaintext=00000001 00100011
ciphertext=11110100 00001011
java mycipher -m decrypt -k 0101010101 -i 00000000 -p f4 -c f2
k1=00011011
k2=10101100
ciphertext=00000001
plaintext=01101000
where f1 is a binary file with two bytes 012316,
and f2 is a binary file with one byte 0116.
IMPORTANT: Make sure that your program exactly follows the above specifications, including the execute/java class file name, the command line input format, and the output format. The TA will test your program by typing testing commands as specified above. If your program cannot give the correct output for a command, you will not receive the credit.
Submission Guide:
Operating System: any, if not Windows/Linux/Mac OS, need to show your code on your own computer.
Programing Language: any, if not Java/Python/C/C++, need to show your code on your own computer.
Please submit your source code and a readme file through Moodle. The readme file should including the following information:
Operating System: xxx
Programming Language: xxx
Compiling Instruction: the command line to compile your code.
Grading Criteria:
Item Percentage
Successful compilation 15%
S-DES key generation 20%
S-DES encryption 15%
S-DES decryption 15%
CBC mode S-DES with single block 15%
CBC mode S-DES with multiple blocks 20%
A PPENDIX PPENDIX C
Simplified Simplified DES
C.1 Overview...................................................................................................................2
C.2 S-DES Key Generation .............................................................................................3
C.3 S-DES Encryption.....................................................................................................3
Initial and Final Permutations..................................................................................3
The Function fK.......................................................................................................4
The Switch Function................................................................................................5
C.4 Analysis of Simplified DES......................................................................................5
C.5 Relationship to DES..................................................................................................6
William Stallings
Copyright 2006
Supplement to
Cryptography and Network Security, Fourth Edition
Prentice Hall 2006
ISBN: 0-13-187316-4
http://williamstallings.com/Crypto/Crypto4e.html
8/5/05
C-2
Simplified DES, developed by Professor Edward Schaefer of Santa Clara University [SCHA96], is an educational rather than a secure encryption algorithm. It has similar properties and structure to DES with much smaller parameters. The reader might find it useful to work through an example by hand while following the discussion in this Appendix.
C.1 Overview
Figure C.1 illustrates the overall structure of the simplified DES, which we will refer to as SDES. The S-DES encryption algorithm takes an 8-bit block of plaintext (example: 10111101) and a 10-bit key as input and produces an 8-bit block of ciphertext as output. The S-DES decryption algorithm takes an 8-bit block of ciphertext and the same 10-bit key used to produce that ciphertext as input and produces the original 8-bit block of plaintext.
The encryption algorithm involves five functions: an initial permutation (IP); a complex function labeled fK, which involves both permutation and substitution operations and depends on a key input; a simple permutation function that switches (SW) the two halves of the data; the function fK again; and finally a permutation function that is the inverse of the initial permutation (IP–1). As was mentioned in Chapter 2, the use of multiple stages of permutation and substitution
results in a more complex algorithm, which increases the difficulty of cryptanalysis.
The function fK takes as input not only the data passing through the encryption algorithm, but also an 8-bit key. The algorithm could have been designed to work with a 16-bit key, consisting of two 8-bit subkeys, one used for each occurrence of fK. Alternatively, a single 8-bit key could have been used, with the same key used twice in the algorithm. A compromise is to use a 10-bit key from which two 8-bit subkeys are generated, as depicted in Figure C.1. In this case, the key is first subjected to a permutation (P10). Then a shift operation is performed. The
output of the shift operation then passes through a permutation function that produces an 8-bit output (P8) for the first subkey (K1). The output of the shift operation also feeds into another shift and another instance of P8 to produce the second subkey (K2). We can concisely express the encryption algorithm as a composition1 of functions:
IP-1 ofK2 oSW ofK1 oIP
which can also be written as:
!
ciphertext = IP-1 fK2
SW fK1 ( ( ( (IP(plaintext)))))
where
K1 = P8(Shift(P10(key)))
K2 = P8(Shift(Shift(P10(key))))
Decryption is also shown in Figure C.1 and is essentially the reverse of encryption:
!
plaintext = IP-1 fK1
SW fK2 ( ( ( (IP(ciphertext)))))
1 Definition: If f and g are two functions, then the function F with the equation y = F(x) = g[f(x)] is called the composition of f and g and is denoted as
F = g of . 8/5/05 C-3
We now examine the elements of S-DES in more detail.
C.2 S-DES Key Generation
S-DES depends on the use of a 10-bit key shared between sender and receiver. From this key, two 8-bit subkeys are produced for use in particular stages of the encryption and decryption algorithm. Figure C.2 depicts the stages followed to produce the subkeys. First, permute the key in the following fashion. Let the 10-bit key be designated as (k1, k2, k3, k4, k5, k6, k7, k8, k9, k10). Then the permutation P10 is defined as:
P10(k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) = (k3, k5, k2, k7, k4, k10, k1, k9, k8, k6)
P10 can be concisely defined by the display:
P10 3 5 2 7 4 10 1 9 8 6
This table is read from left to right; each position in the table gives the identity of the input bit that produces the output bit in that position. So the first output bit is bit 3 of the input; the second output bit is bit 5 of the input, and so on. For example, the key (1010000010) is permuted
to (1000001100). Next, perform a circular left shift (LS-1), or rotation, separately on the first five bits and the second five bits. In our example, the result is (00001 11000).
Next we apply P8, which picks out and permutes 8 of the 10 bits according to the following rule: P8 6 3 7 4 8 5 10 9
The result is subkey 1 (K1). In our example, this yields (10100100)
We then go back to the pair of 5-bit strings produced by the two LS-1 functions and perform a circular left shift of 2 bit positions on each string. In our example, the value (00001 11000) becomes (00100 00011). Finally, P8 is applied again to produce K2. In our example, the result is (01000011).
C.3 S-DES Encryption
Figure C.3 shows the S-DES encryption algorithm in greater detail. As was mentioned, encryption involves the sequential application of five functions. We examine each of these. Initial and Final Permutations
The input to the algorithm is an 8-bit block of plaintext, which we first permute using the IP function:
IP
2 6 3 1 4 8 5 7
This retains all 8 bits of the plaintext but mixes them up. At the end of the algorithm, the inverse
permutation is used:
8/5/05
C-4
IP–1
4 1 3 5 7 2 8 6
It is easy to show by example that the second permutation is indeed the reverse of the first; that is, IP–1(IP(X)) = X.
The Function fK
The most complex component of S-DES is the function fK, which consists of a combination of permutation and substitution functions. The functions can be expressed as follows. Let L and R be the leftmost 4 bits and rightmost 4 bits of the 8-bit input to fK, and let F be a mapping (not necessarily one to one) from 4-bit strings to 4-bit strings. Then we let fK(L, R) = (L ! F(R, SK), R)
where SK is a subkey and ! is the bit-by-bit exclusive-OR function. For example, suppose the output of the IP stage in Figure C.3 is (10111101) and F(1101, SK) = (1110) for some key SK.
Then fK(10111101) = (01011101) because (1011) ! (1110) = (0101).
We now describe the mapping F. The input is a 4-bit number (n1n2n3n4). The first operation is an expansion/permutation operation:
E/P
4 1 2 3 2 3 4 1
For what follows, it is clearer to depict the result in this fashion:
n4 n1 n2 n3
n2 n3 n4 n1
The 8-bit subkey K1 = (k11, k12, k13, k14, k15, k16, k17, k18) is added to this value using exclusiveOR:
n4 ! k11 n1 ! k12 n2 ! k13 n3 ! k14
n2 ! k15 n3 ! k16 n4 ! k17 n1 ! k18
Let us rename these 8 bits:
p0,0 p0,1 p0,2 p0,3
p1,0 p1,1 p1,2 p1,3
The first 4 bits (first row of the preceding matrix) are fed into the S-box S0 to produce a 2-bit output, and the remaining 4 bits (second row) are fed into S1 to produce another 2-bit output.
These two boxes are defined as follows:
8/5/05
C-5
!
S0 =
0 1 2 3
0
1
2
3
1 0 3 2
3 2 1 0
0 2 1 3
3 1 3 2
"
#
$
$
$
%
&
'
'
'
S1=
0 1 2 3
0
1
2
3
0 1 2 3
2 0 1 3
3 0 1 0
2 1 0 3
"
#
$
$
$
%
&
'
'
'
The S-boxes operate as follows. The first and fourth input bits are treated as a 2-bit number that specify a row of the S-box, and the second and third input bits specify a column of the Sbox.
The entry in that row and column, in base 2, is the 2-bit output. For example, if (p0,0p0,3) = (00) and (p0,1p0,2) = (10), then the output is from row 0, column 2 of S0, which is 3, or (11) in binary. Similarly, (p1,0p1,3) and (p1,1p1,2) are used to index into a row and column of S1 to produce an additional 2 bits.
Next, the 4 bits produced by S0 and S1 undergo a further permutation as follows:
P4 2 4 3 1
The output of P4 is the output of the function F.
The Switch Function The function fK only alters the leftmost 4 bits of the input. The switch function (SW) interchanges the left and right 4 bits so that the second instance of fK operates on a different 4 bits. In this second instance, the E/P, S0, S1, and P4 functions are the same. The key input is K2.
C.4 Analysis of Simplified DES A brute-force attack on simplified DES is certainly feasible. With a 10-bit key, there are only 210 = 1024 possibilities. Given a ciphertext, an attacker can try each possibility and analyze the result to determine if it is reasonable plaintext.
What about cryptanalysis? Let us consider a known plaintext attack in which a single plaintext (p1, p2, p3, p4, p5, p6, p7, p8) and its ciphertext output (c1, c2, c3, c4, c5, c6, c7, c8) are known and the key (k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) is unknown. Then each ci is a polynomial
function gi
of the pj
's and kj
's. We can therefore express the encryption algorithm as 8 nonlinear equations in 10 unknowns. There are a number of possible solutions, but each of these could be calculated and then analyzed. Each of the permutations and additions in the algorithm is a linear mapping. The nonlinearity comes from the S-boxes. It is useful to write down the equations for these boxes. For clarity, rename (p0,0, p0,1,p0,2, p0,3) = (a, b, c, d) and (p1,0, p1,1,p1,2, p1,3) = (w, x,
y, z), and let the 4-bit output be (q, r, s, t) Then the operation of the S0 is defined by the following equations:
q = abcd + ab + ac + b + d
r = abcd + abd + ab + ac + ad + a + c + 1
where all additions are modulo 2. Similar equations define S1. Alternating linear maps with these nonlinear maps results in very complex polynomial expressions for the ciphertext bits, making cryptanalysis difficult. To visualize the scale of the problem, note that a polynomial equation in 10 unknowns in binary arithmetic can have 210 possible terms. On average, we might therefore 8/5/05
C-6
expect each of the 8 equations to have 29 terms. The interested reader might try to find these equations with a symbolic processor. Either the reader or the software will give up before much progress is made.
C.5 Relationship to DES
DES operates on 64-bit blocks of input. The encryption scheme can be defined as:
IP-1 ofK16 oSW ofK15 o SW oLo SW ofK1 oIP
A 56-bit key is used, from which sixteen 48-bit subkeys are calculated. There is an initial permutation of 64 bits followed by a sequence of shifts and permutations of 48 bits. Within the encryption algorithm, instead of F acting on 4 bits (n1n2n3n4), it acts on 32 bits (n1…n32). After the initial expansion/permutation, the output of 48 bits can be diagrammed as:
n32 n1 n2 n3 n4 n5
n4 n5 n6 n7 n8 n9
•
•
•
•
•
•
•
•
•
n28 n29 n30 n31 n32 n1
This matrix is added (exclusive-OR) to a 48-bit subkey. There are 8 rows, corresponding to 8 S-boxes. Each S-box has 4 rows and 16 columns. The first and last bit of a row of the preceding matrix picks out a row of an S-box, and the middle 4 bits pick out a column.
P10
10-bit key
8-bit plaintext
ENCRYPTION DECRYPTION
8-bit ciphertext 8-bit ciphertext
Figure C.1 Simplified DES Scheme
8-bit plaintext
Shift
P8
Shift
P8
fK
K1
K2 K2
K1
SW
IP–1
IP
fK
fK
SW
IP
IP-1
fK
P10
10-bit key
P8
K1
P8
LS-1 LS-1
LS-2 LS-2
K2
5
10
5
5
8
8
5
5 5
Figure C.2 Key Generation for Simplified DES
IP
8-bit plaintext
8-bit ciphertext
Figure C.3 Simplified DES Encryption Detail
IP–1
E/P
P4
S0
K1
S1
+
+
f
K
F
SW
8
8
8
8
4
4
2 2
4
4
4
4
4
E/P
P4
S0
K2
S1
+
+
f
K
F 8
8
4
4
2 2
4
4
4
Create a program to encrypt and decrypt binary files using S-DES (Simplified DES) in the Cipher Block Chaining mode. The program takes the input of an initial key and an initial vector, reads the plaintext or ciphertext from a file, conducts the encryption or decryption, and writes the resulting ciphertext or plaintext into a second file.
This is a group project with no more than two students in a group. You can use any of your preferred programming languages and operating systems. The code must be welldocumented for easy understanding.
Input Format:
The program should take a command in the following format.
(java) mycipher -m mode -k initial_key -i initial_vector -p plaintext_file -c ciphertext_file
mode: can be only encrypt or decrypt
initial_key: 10-bit initial key
initial_vector: 8-bit initial vector
plaintext_file: a binary (not text) file to store the plaintext
ciphertext_file: a binary (not text) file to store the ciphertext
Output Format:
The program should print output in the following format.
k1=subkey 1
k2=subkey 2
plaintext=all bytes of the plaintext separated by blanks, starting from the first byte
ciphertext= all bytes of the ciphertext separated by blanks, starting from the first byte
Sample Screen Shot:
Sample Test Cases:
java mycipher -m encrypt -k 0111111101 -i 10101010 -p f1 -c f3
k1=01011111
k2=11111100
plaintext=00000001 00100011
ciphertext=11110100 00001011
java mycipher -m decrypt -k 0101010101 -i 00000000 -p f4 -c f2
k1=00011011
k2=10101100
ciphertext=00000001
plaintext=01101000
where f1 is a binary file with two bytes 012316,
and f2 is a binary file with one byte 0116.
IMPORTANT: Make sure that your program exactly follows the above specifications, including the execute/java class file name, the command line input format, and the output format. The TA will test your program by typing testing commands as specified above. If your program cannot give the correct output for a command, you will not receive the credit.
Submission Guide:
Operating System: any, if not Windows/Linux/Mac OS, need to show your code on your own computer.
Programing Language: any, if not Java/Python/C/C++, need to show your code on your own computer.
Please submit your source code and a readme file through Moodle. The readme file should including the following information:
Operating System: xxx
Programming Language: xxx
Compiling Instruction: the command line to compile your code.
Grading Criteria:
Item Percentage
Successful compilation 15%
S-DES key generation 20%
S-DES encryption 15%
S-DES decryption 15%
CBC mode S-DES with single block 15%
CBC mode S-DES with multiple blocks 20%
A PPENDIX PPENDIX C
Simplified Simplified DES
C.1 Overview...................................................................................................................2
C.2 S-DES Key Generation .............................................................................................3
C.3 S-DES Encryption.....................................................................................................3
Initial and Final Permutations..................................................................................3
The Function fK.......................................................................................................4
The Switch Function................................................................................................5
C.4 Analysis of Simplified DES......................................................................................5
C.5 Relationship to DES..................................................................................................6
William Stallings
Copyright 2006
Supplement to
Cryptography and Network Security, Fourth Edition
Prentice Hall 2006
ISBN: 0-13-187316-4
http://williamstallings.com/Crypto/Crypto4e.html
8/5/05
C-2
Simplified DES, developed by Professor Edward Schaefer of Santa Clara University [SCHA96], is an educational rather than a secure encryption algorithm. It has similar properties and structure to DES with much smaller parameters. The reader might find it useful to work through an example by hand while following the discussion in this Appendix.
C.1 Overview
Figure C.1 illustrates the overall structure of the simplified DES, which we will refer to as SDES. The S-DES encryption algorithm takes an 8-bit block of plaintext (example: 10111101) and a 10-bit key as input and produces an 8-bit block of ciphertext as output. The S-DES decryption algorithm takes an 8-bit block of ciphertext and the same 10-bit key used to produce that ciphertext as input and produces the original 8-bit block of plaintext.
The encryption algorithm involves five functions: an initial permutation (IP); a complex function labeled fK, which involves both permutation and substitution operations and depends on a key input; a simple permutation function that switches (SW) the two halves of the data; the function fK again; and finally a permutation function that is the inverse of the initial permutation (IP–1). As was mentioned in Chapter 2, the use of multiple stages of permutation and substitution
results in a more complex algorithm, which increases the difficulty of cryptanalysis.
The function fK takes as input not only the data passing through the encryption algorithm, but also an 8-bit key. The algorithm could have been designed to work with a 16-bit key, consisting of two 8-bit subkeys, one used for each occurrence of fK. Alternatively, a single 8-bit key could have been used, with the same key used twice in the algorithm. A compromise is to use a 10-bit key from which two 8-bit subkeys are generated, as depicted in Figure C.1. In this case, the key is first subjected to a permutation (P10). Then a shift operation is performed. The
output of the shift operation then passes through a permutation function that produces an 8-bit output (P8) for the first subkey (K1). The output of the shift operation also feeds into another shift and another instance of P8 to produce the second subkey (K2). We can concisely express the encryption algorithm as a composition1 of functions:
IP-1 ofK2 oSW ofK1 oIP
which can also be written as:
!
ciphertext = IP-1 fK2
SW fK1 ( ( ( (IP(plaintext)))))
where
K1 = P8(Shift(P10(key)))
K2 = P8(Shift(Shift(P10(key))))
Decryption is also shown in Figure C.1 and is essentially the reverse of encryption:
!
plaintext = IP-1 fK1
SW fK2 ( ( ( (IP(ciphertext)))))
1 Definition: If f and g are two functions, then the function F with the equation y = F(x) = g[f(x)] is called the composition of f and g and is denoted as
F = g of . 8/5/05 C-3
We now examine the elements of S-DES in more detail.
C.2 S-DES Key Generation
S-DES depends on the use of a 10-bit key shared between sender and receiver. From this key, two 8-bit subkeys are produced for use in particular stages of the encryption and decryption algorithm. Figure C.2 depicts the stages followed to produce the subkeys. First, permute the key in the following fashion. Let the 10-bit key be designated as (k1, k2, k3, k4, k5, k6, k7, k8, k9, k10). Then the permutation P10 is defined as:
P10(k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) = (k3, k5, k2, k7, k4, k10, k1, k9, k8, k6)
P10 can be concisely defined by the display:
P10 3 5 2 7 4 10 1 9 8 6
This table is read from left to right; each position in the table gives the identity of the input bit that produces the output bit in that position. So the first output bit is bit 3 of the input; the second output bit is bit 5 of the input, and so on. For example, the key (1010000010) is permuted
to (1000001100). Next, perform a circular left shift (LS-1), or rotation, separately on the first five bits and the second five bits. In our example, the result is (00001 11000).
Next we apply P8, which picks out and permutes 8 of the 10 bits according to the following rule: P8 6 3 7 4 8 5 10 9
The result is subkey 1 (K1). In our example, this yields (10100100)
We then go back to the pair of 5-bit strings produced by the two LS-1 functions and perform a circular left shift of 2 bit positions on each string. In our example, the value (00001 11000) becomes (00100 00011). Finally, P8 is applied again to produce K2. In our example, the result is (01000011).
C.3 S-DES Encryption
Figure C.3 shows the S-DES encryption algorithm in greater detail. As was mentioned, encryption involves the sequential application of five functions. We examine each of these. Initial and Final Permutations
The input to the algorithm is an 8-bit block of plaintext, which we first permute using the IP function:
IP
2 6 3 1 4 8 5 7
This retains all 8 bits of the plaintext but mixes them up. At the end of the algorithm, the inverse
permutation is used:
8/5/05
C-4
IP–1
4 1 3 5 7 2 8 6
It is easy to show by example that the second permutation is indeed the reverse of the first; that is, IP–1(IP(X)) = X.
The Function fK
The most complex component of S-DES is the function fK, which consists of a combination of permutation and substitution functions. The functions can be expressed as follows. Let L and R be the leftmost 4 bits and rightmost 4 bits of the 8-bit input to fK, and let F be a mapping (not necessarily one to one) from 4-bit strings to 4-bit strings. Then we let fK(L, R) = (L ! F(R, SK), R)
where SK is a subkey and ! is the bit-by-bit exclusive-OR function. For example, suppose the output of the IP stage in Figure C.3 is (10111101) and F(1101, SK) = (1110) for some key SK.
Then fK(10111101) = (01011101) because (1011) ! (1110) = (0101).
We now describe the mapping F. The input is a 4-bit number (n1n2n3n4). The first operation is an expansion/permutation operation:
E/P
4 1 2 3 2 3 4 1
For what follows, it is clearer to depict the result in this fashion:
n4 n1 n2 n3
n2 n3 n4 n1
The 8-bit subkey K1 = (k11, k12, k13, k14, k15, k16, k17, k18) is added to this value using exclusiveOR:
n4 ! k11 n1 ! k12 n2 ! k13 n3 ! k14
n2 ! k15 n3 ! k16 n4 ! k17 n1 ! k18
Let us rename these 8 bits:
p0,0 p0,1 p0,2 p0,3
p1,0 p1,1 p1,2 p1,3
The first 4 bits (first row of the preceding matrix) are fed into the S-box S0 to produce a 2-bit output, and the remaining 4 bits (second row) are fed into S1 to produce another 2-bit output.
These two boxes are defined as follows:
8/5/05
C-5
!
S0 =
0 1 2 3
0
1
2
3
1 0 3 2
3 2 1 0
0 2 1 3
3 1 3 2
"
#
$
$
$
%
&
'
'
'
S1=
0 1 2 3
0
1
2
3
0 1 2 3
2 0 1 3
3 0 1 0
2 1 0 3
"
#
$
$
$
%
&
'
'
'
The S-boxes operate as follows. The first and fourth input bits are treated as a 2-bit number that specify a row of the S-box, and the second and third input bits specify a column of the Sbox.
The entry in that row and column, in base 2, is the 2-bit output. For example, if (p0,0p0,3) = (00) and (p0,1p0,2) = (10), then the output is from row 0, column 2 of S0, which is 3, or (11) in binary. Similarly, (p1,0p1,3) and (p1,1p1,2) are used to index into a row and column of S1 to produce an additional 2 bits.
Next, the 4 bits produced by S0 and S1 undergo a further permutation as follows:
P4 2 4 3 1
The output of P4 is the output of the function F.
The Switch Function The function fK only alters the leftmost 4 bits of the input. The switch function (SW) interchanges the left and right 4 bits so that the second instance of fK operates on a different 4 bits. In this second instance, the E/P, S0, S1, and P4 functions are the same. The key input is K2.
C.4 Analysis of Simplified DES A brute-force attack on simplified DES is certainly feasible. With a 10-bit key, there are only 210 = 1024 possibilities. Given a ciphertext, an attacker can try each possibility and analyze the result to determine if it is reasonable plaintext.
What about cryptanalysis? Let us consider a known plaintext attack in which a single plaintext (p1, p2, p3, p4, p5, p6, p7, p8) and its ciphertext output (c1, c2, c3, c4, c5, c6, c7, c8) are known and the key (k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) is unknown. Then each ci is a polynomial
function gi
of the pj
's and kj
's. We can therefore express the encryption algorithm as 8 nonlinear equations in 10 unknowns. There are a number of possible solutions, but each of these could be calculated and then analyzed. Each of the permutations and additions in the algorithm is a linear mapping. The nonlinearity comes from the S-boxes. It is useful to write down the equations for these boxes. For clarity, rename (p0,0, p0,1,p0,2, p0,3) = (a, b, c, d) and (p1,0, p1,1,p1,2, p1,3) = (w, x,
y, z), and let the 4-bit output be (q, r, s, t) Then the operation of the S0 is defined by the following equations:
q = abcd + ab + ac + b + d
r = abcd + abd + ab + ac + ad + a + c + 1
where all additions are modulo 2. Similar equations define S1. Alternating linear maps with these nonlinear maps results in very complex polynomial expressions for the ciphertext bits, making cryptanalysis difficult. To visualize the scale of the problem, note that a polynomial equation in 10 unknowns in binary arithmetic can have 210 possible terms. On average, we might therefore 8/5/05
C-6
expect each of the 8 equations to have 29 terms. The interested reader might try to find these equations with a symbolic processor. Either the reader or the software will give up before much progress is made.
C.5 Relationship to DES
DES operates on 64-bit blocks of input. The encryption scheme can be defined as:
IP-1 ofK16 oSW ofK15 o SW oLo SW ofK1 oIP
A 56-bit key is used, from which sixteen 48-bit subkeys are calculated. There is an initial permutation of 64 bits followed by a sequence of shifts and permutations of 48 bits. Within the encryption algorithm, instead of F acting on 4 bits (n1n2n3n4), it acts on 32 bits (n1…n32). After the initial expansion/permutation, the output of 48 bits can be diagrammed as:
n32 n1 n2 n3 n4 n5
n4 n5 n6 n7 n8 n9
•
•
•
•
•
•
•
•
•
n28 n29 n30 n31 n32 n1
This matrix is added (exclusive-OR) to a 48-bit subkey. There are 8 rows, corresponding to 8 S-boxes. Each S-box has 4 rows and 16 columns. The first and last bit of a row of the preceding matrix picks out a row of an S-box, and the middle 4 bits pick out a column.
P10
10-bit key
8-bit plaintext
ENCRYPTION DECRYPTION
8-bit ciphertext 8-bit ciphertext
Figure C.1 Simplified DES Scheme
8-bit plaintext
Shift
P8
Shift
P8
fK
K1
K2 K2
K1
SW
IP–1
IP
fK
fK
SW
IP
IP-1
fK
P10
10-bit key
P8
K1
P8
LS-1 LS-1
LS-2 LS-2
K2
5
10
5
5
8
8
5
5 5
Figure C.2 Key Generation for Simplified DES
IP
8-bit plaintext
8-bit ciphertext
Figure C.3 Simplified DES Encryption Detail
IP–1
E/P
P4
S0
K1
S1
+
+
f
K
F
SW
8
8
8
8
4
4
2 2
4
4
4
4
4
E/P
P4
S0
K2
S1
+
+
f
K
F 8
8
4
4
2 2
4
4
4
1 file (11.6KB)
