DES
DES는 미국의 국가 안보국 NSA에서 IBM의 루시퍼 알고리즘을 개량하여 만든 대칭키 암호입니다.
DES는 루시퍼에서 128비트 키를 사용했던 것과 달리 키 길이를 56비트로 줄였고, 내부에서 사용하는 알고리즘도 일부 변경하였습니다.
미국 국립표준기술연구소 NIST는 DES를 1976년부터 2002년까지 표준 블록 암호로 인정했습니다만 현대에는 DES에 대한 공격 기법이 많이 연구되어 DES를 더이상 블록 암호의 표준으로 사용하지 않습니다.
DES는 혼돈 성질을 만족하기 위해 치환을, 확산 성질을 만족하기 위해 순열을 사용합니다.
치환과 순열을 매우 단순한 연산이므로 평문에 이들을 한 번 적용한다고 해서 암호학적 효과를 기대할 수는 없습니다. 그러나 이들을 여러 번 교차해서 반복 적용하면 혼돈과 확산의 성질을 모두 만족하게 된다고 알려져 있습니다.
이런 특성을 이용하여 치환이나 순열 같은 단순한 연산들로 한 라운드로 구성하고, 각 라운드를 여러 번 반복하여 암호학적 안전성을 확보하는 암호를 곱 암호(Product Cipher)라고 합니다.
DES는 8바이트(64비트)를 한 블록으로 하는 블록 암호이며, 전체 구조는 초기 순열, 최종 순열, 페이스텔 구조의 16 라운드, 그리고 각 라운드에 사용되는 48비트의 키를 생성하는 키 생성 함수(Key Generation)로 구성되어 있습니다.
DES 구조
페이스텔 구조
DES에서 라운드 함수를 적용하는 전체 과정은 페이스텔 구조를 이루고 있습니다.
페이스텔 구조는 데이터를 두부분으로 나누어 좌, 우 두부분에 교대로 비선형 변환을 적용시키는 구조를 말하며 이를 3단계로 나누면
입력으로 들어온 블록을 동일한 길이의 왼쪽 블록과 오른쪽 블록으로 나눕니다.
각 라운드마다 오른쪽 블록은 다음 라운드의 왼쪽 블록으로 입력됩니다.
왼쪽 블록은 오른쪽 블록에 라운드 함수를 적용한 결과와 xor되어 다음 라운드의 오른쪽 블록으로 입력됩니다.
수식으로 표현하면
1. \( L_{0} = P[:len(P)/2], R_{0} = P[len(P)/2:] \)
2. \( L_{n+1} = R_{n} \)
3. \( R_{n+1}=L_{n} \bigoplus F(R_{n}, K_{n}) \)
블록 암호는 평문을 복호화 할 수 있어야 하므로, 일반적으로 암호화를 구성하는 각 함수들에 역함수가 존재합니다.
그러나 페이스텔 구조를 사용하면 \(\bigoplus\)의 특성상 역함수가 존재하지 않아도 됩니다.
또한 암호화와 복호화의 구조가 동일하므로, 암호화에 사용한 라운드 키를 역순으로 입력하면 복호화가 이뤄집니다.
한편, 오른쪽 블록은 다음 라운드의 왼쪽 블록으로 어떠한 처리도 없이 입력됩니다.
이런 특성으로 인해 페이스텔 암호는 비페이스텔 암호와 같은 안전성을 갖기 위해 두 배 정도 라운드를 사용해야한다는 단점이 있습니다.
Step1 초기 순열 & Step 3 최종 순열
DES는 시작할 때 초기 순열을, 마지막에는 최종 순열을 수행하며 초기 순열과 최종 순열은 서로 역관계에 있습니다.
임의의 64비트 데이터에 초기 순열을 적용하고, 최종 순열을 적용하면 입력 값이 그대로 출력됩니다.
초기 순열과 최종 순열은 정해진 테이블을 이용하여 64비트 입력을 비트 단위로 전치합니다.
테이블의 n번째 값이 m일 때, 출력의 n번째 비트는 입력의 m번째 비트가 됩니다.
초기 순열과 최종 순열은 각각 초기 순열 테이블과 최종 순열 테이블을 이용합니다.
IPT = [58, 50, 42, 34, 26, 18, 10, 2,
60, 52, 44, 36, 28, 20, 12, 4,
62, 54, 46, 38, 30, 22, 14, 6,
64, 56, 48, 40, 32, 24, 16, 8,
57, 49, 41, 33, 25, 17, 9, 1,
59, 51, 43, 35, 27, 19, 11, 3,
61, 53, 45, 37, 29, 21, 13, 5,
63, 55, 47, 39, 31, 23, 15, 7]
FPT = [40, 8, 48, 16, 56, 24, 64, 32,
39, 7, 47, 15, 55, 23, 63, 31,
38, 6, 46, 14, 54, 22, 62, 30,
37, 5, 45, 13, 53, 21, 61, 29,
36, 4, 44, 12, 52, 20, 60, 28,
35, 3, 43, 11, 51, 19, 59, 27,
34, 2, 42, 10, 50, 18, 58, 26,
33, 1, 41, 9, 49, 17, 57, 25]Step2. 라운드 함수
라운드 함수에는 오른쪽 블록만 입력되므로, 입력의 길이는 32비트입니다. 라운드 함수는 확장 순열, 라운드 키 결합, 치환 테이블 그리고 고정 순열로 이루어져 있습니다.
Step 2.1. 확장 순열과 라운드 키 결합
확장 순열은 입력을 비트 단위로 전치하는 동시에, 전체 길이를 48비트로 확장합니다.
이 과정에서 32비트의 입력값을 4비트씩 8개의 부분으로 나누고, 테이블을 참조하여 각각을 6비트로 확장합니다.
이 과정은 테이블만 다를 뿐, 초기 순열, 최종 순열과 같은 방식으로 이뤄집니다.
라운드 키 결합은 확장 순열로 나온 출력을 라운드 키와 \(\bigoplus\) xor 하는 것입니다.
Step2.2. S-Box와 고정 순열
S-Box는 라운드 키 결합에서 출력된 48비트 결과 값을 32비트로 축소합니다.
S-Box는 4개의 행과 16개의 열로 이루어진 표를 사용하는데, 표의 각 값은 4비트로 표현되는 수입니다.
S-Box가 적용되는 과정은 다음과 같습니다.
먼저, 입력을 6비트씩 8개의 부분으로 나눕니다. 여섯 비트 중 첫 번째와 마지막 비트로 행을 결정하고, 나머지 네 개의 비트로 열을 결정합니다. 그 뒤, S-Box의 표에서 행과 열을 참조하여 값을 반환합니다. DES에서는 여섯 비트로 자른 부분마다 다른 S-Box를 사용합니다.
S-Box로 길이를 축소하고 나면, 고정 순열(Straight P-Box)로 다시 비트 단위 전치가 이뤄집니다.
키 생성 함수
키 생성 함수는 64비트의 입력을 받아 각 라운드에 필요한 48비트 라운드 키를 생성하는 함수입니다.
이 함수는 패리티 비트 제거, 쉬프트, 압축 순열로 구성되어 있습니다.
패리티 비트 제거
패리티 비트 제거는 입력에서 패리티 비트를 제거하고, 남은 56비트에 순열을 적용하는 과정입니다.
DES의 비밀키에서 각 바이트의 가장 오른쪽 비트는 자신이 속한 바이트의 나머지 7비트에 대한 홀수 패리티 비트입니다. 홀수 패리티 비트란 한 바이트를 이진수로 표현했을 때, 1의 개수가 홀수가 되도록 덧붙인 비트를 말합니다. 예를 들어, 1010101에는 1이 4개 있습니다. 홀수 패리티 비트를 적용하면 끝에 비트 1을 덧붙여서, 10101011을 전송해야 합니다.
패리티 비트는 통신 중에 비트 반전이 일어나지 않았음을 보증하는 역할을 합니다. 홀수 패리티 비트를 사용하여 통신할 때, 수신한 바이트 중 1의 갯수가 짝수인 바이트가 있다면 그 바이트에서 임의의 비트에 반전이 일어났음을 수신자가 알 수 있습니다. 이를 확인한 수신자는 손상되지 않은 데이터를 얻기 위해 재전송을 요구할 수 있습니다.
쉬프트
쉬프트는 입력을 왼쪽 28비트와 오른쪽 28비트로 나누어 각각을 1비트나 2비트만큼 왼쪽으로 순환 쉬프트하는 과정입니다. 1, 2, 9, 16 라운드에서는 1비트, 나머지 라운드에서는 2비트만큼 쉬프트합니다.
10101111을 왼쪽으로 1비트 순환 쉬프트하면, 왼쪽 끝의 비트가 오른쪽 끝으로 이동하여 01011111이 됩니다. 마찬가지로 2비트를 왼쪽으로 순환 쉬프트하면 왼쪽 끝의 '10'이 오른쪽으로 이동하여 10111110이 됩니다.
압축 순열
압축 순열은 56비트의 입력을 48비트 길이로 압축하는 과정입니다. 수행 방법은 앞서 설명한 순열들과 같습니다.
