압축, 암호 알고리즘 단순 무식한 이해

압축 암호 알고리즘을 인터넷에서 찾아 봐도 참 설명이 어렵다. 너무 수학적이고 학문적인 표현을 사용한다. 가장 유명하며 그래서 가장 많이 쓰이는 압축 방법 몇 개를 정리해 보겠다. 자기 데이터 압축하거나 암호화할 때 사용하면 되겠다. 압축 방법을 모르면 압축이 암호화 한 것과 다름없다. 

1. 코드(암호) 사전 : 문자/단어 → 숫자

누구에게 편지를 보낸다고 하자. 그런데 그 편지에 사용하는 단어는 99개를 넘지 않는다고 하자. 그럼 모든 단어를 십진수 2개 (00~99)로 나타낼 수 있을 것이다. 예를 들어 우리가 사용하는 단어가 6만 개 미만이라고 할 경우 16비트 정수로 단어를 대신할 수 있다. 그러면 모든 단어는 2바이트만 차지한다. 보통 한글 한 글자는 16비트(완성형, 조합형, 유니코드)로 나타내기 때문에 단어를 문자 하나로 압축한 효과가 있다. 또는 가변 길이를 사용해서 압축할 수도 있다.

• 0xxx.xxxx = 128개의 사용 빈도가 높은 짧은 단어(1 ~ 2 글자 단어)
• 1xxx.xxxx + 0xxx.xxxx = 1만6384개의 중간 길이 단어
• 1xxx.xxxx + 1xxx.xxxx + 0xxx.xxxx = 209만7152개의 긴 단어

이 아이디어는 유니코드 가변 길이(UTF-8)와 비슷하고, 미디 파일에서 음의 길이 표현에서 사용하는 방법과 같다. 여하튼 2바이트만 가지고 거의 모든 단어를 대신할 수 있기 때문에 간단하게 압축이 된다. 문서 압축에 이용해 보시길. 헌데 단어 사전의 양이 너무 방대하다. 이 사전을 미리 상대가 알고 있어야 한다. 우리가 흔히 사용하는 단어는 1만 미만이다. 일상생활에선 몇 천개 수준의 단어만 사용한다.

2. RLE(Run Length Encoding) : 동일 내용 압축

이것은 주로 흑백 이미지나 색상과 명암이 단순한 만화, 문서 이미지 등에서 사용하면 좋다. 이런 자료들은 같은 내용이 반복되는 경우가 많다. 그래서 주행길이코드라고 부르는 것이다. 이 방식은 FAX에 이용하는 방식이다.

AAAAAAABBBBBBCCCCC = A7B6C5

아이디어는 위와 같은데 컴퓨터에선 모든 것을 2진수로 표현하기 때문에 데이터와 길이를 구분하는 표시가 있어야 한다. 그래서 첫 비트로 데이터와 길이를 구분한다고 하면 다음과 같이 된다. 만약 반복이 없는 부분이 나타나면 그대로 표현하는 것이 더 낫다. 그런 경우 첫 비트가 계속 0인 것만 나오겠지?

0xxx.xxxx = 128개의 데이터 구분

1xxx.xxxx = 최대 128까지의 길이

3. 허프만 부호화(Huffman coding) : 빈도 → 길이

이것은 문서나 프로그램에서 단어(코드) 사용 빈도가 높은 것은 짧은 코드로, 빈도가 낮은 것은 긴 코드로 대체하는 것이다. 예를 들어 2진수로는 다음과 같이 코딩할 수 있을 것이다. 마지막 0은 끝을 알리는 구분자이다. 이 방식은 보통 우리가 사용하는 압축 프로그램에서 사용한다. 앞의 코드 사전의 가변 길이와 비슷한 개념이다.

10 = 가장 빈도가 높은 것

110

1110

11110 = 가장 빈도가 낮은 것

이 아이디어는 이미 우리 언어에서 발견할 수 있다. 1~3 글자 단어는 아주 자주 사용하는 문법 단어들이고 4글자 이상은 비교적 자주 사용하지 않는다. GIF, PNG, JPEG 이미지 파일 압축도 이런 방식을 사용한다. 

4. 푸리에 변환 : 패턴/무늬/물결 압축

사진이나 음악처럼 반복 패턴(무늬/물결)이 있는 경우는 어떻게 하지? 예를 들어 다음과 같은 경우 말이다.

ABCABCABCABC = ABC4

반복성을 검사하는 방법은 무식한 비교 외엔 없다. A를 읽고 B와 비교하니 다르다. 그럼 AB를 기억하고 C를 읽어 AB와 비교하니 다르다. 그럼 ABC를 기억하고 다시 A를 읽으니 첫 글자가 같다. 그럼 나머지 BC도 읽어 붙여 비교한다. 그럼 ABC가 일치한다. 1회 반복이 된 것이다. 몇 번 반복 되었는지 계속 비교한다. 이런 짓을 해야 한다.

