DES 암호 [Crypto]

Crypto

DES 암호 [Crypto]

Ohs_ 2020. 2. 28. 20:22

DES : Data Encryption Standard

1970년대, 안전한 암호의 이용에 대한 요구가 증가했습니다. 1, 2차 세계대전이 끝난 이후 암호 시스템을 민간인도 사용할 수 있게 해달라고 요구가 생기게 됩니다. 1973년 5월, NBS(National Bureau of Standars)는 NSA(National Security Agency)와 협의 후 표준 암호알고리즘을 공모하기로 결정합니다. 그 공모 결과로는 적합한 할고리즘이 없었습니다. 1974년 8월, 2차 공모를 진행하고 IBM에서 자사의 Lucifer를 기반으로 개선된 암호알고리즘을 제출하게 됩니다. Lucifer는 Feistel이 개발한 암호알고리즘입니다. 1975년 3월 표준 암호알고리즘이 결정되고 그 알고리즘은 DES 입니다. 1977년 1월, 연방정보처리규격(FIPS) 등록 및 공개가 됩니다.

- 규격

키 길이 : 64비트(56비트 + parity 비트)

평문 블록 길이 : 64비트

암/복호화 반복 횟수 : 16회

기본 구조 : Feistel Network

기본 방식 : IBM의 Lucifer

개선 방식 : Triple Des, G-Des, Des-X, LOKI89, ICE 등

- 암호화

DES의 암호화는 크게 초기전치(IP), 16회 암호화, 역전치, F 함수에서 전치와 환자 실행으로 구성됩니다.

- ①초기전치 : 평문 64비트는 초기 전치(IP : Initial Permutation)표에 의해 64비트로 변환됩니다.

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

- 위의 표는 IP 이며 각 숫자의 의미는 '58번째 비트를 1번째 비트로 이동 50번째 비트를 2번째 비트로 이동 ~ 15번째 비트를 63번째 비트로 이동 7번째 비트를 64번째 비트로 이동'이라는 의미를 가집니다. 해당 표는 표준 표로 따로 정의가 없다면 해당 표를 사용한 초기 전치를 진행하게 됩니다. 초기 전치가 완료 된 후 32비트씩 절반으로 나누어 다음 과정인 반복 연산을 진행하게 됩니다.

- ②반복 연산

Lucifer 의 암호화 과정을 16번 반복하는 구간입니다. 초기 전치 후 32비트 씩 나누어진 블록을 이용하여 암호화를 진행하게 됩니다.

L, R은 앞의 64비트를 절반으로 나눈 값이며 F는 확장전치를 하는 구간입니다. K는 키값이며 키값을 생성하는 연산으로 인해 48비트가 되어있는 상태입니다. 초록 박스는 XOR 연산을 나타냅니다. 각 반복마다 R값은 L값으로 이동하고 R값과 키값을 이용하여 F함수 연산을 합니다. 그리고 L값과 F 함수 연산값을 XOR 연산 후 다음 R값으로 보내지게 됩니다.

F 함수의 확장전치를 하는 이유는 생성된 키값이 48비트이고 키값을 이용해 암호화를 해야하는 R은 32비트이기 때문에 블록 암호의 특징중 하나인 길이를 맞춰줘야 하기 때문에 R을 48비트로 확장시켜주는 연산을 진행하여 길이를 맞춰줍니다. 길이가 맞춰진 R값과 K값을 XOR 연산을 진행합니다. 그리고 연산된 48비트의 값을 8개의 블록으로 나누어 줍니다. '48 / 8 = 6'가 되기 때문에 각 블록은 6비트 씩 나눠지게 됩니다. 8개의 블록으로 나누는 이유는 연산된 48비트를 다시 32비트로 줄여줘야 기존의 L 값과 XOR 연산을 할 수 있기 때문입니다. 그리고 8개의 블록인 이유는 F 함수 내에는 S-BOX라는 6비트로 된 블록을 4비트로 줄여주는 BOX가 있습니다.

양쪽 맨끝 비트(11)는 행 가운데 비트(0110)는 열을 나타내어 6비트를 4비트의 값으로 바꿔줍니다. S-BOX는 따로 정의해주지 않는다면 S-BOX 표준을 사용합니다. S-BOX는 8개가 존재하고 각각의 BOX에 한블록씩 배치되어 4비트로 줄이는 과정을 진행합니다.

S-BOX 연산까지 끝난 F함수를 L과 XOR 연산을 하고 다음 R값으로 넘겨줍니다.

이렇게 해당 과정을 16번 반복합니다.

- ③역전치(IP^-1)

16번 반복 후 역 IP를 이용해 전치를 진행합니다. 이 과정이 암호화 과정의 마무리입니다.

- DES의 키생성

