1. 수학적 배경지식

※ 이 카테고리에 쓸 블록체인 관련 정보글들은 독자가 정규교과과정상의 미적분을 제외한 중, 고등학교 수학을 알고 있다고 가정하고 작성할 것입니다. 만약 글을 읽다가 기본적인 용어에서 막히는 것이 있다면 따로 그 부분에 해당하는 교과과정상의 단원을 공부하는 것을 추천합니다. 그리고 쉬운 설명을 위해 전공자가 보기에는 약간의 모순 혹은 비약이 포함되어있을 수 있습니다. 그렇지만 그러한 세부적인 모순을 알아차릴 만한 지식을 가진 분은 이 글의 예상독자가 아니니 너그러이 양해해주시면 감사하겠습니다.


1. 소수와 소인수분해의 어려움


소수(prime number)는 1을 제외하고 1과 자기 자신만을 약수로 가지는 자연수입니다.(2, 3, 5, 7, 11, 13, 17, ...) 소수의 갯수는 무한하고 분포는 불규칙합니다. 모든 수는 소수의 곱으로 유일하게 표현 가능하며 이를 소인수분해(prime factorization)라고 합니다.(fundamental theorem of arithmetic) 예를 들어 24 = 2 * 2 * 2 * 3으로 소인수분해되고 이 외에 {2, 2, 2, 3}이 아닌 다른 소수들의 곱으로 24를 표현할 수 있는 방법은 없습니다.


수를 곱하는 일에 비해 큰 수를 소인수분해하는 일은 꽤 어렵습니다. 예를 들어 139 * 173을 계산하라는 문제는 계산기가 없더라도 길어봐야 1분 내로 해결할 수 있지만 24047을 두 소수의 곱으로 표현하라고 한다면 이를 풀기 위해서 꽤 많은 시간을 필요로 할 것입니다.


컴퓨터의 관점에서도 비슷합니다. 대략 200자리 가까이 되는 두 소수 p, q를 생각해봅시다. 이 두 소수 p와 q를 곱하는 일은 쉽습니다. 컴퓨터 기준으로 대략 0.01초 내로 답을 구할 수 있습니다. 그런데 p*q를 주고 p, q를 찾으라고 한다면 이는 굉장히 긴 시간을 필요로 합니다. (2009년 기준으로 컴퓨터 한 대가 70일 정도 계산을 해야 p*q로부터 p, q를 찾아낼 수 있습니다.)


2. 아스키코드


컴퓨터의 데이터는 0과 1로만 이루어져있다는 얘기를 얼핏 들어본 적이 있을 것입니다. 그런데 컴퓨터의 데이터가 0과 1로만 이루어져있다면 "abcf", "hello" 등과 같은 문자열을 어떻게 저장하고 있을까요? 컴퓨터는 영문자/특수문자/숫자를 한 바이트(byte)에 저장합니다. 1바이트는 8비트이고, 1비트는 0 혹은 1이 들어갈 수 있는 한 칸을 의미합니다. 즉 1바이트에는 00000000부터 11111111까지 들어갈 수 있으니 256가지의 경우의 수가 생깁니다. 이 때 미리 약속된 부호체계를 기반으로 각 글자를 1바이트에 넣습니다. 이 부호체계를 아스키코드(ASCII CODE)라고 합니다.


예를 들어 "hi123"은 104 105 49 50 51이 되고 이진수로 나타낼 경우 01101000 01101001 00110001 00110010 00110011이 됩니다.


3. 암호학적 해쉬함수


해쉬함수(hash function)은 임의의 길이의 데이터를 고정된 길이로 대응시키는 함수입니다. 예를 들어 f(x) = x를 100으로 나눈 나머지 라고 해봅시다. 이 때 f(x)의 정의역은 무한하고 치역은 0~99로 크기가 제한되어 있습니다. 즉 f(x)는 해쉬함수입니다. 이 때 "f(x) = 52를 만족하는 x를 찾아라" 라는 문제를 생각해봅시다. 우리는 이 문제의 답을 굉장히 쉽게 찾을 수 있습니다. x = 52, 152, 252 등이 f(x) = 52를 만족하겠죠. 그런데 g(x) = (x의 10승을 752으로 나눈 나머지) * (PI의 소숫점 아래 100*x번째 수)를 100으로 나눈 나머지 라는 함수를 생각해봅시다. g(x) 또한 정의역은 무한하고 치역은 0~99로 크기가 제한되어 있으므로  g(x)는 해쉬함수입니다. 마찬가지로 "g(x) =  52를 만족하는 x를 찾아라" 라는 문제를 생각해봅시다. 아까와는 다르게 x를 찾기가 쉽지 않을 것입니다. 1부터 차례차례 넣어보면서 g(1)이 얼마인지, g(2)가 얼마인지, .. 이렇게 g(x) = 52를 만족하는 x를 찾아야겠죠. 왜 f(x) = 52를 만족하는 x가 찾기 쉬웠는데 g(x) = 52를 만족하는 x를 찾기는 어려울까요? 이는 g(x)가 f(x)는 가지지 못한 성질을 가지고 있기 떄문입니다. 암호학적 해쉬함수(Cryptographic Hash Function)이 가지는 성질은 3가지가 있는데 그 중에서 가상화폐 채굴에 쓰이는 성질은 pre-image resistance입니다. 해쉬함수 H에서 주어진 해쉬값 h를 가지는 입력 x를 찾기 힘들다면 이런 해쉬함수는 pre-image resistance입니다. 수많은 입력을 무차별적으로 대입(brute force)하다보면 언젠가는 이러한 입력 x를 찾을 수 있겠지만 위의 f(x)와 같은 예시처럼 무차별적으로 대입하지 않고 주어진 해쉬값 h를 가지는 입력 x를 찾을 수는 없어야합니다. 비트코인은 SHA256이라는 해쉬함수를 사용하고 이더리움은 KECCAK-256이라는 해쉬함수를 사용합니다.


