0. 목차
- 공개 열쇠 암호
- RSA 법
- 하이브리드형 암호
- '일방향성을 가진 함수'를 이용한 다양한 암호 방식들
- '암호화' 기술의 응용
- 양자 컴퓨터와 암호의 미래
1. 공개 열쇠 암호
두 차례의 세계 대전이 끝나자 컴퓨터가 급격히 발전하였다. 그와 동시에 암호 기술도 급격히 진화해 나갔다. 그때까지의 암호는 문자나 낱말의 치환이 생각의 중심이었다. 그런데 모든 정보를 0과 1로 처리하는 컴퓨터가 출현함에 따라, 암호 기술은 숫자 변환을 하는 기술로 생각하게 되었다. 왜냐하면, 컴퓨터는 문자 정보를 다룰 때, 문자를 모두 숫자로 바꾸기 때문이다.
그리고 1976년, 이제까지의 암호와는 전혀 다른 종류의 새로운 암호 이론이 발표되었다. 미국 스탠퍼드 대학의 '휘트필드 디피(Whitfield Diffie)'와 '마틴 헬먼(Martin Hellman)'은 1976년에 '암호의 새로운 방향(New Directions in Cryptography)'이라는, 암호의 역사에 남을만한 논문을 발표하였다. 이것은 암호 역사에 큰 전환점이 되는, 전혀 새로운 이론이었다. 이 논문에서 제시된 '새로운 방향성'이란, '암호화에 쓰는 열쇠(암호 열쇠)'와 '복호에 쓰는 열쇠(복호 열쇠)'가 다르고 더욱이 열쇠를 공개한다는 점이었다. 그래서 이 암호는 '공개 열쇠 암호'라고 불린다.
'공개 열쇠 암호'가 발표되기 이전의 암호는 아무리 복잡한 암호라 해도 '암호 열쇠'와 '복호 열쇠'는 같은 것이었다. 예컨대 앞에서 소개한 '시저 암호'에서는, '암호 열쇠'는 '3문자 뒤로 이동시키기'이고, '복호 열쇠'는 '3문자 앞으로 이동시키기'이다. '방향'의 차이는 있었지만, 열쇠는 같았다. 그리고 '암호 열쇠'는 당연히 비밀이어야 했다. 열쇠를 비밀로 유지하는 것이야말로, 암호의 비밀을 지키는 일이었기 때문이다. 하지만 '휘트필드 디피'와 '마틴 헬먼'의 논문은 '암호에 관한 상식'을 모조리 파괴해버렸다.
1-1. 공개함으로써 생기는 큰 이점
암호 열쇠를 공개함으로써, 그때까지의 암호가 가지고 있었던 문제점을 해결할 수 있었다. 개발자들은 암호 열쇠를 공개하기 위해, '암호 열쇠'와 '복호 열쇠'를 다른 것으로 했다고 말할 수 있다.
종래의 암호 체계에서는 우선 B가 '암호 열쇠'와 '복호 열쇠'가 같다. 따라서 예컨대 A가 B에게 암호화해 정보를 보내고 싶은 경우, '열쇠'를 작성해 A에게 암호 열쇠를 전해야 했다. 만약 열쇠를 비밀리에 전하지 못해 제3자인 X에게 열쇠 정보가 노출되었다면, 암호 통신의 내용은 열쇠를 쥐고 있는 X에게 통째로 노출된다. 그런데 '암호 열쇠'와 '복호 열쇠'가 다르다면, 이 걱정에서 해방된다. 정보의 송신자 A는 이미 B에 의해 공개되어 있는 '암호 열쇠'를 써서 정보를 암호화한다. 수신자 B는 비밀의 복호 열쇠를 써서 그 정보를 원래의 것으로 돌리면 된다. 이 일련의 과정에서 비밀로 해야 할 열쇠의 정보를 외부에 알릴 필요는 전혀 없다. 예컨대 제3자 X가 암호문을 입수해도, 복호 열쇠는 공개되어 있는 암호 열쇠와 다른 것이므로, 복호는 불가능하다.
더욱이 암호 열쇠를 공개하면, A 이외의 사람도 간단히 B와 암호 통신을 할 수 있다. B에게 정보를 암호화해서 보내고 싶은 C나 D도, 공개되어 있는 암호 열쇠를 써서 언제든지 암호화할 수 있는 것이다. 따라서 일부러 B로부터 비밀의 암호 열쇠를 배울 필요가 없다.
이 설명을 듣고 머리 회전이 빠른 사람이라면 '공개 암호 열쇠'의 예가 떠올랐을 것이다. 바로 인터넷에서 신용카드를 써서 쇼핑하는 상황이다. 인터넷상에 있는 B의 가게에서 무엇인가를 사려고 할 때, B에서 일부러 비밀 암호 열쇠를 보내 줄 필요는 없다. 공개되어 있는 암호 열쇠를 써서 신용 카드 정보를 암호화해 B에게 송신하면, B만이 그 정보를 '복호화(Decryption)'할 수 있는 것이다.
1-2. 실현에는 '일방향성이 있는 함수'가 필요
이제까지의 설명을 듣고 '그렇게 좋은 방법이 실제로 실현 가능한가?'라고 의문스러워하는 독자도 있을 것이다. 실은 1976년에 논문이 발표된 시점에서는 '공개 열쇠 암호'의 개념만이 제시되었을 뿐, 구체적인 방법은 고안되어 있지 않았다.
'공개 열쇠 암호'를 실현시키기 위해서는 '일방향성이 있는 함수'가 필요했다. '함수(Function)'란 x의 수치가 결정되면 y의 수치도 결정되는 대응 관계를 말한다. '일방향성을 가진 함수'란 'x에서 y를 정하는 일(x→y)'은 간단하지만, 'y에서 x를 정하는 일(y→x)'은 어려운 성질을 가진 함수를 말한다. 이 성질을 암호에 응용하면, '비밀 열쇠→공개 열쇠'의 작성은 간단한데, '공개 열쇠→비밀 열쇠'의 작성은 어려운 열쇠가 가능해진다.
그런데 과연 그렇게 좋은 함수가 실제로 존재할까? 실은 이러한 함수는 우리 주변에도 있다. 과거에는 집마다 뚜꺼운 책으로 전화번호부가 있었다. 전화번호부에서 홍길동의 전화번호를 조사하는 것은 간단하다. 그러나 전화번호부에서 02-1234-5678라는 전화번호가 누구의 번호인지를 조사하는 일은 극히 어렵다. 이 비유에서는 이름과 전화번호가 1대 1의 대응 관계가 있으면서, 전화번호부에서 '이름→전화번호'는 간단하지만 '전화번호→이름'은 어렵다는 '일방향성'이 생긴다.
2. RSA 법
2-1. 마침내 '공개 열쇠 암호'의 구체적인 방법이 고안되었다.
'공개 열쇠 암호'가 발표된 다음 해인 1977년, 마침내 '공개 열쇠 암호'를 실현시키는 방법이 미국 매사추세츠 공과대학의 '리베스(Rivest)', '샤미어(Shamir)', '아델만(Adelman)' 등 세 사람의 연구로 고안되었다. '공개 열쇠 암호'를 실현시키는 이 방법은 세 사람의 머리글자를 따서 'RSA 법'이라고 불리게 되었다.
세 사람은 '공개 열쇠 암호'의 아이디어를 들었을 때, '공개 열쇠 암호는 실현 불가능하다는 것을 증명하지 못했다. 불가능하지 않다면 구체적으로 만들 수 있다는 생각을 했고, 그 결과 RSA 법의 아이디어에 도달했다. 그러면 RSA 법에서 이용된 '일방향성을 가진 함수'란 무엇이었을까? 그것은 바로 '소인수 분해(Prime Factorization)'였다.
2-2. 소인수 분해(Prime Factorization)
'공개 열쇠 암호'를 마침내 실현시킨 'RSA 법'에서는 '소인수 분해'가 일방향성을 가진 함수로 이용된다. '소인수 분해(Prime Factorization)'란 '어떤 정수를 소수의 곱셈으로 나타내는 일'이다. '소수(Prime Number)'란 그 자신과 1로만 나누어지는 자연수를 말한다. 예컨대, 2, 3, 5, 7, 9, 11, 19 등이 바로 소수이다. 3은 3과 1로 인수분해를 할 수 있다.
'51을 소인수 분해 하라'는 문제가 출제되면, 아마 약간의 시간이 걸리겠지만 곧 3과 17이라는 답에 도달할 것이다. 그런데 이어 '어떻게 소인수 분해를 했는지 설명하라'는 질문을 받으면, 어떻게 대답할 것인가? 아마 '작은 소수부터 차례로 51을 나누어나갔다.' 정도로만 대답할 수 있을 것이다. 실은 소인수 분해의 답을 도출하기 위한 효율적인 방법은 발견되어 있지 않다. 기본적으로 작은 소수부터 차례로 나누어지는가를 확인하는 수밖에 없다. 큰 수의 소인수 분해의 효율을 높이는 방법은 몇몇 고안되어 있긴 한데, 모든 수에 대해서 쓰이는 만능의 방법은 아니다. 그리고 정보 처리 속도가 매우 빠른 컴퓨터를 쓴다고 해도, 큰 수의 소인수 분해는 극히 어렵다.
RSA 법에서는 두 소수 예컨대 3과 17을 '비밀 열쇠'로 이용해, 그 두 소수를 곱해서 나온 수 51을 '공개 열쇠'로 이용한다. 그러면 '비밀 열쇠'에서 '공개 열쇠'를 구하는 3×17→51은 간단한데, '공개 열쇠'에서 '비밀 열쇠'를 구하는 51→3×17은 어려운 '일방향성'이 생긴다. 더욱이 실제의 RSA 법에서는 이보다 훨씬 복잡한 계산을 한다.
2-3. 소수의 자릿수가 많아질수록 안전성은 향상된다.
어렵다고 해도 '자릿수'가 그렇게 크지 않은 수의 '소인수 분해'라면 어느 정도의 시간 내에 컴퓨터로 해결된다. 현재 RSA 법에서는 안전성을 유지하기 위해 약 150자리의 소수 둘을 곱한 수 즉, 300자리를 '공개 열쇠'로 해서 이용하는 일이 추천된다. 우리의 중요나 정보는 이처럼 거대한 수를 이용해 암화함으로써 안전하게 지켜지는 것이다. 더욱이 RSA 법에서 말하는 '안전'이란 '공개 열쇠'에서 '비밀 열쇠'를 꺼내는 데 몇만 년이나 몇백만 년, 또는 그 이상의 엄청난 시간이 걸린다는 것을 의미한다. 결코 절대로 풀지 못한다는 의미는 아니다. 컴퓨터의 성능은 해마다 향상되고 있다. 하지만 공개 열쇠의 자릿수를 여러 개 늘리는 것만으로도 소인수 분해의 난이도는 엄청나게 높아지므로 안정성을 확보할 수 있다. 또한 소수는 자릿수가 커져도 무한히 존재한다는 것이 증명되어 있다.
그러면 RSA 법은 앞으로도 계속 안전할까? RSA 법이 고안된 지 수십 년이 지났지만, RSA 암호화는 안전성을 유지하고 있다. 이것은 소인수 분해의 획기적인 해법이 아직도 발견되지 않았다는 것과 통한다고 할 수 있다. 그러나 미래에 소인수 분해를 간단하게 할 수 있는 획기적인 방법이 발견되지 않는다는 보장은 없다. 그때는 RSA 법을 대신하는 암호화 기술이 필요해질 것이다.
3. 하이브리드형 암호
RSA 법 등으로 이용되는 '공개 열쇠 암호'는 매우 강력한 암호이지만 단점도 있다. 그것은 엄청난 계산을 해야 하기 때문에 암호화나 복호의 처리에 시간이 걸린다는 점이다.
열쇠를 공개하지 않는 '전통적인 암호'는 '암호 열쇠'와 '복호 열쇠'가 모두 비밀이기 때문에, '공개 열쇠 암호'에 비해 '비밀 열쇠 암호'로 불린다. 그런데 '공개 열쇠 암호'가 등장했다고 해서 '비밀 열쇠 암호'가 쓰이지 않게 된 것은 아니다. 진화된 '비밀 열쇠 암호'는 지금도 널리 사용되고 있다. 매우 강력하지만 시간이 걸리는 '공개 열쇠 암호'와 열쇠의 취급에 주의가 필요하지만 처리가 빠른 '비밀 열쇠 암호'를 조합한 '하이브리드형 암호'가 현재 다양한 곳에서 쓰이고 있다.
'하이브리드형 암호'의 기본적인 구조는 어떨까? 먼저 정보의 본체를 '비밀 열쇠 암호'를 써서 암호화한다. 그리고 '비밀 열쇠 암호의 암호 열쇠'를 '공개 열쇠 암호'를 써서 암호화하는 것이다. 결국 2종의 암호를 2단계로 조합해 쓰는 것이다. 이 방법에 의해, 정보의 수신자에게 안전하게 '비밀 열쇠 암호의 암호·복호 열쇠'를 송신할 수 있으며, 전체의 암호화와 복호에 걸리는 시간을 단축시킬 수 있다.
4. '일방향성을 가진 함수'를 이용한 다양한 암호 방식들
RSA 법은 소인수 분해의 어려움을 이용해 안정성을 확보하는데, 소인수 분해 이외에 '일방향성을 가진 함수'를 이용한 암호 방식이 몇몇 고안되어 이용되고 있다.
4-1. 타원 곡선 암호(ECC)
자세한 설명은 생략하지만, 예컨대 '타원이산 로그(Ellipse Discrete Logarithms)'라는 '일방향성을 가진 함수'를 이용한 '타원 곡선 암호(ECC: Elliptic Curve Cryptography)'라는 방식이 있다. '타원 곡선 암호'는 워싱턴 대학교의 수학교수인 '닐 코블리츠(Neal Koblitz, 1948~)'와 IBM연구소의 '빅터 밀러(Victor Miller)'가 1985년에 각각 독립적으로 제안했다. '타원 곡선 암호(Elliptic Curve Cryptography)'는 소인수 분해보다 짧은 열쇠를 써도 같은 안정성을 유지할 수 있다고 한다. 암호화 디지털 서명해 다양한 기능을 실현시킬 수 있으므로, 장래에는 현재 주류인 RSA 법을 대신해 널리 이용될지도 모른다.
5. '암호화' 기술의 응용
우리 주변에서는 '암호화(Encryption)' 기술이 곳곳에서 쓰이고 있다. 인터넷에서 개인 정보를 주고받는 것 말고도, 휴대전화의 통과, 지정 지역 밖에서의 재생을 막는 '리전 코드(Region Code)' 등이 부착된 DVD, IC 카드나 전자 머니, 은행의 ATM 등에도 암호화 기술이 사용되고 있다. 한편 PC를 사용한 e-mail은 기업이나 가정에서 널리 쓰이고는 있으나, 기본적으로 암호화가 되어 있지 않다. e-mail의 정보는 평문의 상태에서 네트워크상을 이동하며, 악의를 가진 제3자가 e-mail의 정보를 입수하면 그대로 내용이 해독된다.
눈에 보이지 않는 디지털 정보가 난무하는 현대 사회에서, 일반인들이 정보의 비밀을 지키기 위해 할 수 있는 일은 무엇이 있을까? 우선 신용카드류의 비밀번호 등, 중요한 정보를 e-mail 등으로 쉽게 송신하지 말아야 한다. 그리고 개인 정보를 송신할 때는 암호화가 이루어졌음 을 확인해야 한다. 또한 정보가 유출될 경우에 대비해, 사이트 등에서 사용하는 비밀번호와 신용카드류에서 사용하는 비밀번호를 다르게 하는 것 등이 있겠다.
6. 양자 컴퓨터와 암호의 미래
암호의 안전성에 위협이 되는 것은, 컴퓨터의 처리 속도가 빨라지고 소인수 분해에 걸리는 시간이 짧아지는 진보는 아니다. 이처럼 '예측할 수 있는 진보'에 대해서는 RSA 법의 열쇠가 되는 소수의 자릿수를 늘리는 대응책을 세울 수 있기 때문이다. 암호에서 진짜로 위협적인 것은 오히려 '예측할 수 없는 진보'이다. 예컨대, 소인수 분해를 간단히 할 수 있는 획기적인 방법이 발견되면, 아무리 열쇠의 자릿수를 늘려도 안전하지 못하게 된다.
현재 RSA 법에서는 예측할 수는 있으나 장래에 언제 실현될지 모르는 위협이 존재한다. 그것은 바로 '양자 컴퓨터(Quantum Computer)'이다. '양자 컴퓨터'는 '양자 역학(Quantum Mechanics)'의 원리를 이용한 컴퓨터이다. 양자 컴퓨터는 현재의 컴퓨터와는 전혀 다른 개념으로 작동하며, 현재의 컴퓨터로 몇만 년이나 걸리는 매우 큰 수의 소인수 분해를 순식간에 풀 수 있다. 이렇게 되면 RSA 법은 안전하지 못하게 된다. RSA 법뿐만 아니라, 현재 사용되고 있는 암호가 앞으로도 계속 안전하다는 보증은 어디에도 없다. 지금도 세계의 암호 연구가들은 더욱 안전하고 실용적인 암호 방식을 개발하기 위해 연구하고 있다.