기초암호학 개념 정리

참고: dreamhack.io/lecture/curriculums/8

Cryptography Fundamental

암호학(Cryptography)

- 좁은 의미: 제3자로부터 정보를 보호하는 방법에 대한 연구

- 넓은 의미: 좁은 의미 + 수신자와 송신자가 서로의 신원을 확인하는 방법, 메세지가 중간에 조작되지 않았음을 보증하는 방법 등을 연구

- 핵심 연구 주제로는 키 생성(Key generation), 암호화(Encryption), 복호화(Decryption)가 있음

 

- 키 생성(Key generation): 암호화 및 복호화에 사용할 키를 만드는 과정

- 암호화(Encryption): 키를 이용해 평문(Plaintext)을 암호문(Ciphertext)으로 변환하는 과정

- 복호화(Decryption): 송신자가 전송한 암호문을 키를 이용해 평문으로 변환하는 과정

- 암호 시스템(Cryptosystem): 암호화와 복호화로 정보가 전달되는 체계

 

고전 암호 키워드

- 치환(Substitution): 평문의 각 문자를 다른 문자로 치환하는 기법. 평문의 문자와 암호문의 문자가 이루는 대응 관계에 따라 단일 치환 암호, 다중 치환 암호로 구분됨.

- 전치(Transposition): 평문을 구성하는 문자들의 순서를 바꾸는 기법.

- 전수 키 탐색 공격(Exhaustive Key Search Attack): 키 공간을 전부 탐색하는 공격 방법. 가능한 키의 수가 적으면 효과적일 수 있으나, 현대 암호는 키 공간의 크기가 매우 넓으므로 이를 대상으로 사용하기 어려움.

- 빈도수 분석(Frequency Analysis): 암호문에서 단어가 등장하는 빈도를 분석하여 통계적으로 복호화하는 공격 기법. 단일 치환 암호를 대상으로 유효함.

 

현대 암호 키워드

- 혼돈(Confusion): 암호문으로부터 평문의 정보를 알아내지 못하게 하는 성질

- 확산(Diffusion): 평문의 작은 변화가 암호문의 큰 변화로 이어지는 성질

- 현대 암호의 네 가지 기능: 기밀성(Confidentiality), 무결성(Integrity), 인증(Authentication), 부인 방지(Non-repudiation)

 

대칭키(Symmetric Key)

- 대칭키 암호 시스템(Symmetric Key Cryptosystem): 송신자와 수신자가 같은 키를 공유하여 정보를 암호화하고 복호화하는 시스템

- 속도가 빠르지만 키 교환이 어려움.

- 그룹 내에 여러 명이 있을 경우 두 사람마다 서로 다른 키를 생성해서 사용해야 함. 즉, N명의 사람이 있을 때 총 N(N-1)/2개의 키가 필요.

- 크게 블록 암호와 스트림 암호로 구분.

 

블록 암호(Block Cipher): 평문을 정해진 크기의 블록 단위로 암호화하는 암호

- 예를 들어 블록의 크기가 4바이트라면 평문을 4바이트의 블록으로 쪼개어 각 블록마다 암호화를 진행함.

블록 암호

- 만약 평문의 크기가 블록 크기의 배수가 아니어서 블록으로 균등하게 쪼갤 수 없다면, 평문 뒤에 데이터를 추가하는 패딩(Padding) 수행.

- 패딩: 평문이 블록 크기의 배수가 될 때까지 데이터를 추가하는 과정.

- 대표적으로 DES와 AES가 있음.

 

* DES(Data Encryption Standard): 여러 라운드에 걸쳐 치환과 순열을 반복하는 곱 암호(Product Cipher)의 일종.

- 혼돈 성질을 만족하기 위해 치환을, 확산 성질을 만족하기 위해 순열을 사용함.

- 초기 순열, 16개의 페이스텔 라운드, 최종 순열로 구성됨.

- 페이스텔 구조: 암호화하려는 데이터를 반으로 나누어, 라운드마다 절반씩 라운드 함수를 적용하는 구조. 라운드 함수에 역함수가 존재하지 않아도 되지만, 비페이스텔 구조보다 많은 라운드가 필요함.

- 64비트의 평문을 한 블록으로 처리.

 

* AES(Advanced Encryption Standard): DES가 취약해진 뒤, NIST가 새로 공모한 블록 암호의 표준 알고리즘.

- SubBytes(State의 각 바이트를 S-Box를 참조하여 치환하는 함수), ShiftRows(State의 각 행을 구성하는 바이트들을 쉬프트하는 함수), MixColumns(열 단위로 치환을 수행하는 함수), AddRoundKey(키 생성 함수로 생성된 라운드 키의 state를 각 바이트별로 XOR하는 함수)로 암호화 및 복호화가 이루어짐.

- SPN(Substitution Permutation Network)이라는 암호 구조 사용.

- SPN: 곱 암호의 일종으로, S-Box를 사용하는 치환과 P-Box를 사용하는 순열을 여러 라운드에 걸쳐 반복함. 라운드마다 입력 전체에 라운드 함수를 적용하므로 페이스텔 구조에 비해 두 배의 안전성을 가짐.

