Chapter 3. 타원곡선 암호

아래 글에서는 “밑바닥부터 시작하는 비트코인(Programming Bitcoin) -한빛미디어(2019)”의 Chapter 3. 타원곡선 암호에 대한 내용을 다룬다.
타원곡선 암호의 동작 원리에 초점을 맞추었으며 유한체 및 타원곡선 함수에 대해 이해하고 있다는 전제하에 글을 작성하였다.

Programming Bitcoin Series

Chapter 1. 유한체
Chapter 2. 타원곡선
Chapter 3. 타원곡선 암호
Chapter 4. 직렬화
Chapter 5. 트랜잭션
Chapter 6. 스크립트
Chapter 7. 트랜잭션 검증과 생성
Chapter 8. p2sh 스크립트
Chapter 9. 블록
Chapter 10. 네트워킹
Chapter 11. 단순 지급 검증
Chapter 12. 블룸 필터
Chapter 13. 세그윗

Overview

비트코인은 특정 중앙 주체가 각 사용자의 신원 정보를 관리하지 않는다. 모든 데이터는 공개되어 있으며, 누구든지 데이터를 확인할 수 있다.

이렇게 공개된 블록체인 환경에서 식별 가능한 신원을 정의하고, 신원을 불특정 다수에게 증명할 방법이 필요하다. 이러한 메커니즘이 없다면 비트코인의 소유 개념이 사라지고 지금과 같은 상품 화폐로서의 가치가 형성되지 못할 것이다.

또한 비트코인을 누군가에게 전달하거나 받는 경우, 이 행위 정보가 (i.e. 트랜잭션) 중간에 위, 변조 되었는지도 확인 가능해야 한다. 인터넷 환경 특성상 전파 과정에서 위, 변조될 가능성이 있기 때문이다. 정리하면 다음을 만족하는 메커니즘이 필요하다.

• 식별 가능한 신원을 정의할 수 있어야 한다.
• 신원 증명에 필요한 데이터 (PIN 번호, 비밀번호 등) 를 외부에 노출하지 않고 신원을 증명할 수 있어야 한다.
• 불특정 다수에게 증명 가능해야 한다. (누구든 신원을 검증할 수 있어야 한다)
• 위, 변조 여부를 파악할 수 있어야 한다.

위의 조건을 만족하는 기술이 공개키 서명 방식이며, 비트코인은 이를 활용하여 신원을 식별, 증명하고 비트코인을 안전하게 교환한다. 비트코인의 보안에 핵심적인 역할을 하는 공개키 서명에 대해 알아보자.

공개키 서명

공개키 서명은 서로 다른 두 개의 키의 수학적 관계를 이용한 디지털 서명 방식이다.

공개키 서명에는 공개키와 이에 대응하는 개인키가 존재하며 이 둘 간에는 수학적 관계가 있다 (자세한건 추후에 설명). 공개키는 이름 그대로 외부에 공개되는 키이며 공개키를 통해 신원을 식별한다. 일종의 아이디라고 볼 수 있다. 개인키는 신원을 증명하는 데 사용되는 주요 데이터이다. 개인키를 소유한 사람이 곧 대응하는 공개키의 주인이며 그러므로 외부에 노출 되어선 안된다.

공개키 서명은 현실의 지불 수단 중 하나인 수표와의 비교를 통해 쉽게 이해할 수 있다. 수표 발행인이 지급인 (은행)과 금액을 수표에 작성한 후 서명하고, 서명된 수표를 은행에서 검증하여 수령인에게 정산해 주었듯이, 디지털 상에서 공개키로 표현된 서명자는 서명 대상 데이터 (i.e. 트랜잭션)에 개인키를 이용하여 전자 서명 데이터를 생성하고, 디지털 상의 검증인은 생성된 전자 서명을 통해 아래의 두 가지를 검증한다.

• 전자서명이 서명자의 공개키에 대응하는 개인키로 서명 되었는지 검증 (수표 발행인의 서명이 맞는가?)
• 서명에 사용된 데이터의 위, 변조 여부 검증 (수표 발행인이 작성한 금액, 서명이 위조되지 않았는가?)

그리고 검증 과정을 통과하고 나면 서명자가 요청한 동작을 처리한다. 현실의 서명 행위를 디지털 상에서 구현했다고 볼 수 있다.

