DES 알고리즘에서 가장 중요한 부분은, 바로 3단계에서 진행되는 f 연산, Feistel Function이다. f 연산은 크게 세 부분으로 나뉘어진다.
1. 32비트를 48비트로 확장하는 Expansion Permutation
2. 보조키 Ki와 48비트의 XOR 연산
3. 확장된 48비트를 6비트씩 8 묶음으로 나누어 복잡한 처리과정을 거친 뒤 다시 32비트로 바꾸는 s-box 연산
4. 32비트를 단순히 자리만 바꾸는 p-box 연산
먼저, Expasion Permutation은 앞 라운드에서 처리되어 넘어온 64비트 가운데 오른쪽 절반인 32비트인 Ri-1를 48비트로 늘려주는 과정이다. 비트를 늘려주는 이유는, 48비트인 보조키 Ki와 XOR 연산이 가능하도록 크기를 맞추기 위해서이다. Expasion Permutation 테이블은 다음과 같다.
32 01 02 03 04 05 04 05 06 07 08 09
08 09 10 11 12 13 12 13 14 15 16 17
16 17 18 19 20 21 20 21 22 23 24 25
24 25 26 27 28 29 28 29 30 31 32 01
이렇게 생성된 비트열과 해당 라운드의 보조키 Ki를 XOR 연산하고, s-box 처리를 하게 된다. s-box 처리는 DES 알고리즘의 가장 핵심적인 부분이면서 매우 복잡한 처리 과정을 거친다. 먼저, 전 단계에서 48비트로 바뀐 수열은 각각 6비트씩 8 묶음으로 나뉜 다음, 8개의 s-box 치환을 거친다. 0번째 비트와 5번째 비트는 행을 결정하며, 1번째 비트부터 4번째 비트까지는 열을 결정한다. 예를 들어, 010000이라면, 00은 10진수로 0이므로 행의 번호는 0이고, 1000은 10진수로는 8이므로 열의 번호는 8이된다. 테이블에서 (0, 8)에 해당하는 값을 2진수로 변환한다. 0011을 얻게 될 것이다. (테이블은 생략) 각각의 s-box 치환을 하고나면 6비트는 4비트의 연산 결과가 나오기 때문에, 32비트 결과를 얻게 된다.
f 연산의 마지막 과정으로, 이 32비트열을 p-box 연산처리하게 되는데, p-box 연산은 단순한 자리바꿈이다. 테이블은 다음과 같다.
16 07 20 21 29 12 28 17 01 15 23 26 05 18 31 10
02 08 24 14 32 27 03 09 19 13 30 06 22 11 04 25
Reference
최병문, 이영환(2007), 암호의 세계, 경문사