[cryptography] Cryptography 3.(1) - Block cipher

 일과 올림픽 때문에 내 블로그가 죽어가고 있었다.. 그동안 정리하려고 자료들을 모아두기만 하였기에 이제 시간을 내서 몰아서 정리를 해야겠다.

 이번엔 Block cipher에 대해서 정리를 해본다.

 Block cipher에는 DES, 3DES, AES 등이 있다. 사실 무선 공유기를 설정할 때에, 어떤 암호화 기법을 사용할지 선택을 해야하기에, 이러한 예의 이름은 상당히 익숙하다. 물론 어떻게 암호화가 되었는지는 이제까지는 몰랐지만 말이다. cryptography 3번째 강의는 이 block cipher에 관한 내용이다. 양이 적지 않기 때문에, 2~3 부분으로 나누어 정리한다.

 이번 강의의 첫번째 부분의 내용을 요약하면 아래와 같다.

1. Block cipher 개요
2. Pseudo Random Function (PRF), Pseudo Random Permutation (PRP)의 정의
3. Secure PRF 정의
4. Example : DES

 그러면, 하나하나 정리를 시작한다.

1. Block cipher 개요

 Block cipher는 n bits의 Plain Text (PT, 평문)을 k bits의 key를 통해서 암호화를 시켜 역시 n bits의 Cipher Text (CT, 암호문)을 만들어 낸다. 여기까지는 Stream cipher와 크게 다를 바가 없어 보인다. 하지만 이제 곧 알게 되겠지만, Stream cipher와는 암호화 방법에서 차이점이 있다.

 이제, Block cipher에서 암호화하는 방법을 살펴보자.

 위의 그림은 Block cipher의 암호화 방법을 도식화한 것이다. 찬찬히 살펴보면, 먼저 key를 확장시켜서 총 n개의 key를 생성해 낸다. 그러면 텍스트와 key를 인풋으로 받는 R (round function)을 총 n번 거치면서 평문 m은 c로 암호화된다. 지금은 조금 받아들이기 힘들 수 있으나, 마지막에 DES에 대한 예를 살펴보면 확실히 와 닿을 것이다.

2. Pseudo Random Function (PRF), Pseudo Random Permutation (PRP)의 정의

 PRF와 PRP는 block cipher의 암호화 과정의 round function을 엄밀하게 정의한 개념들이다. PRF는 좀더 일반적인 개념이고, Block cipher에서 필요한 것은 PRF의 좀더 특별 케이스인 PRP이다.

 PRF의 정의는 상당히 단순하다. 위에 나타난 것처럼, K와 X를 Y로 대응시켜주는 함수 F가 PRF인데, 조건은 이 F(k, x)를 평가하는 효과적인 알고리즘만 있으면 된다. 한마디로 k와 x를 가지고 효과적으로 F(k, x)를 뽑아내면 된다는 것이다.

 이제 PRF를 정의했으니 PRP를 정의해보자.

 PRP는 PRF의 좀더 특별한 케이스이다. 공역이 줄어들고, 조건이 몇가지 더 붙었다. 먼저 PRF의 조건에서 결정적이라는 단어가 추가되었다. 이 말은 즉, k와 x를 주면 E(k, x)는 하나로 결정된다는 것이다. 그리고, 추가적으로 key k가 주어졌을 때는 1대1 대응함수가 된다. 감이 오는가? PRP는 말 그대로 X에서 X로 K에 따라서 순서를 뒤섞어 주는 함수이다. 물론 마지막 조건, 효과적인 역함수가 존재해야 하는 것은 암호의 특성상 당연히 필요하다.