비트코인의 개인키, 주소가 바로 공개키 암호의 개인키, 공개키이다. 비트코인의 주소는 공개키로부터 생성되며, 주소에 대응하는 개인키가 존재한다. 비트코인에서 특정 주소를 소유하고 있다는 것은 곧 이에 대응하는 개인키를 소유하고 있음을 뜻하며, 주소에 해당하는 개인키를 가진 사용자는 해당 주소의 비트코인을 사용할 수 있는 권한을 가진다.

비트코인에서 공개키 서명이 어떻게 활용되는지는 예시를 통해 쉽게 이해할 수 있다. 철수의 주소에 5비트코인이 예치되어 있다고 가정했을 때 1비트코인을 영희에게 전달하는 과정을 통해 공개키 서명이 어떻게 사용되는지 살펴보자.

우선 철수는 자신의 주소에 있는 1 비트코인을 영희에게 전달한다는 내용이 기록된 데이터를 생성할 것이다. 이를 비트코인에서는 트랜잭션이라 부른다.

여기까지의 정보는 철수가 아닌 누구든 생성할 수 있는 데이터다. 해당 데이터가 유효하려면 철수가 주소의 소유주임을 증명 해야 한다. 즉 주소에 해당하는 개인키를 소유하고 있음을 증명하는 정보가 필요하다.

이와 동시에 철수가 생성한 트랜잭션이 네트워크 전파 과정에서 위, 변조되지 않았음을 보장 해야 한다. 누군가 네트워크상에서 철수가 생성한 트랜잭션을 위조하더라도 이를 검증하여 걸러낼 수 있어야 한다는 의미다.

정리하면 트랜잭션이 주소의 실소유주로부터 생성되었음을 보장하는 일종의 서명 데이터가 있어야 비로소 유효한 트랜잭션이 된다.

여기서 공개키 서명이 활용된다. 철수는 개인키를 노출하여 신원을 증명하는 대신 공개키 서명 방식을 활용, 전자서명을 생성하여 신원을 증명한다.

전자서명이 포함된 트랜잭션이 네트워크에 전파되면 각 검증인 (비트코인 노드 운영자) 은 전자서명을 통해 철수가 개인키를 소유하고 있는지, 트랜잭션 전파 과정에서 변조가 일어나지 않았는지 확인하고, 유효한 경우 트랜잭션이 블록에 포함되며 최종적으로 철수의 1비트가 영희에게 전달된다.

이 과정에서 검증자는 전자서명을 통해 개인키를 알아낼 수 없으며, 누구에게나 같은 규칙으로 전자 서명 검증이 가능하므로 불특정 노드로부터 안전하게 신원을 증명할 수 있다.

또한 전자 서명에 트랜잭션 데이터가 포함되어 누군가가 철수의 트랜잭션을 위, 변조하면 전자서명은 유효성을 잃게 된다. 그러므로 철수는 트랜잭션의 전송과정에서 발생하는 위, 변조로 인해 자신의 의도와 다르게 처리되는 것을 우려할 필요가 없다.

여기까지가 기본적인 비트코인에서의 공개키 서명 활용에 대한 개괄이다. 다음은 전자서명 생성, 검증 로직의 구체적인 원리를 설명하고자 한다.

비트코인은 공개키 암호 중 하나인 타원곡선 디지털 서명 알고리즘 (Elliptic curve Digital Signature Algorithm) 를 사용한다. ECDSA는 공개키 암호 알고리즘중 하나로 RSA/DSA와 같은 공개키 암호보다 짧은 키 길이와 빠른 연산속도를 가지면서 같은 수준의 보안 강도를 제공하는 암호 알고리즘이다.

비트코인에서 사용되는 타원곡선 암호의 원리를 구체적으로 이해해 보자. 이를 이해하기 위해선 유한체와 타원곡선 방정식에 대한 이해가 필수이니 앞선 챕터를 선행하여 이해하기를 추천한다.

Deep Dive Into ECDSA

타원곡선 암호에 사용되는 수학 도구

1. 유한체와 타원 곡선 방정식

우선 ECDSA에서 사용되는 핵심 도구에 대해 이해할 필요가 있다. 도구의 성질을 제대로 이해하고 나면 전자 서명 생성, 검증 원리를 이해하는 데 큰 어려움이 없을 것이다.

꽤 긴 여정이 될 수 있으니 방향을 잃지 않기 위해 최종적으로 만들고자 하는 도구가 무엇인지 간단히 언급하고자 한다. 전자서명을 생성, 검증 알고리즘에 필요한 최종 도구는 유한 순환 군이다.

유한 순환 군은 유한체와 타원 곡선 방정식을 통해 도출되므로 이 두 가지를 우선 이해할 필요가 있다.

