유한체: 암호학이 살아가는 수 체계

Annkkitaaa의 원문 연구

왜 “되감기듯 순환하는 것”이 Zcash의 비밀스러운 토대인가

시리즈: Zcash from First Principles . 아티클 1 . 유한체 대상 독자: 입문자. 오직 일반적인 학교 수학(더하기, 곱하기, 나누기)만 안다고 가정합니다. 암호학이나 고등수학의 사전 지식은 필요 없습니다. 이 글을 읽고 나면 얻게 될 것: 유한체가 무엇인지에 대한 직관적이면서도 정확한 이해, 암호학자들이 왜 그것을 사용하는지, 그리고 그것이 Zcash 내부 어디에 등장하는지에 대한 이해.

아티클 0에서는 다섯 명의 등장인물을 만났습니다. 노트, 커밋먼트, 노트 커밋먼트 트리, 널리파이어, 그리고 영지식 증명입니다. 그때 한 가지 열린 질문을 남겨두었죠. 이 모든 키와 비밀 레시피는 실제로 어디에서 오는 걸까? 그것들은 숫자에서 옵니다. 하지만 여러분이 자라며 익숙해진 평범한 숫자가 아닙니다. 그것들은 유한체라고 불리는 특별하고 자기완결적인 수 체계에서 오며, Zcash의 거의 모든 암호학은 그 위에 구축됩니다.

이 글은 그 아이디어를 천천히 이해하도록 돕습니다. 약속한 대로, 먼저 직관부터 시작합니다. 공식은 제값을 할 때까지 등장하지 않습니다.

1. 왜 이걸 알아야 할까요?

보통의 숫자에는 암호학에 불리한 문제가 있습니다. 숫자가 무한히 많고, 정보를 새어나가게 만들기 때문입니다.

숫자가 더 커질 때 무슨 일이 일어나는지 생각해 보세요. 내가 어떤 비밀 계산의 결과가 8,142,067이라고 말하면, 여러분은 이미 꽤 많은 것을 알게 됩니다. 7자리 숫자라는 것, 홀수라는 것, “상당히 크다”는 것까지요. 크기 자체가 단서입니다. 그리고 단서는 프라이버시 시스템이 절대로 내줘서는 안 되는 것입니다.

암호학이 원하는 수 체계는 이런 성질을 가져야 합니다.

• 값의 개수가 유한해서 컴퓨터가 어떤 값이든 반올림이나 오버플로 없이 정확하게 저장할 수 있어야 하고,
• 값이 크기를 드러내지 않아야 합니다. 왜냐하면 그 체계 안에는 사실상 “더 크다”는 개념이 없기 때문이고,
• 암호학적 레시피가 제대로 된 대수를 필요로 하므로 더하기, 빼기, 곱하기, 나누기를 자유롭고 가역적으로 할 수 있어야 하며,
• 가능한 값의 공간이 천문학적으로 커서 추측이 사실상 불가능해야 합니다.

이 바람 목록에는 이름이 있습니다. 그것이 바로 유한체입니다. 기호를 하나도 쓰기 전에, 먼저 그 직관부터 만들어 봅시다.

2. 직관: 시계

사실 여러분은 이미 매일 유한체를 사용하고 있습니다. 벽에 걸린 시계가 바로 그것입니다.

12시간제 시계에서는 숫자가 한 바퀴 돌아옵니다. 10시에서 5시간을 더하면 “15시”가 되는 것이 아니라 3시가 됩니다. 시계에는 오직 12개의 위치만 있고, 맨 위를 지나 계속 세면 다시 처음으로 돌아오기 때문입니다.

방금 일어난 세 가지가 이 글 전체의 핵심입니다.

1. 세계는 유한합니다. 아무리 오래 세어도 위치는 정확히 열두 개뿐입니다.
2. 덧셈은 여전히 작동합니다. 하루 종일 시간을 더해도, 언제나 유효한 시계 위치에 도착합니다.
3. 크기는 더 이상 중요하지 않습니다. “3시”라는 결과만으로는 3시간을 센 것인지, 15시간인지, 27시간인지 알 수 없습니다. 한 바퀴 도는 성질이 크기 정보를 지워버린 것입니다. 이 지워짐이야말로 우리가 원하던 프라이버시 친화적 성질입니다.

