밑바닥부터 시작하는 비트코인 - 1장 유한체
본 게시글에서는 저서 ‘밑바닥부터 시작하는 비트코인’의 Python으로 작성된 예제 코드를 Go로 컨버팅 하여 작성하였습니다.
전체 코드
❓ 유한체를 이해해야 하는 이유
비트코인의 핵심인 전자서명과 서명 검증 알고리즘을 이해하기 위해 필요한 타원곡선 암호를 파악하기 위해
유한체의 정의
- a와 b가 집합에 속해 있으면, a+b와 a*b도 집합 안에 있다 (덧셈과 곱셈에 닫혀있는 집합)
- 집합에 0으로 표기하는 원소가 존재하고 집합 내 다른 원소 a와 + 연산 결과는 a다. 즉 a + 0 = a (덧셈의 항등원 존재)
- 집합에 1로 표기하는 원소가 존재하고 집합 내 다른 원소 a와 * 연산 결과는 a다. 즉 a * 1 = a (곱셈의 항등원 존재)
- 집합의 원소 a와 + 연산 결과가 0이 되게 하는 원소 b가 역시 집합에 속해 있고 이러한 b를 -a로 표기한다 (덧셈에 대한 역원 존재)
- 0이 아닌 집합의 원소 a에 대해 a * b = 1이 되게 하는 원소 b가 역시 집합에 속해 있고 이러한 b를 a-1로 표기한다 (곱셈에 대한 역원 존재)
유한체의 집합 크기를 표현하는 어떤 값 p를 집합의 **위수(order)**라고 합니다.
유한집합 정의하기
집합의 위수가 p이면 집합의 원소는 0, 1, 2, … p-1로 쓸 수 있으며 다음과 같이 표기합니다.
Fp = { 0, 1, 2, … p-1 }
유한체의 위수(p)는 항상 가장 큰 숫자 원소(p-1)보다 하나가 더 많습니다. 또한 유한체는 반드시 소수(prime)이거나 소수의 거듭제곱을 위수로 가져야 합니다.
Go로 유한체 코딩하기
// 유한체의 원소를 나타내는 구조체
type FieldElement struct {
num int
prime int
}
// 유한체의 원소를 생성하는 함수
func New(num, prime int) (*FieldElement, error) {
if num >= prime || num < 0 {
return nil, fmt.Errorf("num %d not in field range 0 to %d", num, prime-1)
}
return &FieldElement{num, prime}, nil
}
// 유한체의 원소를 문자열로 표현하는 함수 (Stringer 인터페이스 구현)
func (f FieldElement) String() string {
return fmt.Sprintf("FieldElement_%d(%d)", f.prime, f.num)
}
// 유한체의 원소가 같은 유한체에 속하고 같은 값을 가지는지 확인하는 함수
func (f FieldElement) Equals(other FieldElement) bool {
return f.num == other.num && f.prime == other.prime
}Python 예제와의 차이점
- 구조체를 사용했습니다.
- 생성자 함수를 추가했습니다.
- 연산자 오버로딩이 불가능한 대신 구조체의 메서드로 기능을 구현했습니다.
나머지 연산
유한체의 정의에 따르면 유한체는 덧셈, 곱셈, 뺄셈(덧셈의 역원), 나눗셈(곱셈의 역원)에 대해 집합이 닫혀 있어야 하는데, 어떻게 한정된 범위의 값을 사용해서 유한체를 구현할 수 있을까요?
정답은 나머지 연산(Modulo Arithmatic)을 사용하는 것입니다.
아무리 큰 수라도 나머지 연산을 적용하면 비교적 작은 범위의 수로 변환됩니다. 예를 들어, 12로 나머지 연산을 실행하는 경우에는 아무리 큰 수라도 0에서 11 사이의 수가 될 것입니다. 마치 아무리 시간이 흐르더라도 시곗바늘은 0부터 11까지의 수를 가리키는 것을 계속 반복하는 것과 같죠.
➕➖ 유한체 덧셈과 뺄셈
덧셈
유한체에서 임의의 수 2개를 꺼내서 더하고 그 수를 위수로 나눈 나머지를 구합니다.
a + b = (a + b) % p
덧셈의 역원
유한체에서 꺼낸 임의의 수 a와 더한 뒤 그 수를 위수로 나눴을 때 나머지가 0이 되는 수 -a를 구합니다.
-a = (-a) % p
뺄셈
유한체에서 임의의 수 2개를 꺼내서 빼고 그 수를 위수로 나눈 나머지를 구합니다.
a - b = (a - b) % p
Go로 유한체 덧셈과 뺄셈 코딩하기
// 유한체의 원소를 더하는 함수 (더한 결과는 같은 유한체에 속함)
func (f FieldElement) Add(other FieldElement) (*FieldElement, error) {
if f.prime != other.prime {
return nil, fmt.Errorf("cannot add two numbers in different Fields %d, %d", f.prime, other.prime)
}
num := (f.num + other.num) % f.prime
return New(num, f.prime)
}
// 유한체의 원소를 빼는 함수 (뺀 결과는 같은 유한체에 속함)
func (f FieldElement) Sub(other FieldElement) (*FieldElement, error) {
if f.prime != other.prime {
return nil, fmt.Errorf("cannot add two numbers in different Fields %d, %d", f.prime, other.prime)
}
num := (f.num - other.num) % f.prime
// 음수일 경우 prime을 더해줌
if num < 0 {
num += f.prime
}
return New(num, f.prime)
}Python 예제와의 차이점
- 연산자 오버로딩이 불가능한 대신 구조체의 메서드로 기능을 구현했습니다.
- 나머지 연산의 결과가 양수로 변환되지 않으므로 원소의 값이 음수인 경우, 위수를 더해줬습니다.
✖ 유한체의 곱셈과 거듭제곱
곱셈
곱셈은 ‘여러 번 더하기’와 마찬가지 이므로 유한체와 임의의 수의 곱셈의 결과는 유한체에 속합니다.
a * b = (a * b) % p
거듭제곱
유한체의 임의의 수를 꺼내서 거듭제곱하고 그 수를 위수로 나눈 나머지를 구합니다.
ab = ab % p
왜 위수가 소수인 유한체가 유용한가?
일반적으로 위수가 소수인 유한체에 0이 아닌 임의의 원소 k로 전체 집합을 곱하면 그 결과는 다시 원래 집합이 됩니다. F5 = { 0, 1, 2, 3, 4 }에 4를 곱한 결과는 { 0, 4, 3, 2, 1 }로 순서만 바뀌었을 뿐 원래 집합과 동일한 것을 확인할 수 있습니다.
그러나 위수가 합성수인 경우에는 위수의 약수로 전체 집합을 곱하게 되면 곱하는 수에 따라 집합이 달라집니다. 예를 들어, F4 = { 0, 1, 2, 3 }이 있고 4의 약수인 2를 전체 집합에 곱하면 그 결과는 { 0, 2 }가 됩니다. 집합의 원소 개수가 적어지는 것을 확인할 수 있습니다.
Go로 유한체 곱셈 코딩하기
// 유한체의 원소를 곱하는 함수 (곱한 결과는 같은 유한체에 속함)
func (f FieldElement) Mul(other FieldElement) (*FieldElement, error) {
if f.prime != other.prime {
return nil, fmt.Errorf("cannot add two numbers in different Fields %d, %d", f.prime, other.prime)
}
num := (f.num * other.num) % f.prime
return New(num, f.prime)
}Go로 유한체 거듭제곱 코딩하기
// 유한체의 원소를 거듭제곱하는 함수 (거듭제곱한 결과는 같은 유한체에 속함)
func (f FieldElement) Pow(exp int) (*FieldElement, error) {
num := pow(f.num, exp, f.prime) % f.prime
return New(num, f.prime)
}
// 거듭제곱을 구하는 함수 (분할정복을 이용)
func pow(num, exp, mod int) int {
if exp == 0 {
return 1
}
if exp == 1 {
return num
}
if exp%2 == 0 {
temp := pow(num, exp/2, mod)
return (temp * temp) % mod
}
temp := pow(num, (exp-1)/2, mod)
return (temp * temp * num) % mod
}Python 예제와의 차이점
- 분할정복을 이용하여 중간중간 나머지 연산을 적용할 수 있도록 별도의 pow 함수를 정의했습니다.
➗ 나머지 연산
유한체의 나눗셈은 일반대수의 나눗셈과 마찬가지로 곱셈의 역연산을 적용할 수 있습니다. 예를 들어, F19에서 3 * 7 = 21 % 19 = 2로부터 2 / 7 = 3이라는 등식이 성립합니다. 어떤 유한체 원소를 0이 아닌 다른 원소로 나눈 결과는 역시 유한체에 소속된 원소이므로 닫혀 있는 나눗셈이 가능해 집니다.
그런데 3 * 7 = 2라는 것을 모른 채 2 / 7 = 3이라는 것을 어떻게 알 수 있을까요?
페르마의 소정리: n(p-1) % p = 1
페르마의 소정리에서 p는 소수입니다. 우리는 소수를 위수로 가지는 유한체를 다루고 있으므로 이 정리를 사용할 수 있습니다.
나눗셈은 곱셈의 역연산이므로 아래와 같이 표현할 수 있습니다.
a / b = a * (1 / b) = a * b-1
여기서 b-1을 구하면 나눗셈 문제가 곱셈 문제로 바뀝니다. b-1은 페르마의 소정리를 활용하여 구할 수 있습니다.
페르마의 소정리에 따르면 b(p-1) = 1
b-1 = b-1 * 1 이므로 페르마의 정리를 적용하면 b-1 * b(p-1) = b(p-2)
따라서 b-1 = b(p-2)
Go로 유한체 나눗셈 코딩하기
// 유한체의 원소를 나누는 함수 (나눈 결과는 같은 유한체에 속함)
func (f FieldElement) Div(other FieldElement) (*FieldElement, error) {
if f.prime != other.prime {
return nil, fmt.Errorf("cannot add two numbers in different Fields %d, %d", f.prime, other.prime)
}
// 페르마의 소정리를 이용하여 나눗셈을 곱셈으로 변환
num := (f.num * pow(other.num, f.prime-2, f.prime)) % f.prime
return New(num, f.prime)
}✖ 거듭제곱 메서드 수정
거듭제곱의 지수가 음수인 경우에도 페르마의 소정리를 활용하여 값을 구할 수 있습니다. p가 소수일 때 a(p-1)은 항상 1이 되므로 지수가 p-1보다 커지거나 -(p-1)보다 작아지게 되면 지수에 나머지 연산을 적용하여 불필요한 연산을 줄일 수 있습니다.
// 유한체의 원소를 거듭제곱하는 함수 (거듭제곱한 결과는 같은 유한체에 속함)
func (f FieldElement) Pow(exp int) (*FieldElement, error) {
exp %= (f.prime - 1)
// 지수가 음수일 경우 양수로 변환
if exp < 0 {
exp += (f.prime - 1)
}
num := pow(f.num, exp, f.prime) % f.prime
return New(num, f.prime)
}테스트 결과
$ go test -v -cover .
=== RUN Test_FieldElement_New
--- PASS: Test_FieldElement_New (0.00s)
=== RUN Test_FieldElement_String
--- PASS: Test_FieldElement_String (0.00s)
=== RUN Test_FieldElement_Equals
--- PASS: Test_FieldElement_Equals (0.00s)
=== RUN Test_FieldElement_Add
--- PASS: Test_FieldElement_Add (0.00s)
=== RUN Test_FieldElement_Sub
--- PASS: Test_FieldElement_Sub (0.00s)
=== RUN Test_FieldElement_Mul
--- PASS: Test_FieldElement_Mul (0.00s)
=== RUN Test_FieldElement_Pow
--- PASS: Test_FieldElement_Pow (0.00s)
=== RUN Test_FieldElement_Div
--- PASS: Test_FieldElement_Div (0.00s)
=== RUN Test_main
--- PASS: Test_main (0.00s)
PASS
coverage: 100.0% of statements
ok finite-field 0.002s coverage: 100.0% of statements참고자료
글에서 수정이 필요한 부분이나 설명이 부족한 부분이 있다면 댓글로 남겨주세요!