유한체와 타원 곡선 방정식에 관한 내용은 앞선 혜수님의 부분에서 구체적으로 설명했으므로 여기선 간단히 설명하고 넘어가겠다.

유한체를 정의하기 위해서 덧셈(+), 뺄셈(-), 곱셈(*), 나눗셈(/) 연산을 나머지 연산자를 활용하여 재정의했다.

그리고 실수에서의 타원 곡선 방정식을 이해하고, 방정식 위의 두 점의 덧셈 연산을 정의했다. 이 과정에서 무한 원점(point at infinity)에 대한 개념이 나왔다.

곡선위 임의의 두 점을 더했을 때 그 결과 또한 곡선 위에 있고 (닫혀 있고) 교환, 결합 법칙이 성립하며 항등원 (무한원점), 역원이 존재함을 증명했으므로 덧셈 연산과 실수체 위의 점의 집합은 아벨 군을 이룬다고 볼 수 있다.

이제 유한체와 타원 곡선 방정식을 합쳐 보자.

유한체는 실수와 같은 체 (field)에 속하므로 실수 체에서 정의된 다양한 성질이나 정리들을 그대로 적용할 수 있다. 즉 실수 체에서 정의한 타원 곡선 방정식은 유한체 위에서도 유효하다.

추상대수학에서 군 (group), 환 (ring), 체 (field)를 정의하는 이유도 여기에 있다. 특정 집합이 체에 속한다는 것을 증명하면, 해당 집합은 체 (field)에 정의된 다양한 수식을 별도의 증명과정 없이 적용할 수 있다.

유한체 위의 타원 곡선 방정식은 실수체의 타원 곡선 방정식과 달리 다소 불규칙한 모습을 보인다.

타원 곡선 방정식이 유한체에서도 유효한 것과 같은 맥락으로 방정식 위의 두 점의 덧셈 연산 또한 유효하다.

2. 타원곡선 위 점의 스칼라 곱셈

점의 스칼라 곱을 이해하면 유한 순환 군을 이해하는 데 필요한 초석을 모두 마련하게 된다.

점의 덧셈 연산을 정의했으므로, 같은 두 점의 덧셈 연산도 가능하다. 그리고 점 덧셈 연산은 결합법칙을 만족하기 때문에 다음과 같이 표현할 수 있다.

(172, 32) + (172, 32) = 2 * (172, 32)

2 * (172, 32) + (172, 32) = 3 * (172, 32)

이런 식으로 얼마든지 계속 더할 수 있으며 이를 스칼라 곱셈 (scalar multiplication)이라고 한다. 점 덧셈에서 결합법칙이 성립하므로 점에 스칼라값을 곱할 수 있다.

아래 그림은 특정 점에 대해서 스칼라 곱셈을 계속해서 수행했을 때의 결과다. 그 결과가 매우 불규칙적이라는 것을 알 수 있다. 점 덧셈이 비선형적이며 계산이 어렵기 때문이다.

특정 점 G에 스칼라 n을 곱하여 나온 결과 점을 P이라고 가정 (i.e. n * G = P) 했을 때 n 값과 G를 알고 있다면 P를 구할 수 있지만 G 값과 P값이 주어졌을 때 n을 구하는 것은 매우 어렵다.

G, P를 알 때 n을 구할 수 있으려면 n = P / G를 구할 수 있어야 하는데, 여기서 문제는 점의 나눗셈 연산을 정의하지 못했다. 그러므로 P, G를 알고 있다고 해서 n을 구할 수 없다. (만약 나눗셈을 정의할 수 있다면 모든 개인키는 공개될 것이다)

이를 이산 로그 문제 (discrete log problem) 라고도 표현하며 이 성질이 타원 곡선 암호에서 핵심적인 수학적 기반이 된다.

3. 유한 순환군

마지막으로 ECDSA의 핵심 도구인 유한 순환 군에 대해 설명한다.

스칼라 곱셈을 계속해서 진행하다 보면 결국 항등원, 즉 무한원점이 나오는 지점이 생기며 특정 점 G에 무한원점이 나올 때까지 스칼라 곱을 한 집합을 유한 순환 군이라 한다.

{1 * G, 2 * G, 3 * G…. n * G} (n * G = point at infinity)

유한 순환 군은 추상 대수학에서 군 종류 중 하나로 아벨 군 (abelian group)이며 특정 원소로 모든 원소를 표현할 수 있는 군을 의미한다. 이때 생성자의 역할을 하는 원소를 Generator라 부른다.