3. Secure PRF 정의

 PRF가 무엇인지 알았다면, 이제 안전한 PRF가 무엇인지 정의를 해야 PRF를 사용하는 Block cipher가 안전한지 아닌지를 알 수 있을 것이다.

 Secure PRF의 정의를 위해 두가지 집합을 새로 정의했다. Funs[X, Y]와 S_F이다. S_F는 모든 Key에 대한 PRF (F)의 집합으로 정의했다. 여기서 포인트는 모든 함수의 집합에서 임의로 선택된 함수와, S_F에서 선택한 임의의 함수가 서로 구별할 수 없다는 부분이다. 이 명제가 성립해야만 이 PRF가 안전하다는 것이다. "구별할 수 없다"에 대해서는 앞서 포스팅한 2.(2)의 PRG Security 부분을 참고하시라.

 4. Example : DES

 이제 마지막으로, DES (Data Encryption Standard)에 대해서 살펴본다.

 DES는 1970년대 초반, IBM의 Horst Feistel이 고안한 Lucifer로 부터 시작된다. 1973년, IBM에서는  NBS (National Bureau of Standards, 미국 표준 규격국)의 block cipher 제안 요청에 따라 Lucifer를 조금 변경하여 제출하였다. 이 것이 DES이며, 1976년에는 연방 표준으로 자리 잡게 되었다. 하지만 1997년, 무차별 대입으로 인해 암호가 깨지면서 보안성에 문제가 제기되었고, 2000년에는 AES가 DES를 대신하게 된다.

 그럼 이제, 이 DES의 원리를 살펴보자. DES의 핵심은 바로 Feistel Network이다.

 위의 그림에서 f1, f2, ..., fd는 바로 다음에서 설명을 하겠다. 먼저 그림을 보면 대강 Feistel Network가 어떤 것인지 감이 올 것이다. 먼저 input은 n bits 짜리 text 2개이다. 첫번째 round function을 지날 때, L1은 R0가 그대로 들어오고, R1은 L0와 f1을 통과한 R0와의 XOR 연산된 값이 들어오게 된다. 이런식으로 반복하여 d번째 결과가 곧 output이 된다.

 항상 암호에서 중요한 것은 역연산이 가능한가이다. 위의 network를 보면 복잡하여 역연산이 불가능해 보일 수도 있지만, 역연산은 생각보다 간단하게 똑같은 회로에서 f1부터 fd까지의 순서만 바꾸면 된다. 결과적으로 추가적인 회로 없이도 역연산을 할 수 있기 때문에 효율적이라 할 수 있겠다.

 여기서, 중요한 정리를 하나 소개한다.

 앞에서 우리가 정의 했던 것은 secure PRF였다. 위의 정리는 key 3개를 사용한 Feistel이 secure PRP이다 라는 것이다 (자세한 증명은 위의 논문 참조). 이는 3DES가 안전하다는 것의 밑바탕이 된다.

 아무튼, 이제 위의 Feistel Network에서 설명을 넘어갔던 f1, f2 ... fd에 대해서 설명을 한다. 이 설명에서 R0, L0 등은 32 bits, 그리고 각 key들은 48 bits를 사용한다고 가정한다.

 수식으로 나타낸다면, f (x) = F (k, x) 정도 이겠다. 먼저 함수 E는 주어진 32 bits 데이터를 확장 및 뒤섞는 역할을 한다. 그 결과 key의 크기와 같은 48 bits 데이터가 나오며, 이는 key와 XOR 연산이 된다. 이는 각 6 bits 씩 나누어져서 S box 들을 통해 4 bits의 데이터로 축소되고, 이것이 다시 모여 32 bits 데이터를 이룬다. P는 단순히 뒤섞는 역할을 하여 결과적으로 32 bits 데이터를 내놓는다.

 한가지 주의할 점이 있다. S box는 6 bits를 4bits로 축소하는 역할을 하는 데, 이 것이 linear 해서는 절대로 안된다. 만약 linear일 경우, 전체 DES cipher 자체가 linear하게 된다.

( m이 64 bits, n이 16이라 하면 각 k가 48 bits 이므로 총 832 bits )

 이렇게 되면 몇개의 암호문만 알게 된다면, 손쉽게 key를 복구할 수 있기 때문에, 암호의 보안성은 사라지게 된다고 한다.

---------------------------------------------------------------------------------------