ECC-9. 타원 곡선 디지털 서명 알고리즘(ECDSA)

타원 곡선 암호에서 디지털 서명은 타원 곡선 디지털 서명 알고리즘(ECDSA)을 통해 이루어집니다. 이는 메시지를 보낸 사람이 정말 본인인지(인증), 메시지가 위변조되지 않았는지(무결성), 그리고 서명한 사실을 부인할 수 없도록(부인 방지) 보장하는 기술입니다.

핵심 원리는 공개 키로는 할 수 없지만 개인 키(비밀 키)로만 쉽게 할 수 있는 수학적 연산을 이용하는 것입니다. 즉, 개인 키 소유자만이 유효한 서명을 생성할 수 있고, 다른 사람들은 해당 개인 키와 쌍을 이루는 공개 키를 이용해 그 서명이 올바른지 검증할 수 있습니다.

앨리스가 밥에게 메시지를 서명하여 보낸다고 가정해 보겠습니다.

1. 키 생성

먼저, 앨리스는 서명과 검증에 사용할 한 쌍의 키를 생성해야 합니다.

공통 정보 공유: 서명자와 검증자는 모두 동일한 타원 곡선($E$)과 그 위의 기준점($G$)을 미리 알고 있어야 합니다. 이 정보는 공개되어 있습니다.
개인 키 ($d_A$): 앨리스는 아무도 모르는 큰 정수 $d_A$를 자신의 개인 키로 선택합니다.
공개 키 ($Q_A$): 앨리스는 기준점 $G$에 자신의 개인 키 $d_A$를 곱하여(타원 곡선 덧셈 연산) 점 $Q_A = d_A \cdot G$를 계산합니다. 이 $Q_A$가 앨리스의 공개 키이며, 모든 사람에게 공개됩니다.

핵심 보안: 공개 키 $Q_A$와 기준점 $G$를 안다고 해도 개인 키 $d_A$를 역으로 계산하는 것은 '타원 곡선 이산 대수 문제'라는 수학적 난제 때문에 사실상 불가능합니다.

2. 서명 생성

앨리스는 보내려는 메시지($m$)에 대해 다음과 같은 과정으로 서명($r, s$)을 생성합니다.

해시 계산: 메시지($m$)를 해시 함수(예: SHA-256)에 넣어 일정한 길이의 해시 값($h$)을 계산합니다. 이는 메시지의 '지문'과 같아서, 메시지가 1비트만 바뀌어도 해시 값이 완전히 달라집니다.

$h = \text{hash}(m)$

임의의 수 선택: 서명할 때마다 새로운 임의의 정수 $k$를 선택합니다. 이 값은 서명 과정에서만 사용되고 반드시 비밀로 유지되어야 합니다.
임시 점 계산: 기준점 $G$에 $k$를 곱하여 새로운 점 $(x_1, y_1) = k \cdot G$를 계산합니다.
서명 값 $r$ 계산: 계산된 점의 $x$ 좌표 값을 가져와 특정 수(모듈러)로 나눈 나머지를 $r$로 정합니다.

$r = x_1 \pmod n$ (여기서 $n$은 곡선의 특정 상수)

만약 $r=0$이면, 다른 임의의 수 $k$를 선택하여 1~3 과정을 반복합니다.

서명 값 $s$ 계산: 다음 공식을 사용하여 $s$를 계산합니다.

$s = k^{-1} (h + r \cdot d_A) \pmod n$
$k^{-1}$는 $k$의 모듈러 역원이며, $d_A$는 앨리스의 개인 키입니다.

만약 $s=0$이면, 다른 $k$를 선택하여 다시 계산합니다.

이제 앨리스는 원래 메시지($m$)와 함께 계산된 한 쌍의 값 ($r, s$)를 밥에게 보냅니다. 이 ($r, s$)가 바로 앨리스의 디지털 서명입니다.

3. 서명 검증

밥은 앨리스로부터 메시지($m$)와 서명($r, s$)을 받고, 앨리스의 공개 키($Q_A$)를 사용하여 이 서명이 유효한지 검증합니다.

해시 계산: 밥 역시 받은 메시지($m$)를 똑같은 해시 함수를 사용해 해시 값($h'$)을 계산합니다.

$h' = \text{hash}(m)$

중간 값 계산: 다음 두 값을 계산합니다.

$u_1 = s^{-1} \cdot h' \pmod n$
$u_2 = s^{-1} \cdot r \pmod n$

여기서 $s^{-1}$는 받은 서명 값 $s$의 모듈러 역원입니다.

검증 점 계산: 앨리스의 공개 키($Q_A$)와 기준점($G$)을 사용하여 새로운 점 $(x_v, y_v)$를 계산합니다.

$(x_v, y_v) = u_1 \cdot G + u_2 \cdot Q_A$

검증 완료: 계산된 점의 $x$ 좌표 값($x_v$)을 특정 수($n$)로 나눈 나머지가 앨리스가 보낸 서명 값 $r$과 일치하는지 확인합니다.

만약 $x_v \pmod n = r$ 이라면 서명은 유효합니다.
그렇지 않다면 서명은 유효하지 않으며, 메시지가 위조되었거나 서명자가 앨리스가 아님을 의미합니다.

이러한 과정을 통해 밥은 메시지를 보낸 사람이 앨리스의 개인 키 소유자임을 수학적으로 확신할 수 있게 됩니다.

천천히, 제대로

이 블로그 검색