블록체인을 공부하면서 dApp을 만들어보고 비트코인이 어떤 방식으로 트랜잭션이 될까라는 부분부터 시작했었다. 그런데 기초 암호학 지식이 없는 상태이다보니 이해하는데 상당한 시간이 걸렸고 수박 겉햛기식으로 학습이 지속되었다.
블록체인을 배우면서 만났던 멘토분께서 암호학을 먼저 공부하는 것이 좋다는 말씀을 듣고 공부한 내용들을 정리하였다.
DES (Data Encryption Standard)
DES는 IBM에서 고안되어 NIST가 미국 표준 암호 알고리즘으로 채택된 대칭 암호화 알고리즘이다.
1998년도에 해독된 암호화 기술이기 때문에, 현재의 일반 컴퓨팅 파워로도 쉽게 뚫린다.
기존에 암호화된 문서를 복호화 하는 용도로만 사용하고 신규 암호화 문서를 생성하는데는 절대로 사용하지 말 것을 권장한다.
개요
DES를 설명하기 전에 대칭 키 암호화 기술에 대해서 알아야 한다. (위키피디아 대칭 키 암호를 참고)
대칭 키 암호화는 암호 / 복호 화에 같은 암호키를 사용하는 암호 알고리즘을 뜻한다.
따라서 DES는 대칭 키 암호 알고리즘에 속하고 블록 암호 기법을 사용하며 16단계의 파이스텔 네트워크(Fesitel Network)를 거쳐 암호화를 수행한다.
> 파이스텔 네트워크 구조는 치환(Substitution), 순열(Permutation)을 번갈아 수행하는 구조이다.
64bit 크기의 블록을 입력으로 가지고, 64bit의 키을 사용하는데 실제키 암호화에 사용되는 키의 사이즈는 56bit이다.
(8bit는 parity bit로 사용된다.)
DES 암호화 과정
Feistel Network는 Round로 구성되어 있고, DES 암호화 과정에서 크게 3가지로 나눌 수 있다.
- Initial Permutation & Final Permutation
- 16 Round Function
- Round-Key Generator
Initial Permutation & Final Permutation
Permutation Table에 따라서 bit의 교환이 일어나고, 이 부분에서는 암호화를 하지 않는다.
IP(Initial Permutation), FP(Final Permutation)라고 불린다.
FP는 IP−1과 같은 의미이다.
아래 그림은 Permutation box 위키피디아에서 참고한 그림이다.
입력된 64bit 평문 데이터가 Initial Permutation을 통해 그 다음인 S-box(Round Function 부분)에 나뉘어 입력이 되는 것을 묘사한 그림이다.
DES의 Permutation 구조를 살펴보자.
그림과 같이 bit가 swap이 된다. 정확히 말하자면 Permutation Table에 따라 bit swap이 되는 것이다.
아래의 그림은 각 Permutation별 Table을 나타낸 것이다.
Round Function
DES 암호화 알고리즘의 실제 암호화는 이 과정에서 일어난다.
- Rx = x 단계 결과물의 오른쪽 32bit
- Lx-1 = (x-1)단계 결과물의 왼쪽 bit
- F = Round Function
- Kx = SubKey
(하위 32bit는 암호화 진행 X 단지 swap만 한다)
참고로 마지막 16 Round는 좌, 우 32bit 교환이 일어나지만 Straight P-box때문에 교환이 일어나지 않는 것과 같다.
수학 식만 본다면 이해하는데 어려움을 느낄수 있지만 그림과 같이 참고한다면 쉽게 이해할 수 있다.
R(오른쪽 bit) 32bit는 Round Function과 XOR이 되어 암호화가 진행된다.
L(왼쪽 bit) 32bit는 이와다르게 암호화는 되지않고 다음단계의 R(오른쪽) 32bit로 swap될 뿐이다.
아래 그림은 Round Function의 디테일한 그림인데, 이 그림을 본다면 이해하는데 도움이 될 것이다.
위에서 상위 32bit가 Expansion P-box에서 48bit 확장전치가 일어난다.
그 다음 K라는 서브키와 XOR 연산을 한 후 S-box에 들어간다.
참고로 아래그림에서 Ri-1은 위 그림의 L, 즉 상위bit를 뜻한다.
Expansion P-box을 먼저 살펴보자.
아래그림은 Expansion P-box에서 암호화 할 비트의 상위 32bit가 어떻게 48bit로 확장이 되는지 설명한 그림이다.
먼저 32bit를 4bit 4개로 나눈다. 그 다음 각 섹션은 6bit로 확장을 한다.
각 섹션에서는 1~4bit는 2~5bit로 복사가 되고 복사된 bit의 첫번째 부분은 그 전 섹션의 4번째 bit가 복사가 된다.
그리고 복사된 bit의 마지막 부분은 다음 섹션의 첫번째 bit가 복사가된다.
아래의 그림은 S-box를 표현한 그림이다.
아래 그림에서 48bit 두개가 있는데 S-box 들어가기 전 연산이다.
이 부분에서는 Expansion P-box를 거친 48bit 암호화 할 bit를 Subkey와 XOR을 한다.
XOR한 48bit 값을 S-box에서 압축 transposition이 일어나며 각 6bit가 4bit로 압축되어 결과값으로 32bit의 값이나오는데,
마지막으로 Permutation (P-box 연산)을 진행해준다. (좌, 우 Swap)
결과적으로 나온 값이 Round Function의 결과 값이다.
Key Generator
이 과정에서는 DES에서 사용하는 56bit 암호 키(대칭키)를 16개의 Subkey로 생성한다.
(Round Function에서 사용할 암호 키)
아래 그림을 보면 처음 Input시 64bit인데 8bit는 오류검증으로 사용하는 Parity bit이다.
Round-key Generator에서 Round key를 생성은 3단계로 이루어진다.
- 1단계 : Key와 Parity bit를 포함한 64bit 값을 입력받는데 `Parity Drop(PC1)`과정에서 PC1 테이블에 의해 8의 배수가 버려진다. 따라서 이 연산 결과 값으로 56bit 암호키를 얻게된다. (64bit -> 56bit)
- 2단계 : 56bit key를 Key swap 연산을 통해 두 개의 28bit block으로 나눈다.
- 3단계 : 두 개의 블록은 1, 2, 9 ,16의 Round Key(Subkey)를 만들 때에는 1bit 왼쪽 순환이동을 하고, 나머지 RoundKey를 만드는 경우는 2bit 순환이동을 한다.
- 4단계 ; 각 28bit block은 PC2연산 - Compression(압축) 전치를 통해 합쳐진 56bit가 RoundFunction에서 사용될 48bit Subkey가 된다. 이때도 1단계와 마찬가지로 입력 값의 8배수 bit는 버려진다. (56bit -> 48bit)
DES 작동 모드
ECB (Electronic Codebook)모드
위에서 설명한 것은 EBC모드를 기준으로 설명을 했다. ECB의 특징으로 3가지가 있다.
- 64bit 평문 단위로 처리한다. 즉, 한번 암호화 할때 64bit 블록단위로 쪼개서 생각한다.
- 암호화 하고자 하는 Bit가 64bit 미만이면 나머지 비트를 채운 후 진행한다.
- 동일한 블록이 입력되면 암호문도 동일하다.
CBC (Cipher Block Chaining)모드
ECB에 문제점으로 인해 CBC가 등장하게 되었다. CBC는 이전 단계에 암호문과 다음 단계의 입력에 XOR이 반영된다.
따라서 동일한 평문 블록이 입력이 되더라도 결과 값으로는 다른 암호문을 얻을 수 있다.
DES의 개선
DES의 brute-force(무차별 공격)에 대한 취약점으로 3중 DES가 나오게 되었다.
3-DES에 대해 간단히 소개하자면 일반 DES과 달리 2개의 암호 키를 사용한다.
또한 암호화, 복호화 과정에 특이한 점을 가지고 있다.
- 암호화 : 암호화 -> 복호화 -> 암호화
- 복호화 : 복호화 -> 암호화 -> 복호화
중간에 암호화, 복호화를 넣어 일반 DES과 다른 점을 가지고 있다.
DES의 특성
1. Avalanche effect (쇄도 효과) - 키의 작은 변화가 결과값에 큰 영향을 미치는 효과를 뜻한다. DES는 이 특징에 대해 강력함을 보였다.
2. Completeness (완전성) - 암호문의 각각의 bit가 원래의 내용의 bit에 의존적이다. (암호문으로부터 평문보호) P-box와 S-box에 의해 강력한 완전성을 보여준다.
현재 DES는 1997년에 미국 보안업체 RSA에서 DES 해독에 $10,000 상금을 걸고 해독 대회를 열었는데, 이때 DES의 56bit 키로 가능한 72천조개의 조합중에 18천조 개의 조합을 넣은 단계에서 해독이 되었다.
현재 상업적으로 사용되는 Private Key 알고리즘에는 적어도 80bit 이상이 되어야한다.
아무튼 1998년에 DES 공격장치가 Brutal Force Attack(무차별 공격)방식으로 2일만에 암호를 탈취했다.
현재는 사용하지 말아야 할 암호이지만 오랜시간 쓰였던 암호이었던 만큼 강화된 다중 DES (ex, 3-DES)를 사용하는 곳이 많으므로 (비용문제 등으로) 알아두는 것이 좋을 듯 하다.
하드웨어 암호 알고리즘으로 많이 사용된다.
참고자료
Tutorials point - DES : https://www.tutorialspoint.com/cryptography/data_encryption_standard.htm
한국기술교육대학교 박승철 교수님 강의 : https://www.youtube.com/watch?v=dFb2ezWDO38
California State Uni.v CS480 : https://slideplayer.com/slide/11006182/
'블록체인 > 암호학' 카테고리의 다른 글
| 모듈러 연산 (Modular arithmetic) (5) | 2019.04.13 |
|---|---|
| 기초 암호학(4) - ECC(타원곡선 암호화 알고리즘) (3) | 2019.04.13 |
| 기초 암호학(3) - 공개키 암호 (RSA, Diffie-Helmman) (1) | 2019.03.27 |
| 기초 암호학(2) - AES (0) | 2019.03.01 |
| Hash 함수를 알아보자 (2) | 2018.11.27 |
댓글