ECC-7. 타원 곡선 암호 키 생성

타원 곡선 암호(Elliptic Curve Cryptography, ECC)에서 키 생성은 공개 키 암호 방식의 핵심적인 부분으로, 개인 키와 공개 키라는 한 쌍의 키를 만드는 과정입니다. 이 과정은 타원 곡선 위의 점들을 이용한 수학적 연산을 기반으로 합니다.

핵심 개념

키 생성 과정을 이해하기 위해서는 몇 가지 기본적인 개념을 알아야 합니다.

• 타원 곡선: 특정 수학 방정식(y2=x3+ax+b 형태)을 만족하는 점들의 집합입니다. 암호학에서는 유한체(finite field) 상에서 정의된 타원 곡선을 사용합니다.
• 기저점 (G): 타원 곡선 위에 미리 정해진 기준이 되는 점입니다. 이 점은 모든 참여자에게 공개되어 있습니다.
• 개인 키 (d): 사용자가 비밀리에 선택하는 매우 큰 정수입니다. 이 키는 절대로 외부에 노출되어서는 안 됩니다.
• 공개 키 (Q): 개인 키와 기저점을 사용하여 계산되는 타원 곡선 위의 한 점입니다. 이 키는 누구에게나 공개될 수 있습니다.

키 생성 과정

타원 곡선 암호의 키 생성 과정은 다음과 같은 단계로 이루어집니다.

1. 타원 곡선 및 기저점 선택: 먼저, 암호 시스템에 사용할 특정 타원 곡선과 그 위의 기저점(G)을 정합니다. 이 정보는 공개되어 있으며, 표준화된 값들(예: secp256k1)을 사용하는 경우가 많습니다.
2. 개인 키 생성: 사용자는 매우 큰 범위의 정수 중에서 무작위로 하나의 숫자, 즉 개인 키(d)를 선택합니다. 이 개인 키는 1부터 n-1 사이의 값이며, n은 기저점 G의 위수(order)입니다.
3. 공개 키 계산: 공개 키(Q)는 개인 키(d)와 기저점(G)을 사용하여 계산됩니다. 계산 방법은 타원 곡선 위의 '점 덧셈' 연산을 d-1번 반복하는 것과 같습니다. 이를 스칼라 곱셈(Scalar Multiplication)이라고 하며, 다음과 같이 표현합니다.

$$Q=d\times G$$

여기서 d×G는 G를 d번 더하는 것을 의미합니다(G+G+...+G).

이렇게 생성된 개인 키(d)와 공개 키(Q)가 하나의 키 쌍을 이루게 됩니다.

핵심적인 수학적 원리

타원 곡선 암호의 안전성은 타원 곡선 이산 대수 문제(Elliptic Curve Discrete Logarithm Problem, ECDLP)의 어려움에 기반합니다.

• 계산은 쉽다: 개인 키(d)와 기저점(G)이 주어졌을 때, 공개 키(Q)를 계산하는 것(Q=d×G)은 컴퓨터로 매우 빠르게 수행할 수 있습니다.
• 역계산은 어렵다: 하지만 반대로, 공개 키(Q)와 기저점(G)이 주어졌을 때, 개인 키(d)를 알아내는 것은 현재 알려진 기술로는 계산적으로 거의 불가능합니다. 이것이 바로 타원 곡선 이산 대수 문제입니다.

이러한 비대칭성 덕분에 공개 키는 외부에 안전하게 공개할 수 있으며, 개인 키를 가진 사람만이 해당 공개 키와 관련된 암호화된 메시지를 해독하거나 전자 서명을 생성할 수 있습니다.

보충 설명

secp256k1

secp256k1은 비트코인과 이더리움 등 여러 블록체인에서 사용하는 표준화된 타원 곡선의 이름입니다. 이 이름은 각 부분의 의미를 조합한 것입니다.

• sec: Standards for Efficient Cryptography (효율적인 암호화를 위한 표준)의 약자입니다. Certicom이라는 회사에서 제정한 표준안입니다.
• p: 곡선이 정의되는 수학적 필드(field)의 종류를 의미하며, 'p'는 소수 필드(prime field)를 나타냅니다. 이는 모든 연산이 특정 소수(p)를 법(modulo)으로 하여 이루어진다는 뜻입니다.
• 256: 키의 비트 길이, 즉 256비트를 의미합니다. 이는 개인 키의 크기와 관련이 있습니다.
• k: 곡선의 종류를 나타내며, 코블리츠 곡선(Koblitz curve)임을 의미합니다. 코블리츠 곡선은 일반적인 타원 곡선에 비해 특정 연산(점 덧셈)을 더 효율적으로 수행할 수 있는 구조적 특징을 가집니다.
• 1: 해당 표준에서 정의된 첫 번째 곡선이라는 의미입니다.

간단히 말해, secp256k1은 "SEC 표준에 정의된, 256비트 키 길이를 사용하는, 소수 필드 위의, 첫 번째 코블리츠 타원 곡선"을 지칭하는 식별자입니다. 이 곡선은 아래의 특정 방정식으로 정의됩니다.

$${y}^2\equiv {x}^3+7\ \left(mod\ p\right)$$

여기서 p는 매우 큰 소수($2^{256} - 2^{32} - 977$)입니다. 암호 시스템에서 모든 참여자는 바로 이 secp256k1 곡선과 여기에 속한 기저점 G를 공유하여 키를 생성하고 검증합니다.

n은 기저점 G의 위수(order)

"위수(order)"는 수학, 특히 군론(group theory)에서 사용하는 용어로, 특정 연산을 반복했을 때 처음 상태로 돌아오기까지 필요한 횟수를 의미합니다.

타원 곡선 암호에서 기저점 G의 위수(n)는 다음과 같은 의미를 가집니다.

기저점 G를 스스로 계속 더해 나갈 때, 무한대의 점(point at infinity, 타원 곡선 연산의 항등원)이 되기까지 필요한 덧셈의 횟수

수식으로는 다음과 같이 표현할 수 있습니다.

• G + G = 2G
• 2G + G = 3G
• ...
• (n-1)G + G = nG = O (무한대의 점)

여기서 n이 바로 위수입니다. n은 매우 큰 소수(prime number)입니다.

개인 키 d는 1부터 n-1 사이의 정수 중에서 선택됩니다. 만약 d를 n 또는 그 배수로 선택하면, 공개 키 Q는 Q = nG = O가 되어버려 개인 키를 특정할 수 없게 되고 암호 시스템이 작동하지 않습니다. 따라서 위수 n은 개인 키를 선택할 수 있는 유효한 범위를 정의하는 중요한 파라미터가 됩니다.