이게 무슨 뜻이야? 암호의 역사

눈을 뜨자마자 핸드폰을 열어 시간을 봅니다. 비몽사몽한 상태로 노트북을 가져와 네이버에 로그인합니다. 그리고 웹툰을 보고 댓글을 쓰거나, 넷플릭스에 들어가 미드를 정주행합니다.

주말을 보내는 저의 모습입니다. 이 과정에서 저는 암호를 몇 번이나 풀었을까요? 핸드폰을 열 때 한번, 노트북을 열 때 한번, 네이버에 로그인할 때 한번, …. 우리들은 살아가면서 수도 없이 많이 암호를 풀며 살아갑니다. 예전에 사용되던 암호문들은 해석할 수라도 있지, 이렇게 온라인으로 입력된 암호는 어떻게 작동하는지 참 알기 어렵습니다. 지금부터 지금까지 존재했던 암호와 작동 방식을 알아가고자 합니다.

대표적인 잠금 장치, 자물쇠

암호의 가치

일단 암호를 우리편이 풀어내는 것을 복호화, 적이 암호를 풀어내는 것을 해독한다고 합니다. 해독하는 데 걸리는 시간과 비용이 복호화 할 때보다 더 많거나, 해독할 수 없는 암호가 좋은 암호입니다. 그러나 생각보다 해독하지 못하는 암호는 많습니다. 일반인이 무작위로 만든 암호의 경우, 풀 가치가 없기 때문에 풀어내지 않습니다.

대칭키를 이용한 암호

암호화를 할 때는 키가 필요합니다. 암호를 만드는 규칙을 보통 키라고 합니다. 이때 대칭 키는 암호화와 복호화시에 같은 규칙이 사용된다는 것입니다.

그 첫 번째 예시는 시저 암호입니다. 시저 암호는 단순하지만, 암호의 역할을 충실히 해냅니다. 시저 암호는 각 알파벳을 숫자에 대응시킨 뒤, 어떤 키(자연수)를 더해 암호문을 만들어냅니다. 우리가 해독할 때는 암호문의 알파벳을 숫자에 대응시켜 키를 빼내서 해독합니다. 만약 중간에 적이 암호문을 가져가더라도 적은 키를 모르기 때문에 해독이 불가능합니다.

조금 더 복잡한 암호는 복합 시저 암호입니다. 한가지의 키만 사용했던 시저 암호와 달리, 복합 시저 암호는 2개 이상의 키를 돌려가며 암호화 하기 때문에 해독하기 더 어렵습니다. 복합 시저 암호를 해독하기 좀 더 어렵게 하려면 난수표를 이용하면 됩니다. 난수표는 특별한 규칙이 없는 수열입니다. 각 문자마다 키가 다르기 때문에 난수표가 없다면 해독은 불가능 합니다. 가끔씩은 특별한 규칙 없이 한 문자를 다른 문자에 대응시켜 암호화 하기도 합니다.

그러나 위에서 말한 몇몇 암호들의 경우 큰 문제가 있습니다. 기술이 발전될 수록 해독하는 시간이 줄어든 다는것입니다. 먼저 시저 암호의 경우 키가 어느 숫자(영어의 경우 26) 이상이 되면, 단어의 수가 정해져 있기 때문에 결국 더 작은 키로 만들어진 암호문과 똑같이 나오게 됩니다. 즉 몇몇 키를 넣어 복호화해보면 결국에는 암호문이 해독할 수 있습니다.

복합 시저 암호의 경우 좀 더 복호화하기 어렵습니다. 언어에는 자주 쓰이는 단어들이 있는데, 예를 들어 영어에서는 the나 a와 같은 단어가 있습니다. 이들 단어 사이 거리의 약수들을 구하다 보면 사용되는 키의 개수를 알 수 있습니다. 총 키의 개수를 알아낸 다음, 시저 암호 해독 방식을 이용하면 됩니다. 마지막으로, 무작위로 대체하는 암호는 이런 시저 암호들보다는 해독하기 어렵지만, 특정 언어에서는 자주 사용되는 문자가 있기 때문에 그 빈도를 이용해 대응시켜 보면 결국 해독할 수 있습니다.

