블록체인 암호학 #1 : 확장된 유클리드 알고리즘

Author : 최원혁

Intro

---

블록체인의 보안성, 합의 알고리즘 디지털 서명, 지갑 등 블록체인의 기본적인 개념과 기능은 전부 암호학으로 구현되어 있다. 블록체인과 암호학은 아주 밀접한 관련이 있는 두 분야이다. 개발자들이 암호학의 원리를 잘 이해하고 실수 없이 코딩할 수 있도록 도움을 주기 위해 암호학에 대한 이해가 필요하다고 생각한다. 논문의 영역과 개발자에게 필요한 지식의 영역 그 경계선까지, 즉 어느정도 심도 깊게 내용을 다룰 예정이다.

 

기본 다지기

---

암호학을 위해 유클리드 알고리즘을 처음으로 배우는 이유는 다음 시리즈에 다룰 모듈러 연산을 이해하기 위함이다. 특히 모듈러 연산은 이더리움 블록체인에서 사용하는 타워 곡선 암호학(Elliptic Curve Cryptography:ECC)을 이해하기 위해 아주 중요한 수학적 연산이다. 유클리드 알고리즘은 암호학에 다가가기 위한 준비의 준비 단계라고 생각하고 이번 글에 접근하면 좋을 것 같다.

 

| 약수

 

약수는 어떤 수를 나누어 떨어지게 하는 수, 즉 해당 수를 나누어 떨어지게 하는 정수를 의미한다. 예를 들어 12라는 숫자를 만들기 위해선 (1 x 12), (2 x 6), (3 x 4) 3가지 경우로 만들 수 있다. 이때 모든 요소를 약수라고 한다. 12의 약수를 아래와 같이 표현할 수 있다.

 

12 = { 1, 2, 3, 4, 6, 12 }

 

| 공약수

 

공약수는 어떤 두 수(또는 두 개 이상의 수)가 가지고 있는 공통된 약수 집합를 의미한다. 아래 예시를 통해 알아보자.

 

example

12 = { 1, 2, 3, 4, 6, 12 }

18 = { 1, 2, 3, 6, 9, 18 }

 

12와 18의 약수는 위와 같다. 이때, 12와 18 두 수의 공통된 약수인 1, 2, 3, 6가 공약수이다.

 

(12, 18)의 공약수 = { 1, 2, 3, 6 }

 

당연하지만 모든 숫자의 가장 큰 공약수는 자기 자신이다. ( $\because 1\times a$ )

 

| 나누기($÷$)연산 : 제수, 피제수, 몫, 나머지

 

우리가 어떤 두 수의 나누기 ($÷$) 연산을 한다고 하면, 아래와 같이 표현할 수 있다.

$$a÷b\Rightarrow a=q\times b+r$$

이때, 4가지 변수가 정의된다.

• $a$ = 피제수(dividend) : 나누어 지는 수
• $b$ = 제수(divisor) : 나누는 수
• $q$ = 몫
• $r$ = 나머지

 

| 가분성(divisibility)

 

가분성이라 나누기 연산( $a=q\times b+r$ )에서 a가 b로 나눠 질 수 있는 성질을 의미하며, r = 0인 경우를 뜻한다. 예를 들어, ( a = 8, b = 2 )일때, 8 $÷$ 2의 나머지 r는 0이 되며, 수학적으로 a | b 라고 표현한다.

 

| 최대 공약수(greatest common divisor)

 

위에서 공약수는 두 수가 가지고 있는 공통된 약수 집합를 의미한다고 했다. 최대공약수는 공통된 약수 집합에서 가장 큰 수를 의미한다. 이때 두 수의 a,b 최대 공약수는 gcd(a,b)라고 표현한다. 12와 18을 통해 예를 들어보자.

 

12 = { 1, 2, 3, 4, 6, 12 }

18 = { 1, 2, 3, 6, 9, 18 }

(12, 18)의 공약수 = { 1, 2, 3, 6 }

 

두 수 12, 18의 공약수가 1, 2, 3, 6일 때, 최대 공약수는 6이 되며 아래와 같이 표현된다.

$$gcd(12,18)=6$$

 

| 서로소(relatively) 관계

 

gcd(a, b)의 결과가 1일 때, a와 b의 관계를 서로소 관계라고 한다. 나중에 모듈러 연산에서 유클리드 알고리즘을 활용할 때 아주 중요하게 적용되는 성질이다.

 

 