이런 순환형 산술에는 정식 이름이 있습니다. 바로 모듈러 산술입니다. 시계는 “modulo 12”, 즉 mod 12로 작동합니다. 수학자들은 위치를 0부터 세는 편을 좋아하므로, “mod 12 시계”는 실제로 0, 1, 2, ..., 11의 위치를 가집니다. mod 7 시계라면 위치는 0부터 6까지입니다.

유일한 규칙: 어떤 계산이든 “mod p”로 하려면, 먼저 보통 산술대로 계산한 뒤 p로 나누고 나머지만 남기면 됩니다. 예를 들어 mod 7에서는 5 + 4 = 9이고, 9를 7로 나누면 나머지가 2이므로 5 + 4 = 2 (mod 7)입니다.

3. 시계에서 체로

시계는 덧셈을 가능하게 해줍니다. **체(field)**는 그보다 한 단계 업그레이드된 개념입니다. 즉, 네 가지 연산이 모두 잘 작동하는 수 체계이며, 특히 까다로운 나눗셈까지 포함합니다.

비형식적으로 말하면, 체란 더하기, 빼기, 곱하기, 나누기를 할 수 있는 “숫자”들의 집합입니다(단, 0으로 나누는 것은 제외). 그리고 우리가 익숙한 규칙들도 그대로 유지됩니다. 덧셈과 곱셈에서는 순서가 중요하지 않고, 괄호를 다시 묶어도 되며, 0과 1이 존재하고, 모든 숫자는 음수와 (단 0을 제외하고) 역수를 가집니다.

유리수는 체입니다. 실수도 체입니다. 우리가 원하는 것은 그중에서도 유한한 체입니다.

여기서 중요한 결과가 나옵니다. 그리고 정말 아름답습니다.

전체 수 0, 1, ..., p-1를 가져와서 모든 산술을 mod p로 하면, p가 소수일 때 그 결과는 유한체가 됩니다. 이것을 F_p라고 씁니다(“에프 서브 p”라고 읽습니다).

따라서 F_7 = {0, 1, 2, 3, 4, 5, 6}는 mod 7의 시계식 산술을 갖춘 진짜 유한체입니다. 이제 실제로 어떻게 작동하는지 봅시다.

F_7에서의 곱셈 (검증됨)

각 칸은 (행 x 열) mod 7입니다.

1부터 6까지의 행을 보세요. 각각의 행에는 0이 아닌 모든 값 1..6이 정확히 한 번씩 들어 있습니다. 이 “중복도 없고, 빠진 것도 없는” 패턴이 바로 체의 눈에 보이는 지문입니다.

나눗셈: 소수가 필요한 마법

나눗셈은 곧 “역수를 곱하는 것”입니다. F_7에서 숫자 a의 역수(또는 inverse)는 a x a^(-1) = 1이 되게 하는 값 a^(-1)입니다. 위 표에서 바로 읽어보면:

하나만 확인해 봅시다. 2 x 4 = 8 = 1 (mod 7)입니다. 따라서 F_7에서 “2로 나눈다”는 것은 “4를 곱한다”는 뜻입니다. 0이 아닌 모든 원소는 이렇게 짝을 이룹니다. 바로 이것이 F_7을 체로 만드는 이유입니다.

4. 왜 법수는 반드시 소수여야 하는가

이 글에서 가장 중요한 아이디어 하나를 꼽으라면 바로 이것이므로, 추상적으로 말하지 말고 구체적으로 보겠습니다.

만약 순진하게 mod 6으로 “체”를 만들려 하면 무엇이 망가지는지 보세요 (6은 소수가 아닙니다):

2 x x = 1 (mod 6)이 되는 x가 있을까요? 전부 확인해 보면 2x0=0, 2x1=2, 2x2=4, 2x3=0, 2x4=2, 2x5=4입니다. 답 1은 한 번도 나타나지 않습니다. 따라서 mod 6에서 2는 역수를 가지지 않습니다. 더 나쁘게는 2 x 3 = 6 = 0 (mod 6)입니다. 0이 아닌 두 숫자를 곱했는데 0이 나왔습니다.