비대칭 키를 이용한 암호

비대칭 암호는 암호화와 복호화에 다른 키가 사용되는 암호입니다. 간단한 비대칭 암호는 곱 암호입니다. 암호화 하는 방식은 시저 암호와 비슷합니다. 각 문자를 숫자에 대응시킨 뒤, 키(자연수)를 곱한 뒤 문자의 개수(영어의 경우 26개)로 나누어 다른 문자에 대응시킵니다. 예시를 들면, A를 0, B를 1,…로 대응 시킨 상황을 생각해 봅시다. 만약 키가 7이라면, D는 숫자 3와 대응되므로 키를 곱한 뒤에는 21이 되어 V와 대응됩니다. 복호화 시에는 15를 다시 곱하면 됩니다. 이런 방식은 키가 커져도 시저 암호와 달리 계속 다르게 암호화가 되어 안전합니다. 그러나 복합 시저 암호를 해독 할 때 처럼, 자주 사용되는 단어를 관찰해보면 키를 알아낼 수 있습니다.

공개 키를 이용한 암호

과거에는 암호를 이용하는 일이 많지 않았습니다. 국가기관이나 전쟁에서 사용되는 경우를 빼면 거의 암호는 사용되지 않았습니다. 그러나 컴퓨터가 만들어지고, 인터넷 망이 생긴 이후 암호가 사용되는 수가 급격히 늘어났습니다. 컴퓨터가 발전되었기 때문에 공개 키를 이용하는 것은 아닙니다. 대칭 키나 비대칭 키를 이용하면, 사용자와 사용자 사이에 키가 하나, 또는 한 쌍씩 필요하기 때문에 필요한 키의 수가 급격히 늘어납니다. 공개 키의 경우 공개 키와 자신의 키 하나만 있으면 되므로, 필요한 키의 개수가 확연히 적습니다.

대표적인 공개키 암호는 RSA 암호입니다. 간단히 원리를 설명하자면, 두 큰 소수 x와 y를 준비해서 (x-1)(y-1)로 나눈 나머지가 1이 되는 e와 d를 구합니다. 그렇게 된 경우, 암호화 할 때는 원하는 숫자의 e제곱을 하고, 복호화할 때는 d제곱을 하면 됩니다. 페르마 소정리를 이용하면 증명할 수 있습니다. 소수가 작은 경우 걸리는 시간이 길지 않으나, 소수가 커질수록 시간이 급격히 늘어나 현실적으로 계산이 불가능합니다.

암호의 미래

아직까지 존재하는 많은 암호는 만약 미래에 컴퓨터가 엄청나게 발전한다면 금방 해독할 수 있습니다. 그래서 현재 연구되고 있는 암호가 양자 암호입니다. 양자 암호는 0과 1이 중첩된 상태를 가지고 있어, 해독은 불가능합니다.

양자 컴퓨터의 사진

더 자세한 정보는 https://www.ksakosmos.com/post/%EB%8F%84%EC%B2%AD%EC%9E%90%EB%A5%BC-%EC%9E%A1%EC%95%84%EB%82%BC-%EC%88%98-%EC%9E%88%EB%8A%94-%EC%95%94%ED%98%B8 를 참고해주시기 바랍니다. 미국과 같은 여러 나라에서 양자 암호를 개발 중인데, 양자 암호가 개발되면 더 이상 해독과의 전쟁이 끝나게 됩니다.

---

민지홍 학생기자 | Computer science | 지식더하기0

참고자료

[1] 암호수학

[2] 세상의 모든 비밀을 푸는 수학

첨부 이미지 출처

[1] https://unsplash.com/photos/JM9KOmX2a7Q

[2] https://ko.wikipedia.org/wiki/%EC%B9%B4%EC%9D%B4%EC%82%AC%EB%A5%B4_%EC%95%94%ED%98%B82

[3] IBM Research, https://www.flickr.com/photos/ibm_research_zurich/40786969122

ⓒ KAIST부설 한국과학영재학교 온라인 과학매거진 KOSMOS