암호화(Cryptography)

 

 

이 글은 Crash Course의 Computer Science를 보고 정리한 글입니다.

  완벽한 100% 보안 컴퓨터 시스템은 존재하지 않는다. 항상 버그가 존재하고 그것을 아는 보안 전문가가 있다. 따라서 시스템 설계자는 다양한 보안 메커니즘으로 공격자를 좌절시키는 방위전략(Defense in Depth)을 사용한다. 여기서는 암호화(Cryptography)에 대해서 알아보겠다.

 

  Cryptography는 'crypto'와 'graphy'로부터 생겨났는데, 대략 번역하면 "비밀을 쓰는 것"이다. 정보를 비밀로 만들기 위해 평범한 텍스트를 암호문으로 변환하는 암호를 사용한다. 암호를 해독할 수 있는 키가 없으면 암호문은 쓸모없는 횡설수설이 되어버린다.

  텍스트를 비밀로 만드는 과정은 "암호화(Encryption)", 거꾸로 암호를 푸는 것은 "복호화/해독(Decryption)"이라 부른다. 암호는 컴퓨터가 나타나기 오래전부터 사용되었다. 줄리어스 시져는 개인 통신을 암호화하기 위해 사용한 현재 시져 암호라고 불리는 것을 사용했다. 그는 메시지의 글자들을 세 자리 앞으로 옮겨서 글을 썼다. 그래서 A는 D가 되었고 "brutus"라는 단어는 "euxwxv"가 된다. 수신자는 메시지를 해독하기 위한 "키" 역할을 하는 알고리즘과 이동한 숫자를 모두 알고 있어야 한다. 시져 암호는 대체 암호(Substitution Ciphers)라고 불리는 더 큰 범주 기술의 한 예시이다. 이것들은 메시지의 모든 문자를 변환 방법에 따라 무언가로 대체시킨다.

  기본 대체 암호의 큰 단점은 글자의 빈도가 보존된다는 것이다. 예를 들어, 문자 'E'는 영어에서 가장 보편적인 문자이다. 그래서 만약 'E'를 'X'로 바꾸면, 암호문에서 'X'가 가장 많이 나타날 것이다. 숙련된 암호 해독가(Crytanalyst)는 메시지를 알아내기 위해 이러한 종류의 통계를 사용하여 거꾸로 알아낼 수 있다.  사실 이 암호 해독은 1587년에 스코틀랜드 여왕 메리가 영국 여왕인 엘리자베스를 죽이려는 음모를 드러내 메리를 처형받게 했다.

 

  암호 기술의 또 다른 기본 부류에는 치환 암호(Permutation Ciphers)가 있다. 기둥형 전치 암호(Columnar Transposition Cipher)라고 불리는 간단한 예제를 살펴보자. 일단 메시지를 받고 격자에 편지를 채운다. "MEET ME FOR LUNCH - STAN"이라는 메시지를 5x5격자에 채운다면

m	e	e	t
m	e		f	o
r		l	u	n
c	h		-
s	t	a	n