- 128비트의 평문을 한 블록으로 처리.

 

 

스트림 암호(Stream Cipher): 송신자와 수신자가 공유하는 데이터 스트림을 생성하고 이를 평문에 XOR하는 암호

- C=P⊕X (C: 암호문, P: 평문, X: 스트림)

- 일반적으로 송신자와 수신자는 스트림을 공유하는 대신 시드(Seed)라 불리는 작은 값을 공유하고, 이를 사전에 합의된 함수의 인자로 넣어 스트림을 각자 생성함.

- 단순한 연산으로만 구현되므로 속도가 매우 빠르지만, 블록 암호보다 안전하지 못함.

- 주로 연산 능력이 부족한 임베디드 기기나 속도가 중요한 환경에서 제한적으로 사용됨.

 

스트림 암호

 

비대칭키(Asymmetric Key)

- 비대칭키 암호 시스템(Asymmetric Key Cryptography): 송신자와 수신자가 서로 다른 키를 사용하여 정보를 암호화하고 복호화하는 시스템. 공개키 암호 시스템이라고도 함.

- 송신자는 수신자의 공개키(Public Key)로 데이터를 암호화하여 수신자에게 전송하고, 수신자는 자신의 비밀키(Private Key)로 이를 복호화함.

- 공개키는 모두에게 공개되어 있으므로 공개키를 아는 사람은 누구나 수신자에게 암호문을 보낼 수 있지만, 개인키는 수신자만 알고 있으므로 공격자가 암호문을 도청해도 이를 복호화할 수 없음.

- 그룹 내의 사람들이 각자의 공개키와 비밀키를 만든 후 공개키만 공개하면 되므로 2N개의 키만 필요.

- 대칭키 암호보다 복잡한 연산이 필요하므로 속도가 느림.

- 대칭키 암호와 같은 안전성을 제공하려면 대칭키 암호보다 긴 키를 사용해야 함.

 

* RSA: 최초의 비대칭키 암호 시스템으로, 현재까지 널리 사용됨.

- 키를 교환하지 않아도 되지만, 대칭키 암호 시스템에 비해 속도가 느림.

 

해시 함수(Hash Function)

- 임의 크기의 데이터를 입력받아 고정된 크기의 데이터를 반환하는 함수

- 해시 값(Hash Value): 해시 함수의 반환값

- MD5, SHA256 등이 있음.

 

* MD5: 임의 입력으로부터 128비트(16바이트)의 값을 생성하는 함수.

- 임의 길이의 입력을 512비트 단위로 쪼갠 후 연산을 거쳐 값을 생성함.

- 다양한 취약점이 발견되어 점점 사용하지 않는 추세.

 

* SHA256: 256비트(32바이트)의 출력을 내는 함수.

- MD5에 비해 길이가 2배로 늘어나 충돌 저항성이 크게 증가함.

- 현재까지 취약점이 발견되지 않아 해시가 필요한 대부분의 곳에서 사용됨.

 

암호학적 해시 함수(Cryptographic Hash Function): 해시 함수 중에서 다음 성질을 만족하는 함수

    1) 제1 역상 저항성: 암호학적 해시 함수 H에 대해 y가 주어졌을 때 H(x)=y를 만족하는 x를 찾기 어려움

    2) 제2 역상 저항성: 암호학적 해시 함수 H에 대해 x가 주어졌을 때 x≠x', H(x)=H(x')을 만족하는 x'을 찾기 어려움

    3) 충돌 저항성: 암호학적 해시 함수 H에 대해 x≠x', H(x)=H(x')을 만족하는 x, x'을 찾기 어려움

    +a) 눈사태 효과: 입력에 작은 변화가 생기면 해시값에 큰 변화가 발생하는 성질

- 어떤 통신의 무결성을 보이기 위해 사용될 수 있음.

- 무결성(Integrity): 데이터가 무결(수신한 데이터가 원본과 같음)하게 송수신되는 성질

- 민감한 데이터를 보관할 때 사용될 수 있음.

 

MAC(Message Authentication Code): 메시지 인증 코드. 데이터와 함께 보내는 추가 정보.

- MAC을 통해 데이터의 무결성을 보장할 수 있고, 현재 통신 중인 상대방이 위장한 공격자가 아니라는 사실을 알아낼 수 있음.

- 송신자는 수신자에게 메시지를 보낼 때 메시지와 키를 이용해 계산된 MAC 값을 같이 보내고, 수신자는 기존에 알고 있던 키를 이용해 수신한 메시지의 MAC을 계산하여 전송받은 MAX과 일치하는지 비교함.

- MAC을 만드는 방법은 크게 암호학적 해시 함수를 이용하는 방법과 블록 암호를 이용하는 방법으로 나뉨.

- HMAC(keyed-Hash Message Authentication Code): 키와 해시 함수를 사용하여 MAC값을 생성하는 알고리즘