유클리드 알고리즘

---

유클리드 알고리즘은 어떤 두 수의 최대 공약수를 효율적으로 계산할 수 있는 수학적 알고리즘이다. 위에서 최대공약수를 12와 18를 통해 간단하게 알아봤지만, 암호학에서 다루는 숫자는 엄청나게 커지기에 최대 공약수라는 결과는 결코 쉽게 얻을 수 없는 숫자이다. 이를 위해 등장한 수학적 개념이 바로 유클리드 알고리즘이다.

 

유클리드 알고리즘 특징

---

유클리드 알고리즘은 아래 두가지 수학적 특징을 갖고 있다.

$$gcd(a,0)=a$$

$$gcd(a,b)=gcd(b,r)$$

먼저 이 두가지를 증명해보자

 

$gcd(a,0)=a$

 

0은 모든 수에 의해 나누어 진다. 즉, 0의 공약수는 모든 정수라고 할 수 있다.

모든 숫자의 가장 큰 공약수는 자기 자신이다. 때문에 a가 갖는 공약수 중에서 가장 큰 수 또한 자기 자신 a이다.

0의 공약수(모든 정수)에는 a가 포함되어 있다. 때문에 $gcd(a,0)=a$이 된다.

 

$a\ge b,gcd(a,b)=gcd(b,r)$

 

두번째 특징은 유클리드 알고리즘의 전부라고 생각해도될 정도로 아주 중요한 특징이다. 위에서 두 수(a, b)의 나누기 연산을 한다고 하면, 아래와 같이 표현할 수 있고 했다.

$$a÷b\Rightarrow a=q\times b+r$$

$gcd(a,b)=gcd(b,r)$의 변수 a, b, r는 위 나누기 연산에서 정의된 변수와 같다. 즉, 두번째 특징을 풀어서 얘기하면, a와 b의 최대 공약수와 b와 r (a $÷$ b 나머지)의 최대 공약수가 같다는 얘기다. 아래 예시를 통해 알아보자.

 

(1) 먼저 나누기 연산을 통해 나머지 값 r를 구한다.

 

$\because a=48,b=18$,

$\therefore 48÷18\Rightarrow 48=2\times 18+12$,

$\therefore r=12$

 

(2) 이때, 변수 a, b, r의 공약수는 아래와 간다.

 

$a(48)공약수=1,2,3,4,6,8,12,16,24,48$

$b(18)공약수=1,2,3,6,9,18$

$r(12)공약수=1,2,3,4,6,12$

 

(3) a와 b의 최대 공약수, b와 r의 최대 공약수를 비교한다.

 

gcd(48, 18) = 6

gcd(18, 12) = 6

 

(4) $gcd(a,b)=gcd(b,r)$라는 결론이 나온다.

 

 

유클리드 알고리즘 연산

---

이제 유클리드 알고리즘이 갖는 특징을 활용한 알고리즘 연산을 통해 두 수의 최대 공약수를 구해보자. 유클리드 알고리즘 연산은 간단하게 말하면 $gcd(a,b)=gcd(b,r)$을 반복하여 $gcd(a,0)=a$ 에 도달하는 것을 말한다. 실습으로 $gcd(36,10)$을 구해보자.

 

[그림 1] 유클리드 알고리즘 연산

 

(1) $\because$ a(36)와 b(10)을 나눈 나머지 r = 6이다.

     $\therefore$ $gcd(36,10)=gcd(10,6)$ 이 성립한다.

 

(2) $\because$ a(10)와 b(6)을 나눈 나머지 r = 4이다.

      $\therefore$ $gcd(10,6)=gcd(6,4)$ 이 성립한다.

 

(3) $\because$ a(6)와 b(4)을 나눈 나머지 r = 2이다.

      $\therefore$ $gcd(6,4)=gcd(4,2)$ 이 성립한다.

 

(4) $\because$ a(4)와 b(2)을 나눈 나머지 r = 0이다.

      $\therefore$ $gcd(4,2)=gcd(2,0)$ 이 성립한다.

 

(5) $\because$ gcd(2, 0) = 2이다.

      $\therefore$ $gcd(36,10)=gcd(2,0)=2$가 된다.

 

위 예시를 통해 36과 10의 각자의 모든 공약수를 구하지 않고, 두수의 최대공약수를 유클리드 알고리즘을 통해 구해봤다.