위와 같다. 다음으로, 메시지를 암호화하기 위해 다른 순서로 문자를 읽는다. 한 번에 왼쪽 아래부터, 위쪽으로 한 열씩 읽는다고 해보자. "scrmmth eea l en-uft  no ". 새로운 문자 순서로, 순열이라 불리는 암호화된 메시지가 된다. 배열 방향인, 키 역할을 하는 것이 5x5칸의 배열이다. 이전 기술과 마찬가지로, 암호와 키가 알려지면, 수신자는 과정을 역으로 하여 원문을 밝혀낼 수 있다.

 

  1900년대에는 암호 작성이 암호화 기계의 형태로 기계화되었다. 가장 유명한 것은 나치가 전시 통신을 암호화하는 데 사용한 독일의 애니그마이다. 애니그마는 키보드와 램프 보드가 있는 타자기 비슷한 기계였으며, 둘 다 전체 알파벳을 표시했다. 그 위에 애니그마의 암호화 기능의 핵심인 일련의 배열 가능한 회전자가 있었다.

  먼저, 하나의 회전자를 가지고 살펴보자. 한쪽에는 26개의 글자를 위한 전기 접점이 있다. 이 접점은 한 글자마다 서로 다른 글자로 바뀌어 엇갈리는 선들을 사용하여 회전자의 다른 쪽에 연결된다. 바로 대체 암호가 사용되는 것이다. 그러나 애니그마는 3개 이상의 회전자를 연속적으로 사용했기 때문에 더 정교해졌고, 각각의 회전자는 연속적으로 사용되었다. 회전자는 26개의 가능한 시작 위치에서 회전할 수 있었고, 서로 다른 순서로 삽입될 수 있었으며, 다른 대체 매핑이 많이 존재했다.

  회전자 뒤에는 반사장치라는 특별한 회로가 있었다. 신호를 다른 회전자에 전달하는 대신 모든 핀을 다른 핀에 연결하고, 회전자를 통해 다시 전기 신호를 내보냈다. 마지막으로, 키보드에서 오는 문자를 선택적으로 교체할 수 있도록 기계 앞면에 플러그 보드가 있어서 다른 수준의 복잡성이 추가되었다.

  위의 간소화된 회로로, 예제의 애니그마 배열을 사용해 글자를 암호화해보자. 'H'키를 누르면 전기가 흘러 플로그 보드를 통과한 후 회전자로 가서 반사장치를 지나 회전자와 플러그 보드를 다시 통과해 나와 램프 보드에 'L'을 비춘다. 따라서 'H'는 'L'로 암호화된다. 회로가 양방향으로 흐를 수 있기 때문에 만약 'L'을 입력하면 'H'가 나타난다. 여기서 암호화 및 암호 해독은 같은 과정이기 때문에 송수신 기계의 구성과 연결을 확인하기만 하면 암호를 해독할 수 있다.

  이 회로를 주의 깊게 살펴보면, 글자 자체가 암호화될 수 없음을 알 수 있다. 이는 치명적인 암호 약점으로 드러났다. 마지막으로, 애니그마가 단순한 대체 암호가 되는 것을 막기 위해 한 글자가 입력될 때마다, 회전자가 차의 주행 기록계처럼 한 칸씩 전진한다. 따라서 AAA 텍스트를 입력하면 대체 매핑이 키를 누를 때마다 바뀌어 BDK로 나올 것이다.

 

  컴퓨터가 출현하면서, 암호화는 하드웨어에서 소프트웨어로 옮겨졌다. 가장 초기의 소프트웨어 암호 중 하나는 데이터 암호화 표준(Data Encryption Standard ; DES)이 널리 보급되었다. 이것은 1977년 IBM과 NSA가 개발했다. DES는 알려진 대로 원래 56비트 길이의 이진 키를 사용했기 때문에 2의 56승인 대략 72조 개의 다른 키를 가졌다. 1977년으로 돌아가면, 아마 NSA를 제외한 누구도 가능한 모든 키를 무차별 대입할 수 있는 컴퓨팅 파워를 가진 자는 없었을 것이다.

  그러나 1999년에는 25만 달러짜리 컴퓨터로 가능한 DES키를 이틀이면 모두 시도할 수 있게 되었다. 이는 암호를 안전하지 않게 만들었다. 그래서 2001년에 고급 암호 표준(Advanced Encryption Standard ; AES)이 최종 완성되었다. AES는 훨씬 더 큰 128, 192 또는 256 비트 크기의 키로 침입자가 무차별 대입을 하기 훨씬 어렵게 만들었다. 128비트 키의 경우, 모든 조합을 시도하는 데에 1 조년이 필요하다. AES는 데이터를 16바이트 블록으로 자른 다음 키 값을 기반으로 일련의 대체 및 순열을 적용하고, 메시지를 모호하게 하는 다른 작업을 추가한다. 그리고 이 과정을 각 블록에 대해 10번 이상 반복한다. 

  여기서 왜 단지 10번 반복인지, 또는 만개의 비트가 아닌 왜 128비트의 키일지 궁금해 할 수도 있다. 이것은 성능의 균형 때문일 것이다. 이메일 암호화 및 전송에 몇 시간, 또는 보안 웹 사이트에 연결하는 데 몇 분이 걸린다면, 사람들은 그것을 사용하지 않을 것이다. AES는 성능과 보안을 균형 있게 하여 실용적인 암호화를 제공한다. 오늘날 AES는 아이폰의 파임 암호화에서부터 WAP2를 통한 WIFI로 데이터 전송, HTTPS를 사용하여 웹 사이트에 액세스 하는 등 모든 곳에서 사용된다.

 

  지금까지 나온 암호화 기술은 수신자와 발신자 모두가 알고 있는 키를 사용한다. 보낸 사람은 키를 사용하여 메시지를 암호화하고 받는 사람은 동일한 키를 사용하여 메시지를 해독한다. 예전에는 키가 말이나 물리적으로 공유되었는데, 예를 들면 애니그마는 일일 설정 코드북을 제공했다. 그러나 이 전략은 인터넷 시대에는 결코 작동하지 않을 수 있다. 필요한 것은 공용 인터넷을 통해 사용자에게 비밀 키를 보내 서버에 안전하게 연결하는 방법이다. 만약 키가 개방되어 해커가 가로챌 경우 안전하지 않을 것이다.

  해결책은 "키 교환(Key Exchange)"이다. 두 컴퓨터가 키를 보내지 않고 키에 동의할 수 있게 해주는 알고리즘이다. 한 방향으로 수학적인 계산을 하기는 매우 쉽지만 거꾸로 하기엔 어려운 일방 함수를 사용할 수 있다. 일방 함수가 어떻게 작동하는지 보여주기 위해 페인트 색상으로 비유하자면, 페인트 색상을 혼합하는 것은 쉽지만, 혼합된 페이트에 사용된 구성 색상을 알아내는 것은 어렵다는 것이다.

  이 비유에서 비밀 키는 고유한 페인트 색조와 같다. 첫 번째, 모두가 볼 수 있는 공개 페인트 색상이 있다. 저와 당신이 각각 비밀의 페인트 색상을 고른다. 열쇠를 교환하기 위해, 저의 비밀 페인트 색과 공개된 페이튼 색상을 섞는다. 그런 다음, 저는 그 혼합색을 어떤 수단이든 사용해 당신에게 보낸다. 당신도 똑같이 한다. 당신의 비밀 페인트를 공개 색상과 섞은 다음 저에게 보낸다. 당신의 색을 받으면, 저의 개인 색을 추가하여 세 가지 페인트의 모든 조화를 만들어 낸다. 당신도 똑같이 한다. 그러면 우리는 모두 같은 페인트 색을 얻게 된다. 우리는 서로에게 개인적인 비밀 색상을 공개하지 않고 이것을 공유 비밀로 사용할 수 있다. 관찰자는 부분적인 정보를 알 수 있지만 공유된 비밀 색상을 알아내기는 매우 어렵다.

  실제로, 수학적인 일방 함수는 더 완벽하고 이것은 Diffie-Hellman 키 교환 방식이다. Diffie-Hellman에서 일방 함수는 모듈러 지수이다. 이것은 하나의 숫자를 밑수, 다른 숫자를 지수로 취하고 세 번째 수로 나눌 때 나머지를 취하는 모듈이다. 예를 들어, 3의 5승에 31을 모듈로 하여 계산을 한다고 가정하면, 3의 5승은 243이고 이것을 31로 나누면 나머지는 26이다.

  결과와 밑수만 주어졌을 때, 어려운 부분은 지수를 알아내는 것이다. 만약 3에 어떤 비밀의 수를 지수로 하고, 31로 나누어 나머지로 7을 얻었다면 비밀의 수를 알아내기 위해서는 많은 지수 테스트를 해야 할 것이다. 이 숫자를 크게 만들어 수백 자리 길이를 갖게 되면 비밀 지수를 찾는 것은 거의 불가능하다.

  이제 Diffie-Hellman이 모듈화 지수법을 사용하여 공유 키를 계산하는 방법에 대해 살펴보자. 첫 번째는 공유 값 설정이다. 밑수와 모듈러스, 이것은 이전에 공개 페인트 색상과 같다. 모두가 알 수 있다. 당신에게 안전하게 메시지를 보내기 위해 비밀 지수 X를 선택할 것이다. 그러면 B의 X승을 계산하고 모듈로 M을 계산한다. 이 큰 숫자를 당신에게 보낸다. 단신은 비밀 지수 Y를 골라 똑같이 한다. B의 Y승에 모듈러스 M을 한 값을 저에게 보낸다. 공유 비밀 키를 만들려면 당신이 저에게 보낸 것을 받아, 그것의 제 비밀 지수 X로 거듭제곱을 한다. 이것은 수학적으로 B의 XY제곱 모듈러스와 같다.