반복을 인식하려면 과거를 기억해야 하고 과거와 현재를 계속 비교해야 하기 때문에 계산양이 많다. 짧은 반복은 눈에 쉽게 보이는데 아주 긴 천문학적 수준의 반복은 반복인지 느끼지도 못 한다. 큰 반복을 파악하려면 장기간의 과거 기억이 필요하다.

소리나 이미지의 경우 주기적인 특성을 보이는데 이런 주기적 특성을 분석할 때 푸리에 변환을 사용한다. 매우 계산 시간이 많이 소모되는데 주기적인 데이터의 경우 그 주기만 파악하면 압축 효과가 있다. MP3나 JPEG, MPEG 등에서 사용한다. 그런데 우리가 이 짓을 해서 압축할 수준은 아니겠지? 그래도 몇 가지 비슷하게 하는 방법이 있다.

1. 구간 평균을 뺀다.
2. 음수와 양수가 교차하는 지점의 간격을 조사한다. 
3. 주기성이 있다면 특정 간격들에서 빈도가 높게 나타난다.
4. 주기성이 보이는 간격들을 모두 합한 길이가 반복 주기다.

5. 암호화 방법 = 내용 바꾸기 + 위치 바꾸기

압축을 푸는 방법을 알려 주지 않으면 그대로 암호가 된다. 옛날부터 사용하던 암호화 방법이 있다. 문자 하나를 대체하는 방법과 문자들의 자리 바꾸는 방법이다. 이 두 방법을 섞어 사용한다. 자리 바꾸기를 하려면 단위 블록을 정해야 한다.

가나다라마 = ABCDE (문자 바꾸기)

가나다라마 = 다나라가마 (자리 바꾸기)

가나다라마 = CBDAE (문자 바꾸기 + 자리 바꾸기)

위에서 5글자를 블록으로 정해서 문자 바꾸기와 자리 바꾸기를 한 경우이다. 문자 바꾸기는 코드 사전과 비슷한 느낌일 것이다.

6. 대칭 키 암호

문자를 바꾸거나 자리를 바꾸는 방식을 알려주는 정보(숫자)가 키(열쇠)이다. 암호를 만든 쪽과 암호를 푸는 쪽이 같은 키를 사용하면 대칭키 암호이다. 이 암호 키는 당연히 정보를 주고 받을 사람 둘만 알고 있어야 한다. 문제는 10명이 서로가 모르게 암호를 사용해서 통신할 경우 10*10/2-10/2=50개의 키가 있어야 한다는 것이다. 즉, 1명은 나머지 9명과의 암호 키를 가지고 있어야 어느 한 사람과 통신할 때 나머지 8명이 해독할 수 없게 된다. 양쪽이 같은 암호를 알고 있기 때문에 어느 한 쪽이 뚫리면 암호는 깨진다. 상대가 배신하면 내가 당하는 것이다.

7. 공개 키 암호

10명의 사람이 있을 때 각자 자신의 공개 키와 비밀 키 짝을 가지고 있다고 하자. 10명은 각자의 비밀 키만 기억하면 된다. 공개 키는 무두에게 공개한다. 그럼 암호화하는 쪽에선 상대의 공개 키로 암호화해서 보내면 받아 해독하는 쪽에선 자신의 비밀 키를 이용해서 암호를 푼다. 대칭 키와 비교해서 사람의 수에 비례한 공개 키만 알면 되기 때문에 편하다. 10명 모두 10명에 대한 동일한 공개 키를 가지고 있고 오직 1개 자신의 비밀 키만 외우면 된다.

공개 키 : ID, 주민 번호, 계좌 번호 같은 것

비밀 키 : PW, 일반 암호, PIN 번호 같은 것

PIN = Personal Identification Number = 숫자 암호(은행 암호)

일반 암호 : 문자+숫자+기호 조합

공개 키가 편한 점은 공개 키 목록을 잃어 버렸을 때 다른 한 사람에게 공개 키를 물어 볼 수 있다는 점이다. 대칭 키의 경우 자신이 가진 키 목록을 잃어버리면 9명 모두 찾아다니며 키를 수집해야 한다는 것이 불편하다.

공개 키가 가능해진 이유를 보면 큰 소수(prime number)의 곱을 구하기는 쉬워도 그 수를 다시 인수 분해하기는 어렵다는 점을 이용했다고 한다. 그러면 공개 키와 비밀 키는 다음과 같은 관계란 것이다. 공개키로 암호화 하고 공개키로 암호를 풀 수 없는데 비밀 키가 있어야 암호를 풀 수 있는 알고리즘이 있어야 가능한 방법이다. 그러니까 암호화 하는 키와 암호를 푸는 키가 달라야 한다.

