타원곡선 키 톺아보기
서울대학교 블록체인 학회 디사이퍼(Decipher)에서 ‘타원곡선 키 톺아보기’를 주제로 Weekly Session에서 발표한 내용을 담았습니다. 본 글은 블록체인 기술이 기초로 두고 있는 암호기술 중 타원곡선을 활용한 암호화방식과 키의 생성방식에 대한 내용을 다루고 있습니다.
Author SangyunOck, GoToDi
Seoul Nat’l Univ. Blockchain Academy Decipher(@decipher-media)
Introduction
블록체인 생태계를 처음 접할 때 가장 먼저한 활동은 일반적으로 메타마스크 등의 지갑 서비스를 통해 공개키(public key)와 개인키(private key)를 만들고 저장해두는 일입니다. 그 과정 중 가장 중요하게 다뤄지는 단계는 개인키를 저장하는 부분입니다. 개인키는 한 번 잃어버리면 복구가 불가능하기 때문에 블록체인 생태계에 있는 사람이라면 누구나 처음 온보딩하는 사람들에게 그 부분을 강조하곤 합니다. 그런데 왜 개인키는 복구가 불가능한 것일까요?
본 글은 위와 같은 단순한 질문에서 출발했습니다. 많이들 아시다시피 암호와 관련한 내용은 블록체인 전반에서 찾아볼 수 있습니다.
블록체인의 시작은 비트코인이었고, 비트코인은 암호기술을 통해 중개기관 없이 이중지불 문제를 해결하기 위해 만들어졌습니다. 그 움직임에 동참했던 사람들이 겪은 시대는 컴퓨터와 인터넷이 보급되면서 익명의 사람들과 정보를 주고 받는 일이 일상화 되어가고 있었고, 더더욱 많은 사람들이 블록체인이란 기술에 관심을 가지게 되었고, 다양한 암호학 이론들을 이에 적용하는 시도를 하게 되었습니다. 블록체인에서 암호기술은 어떤 기능을 하고 있을까요?
암호의 중요성과 활용예시
암호기술은 블록체인의 가장 핵심적인 개념인 분산원장을 구현하는데 활용되었습니다. 분산원장은 분산된 참여자가 상호간에 주고받은 동일한 메시지를 보관하는 방식입니다. 이를 위해선 블록체인 네트워크를 사용하는 사용자와 운영을 담당하는 노드의 메시지가 안전하게 오갈 수 있어야 합니다.
사용자↔노드, 노드↔노드 사이에 메시지를 주고 받는 과정에서 사용하는 암호기술을 간단하게 살펴보겠습니다.
비트코인을 기준으로 메시지가 전달되는 과정을 거래하는 경우를 예로 들겠습니다.
- 사용자가 거래내용과 서명을 노드로 전달합니다. 서명은 사용자가 본인이 보냈다는 사실을 증명하기 위해 전달합니다. 서명은 거래내용을 사용자만 알고 있는 키(개인키)로 암호화하는 방식으로 생성합니다. 또한 서명은 SHA256 방식을 통해 해시됩니다.
- 사용자의 요청을 받은 노드는 메시지가 유효한 것인지를 검증합니다. 사용자의 공개키, 원본 메시지, 그리고 서명을 통해 전달한 메시지가 정말 해당하는 사용자가 보낸 것인지 검증할 수 있습니다.
- 노드는 메시지가 유효하다고 판단될 경우, 메시지를 모아놓는 멤풀로 전달하고, 다른 노드들에게도 검증이 완료된 메시지를 전달합니다. 이를 수신한 노드는 마찬가지로 같은 과정을 통해 검증하고 다른 노드로 전파합니다.
암호화 방식의 종류
일반적으로 암호화 방식은 크게 두 가지의 기준으로 분류할 수 있습니다. 첫 번째 기준은 양방향/단방향입니다. 단뱡향 알고리즘은 원본 데이터(평문)를 해시하여 암호화 이후 다시 원본으로 되돌릴 수 없는 방식을 칭합니다. 주로 원래 데이터 자체가 필요하는 것이 아니라 데이터의 무결성을 확인하거나 일치하는지 검사를 할 때 사용합니다. 양방향 알고리즘은 원본을 암호문으로 바꾸었다가 다시 원본으로 복구할 수 있는 방식입니다.
두 번째 기준은 대칭키/비대칭키입니다. 대칭키 알고리즘은 암호화 및 복호화를 할 때 사용하는 키가 동일한 방식이고, 비대칭키는 그와 반대로 사용하는 키가 서로 다른 방식입니다. 대칭키 암호화 방식의 경우는 암호문을 받는 대상까지 전달하는 과정에서 제3자가 복호화를 하여 메시지를 볼 수 없도록 하기 위해 키와 암호문을 분리하여 전달해야 하지만, 비대칭키는 그렇지 않습니다.
누구든지 원장에 기록된 데이터를 검증할 수 있어야 하고, 데이터의 크기가 큰 이전 블록 전체에 관심을 가지기 보다는 정합성 검증에 초점을 두기 때문에 해시를 하므로 비트코인에서는 단방향, 비대칭키 암호화 방식을 사용합니다.
개인키와 공개키 생성방식
키는 어떻게 만들어지는 걸까요? 잠시 위 이미지에서 보이는 숫자 중에서 아무거나 하나 골라보시기 바랍니다. 고르고 난 뒤에, 숨기고 싶은 내용 알기 위해서 그 숫자가 필요하다고 결정하면 곧 키를 만들게 되는 것과 동일 합니다. 즉, 키는 하나의 숫자입니다.
앞서 본 암호화방식의 분류 중에서 RSA 기법의 예시를 통해 공개키 암호화 방식에 대해 조금 더 자세히 알아보도록 하겠습니다.
수신자, 발신자 모두 일련의 16진수로 표현되어있는 숫자를 각자 개인키로 가지고 있다고 할 때, RSA 방식을 통해서 각 공개키를 생성할 수 있습니다. 이렇게 만들어진 개인키, 공개키를 사용하는 사례를 살펴보겠습니다.
첫 번째 사례는 발신자가 특정 수신자만 볼수 있는 메시지를 전달하는 경우 입니다. 보이는 바와 같이 보내고자 하는 메시지를 특정 수신자만 볼수 있어야 하므로, 발신자는 메시지<”SATOSHI IS ME. I HAVE 100BTC”>를 수신자의 공개키로 암호화를 합니다. 암호화된 메시지<”cXi0U3nKN1fdF…>는 수신자의 개인키로만 복호화가 가능합니다. 수신자의 개인키는 수신자만 알고 있는 것이므로, 다른 사람은 해석할 수 없고 수신한 수신자는 자신의 개인키를 사용해 복호화를 하게 되면 원본 메시지를 볼 수 있습니다.
두 번째 사례는 발신자가 특정 수신자에게 본인이 발신자임을 증명하는 경우입니다. 발신자는 전달하려는 메시지<”IT’S ME”>를 전하면서 그 메시지를 보낸 것이 본인임을 증명하기 위해서 본인의 개인키로 암호화를 해서, 공개키와 함께 수신자에게 전달합니다. 그렇게 암호화된 메시지<”U+OTTR9yc34n9…”>는 발신자의 공개키로만 복호화가 가능합니다. 따라서 수신자는 암호화된 메시지와 함께 송부된 발신자의 공개키로 복호화를 해서 메시지를 확인하면, 메시지의 발신자 여부를 확인할 수 있습니다.
비트코인에서도 마찬가지로 공개키 암호화방식이 활용되었습니다.
그렇다면 우리가 비트코인에서 사용하는 개인키, 공개키, 서명 자체는 어떻게 만들어지는걸까요?
비트코인에서 사용하는 키와 관련된 암호 알고리즘은 ECC(Elliptic Curve Cryptography)로, 타원곡선을 이용한 방식입니다. 타원곡선은 y² = x³ + ax + b라는 수식을 가지는데, 비트코인은 a와 b의 값이 각각 0과 7인 secp256k1을 사용합니다. 다음은 암호화와 관련된 각각의 값의 특성입니다.
- 개인키: 무작위로 생성한 숫자. (256비트 길이, 약 10의 77승)
- 공개키: 개인키를 통해 만들어지는 좌표를 이어 붙여 만드는 값
- 서명: 개인키와 보낸 메시지를 통해 만들어지는 값
개인키는 유추가 힘든 무작위로 생성된 어떤 숫자이고, 공개키는 secp256k1에서 정하고 있는 타원곡선 상의 어떤 좌표를 개인키만큼 곱한 값의 x,y 좌표를 이어 붙여 만든 어떤 값입니다. 서명은 보낸 메시지를 SHA256으로 해시한 후 개인키를 이용해 만든 값입니다. 그럼 이것을 어떻게 실제로 동작하는지 설명을 하겠습니다.
타원곡선함수의 연산
우선 컴퓨터에서 값들을 연산하기 위해서는 한정된 숫자가 필요합니다. 숫자는 무한하기 때문에, 이들을 일정 범위 내에서만 사용하도록 유한체라는 개념을 도입합니다.
유한체란 말 그대로 유한개의 원소를 갖는 집합인데, 다음과 같은 성질을 만족해야 합니다.
- 원소의 개수가 유한하다.
- 사칙연산이 가능해야 하며, 연산의 결과가 다시 체의 원소에 포함되어 있어야 한다.
- 결합법칙이 성립한다.
- 교환법칙이 성립한다.
- 분해법칙이 성립한다.
- 항등원이 존재한다: 어떤 원소와 항등원을 더하거나 곱했을 때 다시 해당 원소가 된다.
- 역원이 존재한다: 어떤 원소와 역원을 더하거나 곱했을 때 항등원이 된다.
위 성질을 만족하기 위해서는 사칙연산을 다시 정의해야 합니다. 먼저 재정의한 덧셈이 기하적으로 어떻게 설명되는지 살펴보도록 하겠습니다.
덧셈을 정의하는 방식은 다음과 같습니다.
- 타원곡선 상의 두 점을 지나도록 직선을 긋는다.
- 직선과 곡선이 만나는 또 다른 한 점을 찾는다.
- 해당 점을 x축에 대해 대칭시킨다.
위의 그림은 나올 수 있는 경우를 모두 보여주고 있는데 1,2의 경우에는 정상적으로 직선과 만나는 또 다른 점을 찾을 수 있는 반면, 3,4에서는 다른 한 점을 찾을 수 없습니다. 이런 경우, 두 점의 덧셈 결과가 무한원점이라고 합니다. 그리고 무한원점은 타원곡선에서의 항등원으로 역할합니다.
그럼 이를 수식으로 풀면 어떻게 되는걸까요? 유한체의 성질을 만족하기 위해서 덧셈의 결과에 나머지를 취하는 mod연산을 하여 덧셈을 재정의합니다.
이때 p는 유한체의 전체 원소의 개수를 뜻하는 수로, 위수라고 하며 소수입니다.
곱셈은 더하기를 반복한 연산이므로 덧셈과 마찬가지로 연산의 결과에 나머지를 취합니다.
하지만 타원곡선의 나눗셈은 이산로그 문제로 인해 단순히 나머지 연산을 취하는 것으로는 구할 수 없습니다. 따라서 나눗셈은 곱셈의 역연산이라는 성질을 통해 구해야 합니다. p가 소수이므로 페르마의 소정리를 이용하면 이를 곱셈으로 바꿀 수 있습니다.
- a / b = a * b^(-1)
- b^(p-1) =1 → 페르마의 소정리
- b^(-1) = b^(-1) * 1 = b^(-1) * b^(p-1) = b^(p-2)
- 따라서 a / b = a * b^(p-2)
위 그림(실수체에서의 타원곡선 상 덧셈의 기하학적 표현)의 첫 번째의 경우에는 두 점을 지나는 직선의 방정식에서 기울기를 찾고, 다른 한 점을 타원곡선에 대입하여 찾는 방식으로 덧셈을 합니다.
이후 x3와 y3에 각각 mod p를 취해주면 됩니다.
두 번째 경우는 직선이 타원곡선에 접하고 있으므로 타원곡선의 방정식을 미분하여 기울기를 바로 구할 수 있습니다.
이후 마찬가지로 mod p를 취해주면 됩니다.
공개키의 생성
개인키와 공개키의 관계는 다음과 같습니다.
P: 공개키
G: 타원곡선상의 한 점
S: 개인키
앞서 설명했듯이 공개키는 타원곡선상의 한 점을 개인키만큼 더한 어떤 좌표입니다. 그런데 위수가 매우 크기 때문에 연산의 횟수를 줄여서 빠르게 곱셈을 수행해야 합니다. 어떻게 하면 좋을까요?
같은 두 점을 더하는 것은 타원곡선의 기울기를 이용하여 덧셈을 빠르게 할 수 있는 성질을 이용하는 것입니다. G * 2 = G + G이므로 G * 8을 구할 때 G + G + G …+ G를 하는 것이 아니라 G * 2 → G*2² → G * 2³과 같이 2의 거듭제곱으로 빠르게 곱셈을 하는 것입니다.
어떤 수를 2의 거듭제곱으로 표현하고, 최고차항에 도달할 때까지 나온 값들을 가지고 있다가 필요한 값들만 덧셈을 하면 로그 스케일로 연산을 줄일 수 있게 됩니다. 이를 pseudo-code로 작성하면 다음과 같습니다.
let bits = bit_representation(s) # the vector of bits (from LSB to MSB) representing s
let res = 0
let temp = P # track doubled P val
for bit in bits:
if bit == 1:
res = res + temp # point add
temp = temp + temp # double
return res이렇게 개인키로 공개키를 구하는 것은 짧은 시간 안에 연산이 가능하지만 반대의 연산은 매우 오랜 시간이 필요합니다. 그 이유는 위에서 나눗셈을 유한체에서 정의한 것을 떠올려보면 알 수 있습니다. p-2 만큼의 거듭제곱을 해야 하기 때문에 엄청나게 많은 연산이 필요하기 때문입니다.
서명의 생성과 검증
이제 디지털 서명을 생성하여 정말로 개인키를 가진 사람이 메시지를 보냈다는 것을 증명하는 방식에 대해 알아보도록 하겠습니다.
생성
- h = hash(m): 원본 메시지(평문)을 해시하여 고정 길이로 만드는 과정을 거칩니다. 비트코인에서는 SHA256 방식을 이용하므로 길이는 256비트가 됩니다.
- k = random(private key, h): 개인키와 해시된 메시지를 기반으로 하는 deterministic하고 랜덤한 값인 k를 구합니다
- R = k * G: 랜덤한 점 R를 구합니다. 이 때 R의 x좌표를 r이라고 하겠습니다.
- 다음 식을 통해 r과 서명 s를 반환합니다. 서명의 길이는 64바이트가 됩니다.
검증
- h = hash(m): 서명을 생성할 때 사용한 같은 해시 알고리즘을 사용해 평문을 해시합니다.
- 서명의 역원s1 을 계산합니다
3. 서명을 할 때 사용한 점인 R’을 복원합니다
4. R’의 x좌표와 r이 같은지 확인합니다.
원리
어떻게 이것이 가능한 것일까요? 서명하는 과정과 검증하는 과정을 수식으로 나타내면 그 원리를 알 수 있습니다.
R’을 풀어서 쓰면 위와 같고, s1, G가 공통적으로 곱해져있으므로 아래와 같이 정리 할 수 있습니다.
또한, 서명의 역원 s1은 아래와 같이 풀어쓸 수 있습니다.
풀어서 쓴 s1을 R’의 s1에 대입하여 정리하면, 최종적으로
이고,
이므로,
이 되어 공개키, 개인키로 각각 암호화, 복호화한 결과가 동일함을 확인 할 수 있습니다.
암호기술의 지속가능성
앞서 살펴본 암호기술을 비롯하여 여러 가지 종류의 암호기술이 우리가 현재 사용하고 있는 대부분의 IT 서비스에서 활용되고 있습니다. 우리에게 도식화해서 표현해보자면 아래 그림과 같이 나타낼수 있습니다.
암호기술 덕분에 안전하게 메시지를 주고 받을 수 있는 통신 기술의 발전이 가능했고, 그 덕에 우리는 그 위에서 여러가지 서비스를 안전하게 사용할수 있게 되었습니다.
그렇다면 암호기술은 무엇을 전제로 하고 있을까요? 많은 암호화 기술은 물리적인 하드웨어를 포함한 컴퓨팅 수준의 한계를 전제로 하고 있습니다.
과연 이것은 앞으로도 지속가능할까요?
짧게는 우리가 사는 세대까지는 계속 될수 있습니다. 혹자는 우리가 흔이 알고 있는 현재 컴퓨팅 아키텍처인 폰노이만 방식의 CPU/GPU- DRAM-NAND 의 방식 자체는 향후 10~20년까지도 대체가 어렵다고 말하기도 합니다.
그러나, 마냥 그렇게 생각하기엔 더 높은 수준의 컴퓨팅 기술을 요구하는 움직임은 지속적으로 증가해왔고, 그 속도는 점점더 기하급수적으로 빠르고 강해지고 있습니다.
지난 IT산업의 발전 과정과 현재의 모습을 돌아보면 쉽게 알수 있습니다. PC, 인터넷, 모바일 등의 흐름 속에서 컴퓨팅 파워에 대한 수요는 점점 높아져왔고, 데이터 형식도 텍스트에서, 사진, 영상 그리고 AR,VR 방식의 컨텐츠까지 더 큰 용량을 사용 하는 쪽으로 발전해오고 있습니다. 최근에는 AI 서비스 쪽에서도 필요로 하는 연산량이 폭발적으로 성장하고 있습니다.
앞으로도 더 낮은 에너지로, 한번에 더 많은 데이터를 빠르게 처리하고자 하는 수요는 계속 될 것이고, 그 수요를 맞추기 위해 여러가지 컴퓨팅 기술이 개발될 것입니다.
그 노력은 기존의 폰노이만 아키텍처 내에서의 발전도 있지만, 폰노이만 아키텍쳐를 벗어나기 위한 노력도 같이 이뤄지고 있습니다. 대표적으로는 양자컴퓨터가 있습니다. 이를 대비하기 위해서 SKT에서 양자암호통신망 기업을 인수 해서 국가 시험망에서 실증사업을 운영하고 있기도 합니다.
여전히 한계가 있다는 시각도 분명 존재하지만, 느리지만 꾸준하게 혁신을 이뤄나가고 있는 컴퓨팅 기술에 대한 변화도 놓치지 않고 함께 지켜봐야할 것입니다.