이 두 번째 문장은 산술에 있어 재앙입니다. 0이 아닌 두 값이 곱해서 0이 되는 현상(이를 **영인수(zero divisor)**라고 합니다)이 생기면 나눗셈이 망가지고, 나눗셈이 망가진 체계는 더 이상 체가 아닙니다. 이런 일이 일어나는 정확한 이유는 6이 2 x 3으로 인수분해되기 때문입니다.

소수는 정의상 그런 인수를 갖지 않습니다. 따라서 소수 mod에서는 영인수가 생길 수 없고, 0이 아닌 모든 원소가 깔끔한 역수를 가지며, 구조가 올바른 체가 됩니다.

이후 글에서도 재사용할 수 있는 한 줄 요약: 법수가 소수면, 깔끔한 나눗셈이 나온다.

5. 만나볼 가치가 있는 단 하나의 공식: 컴퓨터가 역수를 찾는 방법

F_7에서는 표를 보고 역수를 읽어낼 수 있었습니다. 하지만 Zcash에서 쓰는 소수는 수백 자리이므로 표를 만드는 것은 불가능합니다. 대신 고전적인 지름길이 하나 있고, 이 글에서 나오는 유일한 공식이기도 합니다.

Fermat's Little Theorem에 따르면, 소수 p와 임의의 0이 아닌 a에 대해:

a^(p-1) = 1   (mod p)

이 식을 약간 바꾸면(a 하나를 떼어내면), 역수가 공짜로 나옵니다.

a^(-1) = a^(p-2)   (mod p)

F_7에서 시험해 봅시다 (p = 7이므로 p - 2 = 5). 2의 역수는 2^5 = 32 = 4 (mod 7)이어야 합니다. 실제로 위 표에서도 2^(-1) = 4였습니다. 컴퓨터는 큰 거듭제곱을 매우 빠르게 계산할 수 있으므로, 이 방법은 엄청나게 큰 소수에 대해서도 “역수를 구하라”를 빠르고 정확한 계산으로 바꿔줍니다.

이 공식을 외울 필요는 없습니다. 중요한 것은 유한체에서의 나눗셈은 빠르고 정확한 연산이라는 점입니다. 바로 그래서 암호학자들은 그 위에 안심하고 구조를 쌓을 수 있습니다.

6. 왜 암호학은 유한체를 사랑하게 되었는가

이제까지의 직관을 모아 보면, 전체 이유는 한 페이지로 정리됩니다.

한 문장으로 요약하면, 유한체는 산술을 위한 완전히 닫혀 있고, 완전히 정확하며, 완전히 거대한 놀이터입니다. Zcash의 나머지 모든 것은 그 안에서 놀며 만들어집니다.

7. 이것이 Zcash 안에서 어디에 있는가

“Zcash가 유한체를 사용한다”는 말을 그냥 믿을 필요는 없습니다. 여기 구체적인 지도가 있습니다(더 깊은 내용은 이후 글에서 다룰 것이고, 지금은 그 흔적이 실제라는 것만 보여주려는 목적입니다).

• Sapling(이전 세대의 실드 설계)은 BLS12-381이라는 곡선 위에서 증명을 구성하며, 그 기저체는 381비트 길이의 소수를 사용합니다. 모든 좌표, 키, 증명 원소는 그 소수를 기반으로 한 유한체의 원소입니다.
• Orchard(현재의 실드 설계)는 Pallas와 Vesta(이른바 “Pasta” 곡선)라는 한 쌍의 곡선을 사용하며, 그 체는 대략 255비트 길이의 소수를 사용합니다.
• 아티클 0에서 본 노트 커밋먼트, 널리파이어, 그리고 영지식 증명 내부의 숫자들은 결국 이 유한체들 중 하나의 원소입니다. 프로토콜이 “이 커밋먼트를 계산하라”고 말할 때, 그 뜻은 “그 소수 mod로 이 산술을 수행하라”는 것입니다.

따라서 아티클 0의 열린 질문, *“그 비밀 레시피는 어디에서 오는가?”*에 대한 답은 여기서 시작됩니다. 모든 것은 유한체 안의 산술로부터 시작합니다. 다음 글에서는 이 체를 가지고 실제 객체, 즉 타원곡선 위의 점들을 만들 것이고, 그것들이 키와 커밋먼트가 됩니다.