DES는 암호화 과정만큼 키생성 과정도 복잡합니다. 키의 길이는 8비트씩 8개 총 64비트로 이루어져 있으며 각 비트의 끝부분에 오류 검출을 위한 페리티 비트가 포함되어 있습니다. 그래서 실질적인 키의 길이는 56비트 입니다. 64비트의 키를 이용하여 48비트의 서브키를 만들고 해당 서브키를 각 반복마다 연산에 사용합니다.

- ①키 설정

K 는 암호화하는 사용자가 정한 56비트의 키값입니다. 앞서 말했듯이 56비트에 8비트의 패리티 비트(오류검출비트)가 붙어 총 64비트 입니다. 실질적으로 사용하는 비트는 56비트 입니다.

- ②평형전치(PC-1)

평형 전치를 진행합니다. 단순한 전치로 미리 정해진 표준 PC-1 이라는 태이블을 이용하여 앞의 DES 암호화 시 맨처음 수행했던 IP와 같은 원리로 전치를 진행합니다. 또한 맨 끝의 패리티 비트를 제거하여 실질적인 키값인 56비트만 남게하고 서브키 생성을 위해 절반으로 나눕니다.

57	49	41	33	25	17	9
1	58	50	42	34	26	18
10	2	59	51	43	35	27
19	11	3	60	52	44	36

<왼쪽(C0)>

63	55	47	39	31	23	15
7	62	54	46	38	30	22
14	6	61	53	45	37	29
21	13	5	28	20	12	4

<오른쪽(D0)>

위의 테이블을 이용하여 전치를 하고 28비트씩 반으로 나눕니다.

- ③Rotate

왼쪽으로 정해진 횟수(반복한 라운드 수)만큼 Rotate(Cyclic Shift)시킵니다.(암호 해독할 때는 오른쪽으로 이동합니다.) 첫 번째 키는 1번만 rotate 시킵니다.

해당 과정을 거처서 C1과 D1이 생성됩니다.

- ④축약전치(PC-2)

축약전치 과정을 통해 나눠진 두 블록을 하나로 합치고 각 라운드에 사용 될 서브 키가 생성이 됩니다. 또한 이름에서도 알 수 있듯이 축약 전치이기 때문에 두 블록이 합쳐진 후 56비트가 아닌 48비트로 축약하는 과정이 포함됩니다. 축약하는 방법은 PC-2 테이블을 이용하여 축약을 진행합니다 축약 방법은 IP 를 이용한 전치 과정과 동일합니다. 단 테이블에 없는 값은 버려지는 값으로 8개의 비트가 테이블에 지정이 안되어 있고 그렇기 때문에 48비트로 축약이 가능합니다.

14	17	11	24	1	5
3	28	15	6	21	10
23	19	12	4	26	8
16	7	27	20	13	2
41	52	31	37	47	55
30	40	51	45	33	48
44	49	39	56	34	53
46	42	50	36	29	32

<PC-2 테이블>

축약전치 과정을 통해 첫 번째 서브키가 생성됐고 2번째 암호화 라운드에 사용될 서브키를 생성하기 위해 축약전치 연산을 하지않은 C1과 D1은 다음 라운드로 이동하여 2라운드의 서브키를 생성하게 됩니다.

- 해당 서브키생성 과정을 반복하여 총 16개의 서브키를 생성합니다. DES 키스케줄링에는 환자가 없는 것이 특징이고 암호화의 각 라운드마다 키를 생성해도 되지만 미리 키생성만 시켜놓고 암호화 시 미리 생성해 놓은 서브키를 이용하여 빠르게 암호화도 가능합니다.

- 복호화

DES의 암호화과정과 키생성은 위와같은 방식으로 진행되며 DES로 암호화된 내용을 복호화 하는 방법은 암호화 과정을 똑같이 반복하되 키값을 16번째 라운드에 사용한 서브키 부터 1번째에 사용한 키 순서로 즉 서브키 순서만 반대로하여 위의 과정을 똑같이 진행하면 복호화가 됩니다.

저작자표시 비영리 변경금지

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

14	17	11	24	1	5
3	28	15	6	21	10
23	19	12	4	26	8
16	7	27	20	13	2
41	52	31	37	47	55
30	40	51	45	33	48
44	49	39	56	34	53
46	42	50	36	29	32

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

14	17	11	24	1	5
3	28	15	6	21	10
23	19	12	4	26	8
16	7	27	20	13	2
41	52	31	37	47	55
30	40	51	45	33	48
44	49	39	56	34	53
46	42	50	36	29	32

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

14	17	11	24	1	5
3	28	15	6	21	10
23	19	12	4	26	8
16	7	27	20	13	2
41	52	31	37	47	55
30	40	51	45	33	48
44	49	39	56	34	53
46	42	50	36	29	32