이산로그 문제에 대한 빠른 암호해독법 개발 - 서울대 천정희-홍진 교수팀, Asiacrypt 최우수 논문상 수상 -
1. 연구 배경 및 현황 현대 사회에서 컴퓨터 이용이 증가함에 따라 정보를 보호하는 것이 중요한 문제로 대두되고 있다. 인터넷 뱅킹이나 전자 상거래 등과 같이 인간 생활을 편리하게 만드는 시스템들이, 이에 대한 정보 보호가 제대로 이루어지지 않으면서, 오히려 개인의 사생활 침해를 발생시키거나, 회사 기밀을 노출시키고, 심지어는 새로운 사회 범죄 문제를 일으키는 등 많은 문제를 야기하는 상황에 우리는 직면해있다. 결과적으로 이러한 문제가 생기지 않도록 정당한 사용자 외에는 정보에 접근할 수 없도록 만들어주는 암호 시스템의 중요성이 나날이 커져가고 있다.
암호학 분야는 크게 비밀키 암호와 공개키 암호 분야로 나눌 수 있다. 비밀키 암호는 주로 암호화 자체를 효율적으로 하는 도구로 사용되며, 비밀키 암호로 처리된 결과는 일반적으로 키(열쇠)가 있어야만 복구할 수 있는 형태가 된다. 효율적인 암호화 통신을 위해서는 이 키의 안전한 전달 또는 공유가 중요한 문제가 된다. 1976년 Diffie와 Hellman에 의해서 처음 시작된 공개키 암호는 이러한 키교환 문제를 효율적으로 해결할 수 있도록 하는 방법이며, 이후 디지털 서명이나 전자화폐 같은 새로운 암호의 응용을 출현하게 하였다. 공개키 암호는 그 안전성의 기반을 수학적인 난제에 두는데, 그 중 대표적인 것이 인수분해와 이산대수 문제이다.
이산대수 문제는 g로 생성되는 유한 순환군의 임의의 원소 h에 대하여 h=gx를 만족하는 가장 작은 양의 정수 x를 구하는 것을 말한다. 이는 암호화, 전자서명, 키교환 등 다양한 암호기술에 응용되고 있으며, 우리가 생각하는 것보다 훨씬 우리 생활과 밀접하게 사용되어 있다. 실제로 암호론에서는 주로 유한체의 곱셈 부분군과 타원곡선의 부분군이 이러한 유한 순환군으로 사용되며 이번 연구결과는 유한체의 경우를 다루고 있다.
이산대수 문제에 기반한 공개키 암호는 우리가 인식하지 못하는 사이에 우리 생활 속에서 이미 자주 사용되고 있다. 예를 들어 미국 표준 전자서명(DSA, Digital Signature Standard)은 유한체 위의 이산대수 문제에 기반하여 설계되었으며, 이는 인터넷 보안의 도구로 여러 제품에 구현되어 있다. Netscape가 개발한 인터넷 보안 프로토콜 SSL은 현재는 TLS이라는 형태로 전세계적인 표준이 되었는데, 이는 대부분의 web browser에 구현되어 있다. 인터넷 사용 중 주소창에 “https”를 보게 되는 경우는 TLS가 동작 중이라고 생각해도 된다. 또한 원격 컴퓨터에 접속 방법으로 telnet을 대체하고 있는 ssh 또한 DSA를 구현하여 활용하고 있다.
1971년 Shanks가 이산대수 문제를 해결하기 위한 알고리즘을 제시한 이후로, 1978년에 Pollard가 Shanks의 알고리즘과 같은 복잡도를 같지만 저장 공간 필요성을 개선한 알고리즘을 제안하였고, Pohlig와 Hellman은 유한 순환군에서의 이산대수 문제의 어려움은 군의 위수를 나누는 가장 큰 소수에 의해서 결정된다는 사실을 보였다. 이후, 유한체 이산대수를 준지수시간 안에 해결하는 Index Calculus 방법이 제안되었지만, 유한체 곱셈군의 부분군이나 타원곡선 덧셈 군에서는 여전히 Pollard 방법이 가장 효율적인 알고리즘으로 알려져 있다. 1999년에 Pollard 방법의 효율적인 병렬화 방법이 제시된 것을 제외하고는, 90년대 이후로 이산대수 연구는 큰 진전이 없는 상태이다.
천정희-홍진 교수팀에 의해서 제시된 결과는 이렇게 답보 상태에 머물고 있는 이산대수 연구에 진전을 가져온 결과로서, 이는 유한체 곱셈군의 부분군에서 이산대수 문제를 해결하는데 가장 효율적인이라고 알려진 Pollard의 방법을 개선한 것이다.
2. 연구 내용 및 방법 이산대수 문제를 해결하기 위해서 Pollard가 제안한 것은 gihj 형태로 표현된 군의 원소들 중에서 같은 원소를 찾고, h의 이산대수를 구하는 방법이다. 즉, gahb=gchd와 같은 형태의 충돌쌍으로부터 얻은 선형 방정식 a+bx=c+dx에서 h의 이산대수 x를 구하는 것이다. 이러한 충돌쌍을 효율적으로 찾기 위해서 Pollard가 제시한 방법은 순환군 위에서의 함수 f를 이용하여 gihj형태의 수열 (gi)i≥0, gi+1=f(gi)을 생성하고, 그 수열 안에서 충돌쌍을 찾는 것이다. Birthday Paradox에 의해서 충돌쌍이 발생하기까지 대략 순환군 위수의 제곱근 번 f 계산이 필요하기 때문에, Pollard가 제시한 알고리즘의 복잡도는 군 위수의 제곱근 번 f 계산이 된다.
천정희-홍진 교수팀은 충돌쌍을 찾는데 있어서 수열 (gi)i≥0의 모든 항을 계산할 필요가 없다는 점에 착안하여 Pollard의 방법을 개선하였다. 즉, 두 개의 군 원소 gi, M로부터 이를 곱한 결과에 대한 몇 비트 정보를 (군 연산을 하지 않고) gi와 M만으로 얻어내는 방법을 이용하여, 한 번 f의 계산이 필요했던 것을 (f 계산보다 효율적인) 다른 연산으로 대체하여 알고리즘의 전체적인 복잡도를 개선하는 방법을 제시하였다. 천정희-홍진 교수팀은 구체적으로 유한체에서 두 원소를 곱하지 않고 곱한 결과의 몇 비트 정보를 얻어내는 방법을 제시하여, 유한체 상에서 이산대수 알고리즘을 수십 배 빠르게 개선하였다.
3. 연구 성과 및 향후 계획 천정희-홍진 교수팀은 유한체의 곱셈 부분에서의 이산대수 문제를 기존의 방법보다 수십 배 빠르게 해결하는 방법을 제안하였다. 이 연구결과는 90년대 이후 이산대수 연구에 큰 진전이 없는 상황에서 제시된 성과이다. 이는 암호분야의 3대 학회 (Crypto, Eurocrypt, Asiacrypt) 중 하나인 Aisacrypt에서 발표될 예정이다. 또한, 채택된 33편의 논문 (196편 제출) 중에서 중 최우수 논문으로 선정이 되었으며, 암호 분야의 최고 저널이며 수학분야 상위 5%에 속하는 저널인 Journal of Cryptology에 초청되었다. 천정희-홍진 교수팀의 결과는 이산대수를 해결하는 새로운 접근 방법을 제시한 것으로서, 이를 이용하여 타원곡선에서의 이산대수 알고리즘을 개선하려는 계획을 갖고 있다. 최근에는 미국국가안보국(National Security Agency: NSA)에서 타원곡선 암호를 대외비(unclassified)뿐 아니라 기밀(top secret)문서의 암호화에도 사용할 수 있다고 발표하였다. 이에 따라 타원곡선 암호의 빠른 해독 기술은 더욱 큰 파급효과를 가질 것으로 보인다.
Notice
Home > Board > Notice