8. 솔직한 단서 하나

입문자 친화적으로 유지하기 위해, 몇 가지 사실은 단순화했습니다. 유한체는 F_p 형태만 있는 것이 아닙니다. 원소가 p^n개인 체(이를 **확장체(extension fields)**라고 부릅니다)도 만들 수 있으며, 이런 체는 Sapling의 증명 시스템이 의존하는 “페어링”에서 중요합니다. 또한 우리는 체 공리의 전체 목록도 생략했고, 이런 크기의 소수가 어떻게 선택되고 검증되는지도 자세히 다루지 않았습니다. 그렇다고 해서 지금 여러분이 얻은 직관이 바뀌는 것은 아닙니다. 다만 더 정교해질 뿐입니다. 이후 글에서 필요해질 때, 표시를 달아가며 그 정확성을 다시 더해가겠습니다.

9. 요약

• 암호학에는 유한하고, 정확하며, 크기에 둔감하고, 완전히 가역적이며, 거대한 수 체계가 필요합니다. 그 체계가 바로 유한체입니다.
• 직관은 시계입니다. 즉, 숫자가 한 바퀴 도는 산술(모듈러 산술)이며, 이것이 숫자의 “크기”를 자연스럽게 지워줍니다.
• 숫자 0..p-1에 대해 소수 p를 법수로 하여 산술을 하면 진짜 체 F_p가 되며, 이 안에서는 0이 아닌 모든 원소가 역수를 가지므로 나눗셈도 가능합니다.
• 법수는 반드시 소수여야 합니다. 합성수를 법수로 쓰면 영인수(예: 2 x 3 = 0 mod 6)가 생겨 나눗셈이 망가집니다.
• 컴퓨터는 Fermat's Little Theorem (a^(-1) = a^(p-2))을 이용해 역수를 빠르게 구합니다.
• Zcash에서는 모든 키, 커밋먼트, 널리파이어, 증명 원소가 궁극적으로 큰 유한체의 원소입니다(Orchard는 255비트 Pasta 체, Sapling의 BLS12-381은 381비트 체 사용).

용어집

FAQ

왜 그냥 보통의 정수나 소수를 쓰지 않나요? 소수점 수는 반올림되고 흔들리며, 정수는 끝없이 커지고 크기를 드러냅니다. 유한체는 정확하고, 경계가 있으며, 크기에 둔감하므로 암호학에 필요합니다.

“한 바퀴 돈다”는 것은 정보를 잃는 건가요? 의도적으로 그렇습니다. 중간값의 크기를 지우는 것은 프라이버시 관점에서 버그가 아니라 기능입니다.

소수가 클수록 항상 더 안전한가요? 대체로는 체가 클수록 가능한 값이 많아지고 추측이 어려워지지만, 보안성은 체의 크기만이 아니라 전체 구성에 달려 있습니다. 이후 글에서 이것을 더 정확히 다룹니다.

왜 Zcash는 이런 특정 소수들(255비트, 381비트)을 쓰나요? 그 소수들 위에 세운 곡선이 증명 시스템에 맞는 구조와 효율을 갖도록 선택되었기 때문입니다. 그 “맞는 구조”가 바로 다음 두 편의 주제입니다.

직관 점검하기

F_7에서 5 - 6은 얼마일까요? (기억하세요: 한 바퀴 돌면서 {0,...,6} 안에 머물러야 합니다.) (정답은 아래에 있습니다.)

다음에는

아티클 2 . 타원곡선: 방금 만든 유한체를 바탕으로, 점들을 서로 “더할” 수 있는 이상한 종류의 곡선을 그려봅니다. 그 점들은 Zcash의 키와 커밋먼트가 되며, 전체 프라이버시 시스템을 가능하게 하는 단방향 함정을 숨기고 있습니다. 늘 그렇듯, 먼저 직관부터 시작합니다.

이 글은 ZecHub를 위한 Zcash from First Principles 시리즈의 일부입니다. CC BY-SA 4.0 라이선스 적용.