4. 합동식


합동식(modulus)은 정수의 합과 곱을 어떠한 수의 나머지에 대해 정의하는 방법입니다. 예시를 보면 쉽게 이해가 갈 것입니다.


3%5Cequiv%207(mod%5Cquad%204)%20  (3과 7은 4로 나눈 나머지가 같습니다.)

%5Ccombi%20%5E%7B%203%20%7D%7B%203%20%7D%5Cequiv%207(mod%5Cquad%202)%20


5. 오일러의 정리


오일러-파이 함수(Euler's  phi function)은 1부터 n까지의 정수 중에 n과 서로소인 수의 갯수를 의미합니다. 예를 들어 n=6일 경우 1~6까지의 정수 중에서 6과 서로소인 수는 1과 5가 있으므로 %5Cphi%20(6)%5Cquad%20%3D%5Cquad%202%20입니다. N=pq(p, q는 소수)에 대해서 %5Cphi%20(N)%5Cquad%20%3D%5Cquad%20(p-1)(q-1)%20 이라는 성질이 있습니다. 또한 주어진 임의의 수 N과, N과 서로소인 수 a에 대해 %5Ccombi%20%5E%7B%20%5Cphi%20(N)%20%7D%7B%20a%20%7D%5Cequiv%201%5Cquad%20(mod%5Cquad%20N)%20 이라는 성질이 있습니다. 이 식이 오일러의 정리입니다. 예를 들어 N=21일 때 phi(21) = 2*6 = 12이고, 21과 서로소인 임의의 수 a에 대해 a의 12승은 21로 나눈 나머지가 반드시 1입니다.


6. 전자서명


일상 생활에서 서명은 나의 신원을 증명하기 위해서 사용합니다. 전자서명(digital signature) 또한 비슷하게 어떤 행위의 주체가 나임을 증명하기 위한 수단인데, 수학적인 원리를 이용해서 인증(Authentication) 뿐만 아니라 무결성(Integrity), 부인방지(Non-reputation) 또한 제공합니다. 다양한 전자서명이 있지만 비트코인/이더리움에 쓰이는 전자서명은 소인수분해의 어려움을 기반으로 합니다. 오일러의 정리를 완벽하게 이해해야 전자서명도 이해할 수 있습니다.


Alice가 메시지 M을 서명하고 싶다고 가정해봅시다. Alice는 임의로 굉장히 큰 소수 p, q를 정해서 N=pq를 계산합니다. 그리고 임의의 비밀 정보 d를 정합니다. 이렇게 p, q, d를 정했으면 거의 다 끝났습니다. 이제 de%5Cequiv%201(mod%5Cquad%20%5Cphi%20(N))%20를 만족하는 e를 알아냅니다. 이러한 e는 유클리드 호제법(Euclidean algorithm)으로 쉽게 계산할 수 있습니다. N, e는 모두에게 공개하고 p, q, phi(N), d는 Alice만 알고 있는 비밀 정보입니다. 이제 Alice는 메시지 M과 서명 Sign%5Cquad%20%3D%5Cquad%20%5Ccombi%20%5E%7B%20d%20%7D%7B%20M%20%7D(mod%5Cquad%20N)%20 을 공개합니다. 이제 외부인들은 %5Ccombi%20%5E%7B%20e%20%7D%7B%20Sign%20%7D(mod%5Cquad%20N)%20 을 계산해서 이것이 M과 같은지를 확인합니다. 만약 이것이 M과 같으면 외부인은 메시지 M과 Sign을 보고 이 메시지가 Alice로부터 왔음을 확인할 수 있습니다.(Alice를 제외한 나머지 사람은 Sign = M^d을 만들어낼 수 없기 때문입니다.


'컴퓨터과학 > 블록체인' 카테고리의 다른 글

1. 수학적 배경지식  (2) 2018.01.24
  Comments
댓글 쓰기