$$ (B^Y mod M)^X = B^{YX} mod M $$

당신은 제가 한 것을 가져다가 똑같이 Y제곱을 하여 둘 다 결국 같은 숫자로 끝나게 된다. 이것은 절대 서로의 비밀 번호를 보내지 않았지만, 같은 비밀 공유 키이다. 이 큰 숫자를 AES 암호화처럼 암호화된 통신을 위한 고유 키로 사용할 수 있다.

 

  Diffie-Hellman 키 교환은 공유 키를 설정하기 위한 한 가지 방법이다. 이러한 키는 수신자와 발신자가 모두 메시지를 암호화 및 해독에 사용할 수 있는 키이다. 이를 양쪽의 키가 모두 같기 때문에 대칭 키(Symmetric-key)라고 한다. 시저 암호, 애니그마 및 AES 모두 대칭 암호화(Symmetric Encryption)이다.

  또한 2개의 다른 키를 사용하는 비대칭 암호화(Asymmentric Encryption)가 있다. 하나는 공개이고 다른 하나는 비공개이다. 따라서 사람들은 개인 키로 수신자만 해독할 수 있는 공개 키를 사용하여 메시지를 암호화할 수 있다. 즉, 공개키만 알고 있는 것은 암호화를 할 순 있지만 해독은 할 수 없다는 것이다. 따라서 비대칭이라고 한다.

  예를 들어 키로 열 수 있는 자물쇠가 있는 상자에 대해 생각해 보자. 보안 메시지를 받으려면 발신자에게 상자와 자물쇠를 보낼 수 있다. 발신자는 메시지를 넣고 잠근다. 이제 저 상자를 저에게 돌려보낼 수 있고 제 개인 키로만 열 수 있다. 상자를 잠그고 나면 보낸 사람이나 상자를 찾은 누구라도 무차별한 공격 없이는 열 수 없다.

  같은 방식으로, 디지털 공개 키는 오직 개인 키로 해독할 수 있는 것을 암호화한다. 반대로 공개 키로 해독할 수 있는 개인 키로 무언가를 암호화하는 것도 가능하다. 이것은 서버가 개인 키를 사용하여 데이터를 암호화하는 서명에 사용된다. 누구나 서버 공개키를 사용하여 암호를 해독할 수 있다. 이것은 소유자만이 개인 키를 사용하여 암호화할 수 있기 때문에 위조할 수 없는 서명처럼 작동한다. 그것은 가짜가 아닌 올바른 서버 또는 사람에게 데이터를 얻고 있다는 것을 증명한다.

  오늘날 가장 널리 사용되는 비대칭 암호화 기술인 RSA는 발명가 이름을 따서 명명되었다. Rivest, Shamir 및 Adleman이다.

 

  이제 암호화의 모든 "핵심" 부분인 대칭 암호화, 키 교환 그리고 공개 키 암호화에 대해 모두 알아보았다. 은행과 같은 보안 웹사이트에 연결할 때 주소창에 작은 자물쇠 아이콘은 컴퓨터가 공개 키 암호화를 사용하여 서버를 확인하고, 비밀 임시키를 설정하고, 대칭 암호화를 사용하여 염탐자로부터 모든 앞뒤 통신을 보호하고 있음을 의미한다.

  온라인으로 물건을 사거나, BFF에 이메일을 보내거나, 고양이 비디오를 탐색하는 등 어떤 것이든 암호화는 모든 것을 안전하고 사적으로 보안하도록 유지한다.