[밑바닥 부터 시작하는 비트코인] -3.타원곡선 암호
본격적인 타원곡선 암호 알고리즘과 이산로그 문제
Programming Bitcoin : 밑바닥부터 시작하는 비트코인
출처 : Programming Bitcoin by Jimmy Song(O'Reilly). Copyright 2019 Jummy Song, 978-1-492-03149-9
안녕하세요, 스크립토 5기 배준호입니다. 이번 챕터3부터는 본격적으로 티원곡선 암호 알고리즘에 대해서 살펴보게 됩니다.개인적으로는 이 부분이 조금 어려웠었는데요, 사실 차근차근 생각해 보면 또 크게 어렵지는 않습니다. 제가 자세한 증명, 구현 부분등은 책처럼 디테일 하게 다루지는 않으니, 만약 더 자세히 알고싶으시다면 "밑바닥 부터 시작하는 비트코인" 책을 직접 사셔서 살펴보는 것을 추천합니다.
Chapter 3-1. 타원곡선 암호
저번 시간에 살펴본 타원곡선은 실수'체'에서 정의되어 있었는데요, 이번에 다룰 타원곡선은 챕터1에서 살펴본 '유한체'에서 정의되어 있는게 주요한 점입니다. 그리고 이러한 곡선위의 점의 특성과 이산로그 문제의 특성을 통해서 개인키, 공개키 알고리즘을 살펴볼 것입니다.
1. 실수체에서 정의된 타원곡선
챕터2에서 다루었던 타원곡선은 당연히 무한히 많은 실수값을 갖습니다. 따라서 그래프를 그리면 무한히 많은 점들이 찍혀서 곡선 모양의 선의 모습을 가지고 있었습니다. 또한 실수는 챕터1에서 다루었던 체(Field)의 요건을 만족하기 때문에 타원곡선 함수의 변숫값으로 사용할 수 있었습니다. 원소의 개수가 무한하다는 것만 제외하면, 실수체는 유한체와 동일한 성질이 있습니다. 덧셈과 곱셈에 대해 닫혀있고(결과 역시 같은 체에 속하고), 덧셈에 대한 항등원과 역원이 존재하며, 곱셈에 대한 항등원과 역원 역시 존재하는 것입니다.
책에서 흥미롭게 생각하는 부분은 타원곡선 함수의 변수와 계수들이 어떤 체에서 정의되었는지와 상관없이 그 타원곡선에서 점 덧셈 성질이 성립하는 것, 즉 점 덧셈 방정식의 근이 어떤 체 소속인지와 무관하게 점 덧셈이 성립하는 것입니다. 이 부분은 타원곡선 함수의 특징인 것 같습니다. 그렇다면, 이제부터는 우리가 챕터1에서 다룬 유한체 기반으로 타원곡선 함수를 정의할 수 있고, 그러한 타원곡선 함수에서도 동일하게 점 덧셈의 성질을 그대로 이용할 수 있습니다. (물론 이러한 경우 모든 사칙연산은 유한체에서 재정의된 사칙연산을 기반으로 합니다.)
2. 유한체에서 정의된 타원곡선
유한체는 실수체와는 다르게 원소가 무한하지 않습니다. 따라서, 유한체에서 정의된 타원곡선은 실수체에서 정의된 타원곡선처럼 매끄러운 곡선 모양이 나오지 않을 것이라는 것 정도는 상상해 볼 수 있습니다. 우선, 우리가 사용하는 타원곡선 함수는 다음과 같습니다.
가령, 어떤 특정한 위수를 가진 F에 의해서 정의된 타원곡선은 다음과 같이 그려집니다.
출처 : https://ethresearch.kr/t/topic/165대충 4개의 그림처럼 불규칙한 점의 모습으로 그려집니다. 매끄러운 타원의 모습과는 많이 다릅니다. 다만, Y축의 중간값 정도를 지나는 수평축을 기준으로 대칭이며, 하나의 X값은 최대 2개의 Y값을 가지고 있습니다. 모양이 조금 이상하더라도, 크게 달라지는 것은 없습니다. 유한체에서 정의된 각종 연산이 그대로 점 덧셈 방정식에서 사용될 수 있기 때문입니다.
구현
1) 그냥 Point 객체에 필요한 파라미터, 그러니까 계수와 좌표를 챕터1에서 정의한 유한체의 원소로 정의해서 넘겨주면 됩니다.
1) Point class에서 사용되는 여러가지 연산들(+,-,*,/,**)은 실수의 사칙연산이 아닌 FieldElement에서 정의된 사칙연산으로 수행됩니다.
3. 유한체에서 정의된 타원곡선 위 두 점의 덧셈
챕터2에서 정의한 타원곡선 위 두 점의 '덧셈'은 주어진 두개의 점을 통해서 새로운 점을 찾는 과정이었습니다. 두 점을 연결하는 직선을 찾고, 그 직선이 타원곡선과 만나는 또 다른 점을 찾은 뒤, 그 점을 x축 대칭했었습니다. 직선의 방정식 역시 곧은 직선 모양이 나오지 않지만, 사용에는 큰 무리가 없습니다. 타원곡선 위 점 덧셈은 유한체이건 실수체이건 모든 체에서 성립하기 때문입니다. 따라서, 실수체에서 사용한 점 덧셈 공식들은 그대로 유한체에서 사용될 수 있습니다.
서로 다른 두 점인 경우였죠
같은 점인 경우이와같은 성질로부터 암호이론의 기본 알고리즘(cryptographic primitives)를 전개할 수 있습니다.
4. 타원곡선 위 점의 스칼라 곱셈
(170,142) + (170,142) 는 2ㆍ(170,142)로 표현될 수 있습니다. 또한, 점 덧셈에는 결합법칙이 성립하기 때문에 2ㆍ(170,142) + (170,142) = 3ㆍ(170,142)로 표현될 수 있습니다. 만약 결합법칙이 성립하지 않는다면, 불가능합니다. 이것이 바로 스칼라 곱셈입니다. 점 앞에는 얼마든지 스칼라 값을 곱할 수 있습니다. 스칼라 곱셈의 결과는 실제 계산하지 않고서는 그 값을 예측하는 것이 매우 어렵습니다.
밑바닥 부터 시작하는 비트코인, 91p위 그림은 223을 위수로 가지는 F에서 정의된 secp256k1 곡선 위의 점 (170,142)에서의 스칼라 곱셈 결과입니다. 점 옆에 표시된 숫자가 스칼라 값입니다. 아주 불규칙하게 점들이 찍힌 것을 볼 수 있습니다. 따라서, 스칼라 곱셈을 하는 것은 어려울 것이 없지만 그 반대의 계산, 즉 나눗셈은 아주 어려운 문제가 됩니다. 이를 이산로그 문제(discrete log problem)이라 하며, 타원곡선 암호 방법의 원리입니다.
이산로그 문제
잠시 책에서 다루고 있는 이산로그 문제를 짚고 넘어가겠습니다. 우리가 점과 점사이의 연산을 '덧셈'이라고 하였습니다. 하지만, 그 본질은 두 점을 통해서 새로운 점 하나를 찾아내는 과정이었습니다('덧셈'이라는 의미에서 자유롭게 생각해봅시다). 만약 점과 점 사이의 연산을 '곱셈'이라고 정의했다고 쳐봅시다. 어차피 새로운 점 하나를 찾아내는 과정이니까 덧셈이라 정의하든 곱셈이라 정의하든 본질은 같을 것입니다. 그러면 같은 점을 계속해서 '곱하는 것'(우리가 덧셈이라고 정의 했으면 계속해서 더하는 행위, 즉 스칼라 곱)은 '스칼라 거듭제곱'의 형태로 표현이 될 수 있습니다. 그렇다면
만약 점 덧셈이었다면 7 ㆍP = Q로 정의되었겠죠?이는 점 곱셈을 7 스칼라 거듭제곱 하였다고 볼 수 있습니다. 여기서 우리가 할 것은 이 스칼라 값을 찾는 것입니다. P와 Q가 정해졌을 때, 즉 점과 스칼라 거듭제곱의 결과가 주어졌을 때, 과연 지수를 찾을 수 있느냐는 것입니다.
여기서 아직까지 우리는 좌변을 직접 계산하는 알고리즘은 없습니다. 즉, 답을 로그의 답을 구하는 방법이 없다는 것입니다.
다시 이산로그 문제에서 돌아오겠습니다. 결론적으로는, 이 유한체로 정의된 타원곡선 위의 점에 스칼라 값을 곱하게 되어 결과가 나오게 되었을 때, 직접 해보지 않고서야 점과 결과값만 보고서는 그 지수를 추론하기가 너무 어렵다는 것입니다. 뭔가 암호 알고리즘의 느낌이 강하게 나지 않습니까?
무튼, 다시 스칼라 곱에 대한 이야기로 돌아와서, 스칼라 곱셈의 또다른 성질이 있는데, 바로 어떠한 점에 스칼라 값을 계속해서 증가시키면서 곱하면 무한원점 I(항등원)에 도달하는 것입니다. 따라서 우리는 특정한 점 G에 스칼라 값을 무한원점에 도달할 때 까지 계속해서 곱한다면
{G,2G,3G,4G,5G,.......nG(=0)}이라는 집합을 얻을 수 있고, 이는 수학적으로 군(Group)이라고 합니다. n 역시 유한한 특정 값이기 떄문에, 유한군이라고 합니다.
책의 예시와 군의 개념을 통해서 다시한번 이산로그 문제를 살펴보겠습니다. 223을 위수로 가지는 유한체에서 정의된 타원곡선 위의 점(47,71)에 1부터 22까지 스칼라 곱을 한 결과를 살펴본다면,
이런 결과가 나오게 됩니다. 딱 봐도 결과가 매우 불규칙적입니다. 이산 로그 문제는 다음과 같습니다. 가령, (47,71)에 어떤 스칼라 값을 곱해야 (154,73)이 나오게 되는지를 계산하는 것은 매우 어렵습니다. 지금이야 군의 원소가 많지 않기 때문에 전부 다 계산을 해 보면 모든 스칼라 값을 확인할 수 있지만, 군의 원소의 갯수가 매우 많아진다면, 사실상 스칼라 값을 알아내는 것은 불가능합니다.
4. 스칼라 곱셈으로 생성된 군의 성질
앞의 내용에서, 특정한 점 G에 스칼라 값을 계속해서 곱해서 생성해 낸 점의 집합을 유한군이라고 하였는데, 정확하게는 유한순환군이라고 부릅니다. 순환군이란 하나의 원소에 의해서 생성해 낸 군을 의미합니다. 그 하나의 원소는 생성점입니다.
군에서는 연산이 덧셈만 존재합니다. 그리고 그 덧셈은 닫혀있고, 역원과 항등원이 존재하며, 교환법칙과 결합법칙이 존재합니다.
5. 스칼라 곱셉 구현
점 P에 스칼라가 곱셈을 한다면 7*P와 같은 형태로 나타날 것입니다. 하지만 이는 int형과 Point형의 연산이기 때문에 그러한 연산을 새로 오버라이딩 할 필요가 있습니다. 파이썬에서는 __rmul__메서드를 제공합니다. __rmul__메서드는 right multiply라는 의미로, 연산자 오른쪽에 있는 객체의 클래스에서 정의한 메서드로 연산을 수행하는 것입니다. 지금의 경우, 연산의 대상들이 서로 다른 데이터 타입이기 때문에 __rmul__메서드를 사용할 수 있는 것입니다.
가장 간단한 방법은 스칼라값 만큼 계속해서 점 덧셈을 시켜주면 되는 것입니다. 하지만, 그러한 경우 만약 스칼라 값이 매우 크다면 실행시간이 매우매우 길어질 것입니다. 가령, 스칼라 값이 1조라면 1조번 같은 점 더하기 연산을 해야 합니다. 책에서는 이진수 전개방식을 활용해서 logn번의 루프(밑=2)로 끝냅니다. 1조는 40번의 루프 계산만에 끝나게 됩니다. 이 방법은 비트 연산을 활용하는 방법입니다.
코드분석
1) coefficeint는 스칼라값을 의미합니다.
2) current는 시작하는 점으로 초기화됩니다.
3) result는 무한원점, 0에 해당하도록 초기화됩니다.
4) while 루프에서는 스칼라값을 이진수로 표현했을 때, LSB(맨 오른쪽 비트)가 1인지 확인하고 1이면 result에 더합니다.
5) 만약 LSB가 1이 아니라면 result에 더하지 않습니다.
6) 매 루프마다 result에 더해질 값인 current는 중첩됩니다.
7) 루프 마지막에는 right shift를 통해서 LSB를 밀어냅니다. (1을 탈락시킵니다 or 2로 나눕니다)
스칼라 값을 직접 이진수로 써보고 한번 손으로 계산을 해보면 이해할 수 있습니다.
일단 여기까지를 타원곡선 암호-1로 정리하겠습니다. 이제 지금까지 배운 것을 토대로 비트코인에서의 공개키 암호와 서명생성,서명 검증을 직접 구현하면 됩니다. 이 뒷부분은 약간 수식을 쓸게 있는데 브런치에서 수식 삽입을 지원을 안해주니 쓰기가 너무 귀찮 힘드네요.. 다음편은 빠르게 돌아오겠습니다.
