본 탐구는 교내 ‘수학세미나’ 보고서로 작성되었음을 알려드립니다.

탐구 동기

2학년 때 학술제에서 소인수분해와 나누기연산의 역연산에 천문학적 시간이 소요된다는 수학적 원리를 기반으로 하는 RSA암호에 대해 다루었는데, 이때 후속 연구로 RSA보다 보안성이 뛰어나고 기하학적 원리가 사용되는 타원곡선암호에 대해 탐구해보고 싶다고 말했었다. 이번 수학세미나 독서 수행평가에서도 암호학과 관련된 도서를 읽고 여러 가지 암호 알고리즘들을 탐구했었는데, 역시 가장 흥미로웠던 암호는 타원곡선 암호였고, 마침 수1, 2에서 다루게 되는 소인수 분해의 원리나 곱셈, 그래프 분석에 대한 내용이 담겨 있어서, 본 보고서에서는 이를 더 심화탐구 해 보려고 한다. 특히 디지털암호체계에 속하는 타원곡선암호는 비트코인 등 전자상거래, 디지털 키 교환 등 인터넷에서 일어나는 모든 과정에서 입지를 넓혀가고 있기 때문에 원리를 알아볼 필요가 있다고 생각했다.

또한 암호학은 창과 방패같다. 예를 들어 천문학적 연산시간이 소요되는 것에 기반하는 RSA암호는 최근 연산속도가 기존 컴퓨터의 제곱을 뛰어넘는 속도를 가지므로 RSA를 위협하고 있다. 이 흐름을 이어 독서 교과시간에 양자알고리즘을 주제로 탐구를 진행하기도 했다. 이러한 고등학교 전체에 걸친 암호학 탐구의 흐름을 이어서, 그리고 암호학을 배우는 데에 있어서 암호의 새로운 발전 경향을 알아보는 것은 꼭 필요한 자세라고 생각했다.

ECC를 알아보자.

타원곡선암호(ECC)는 타원곡선방정식을 이용한 공개키 알고리즘인데 공개키 알고리즘이란 암호화와 복호화에 사용되는 키가 서로 다른 암호 방식이다. RSA암호는 컴퓨터가 곱셈연산은 빠르게 수행할 수 있지만 곱셈의 역연산인 소인수분해를 하는 데에 많은 시간이 걸린다는 수학적 원리를 사용한다. RSA의 경우 메르센 소수 등의 개념을 이용한 빠른 계산 기법이 일부 존재하지만 ECC의 빠른 계산을 도울 수 있는 방법은 아직 전무하다. 또한 타원곡선의 기하학적 원리를 사용하므로 RSA에 비해 같은 길이의 암호를 사용할 때 훨씬 많은 연산을 요구한다. 즉, 같은 길이의 킷값으로 더 높은 암호 효율을 자랑한다.

아래는 타원곡선의 그래프이다. 타원곡선암호 타원곡선은 타원곡선암호 의 방정식으로 정의된다. 타원곡선에서는 ‘점 배가 연산’, ‘덧셈연산’ 등 다양한 연산이 있는데 대표적인 연산만 알아보자. 덧셈 연산은 P와 Q를 알 때, P+Q는 P와 Q를 연결한 직선이 타원곡선과 만나는 P과 Q가 아닌 지점인 R을 말하고, P+Q=R이라고 표현한다. (P+Q+R=0으로 설명하고, R+Q=-R으로 설명하여 R의 역원 개념을 이용해 설명하는 자료들도 있다.)

ECC의 수학적 원리는 다음과 같다. ‘P: 생성자, 타원곡선 상의 임의의 점, x: 개인키, 난수 생성기로 생성한 P보다 작은 소수, Q: 공개키, 개인키로부터 연산됨’으로 정의할 때, 점 P(x,y)가 타원곡선 상에 위치해 있을 때, 두 점 P, Q와 임의의 정수 x에 대해 ‘Q=xP‘라는 방정식을 정의할 수 있다. 이 수식에서 x와 G를 이용해 Q를 구하기는 쉽기만 알려진 P값과 Q값을 통해 x값을 구하기 힘들다는 ‘타원곡선 이산대수 문제’의 원리가 ECC의 보안성의 중심이다.

타원곡선 이산대수의 문제의 해결 방법은 Q=xP에서 타원곡선에서의 덧셈정리를 이용해 P+P=Q가 성립하는지 판별하고, 만약 성립하지 않는다면 P+P+P=Q가 성립하는지 확인하고 또 P+P+P+P=Q가 성립하는지 연속적으로 계산하는 것 뿐이다. 이 계산을 그나마 효율적으로 할 수 있는 방법으로는 ‘Double and Add 알고리즘’이 있긴하지만 이것 또한 P+P를 연산하여 얻은 2P값을 활용하여 2P+2P를 통해 4P를 얻을 수 있다는 구한 수를 그저 재활용하는 방법이다. 따라서 타원곡선 이산대수 문제에서 x의 값이 커지면 P를 더하는 과정을 매우 많이 거쳐야 하므로 이 문제를 해결하기가 매우 어렵다고 한다. 또한 이 x값을 도출하기가 어려운 이유가 구체적인 증명은 아직 없다고 한다. 단지 여러 계산 결과에 따르면 타원곡선 이산 대수문제는 타원곡선 이산대수 문제는 소인수분해의 몇 배로 훨씬 해결하기 어려운 문제라고만 전해진다.

지금까지는 실수 범위에서의 ECC의 원리를 대략적으로 살펴보았다. 그러나 암호학에서 사용될 때에는 유한체의 범위에서 알고리즘이 작동하는데, 유한체란 특정한 범위의 수 안에서 mod 연산을 통해 이루어지는데, 실수 범위에서 작동할 때와는 다르게 역원을 구하는 방법 등에서 다른 알고리즘을 더 사용해야 하는 등 더 복잡하다.

ECC와 RSA를 비교했을 때, RSA는 암호화에 주로 1024비트를 사용하는 반면, ECC는 160비트를 사용하지만 RSA보다 뛰어난 안정성을 가지고 암호화 처리속도가 빠르다. 현재 비트코인이나 애플서비스의 DNS 정보 암호화 등등에 사용되고 있다고 한다.

‘고등수학으로 이해하는 타원곡선암호학’ 강의를 참고하였다.

대학교 전문 강의를 들은 내용이 아니기에 잘못된 내용이 있는 경우 splanky0314@gmail.com으로 부탁드립니다.