1. 공개 키 = 비밀 키1 x 비밀 키2
2. 비밀 키2 = 공개 키 x 비밀 키1
3. 비밀 키1 = 공개 키 x 다른 키2

우리가 구한 소수가 많아야 안전하겠다. 예를 들어 우리가 파악한 소수가 100개라고 한다면 그 조합은 100x100 = 1만개가 나온다. 여하튼 공개 키는 대칭 키보다 암호가 뚫릴 가능성이 더 높다. 공개 키에 비밀 키의 힌트가 담겨 있기 때문이다. 인수 분해만 성공하면 풀린다. 역시 키 자체도 비밀로 하는 것이 안전하다. 이 인수 분해를 하자고 양자 컴퓨터를 개발하고 있다고 하는데 잘 안 되는 거 같다.

---

모두가 가질 수 있고 가져야 하는 것에는 뭐가 있을까?

옷, 식량, 집, 교육, 의료, 에너지, 통신, 대중교통 등이다.

국가는 모든 국민에게 이것을 제공하려고 노력해야 한다. 이건 생존과 관련 있고 삶에 필수적인 것들이다. 그리고 모두에게 나눠 줄 수 있는 것이다. 교육은 지식을 나누는 것이라서 얼마든지 공짜로 나눌 수가 있다. 의료는 병든 사람만 필요한데 병든 사람 중에 부자만 병원에 간다면 의사들도 돈을 못 벌 것이다. 그런 사회에선 의료비는 졸라 비싸면서 혜택 받는 사람은 적어진다. 에너지는 식량과 별로 다를 것이 없다. 모든 활동엔 에너지가 필요하다. 그래서 이 시대 식량처럼 저렴한 것이 에너지다. 통신망과 교통망은 돈이 많이 들어가기 때문에 원래 기업보다 돈이 가장 많은 국가에서 제공해야 한다. 이런 것을 민영화(사유화) 하면 국민만 손해 본다.

모두가 가질 수도 없고 모두가 가지면 문제가 되는 것은?

자동차, 배, 비행기, 황금, 미녀 등이다.

황금, 미녀는 그 수가 적기 때문에 모두가 가질 수 없는 것이다. 그리고 생존에 꼭 필요한 것도 아니다. 자동차, 배, 비행기를 모두가 가진다고 해 보라. 이것들이 할 일 없이 놀 때는 주차난이 발생하고 일 하러 나갈 때는 도로, 바다, 하늘이 막힌다. 그래서 이런 것들은 대중교통으로 제공해야 옳은 것이다. 도시 내부의 순환, 도시 사이의 연결엔 대중 교통이 담당하고, 그 외의 대중교통이 통하지 않는 곳에서 직업적으로 운송을 담당하는 사람들에게만 허용해야 한다. 보통 시골에서 자기 자동차를 소유하고 도시에선 전철, 버스, 택시를 타야 정상인데 거꾸로 된 것 같다.

사유화보다 공유화하는 쪽이 바람직한 것은?

농지, 어장, 광산, 공장, 시장, 은행 등 일터이다.

일터는 사적인 공간이 아니다. 사유물이 될 경우 사회 문제를 발생시킨다. 사장이 돈과 힘을 이용해서 여직원을 강간하는 경우 등, 빈부격차를 심화하고 시장을 어지럽힌다. 운영은 민간에게 맡기더라도 소유는 국가가 해야 바람직하다. 즉, 민간에게 대여하고 대여료를 세금 형식으로 받는 것이다. 이렇게 하면 사유재산이 아니기 때문에 국가가 주도적으로 빈부격차를 해소할 수 있고, 모든 사람이 놀고 먹지 않고 일을 하게 되며, 자본주의 시장 논리에도 부합 된다.

이건 사유재산이 없고 공동 생산, 공동 분배하는 공산주의와 다르다. 사적인 물건과 공간에만 사유재산을 인정하고 공적인 공간과 물건은 국유화 되어 있지만 그 것을 운영함에는 경쟁이 있기 때문에 자본주의와 같다. 공산주의가 무너졌다고 해서 긴장을 풀고 옛날 마르크스 시절의 자본주의로 후퇴하면 경제 불황만 계속 될 것이다. 80년대 자본주의(유럽/미국)가 공산주의(소련)를 이길 수 있었던 이유는 빈부격차가 심하지 않은 건전한 자본주의였기 때문이다. 80년대 한국 경제 성장도 이들 유럽/미국의 경제 성장 때문이지 박정희, 전두환의 공이 아니다.