유한체의 타원 곡선 위의 점의 스칼라 곱으로 만들어진 유한 순환 군은 다음과 같은 특징을 가진다.

• 아벨 군 (abelian group)이므로 덧셈 연산에 대해 집합이 닫혀있고 교환, 결합 법칙이 성립하며 항등원, 역원이 존재한다.
• 각 요소는 G에 스칼라 n을 곱한 결과이며, 요소와 G 값으로부터 n을 파악하기가 어렵다. (이산 로그 문제)

이러한 유한순환 군의 수학적 특성을 활용하여 ECDSA를 구현할 수 있다.

ECDSA — 전자 서명 생성, 검증 알고리즘

ECDSA 에서는 앞서 정의한 유환 순환 군을 활용한다. 유한 순환 군의 각 요소는 scalar * Generator (a.k.a. G) 을 곱한 결과임을 알 수 있을 것이다. 여기서 개인키와 공개키의 관계가 정의된다.

바로 scalar 값이 개인키이며 개인키에 G를 곱한 결과가 공개키이다. 앞서 설명했듯이 개인키를 통해 공개키를 생성하는 작업은 쉽지만 그 반대는 어렵다. 그리고 이 관계에서 발생하는 이산 로그 문제를 활용하여 전자 서명을 생성하고, 검증하는 알고리즘을 구현할 수 있다.

1. 전자 서명 생성, 검증 알고리즘

전자 서명의 생성 및 검증 알고리즘 원리를 설명하고자 한다. 유한 순환 군의 특성과 간단한 방정식 계산법만 알고 있다면 원리를 이해하는 데 큰 무리가 없다.

앞서 설명했듯이 개인키와 공개키는 유한 순환 군의 각 요소다. 이를 식으로 정의하면 다음과 같다.

P = e * G

여기서 G는 제너레이터이며, e는 개인키, P는 공개키이다.

전자 서명 알고리즘이 만족해야 하는 조건을 다시 한 번 정리해 보자.

• 서명자가 소유한 공개키 P에 대응하는 개인키 e 를 검증인에게 노출하지 않고 소유 증명할 수 있어야 한다
• 불특정 다수의 검증인으로부터 항상 동일한 방법으로 증명 가능해야 한다
• 증명 데이터는 서명하고자 하는 데이터 (여기서는 트랜잭션)에 대한 무결성을 보장해야 한다. 즉 서명 대상의 데이터 (트랜잭션) 가 변경되는 경우 전자서명 자체가 무효화 되어야 한다.

위 조건을 만족하는 전자 서명 생성, 검증 알고리즘을 만들어 보자.

서명자는 전자서명을 생성하기 위해 임의의 값 k와 이에 대응하는 R (random)을 정의한다. 수식은 다음과 같다.

R = k * G

그리고 다음과 같은 방정식을 정의한다. 아래 방정식은 G, P, R이 주어졌을 때 u, v를 알아내는 문제이므로 여전히 이산 로그 문제를 가지고 있다. 다른 점은 미지수가 2개이므로 만족하는 해가 다양하다는 점이다.

u * G + v * P = k * G = R

여기서 방정식을 만족하는 u, v를 구하는 방법은 두 가지가 있다. 첫 번째는 R 값이 나올 때까지 u, v 값을 무차별 대입하는 것이며, 두 번째는 P에 해당하는 개인키 e를 알고 있다는 전제하에 위 수식을 풀어서 만족하는 u, v를 구하는 방법이다.

무차별 대입은 일반적인 풀이방법이 아니므로 두 번째 방법에 대해서 구체적으로 알아보자.

우선 위 방정식을 P에 관하여 정리하면 다음과 같다.

-> u * G + v * P = R

-> u * G + v * P = R = k * G

-> P = ( (k - u) / v ) * G

이때 e를 안다고 가정하여 P를 e * G로 치환하고 e에 관하여 정리하면 다음과 같다.

e = (k - u) / v

여기서 서명자가 e, 즉 개인키를 알고 있다면 위 방정식을 만족하는 u와 v를 결정할 수 있다. 반면 알지 못한다면 u, v를 알아내는 방법은 첫 번째 방법인 무차별 대입뿐이며 이는 유한체의 위수가 크면 클수록 수많은 값을 대입해야 하므로 불가능에 가깝다. 그러므로 서명자가 적절한 u, v를 결정하여 제시할 수 있다는 것은 e 값을 알고 있다고 볼 수 있다. 이러한 방식으로 서명자는 개인키를 공개하지 않고 개인키를 증명할 수 있다.

