[cryptography] Cryptography 1 - introduction

암호는 나에게 마치 퍼즐 게임을 푸는 것처럼 흥미로운 소재이다.

내가 좋아하는 퍼즐게임 중 하나인 스도쿠를 예로 들어보자.

 스도쿠에서 처음 주어지는 판을 암호화된 정보라 하고, 이를 일련의 과정을 통해 풀어냈을 때, 얻어지는 완성된 판을 원래의 정보라고 생각해보면 암호와 퍼즐이 상당히 비슷하다는 생각이 들지 않는가.

 물론, 퍼즐은 목적 자체가 풀어보는 것이고 암호는 풀지 못하는 것 (최소한 풀지 못할 것을 예상하는 것)으로 근본적인 차이가 있지만 많은 공통점이 있는 것도 사실이다.

 남이 감추고 싶어하는 정보를 캐내어 보는 것에는 관심이 없지만, 암호 해독 자체로도 흥미로운 소재임이 틀림없다.
또한, 보안이 이슈인 요즈음, 프로그래머로서 암호에 관심을 가지는 것도 좋은 자세라고 생각한다.

 암호학에 입문하는 방법은 여러가지가 있겠지만, 나는 coursera.org에서 제공하는 Cryptography 강의를 들으려 한다. 위의 사이트에서는 해외 유명대학들에서 무료로 제공하는 양질의 강의를 들을 수 있어 정말 좋다.

 앞으로 블로그에 Cryptography 강의를 듣고 배운 것과 몇가지 드는 생각들을 정리할 생각이다. 이에 추가적으로 관련된 정보를 찾아 정리할 수도 있고, 시간이 남는다면 Course에서 제공하는 숙제를 제외한 (이에 관련된 정보를 공유하지 말라는 Honor Code에 동의를 했답니다 ㅋ) 직접 작성한 코드도 포스팅할 예정이다.


 맨 처음 1강은 여느 강의와 마찬가지로 Introduction으로 시작을 한다.
원래 Introduction은 흥미를 돋우기 위해 재미있는 것 위주로만 (^^) 정리를 했는데, 부분부분 조금 나누어 보자면,

1. 암호학에서의 세 단계 (Three steps in Cryptography)
2. 기억해야 할 몇가지    (Things to remember)
3. 공유키 프로토콜
4. 그리고 암호학의 간략한 역사

로 나눌 수 있겠다.


- 암호학은 매우 과학적으로 철저한(rigorous) 학문이라고 소개한다. 이 철저함을 위한 암호학의 세가지 단계가 있는데,

• 먼저 위협 모델을 자세하고 구체적으로 세워야 한다.
• 다음으로는 암호화된 모델을 내놓는다.
• 마지막으로, 위협 모델에서 암호화된 모델을 부수는 것이 암호화된 모델에 내재된 어려운 문제 (아주 큰 소수의 곱의 인수분해 등)을 푸는 것이라는 것을 증명한다.

 예를 들어, 국가의 안보에 관련된 파일이 있다고 하자. 이 파일의 암호를 부수는 위협 모델로, 적국의 스파이가 슈퍼컴퓨터를 이용하는 상황을 생각해 볼 수 있다. (아직 초기라 어느정도 더 자세하고 구체적이여야 하는 지는 잘 모르겠다.) 그래서 그 국가에서는 이를 암호화 하기 위한 모델을 내놓는다. 이 모델을 검증하는 것은, 스파이가 이 파일의 암호를 푸는데, 이 모델에 내재된 어려운 문제를 풀어야만 한다는 것을 증명해야한다. 만약 암호 모델이 의도한 것과는 다르게 파일 내부에 암호값이 존재한다든지 하는 경우는 어려운 문제를 풀어낼 필요없이 암호가 해독된다. 즉, 이 모델은 암호 자체가 되지 않을 수 있다는 것이다.

 - 또한 몇가지 기억해야할 것들이 있다.

• 암호는 굉장한 도구이다.
• 많은 보안 메카니즘의 기초가 된다.
• 암호는 모든 보안문제에 대한 해결책은 아니다.
• 적절하게 수행되고, 사용되지 않는다면 믿을 수 없다.
• 마지막으로 암호는 너 스스로 발명하려고 노력해야할 것이 아니다.

 몇가지는 한눈에 이해가 가지만 다른 몇가지는 언듯 이상해 보일 수도 있다.

