DES 이해
DES에 대해서 이해해보자.
1. INTRODUCTION
i. History
DES는 대칭키 블록암호로 미국국립기술표준원(NIST, National Institute of Standards Technology)에서 공표하였다.
+ 우리나라에서 개발한 대칭키 암호로는 SEED가 있다.
ii. Overview
DES는 64비트 블록암호이다.
8비트(ASCII code)가 하나의 문자를 구성하므로 64비트는 8개의 문자이다.
8개의 문자를 한꺼번에 암호화 하는것이다.
이후로 들어오는 문자들을 64비트씩 동일한 키로 암호화한다.
이후에 이들을 합하면 전체 암호문이 된다.
블록 암호 DES를 대략적(전체적)으로 나타내면 다음 그림과 같다.
64비트 평문을 암호화 과정(DES cipher = Encryption)을 거쳐 64비트 암호문이 나온다.
암호문은 복호화 과정(DES reverse cipher = Decryption)을 거쳐 64비트 평문이 된다.
이 과정에서 56비트 키가 중요하게 작용한다.
왜 64비트가 아니고 56비트 키인가 하면, 처음에 64비트 평문이 주어질 때 본래 original key는 64비트로 주어진다.
이를 8비트씩 끊었을 때, Parity Bit(= 검사 비트)가 안에 하나씩 존재한다.
8비트에서 이 Parity Bit를 하나씩 총 8개를 제외했더니 나오는게 56비트인 것이다.
이렇게 나온 56비트 키는 Split -> 28비트 / 28비트로 나누어졌다가 압축(conpression)되어 48비트로 또 다시 변하게 된다.
치환에서 straight 치환, 확장 치환, 축소 치환이 있다.
DES에서는 이 세개를 다 사용한다.
어떨 때는 확장 치환, 어떨 떄는 축소 치환을 한다.
또 처음에 하는 초기치환(Initial Permutation)이라는게 있고, 마지막 최종치환으로 straight 치환이 있다.
초기치환 -> 확장 or 축소치환 등 -> 최종치환(straight 치환) 순서이다.
확장 치환은 비트가 늘어나는거고, straight는 유지, 축소는 줄어드는 것이다.
이러한 암호화를 블록단위로 한다고 해서 블록암호라고 한다.
이에 대해서는 밑에서 다시 다루겠다.
2. DES STRUCTURE
암호화 과정은 2개의 치환(P-박스)과 16개의 Feistel 라운드 함수로 구성된다.
P-박스는 Straight 치환이고, 16개의 라운드를 거친다.(Feistel 구조)
블록 암호에는 Feistel 구조가 있고 non Feistel 구조가 있다.
non Feistel 구조는 모든 과정에서 역함수가 존재하는 것인데, 대표적으로 AES가 있다.
AES는 DES를 대치해서 만들어진 것이다.
DES에서 약점이 발견되어서 다시 연구를 통해 AES를 공표한 것이다.
DES는 역함수가 존재하는 것도 있지만 존재하지 않는 것도 있기 때문에 Feistel 구조이다.
평문을 암호문으로 변환 시킨다는 것은, 평문의 비트(0,1,0,1, …)를 변화시켜서 비트수가 달라져야 한다는 것이다.
비트수가 달라진다는 것은 평문의 1의 갯수가 유지되지 않는다는 것이다.
1의 갯수가 유지된다면 어떠한 패턴을 알아낼 수가 있게 된다.
이러한 갯수를 유지하지 않게 만들기 위해서 필요한 것이 라운드, 암호화 함수, 스왑같은 현대 대칭키 암호들의 구성요소들이다.
하지만 초기치환과 최종치환은 여기에 아무런 영향을 주지 않는다.
그렇다면 DES암호에 이러한 치환들이 왜 필요한가?
초기치환과 최종치환을 넣음으로서 Hardware로 구현하기가 좋게끔 할 수 있다.
사실 소프트웨어로 구현하기 위해서는 배열로 만들어도 초기치환도 최종치환도 64비트로 만들어야 한다.
왜냐하면 치환이라는 것은 64비트 배열 입력값이 있으면 64비트 결과가 나와야하는데 이게 상당히 쉽지 않을 수 있다.
따라서 굳이 초기치환과 최종치환을 넣은 것은 하드웨어로 구현할 때 좀 더 유리하기 때문이다.
위 그림은 전체적인 DES의 구조이다.
64비트 평문이 들어온다.
이전의 고전 암호에서는 문자 단위로 했지만, 이제는 비트 단위로한다.
처음에 Initial permutation(64비트 Straight 치환)을 한다.
치환을 하고 나면 Round 1을 하는데 이 라운드는 Mixer 부분과 Swap 부분으로 나뉘어진다.
Mixer 부분으로 들어가기 전에 64비트를 32비트 / 32비트로 나누어서 처음 32비트는 left에, 다음 32비트는 right로 둔다.
이를 Split이라고 한다.
Split도 현대 대칭키 암호의 구성 요소이다. 라운드를 돌 때 64비트에서 Parity Bit를 제외한 56비트 키가 들어온다. 총 16라운드를 돌아야하기 때문에 56비트 키로부터 각각의 라운드에서 돌게 되는 키(K1, K2, K3 … K16)를 생성해야한다.
이를 부분키라고 한다.
그런데 현재 라운드에 있는건 32비트 / 32비트인데 키는 48비트이다.
둘을 연산하기 위해서는 키 48비트를 축소(치환)해야한다.
그래야 xor 연산을 할 수 있다.
앞에서 말했지만 Round는 Mixer와 Swap으로 나뉘어지는데, Swap에서는 left와 right를 바꿔준다.
이렇게 mix와 swap을 하는 이유는 본래 평문이 가지고 있는 특징을 없애기 위해서이다.
이를 위해서 16라운드를 도는것이다.
그러면 왜 하필 16라운드 까지냐? 하고 물을 수 있을 것이다.
보안의 특성중 가용성이라는 것이 있다.
시간이 많이 걸리면 안된다는 뜻이다.
이러한 것을 모두 고려했을때 16라운드가 최적이라는 결론이다.
1라운드부터 쭉 돌다가 마지막 16번쨰 라운드에서는 Swap이 제외된다.
이유는 후술하겠다.
라운드를 마쳤으면 합병을 해서 64비트가 되고 마지막 Final permutation을 통하면 64비트 암호문이 완성된다.
i. 초기치환과 최종치환(Initial and Final Permutations)
치환(permutation)은 순서를 다 바꿔주는 것이다.
첫번째 있었던 비트(입력)는 40번째(출력)로 보내고, 58번째 있었던 비트(입력)는 첫번째(출력)로 오게 된다.
이런 초기 치환이 있다.
이후로 쭉 16라운드를 거쳐 64비트로 합병이 되고 Final Permutation에서 초기치환에서 58번째에 있었던 비트가 첫번째로 갔으므로, 첫번째 비트가 58번째 비트로 복귀된다.
40번째도 마찬가지로 첫번째 비트로 복귀된다.
결국 1은 1로, 58은 58로 갔으므로, 이것은 서로 역관계에 있음을 나타낸다.
앞서 했던 말을 다시 하자면, 라운드에서는 Mixer, Swap과정을 거친다.
이 때 마지막 16라운드에서는 Swap단계를 제외한다.
이유는 다시 복호화 과정을 거칠 때 서로 역연산이 이루어지게끔 하기 위해서이다.
!뒤 대괄호에 파일이름 Table_6.1, 경로 마지막 이미지파일명 Table_6.1로 지정했는데 엑박이 떴다… 왜일까? 바뀐건 t 대소문자 뿐이다.
처음에 initial Permutation을 할 때 앞에서부터 1 2 3 — 64비트까지 순서로 정하자.
이 때 58번째에 있는 값을 첫번째 자리로 가지고 오라는 뜻이다.
마찬가지로 50번째는 두번쨰로 가져온다.
첫번째 있던 것은 40번쨰로 갔을텐데 표에서는 보이지 않는다.
Final Permutation 첫번째 줄에서 40번째가 첫 번째로 복귀한것을 볼 수 있다.
다음은 예제이다.
입력을 초기치환을 하고 나면 출력이 나온다.
이를 확인해 보라는 예제이다.
입력으로 나와있는 것은 16진수이다.
따라서 0 하나가 0000을 나타낸다.
2는 0010을 의미한다.
즉, 15번쨰 비트가 1이다.
그리고 맨 마지막에 1이 있으므로 0001, 즉 64번째 비트가 1이다.
이제 15번째에 있던 1이 어디를 가고, 64번째에 있던 1이 어디로 가는지 테이블로부터 찾아야한다.
여기에는 올리지 않았지만, 테이블을 보면 15번쨰는 25번쨰로 가고, 64번째는 63번째로 갔다.
그러면 초기 치환에 의해서 25번째와 64번째만 1이 되어야한다.
초기치환과 최종치환은 역관계이기 때문에, 반대로 적용하면 결과값으로 위 예제의 입력값이 나오게 된다.
테이블(초기 치환 테이블)의 총 경우의 수는 64!이다.
그에 따른 역테이블(최종 치환 테이블)도 마찬가지이다.
이 경우의 수 중에 특정 테이블을 선정하는데에는 따로 큰 의미가 있는 것은 아니다.
현대 대칭키 암호의 의미는 혼돈과 확산을 주는 것이다.
테이블 선정에 이런 혼돈이나 확산을 주는데에는 영향이 없다.
확산은 평문이 가지고 있는 특징을 암호문으로 변환했을때 완전히 뭉개는 것을 의미한다.
이런 대칭키 암호에는 키가 반드시 들어가는데, 이 암호문과 키와의 관계를 무너뜨리는것이 혼돈이다.
확산과 혼돈 효과를 주기 위해 치환, 축소 등을 하는 것이다.
그러나 초기치환과 최종치환은 여기에 아무런 영향을 주지 않는다.
결론
초기치환과 최종치환은 서로 역의 관계에 있는 단순 P-박스이다.
두 치환은 DES에 있어서 암호학적으로는 중요하지 않다.
ii. 라운드(Rounds)
DES는 16번의 라운드 함수를 사용한다.
16번의 라운드를 거치는 이유는 16번이 최적의 시행 수이기 때문이라고 했다.
16라운드 이하는 전수조사에 취약하고, 16라운드 이상은 가용성에 문제가 생긴다.
DES의 각 라운드 함수는 Feistel 암호로, 아래 그림과 같다.
앞에서 말했듯이 Feistel 암호는 역이 존재하는 것이 있고 존재하지 않는 것도 있다.
늘 역이 존재하는 암호는 non Feistel 암호라고 하며, 대표적인 예로 AES가 있다.
초기치환을 거친 것을 32비트씩 Split 한다.
여기서부터 Mixer 단계이다.
Left의 32비트는 그대로 내려온다.
F(RI-1,KI)
위 함수를 DES암호함수(DES암호의 심장)라고 한다.
가장 핵심적이라는 뜻이다.
이제 Right의 32비트와 키 KI(64비트에서 패리티비트를 제외해 56비트가 된 것을 축소치환을 해서 48비트가 된 키)끼리 xor연산을 해야하는데 서로 비트수가 다르다.
때문에 48비트 키를 S box라는 것에 통과시킨다.
S box는 6비트를 입력받아서 4비트로 출력시킨다.
이 S box는 8개가 있다.
그래서 48비트가 들어와서 32비트로 변환되는것이다.
이제 Right와 연산을 해서 32비트가 나오면 내려온 Left와 xor연산을 시행한다.
여기서부터 Swapper 단계이다.
xor연산을 시행한 것과 Right(아무것도 바뀌지 않은 순정 RI-1)을 swap한다.
swap을 하는 이유는 확산 효과(쇄도 효과)를 주기 위해서이다.
이제 다음 라운드로 넘어가서 같은 과정을 거치는데, 이번에 키 K1을 사용했다면 다음에는 K2를 사용한다.
여기까지 50:33
