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

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

핵심 개념

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

• 타원 곡선: 특정 수학 방정식($y^2=x^3+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은 개인 키를 선택할 수 있는 유효한 범위를 정의하는 중요한 파라미터가 됩니다.