하지만 생각해 보면 고개가 끄덕여질 것이다. 보안 문제에서 가장 취약한 부분은 사람이다. 사회공학(Social Engineering)에 능통한 사람들은 이 가장 취약한 부분을 노린다. 아무리 강한 암호로 보호되고 있다고 한들, 접근 권한을 가진 '사람'을 통해 접근한다면 어떻게 막을 수 있겠나... 

 또한 마지막 말은 나도 잘 이해가 가지 않았는데, 설명하기로는 이 강의에서 소개하는 암호들과 여러 암호들은 많은 연구가 이루어져서 쉽게 파괴가 가능하다는 의미에서 이런 말을 집어 넣은 것 같다.

- 공유키 프로토콜

 공유키 프로토콜의 핵심은 말 그대로 서로 Key 를 공유하는 것이다. 위의 그림에서 m은 원본 메시지, k는 공유키, c는 암호화된 메시지, E는 암호화 알고리즘, D는 복호화 알고리즘이다.

 이 프로토콜에서는 암호화된 메시지를 제 3의 존재가 가로챈다 하더라도 키가 없다면 쉽게 원본 메시지를 알 수 없다. 하지만 중요한 점은 키를 가지고 있다면 메시지의 암호화나 복호화는 매우 효율적으로 빠른 알고리즘이어야 한다는 점이다.

- 암호학의 간략한 역사

 암호학의 발전 과정을 간략하게 소개하면서 몇가지 암호화 방법을 소개한다.

• Substitution Cipher (대치 암호)

          대치 암호는 알파벳의 순서를 뒤죽박죽으로 섞어 암호화 하는 방식이다. 즉 암호문을 주고 받는 두 사람이 공유하는 키는 예를 들어 아래처럼 되어있다.

 이러한 키를 가지고 acyzb를 암호화 한다면 cloeq가 되겠다.

대치암호 방식은 알파벳의 빈도를 이용한 방법으로 쉽게 풀릴 수 있다는 한계점이 있다.

 예를 들어, 단일 알파벳중 가장 많은 빈도로 나타나는 것은 'e'이므로 암호문을 분석하여 가장 많이 나타나는 알파벳을 'e'로 치환하는 등의 방법으로 쉽게 풀린다는 것이다. 

• Vigener Cipher

                   Vigener 암호는 16세기에 Vigener가 고안한 암호이다.

먼저 Key 값을 설정해야한다. 만약 k = HELLO 라고 하고, 암호화 해야할 문장이 ICANDOTHAT이라고 해보자. 이 때, 키를 문장의 길이에 맞게 먼저 늘린다.

그리고 각 알파벳의 값에 A:=0부터 시작해서 Z:=25까지 부여를 한다. 그러면 키와 메시지의 첫번째 알파벳에 대응 되는 값은 H := 7이고 I := 8이다. 이제 이 두 숫자를 더한 후, mod 26을 취하면 15이고, 이 값은 P에 해당된다. 즉,

이런 식으로 암호화가 된다는 것!

이를 키 없이 해독하는 것은 대치 암호법 보다는 조금 복잡하지만 현대의 컴퓨터로 계산하면 역시, 빠르게 풀 수 있다는 한계점이 있다.

 해독 방법은 먼저 키의 길이를 가정한 후, 대치 암호를 해독하는 것처럼, 각 자리에 맞추어 암호를 해독한다. 맞지 않으면 키의 길이를 다시 바꾸어가면서 해독하면 된다.

• Rotor Machine

            Rotor Machine은 1920~1970년 사이에 사용된 암호화 기계다. 먼저 대치 암호화를 통해 알파벳을 뒤섞은 후, 한 글자를 칠 때마다 이 순서가 한칸씩 돌아가면서 재 암호화되기 때문에 빈도를 이용한 방법으로 해독을 하는 것이 불가능하다.

 하지만 이 방법도 역시 현대의 컴퓨터로 Brute force algorithm을 통해 쉽게 해결할 수 있다.

• Data Encryption Standard

            현대에는 Data Encryption Standard (DES)라는 발달된 형태의 암호화 기법이 나타났다. 이는 64bit 키를 이용한 암호화 방식인데, 이 것 역시도 너무나 발달된 컴퓨터의 능력 때문에 안전하지 못하다. 이를 더 보강한 Advanced Encryption Standard (AES)가 있는데, 이는 128bit 키를 이용한다. 자세한 내용은 이제 앞으로의 강의에서 설명해 주신단다.