서명자가 e를 알고 있다는 가정하에 서명자는 u, v를 다음과 같이 설정한다.

u = r/s

v = z/s

s = (z + r * e) / k

여기서 r은 R의 x 좌표다. 그리고 z는 일종의 서명 대상 데이터이다. 그리고 z는 일종의 서명 대상 데이터이다. 비트코인으로 따지면 트랜잭션 데이터라 볼 수 있다(정확히는 트랜잭션 데이터를 직렬화 한 후 해시 연산한 값).

그리고 s 값은 r / s * G + z / s * e * G = k * G를 s에 관해 정리했을 때 나오는 값이다. r과 z값을 수식에 포함한 이유는 나중에 설명하겠다.

위와 같이 u, v를 설정하면 방정식은 최종적으로 다음과 같다.

r/s * G + z/s * P = R(x=r)

여기서 r, s 가 바로 전자 서명 데이터다. 서명자는 전자 서명 데이터로 r, s 를 검증자에게 제시한다.

이때 각 검증자는 위 방정식에 서명자가 제시한 r, s 와 트랜잭션 데이터 z, P 값을 대입해 보고 등식이 성립하면 전자서명이 유효하다고 판단한다.

전자서명이 유효하다는 의미는 검증인이 전자서명을 통해 서명자가 공개키 P 에 해당하는 비밀키 e 를 알고 있다는 것을 확인했다는 의미다. 서명자가 수식을 만족하는 u, v를 제시 하였으며, 이는 위 전제에 따라 서명자가 e 값을 알고 있다고 볼 수 있기 때문이다.

여기서 위 수식에 r 과 z 값을 포함하는 이유는 각 다음과 같다.

우선 r의 경우 서명자가 k와 e 값을 알고 있음을 증명하기 위해서 포함된다. 해당 값이 수식에 포함되지 않으면 누구나 등식을 만족하는 r, s를 만들 수 있다. 비유하자면 궁수가 자신의 실력을 입증할 때 특정 목표를 미리 선정하고 목표물에 활을 맞춤으로써 증명하는 것이 아닌, 아무 곳에 활을 쏘고 활을 맞은 대상이 원래 목표물이었다고 말하는 것과 같다.

z는 서명 대상 데이터 (트랜잭션)의 위, 변조를 예방하는 역할을 한다. 트랜잭션이 전송되는 과정에 누군가가 트랜잭션의 값을 변경하면 결과적으로 z값이 변경되고, 변경된 z값으로 인해서 전자서명 검증에 실패하게 된다. 트랜잭션의 위, 변조를 확인하기 위해 각 검증인은 전달받은 트랜잭션을 통해 직접 z 값을 생성하여 전자 서명 검증에 사용한다.

이러한 전자 서명 생성 및 검증 알고리즘은 앞서 제시했던 조건을 모두 만족한다.

• 서명자가 제공하는 데이터를 통해 e값을 유추하는 것은 불가능에 가깝다. 즉 서명자는 e 값을 노출하지 않고 e 소유 증명을 할 수 있다.
• 누구든 검증 절차를 알고 있으면 같은 방식으로 전자서명의 유효성을 검증할 수 있다. 즉 불특정 다수에게 증명 가능한 방식이다.
• 트랜잭션 데이터(z)를 서명 알고리즘에 포함하여 트랜잭션 데이터의 무결성을 보장한다. 트랜잭션 데이터가 전송과정에서 위, 변조되는 경우 전자 서명의 유효성이 사라진다.

여기까지 이해했다면 k 값의 중요성 또한 알 수 있을 것이다. k 값이 노출되면 k 값을 이용하여 e 값을 도출할 수 있다. 즉 임의의 k 값 또한 절대 외부에 공개되어서는 안된다.

또한 동일한 k 값으로 두 개의 서명을 생성하게 되면 결론적으로 개인키를 노출하게 된다. 그렇기 때문에 서명에서 동일한 k 이 사용되어서도 안된다. 이러한 문제를 인지하고 비트코인에서는 k 값을 RFC6797을 이용하여 생성한다.

RFC6797은 결정론적인 전자 서명 생성 방법을 정의한다. 결정론적 특성으로 인해 항상 특정 개인키가 생성한 트랜잭션에 대한 전자서명은 항상 동일한 k값을 도출하며, 이는 트랜잭션 가변성 문제를 보완하기도 한다.