이와 같은 방법으로 우리는 두 수 a, b의 공약수를 구할 필요 없이, 유클리드 알고리즘을 통해 최대 공약수를 간단하게 구할 수 있다.

 

확장된 유클리드 알고리즘

---

암호학에서 사용하는 모듈러 연산은 확장된 유클리드 알고리즘의 개념 이해가 필요하다. 때문에 위에서 다뤘던 유클리드 알고리즘은 확장된 유클리드 알고리즘을 이해하기 위한 준비 단계였다. 지금부터 확장된 유클리드 알고리즘에 대해 알아보자

확장된 유클리드 알고리즘은 두 수의 최대 공약수를 구하고, $s\times a+t\times b=gcd(a,b)$가 되는 s와 t를 구하는 알고리즘이다.

 

 

확장된 유클리드 알고리즘 특징

---

확장된 유클리드 알고리즘은 아래와 같은 수학적 특징을 갖는다.

$$r=R1-qR2,s=S1-qS2,t=T1-qT2$$

여기서 $R1,R2,S1,S2,T1,T2$는 유클리드 알고리즘 연산의 각 라운드(Round) 슬롯에 위치하는 값을 의미한다. 위 [그림 1]을 통해 유클리드 알고리즘 연산을 실습했었다. 이때, Round 별로 a와 b의 값이 각 위치에(슬롯)에 들어가는걸 알 수 있다. 각 라운드의 a, b가 여기서 $R1,R2$가 된다. 아래 [그림 2] $gcd(36,10)$를 통해 $R1,R2,S1,S2$를 먼저 이해해보자.

 

[그림 2] 확장된 유클리드 알고리즘 $R1,R2,S1,S2$

 

 

여기서 중요한 특징은 바로 $r=R1-qR2$의 몫 q가 $S1,S2$계산에 공유된다는 점이다. $R1,R2$는 위에서 했던 유클리드 알고리즘과 똑같다. 그럼 $S1,S2$ 에 대해 알아보자.

 

$S1,S2$은 초기값(init)이 존재한다. $S1=1,S2=0$으로 정의한다. 그리고 $R1,R2$ 라운드에서 도출된 몫(q)를 공유받아서 $s=S1-qS2$성질을 통해 마지막 라운드까지 계산한 후, 더 이상의 라인드가 진행되지 않을때 마지막 s가 최종 결과가 된다. 위 그림으로 봤을 때, s = 2가된다.

 

다음으로 아래 [그림 3]을 통해 $T1,T2$를 알아보자.

 

[그림 3] 확장된 유클리드 알고리즘] $R1,R2,T1,T2$

 

$S1,S2$ 연산때랑 반대로 $T1,T2$의 초기값(init)은 $T1=0,T2=1$으로 정의한다. 마찬가지로 $R1,R2$ 라운드에서 도출된 몫(q)를 공유받아서, 더 이상의 라인드가 진행되지 않을때 마지막 t가 최종 t 결과가 된다.

확장된 유클리드 알고리즘은 $s\times a+t\times b=gcd(a,b)$가 성립되는 s와 t를 구하는 알고리즘라고 했다. 유클리드 알고리즘으로 구한 $gcd(36,10)$와 확장된 유클리드 알고리즘을 통해 구한 s와 t를 대입하여 $s\times a+t\times b=gcd(a,b)$를 증명해볼 수 있다.

 

(1) $gcd(36,10)=2,s=2,t=-7$

 

(2) $gcd(36,10)=2\times 36+10\times -7=72-70=2$

 

최종적으로 확장된 유클리드 알고리즘 성질 $s\times a+t\times b=gcd(a,b)$ 처럼 결과가 도출된걸 확인할 수 있다.

 

 

확장된 유클리드 알고리즘과 암호학

---

확장된 유클리드 알고리즘은 위에서 설명했던 것 처럼 모듈러 연산에서 활용하는 아주 중요한 개념이다. 그리고 모듈러 연산은 암호학, 특히 타원 곡선 암호학에서 아주 중요한 개념이다. 또한 위에서 아주 가볍게 지나갔지만 gcd(a, b)의 결과가 1일 때, a와 b의 서로소 관계라고 또한 모듈러 연산에서 활용되는 개념이다. 계속해서 다음 시리즈로 모듈러 연산에 대해 알아보도록 하자.