[암호학] 6. 디지털 서명

이전 글에서 해시 함수에 대해 알아보았습니다. 해시 함수는 원래의 내용을 얻을 수 없는 일방향 함수로, 해시값을 통해 무결성을 지킵니다. 디지털 서명은 해시 함수와 공개키 암호 시스템을 이용해 데이터의 진위성과 무결성을 지킬 수 있습니다.
데이터의 진위성과 무결성을 지킬 수 있다는 말을 예를 들어 설명하겠습니다. 만약 앨리스가 밥에게 보내는 이메일에 앨리스가 디지털 서명을 했다면 그 이메일이 위조되지 않음을 보장함과 동시에 밥이 이메일 작성자가 앨리스 임을 확인할 수 있습니다. 디지털 서명은 다음 요구사항을 충족해야 합니다.

• 위조 방지 (Unforgeability)
• 사용자 인증 (User authentication)
• 부인 방지 (Non-repudation)
• 변조 방지 (Unalterability)
• 재사용 방지 (Non-reusability)

디지털 서명의 설계

디지털 서명은 여러 방식으로 나뉘지만 일반적으로 3개의 알고리즘으로 구성됩니다.

• 키 생성 알고리즘
• 서명 생성 알고리즘
• 서명 검증 알고리즘

보통 디지털 서명은 비대칭 키 방식으로 키를 생성하고 데이터와 개인키를 결합해 서명을 생성하는 단계, 공개키와 메시지, 서명을 이용해 서명을 검증하는 단계로 나뉩니다. 각각의 알고리즘은 함수로 볼 수 있습니다. 먼저 간단하게 NIST의 디지털 서명 표준인 FIPS 186-4 DSS(Digital Signature Standard)의 DSA(Digital Signature Algorithm)에 대해서 알아보겠습니다.

DSA

DSA에는 총 5가지 변수가 필요합니다.

• $p$ : 512~1024비트의 소수
• $q$ : $p - 1$의 약수인 160비트의 소수
• $g$ : 위수가 $q$인 $\mathbb{Z}_p$의 원소 $g$ ($g = h^{(p - 1)/q}\ \text{mod}\ p$, $h$는 $1 < h < p - 1$을 만족하는 정수로, 주로 2를 사용합니다)
• $x$ : $0 < x < q$ 인 무작위 정수 (개인키)
• $y$ : $y = g^x\ \text{mod}\ p$ (공개키)

$p$와 $q$의 길이는 달라질 수 있으나 예시에서는 일부 범위로 고정하겠습니다.

$y$를 통해 $x$값을 알아내는 것은 이산로그문제이기 때문에 $y$가 공개되더라도 $x$값을 쉽게 알아낼 수 없습니다.
이 변수들이 다 정해졌다면 키 생성 과정을 모두 마친 것입니다.

서명

DSA의 서명을 위해서는 논스(Nonce)라고 하는 무작위 값이 필요합니다. $0 < k < q$을 만족하는 무작위 값 $k$를 선정합니다. 논스값이 정해졌다면 $r$, $s$를 만듭니다. 서명에 필요한 해시 함수 $H(m)$ 또한 선정합니다.

• $r = (g^k\mod p)\mod q$ (만약 $r = 0$이라면 $k$를 다시 고릅니다)
• $s = k^{-1}(H(m) + xr)\mod q$ (만약 $s = 0$라면 $k$를 다시 고릅니다)

여기서 $(r, s)$가 서명이 됩니다.

검증

$m, (r, s)$을 받게 되면 디지털 서명을 검증할 수 있습니다. 디지털 서명의 검증 과정은 다음과 같습니다.

1. $w = s^{-1}\mod q$를 계산합니다.
2. $u_1 = H(m)\cdot w\mod q$, $u_2 = rw\mod q$를 계산합니다.
3. $v = (g^{u_1}\cdot y^{u_2}\mod p)\mod q$를 계산합니다.
4. $v = r$ 이 성립한다면 서명이 검증된 것입니다.

먼저 서명 단계에서 $k = s^{-1}(H(m) + xr)\mod q$가 성립합니다. 따라서 다음 사항이 성립합니다.

$\begin{aligned} g^k &= g^{H(m)s^{-1}}\cdot g^{xrs^{-1}}\\ &= g^{H(m)s^{-1}}\cdot y^{rs^{-1}}\\ &= g^{u_1}\cdot y^{u_2} \end{aligned}$

그렇기 때문에 $r = (g^k\mod p)\mod q =(g^{u_1}\cdot y^{u_2}\mod p)\mod q = v$를 통해 만약 $m, (s, v)$가 달라지지 않았다면 $r =v$가 성립하게 됩니다.

---

RSA-Signing

RSA 디지털 사인은 RSA 암호화 방식과 비슷합니다.

키 생성

개인키와 공개키를 생성하는 방법은 RSA 암호와 동일합니다.

1. 1024비트보다 긴 소수 $p$, $q$를 고릅니다.
2. $n = pq$를 구하고 $\phi(n) = (p-1)(q-1)$을 구합니다.
3. $\phi(n)$과 서로소인 정수 $e$를 고릅니다.
4. $ed = 1\mod\phi(n)$인 $d$를 고릅니다.

$(n, e)$가 공개키, $d$가 개인키가 됩니다. $p$, $q$ 또한 공개되지 않도록 해야합니다.

서명

서명과 검증은 해시 함수가 있는지의 여부에 따라 과정이 달라집니다.

• 해시 함수가 없을 때, $s = m^d \mod n$ 인 $s$가 서명이 됩니다.
• 해시 함수가 있을 때, $s = H(m)^d \mod n$인 $s$가 서명이 됩니다.

둘 모두 $s$를 서명으로 같이 전송합니다.

검증

• 해시 함수가 없을 때, $m = s^e \mod n$ 인지 확인합니다.
• 해시 함수가 있을 때, $H(m) = s^e \mod n$ 인지 확인합니다.

검증의 증명도 간단합니다. $m$과 $H(m)$을 모두 $M$이라고 부르겠습니다. $s^e \equiv (M^d)^e \equiv M\mod n$ 을 만족하므로 검증할 수 있습니다. RSA 디지털 서명에는 해시 함수가 필수적인데, 해시 함수가 없다면 $m_1$, $m_2$에 대한 서명 $s_1$, $s_2$에 대한 정보가 있을 때 개인키를 알지 못하더라도 간단하게 $s_1\cdot s_2$로 $m_1\cdot m_2$에 대한 서명을 만들어낼 수 있습니다. 그러나 해시 함수를 거친 값은 단순 곱셈으로 서명 정보를 얻을 수 없습니다.

---

ECDSA

타원곡선 디지털 서명(Elliptic Curve Digital Signature Algorithm, ECDSA)은 DSA를 타원곡선 위에서 수행합니다.

키 생성

RSA 디지털 서명이 RSA 암호화와 동일한 키 생성을 하는 것과 마찬가지로 ECDSA도 ECC와 동일하게 키를 생성합니다. 타원곡선의 도메인 파라미터는 이미 정해져 있다고 가정하겠습니다. 실제로 디지털 서명을 위해 타원곡선을 선택할 때도 이미 표준으로 정해진 타원곡선을 선택하는 것이 권장됩니다.

• $1 \le d \le n - 1$인 개인키 $d$를 선택합니다.
• 생성원 $G$에 $d$를 곱하는 연산을 통해 $Q = dG$를 얻습니다. $Q$가 공개키가 됩니다. $Q$는 $\mathcal{O}$가 아니어야 합니다.

서명

DSA와 마찬가지로 ECDSA 또한 해시 함수 $H(m)$을 정하고 $m, (r, s)$를 전달해야 합니다.

• $1 \le k \le n - 1$인 무작위 논스값을 선택합니다.
• $kG$를 계산해 $(x_1, y_1)$을 구합니다.
• $r = x_1\mod n$을 사용해 $r$을 구합니다. 만약 $r = 0$이면 다른 논스값을 다시 정합니다.
• $s = k^{-1}(H(m) + dr)\mod n$를 구합니다. 만약 $s = 0$이면 다른 논스값을 다시 정합니다.

여기서 $(r, s)$가 서명이 됩니다.

검증

검증은 다음과 같은 단계들로 진행됩니다.

1. $Q$는 무한원점($\mathcal{O}$)이 아니며 $nQ = \mathcal{O}$를 만족해야합니다.
2. $w = s^{-1}\mod n$를 계산합니다.
3. $u_1 = H(m)\cdot w\mod n$을 계산합니다.
4. $u_2 = rw\mod n$을 계산합니다.
5. $C = u_1G + u_2Q\mod n$인 점 $C$를 계산합니다.
6. 점 $C$가 $(x, y)$이라고 할 때, $r \equiv x\mod n$이 성립한다면 서명이 검증된 것입니다.

$C = u_1G + u_2Q$가 나온 5번 단계에서 시작하겠습니다.

$\begin{aligned} C &= u_1G + u_2Q\\ &=u_1G + u_2dG\\ &=(u_1 + u_2d)G\\ &=(H(m)w + rdw)G\\ &=(H(m) + rd)wG\\ &=(H(m) + rd)(H(m) + rd)^{-1}(k^{-1})^{-1}\cdot G\\ &=kG \end{aligned}$

타원곡선이 유한체이기 때문에 분배법칙이 성립하고, 따라서 간단하게 각각의 변수의 정의만 잘 대입한다면 $C$의 $x$좌표와 $r$이 같다는 것을 확인할 수 있습니다.

공개키 복구

만약 $m, (r, s)$가 있다면 서명자의 공개키를 복구할 수 있습니다. 서명은 유효하다고 가정하겠습니다.

1. $x$좌표가 $r, r + n, r + 2n \dots$인 점 $R = (x_1, y_1)$을 구합니다. $y$좌표는 각각의 $x$좌표에 대해 점 $R$이 타원곡선 위에 있도록 정합니다.
2. $u_1 = -H(m)\cdot r^{-1}\mod n$와 $u_2 = sr^{-1}\mod n$을 구합니다.
3. $Q = (x, y) = u_1G + u_2R$을 구합니다.

여기서 $Q$가 공개키가 됩니다.

$Q$가 공개키가 된다는 것을 증명하겠습니다.

$\begin{aligned} Q &= u_1G + u_2R\\ &= u_1G + u_2kG\\ &= (u_1 + u_2k)G\\ &= (-H(m)\cdot r^{-1} + skr^{-1})G\\ &= (-H(m)\cdot r^{-1} + k^{-1}(H(m) + rd)kr^{-1})G\\ &= (-H(m)\cdot r^{-1} + (H(m)r^{-1} + d))G\\ &=dG \end{aligned}$

---

Schnorr Signature

슈노르 서명(Schnorr signature)는 DSA가 영향을 받은 디지털 서명 시스템으로 스마트 카드를 위한 효율적인 디지털 서명으로 발명되었습니다.

키 생성

키 생성 과정은 DSA와 비슷합니다.

• 1024비트의 소수 $p$, $p - 1$의 약수인 160비트 소수 $q$
• 위수가 $q$인 $\mathbb{Z}_p$의 원소 $g$ ($g^q \equiv 1\mod p$)
• $x \in_R [1, q - 1]$인 정수 개인키 $x$ ( $\in_R$ 기호는 집합 내 무작위(random) 추출이라는 뜻입니다)
• 공개키 $y = g^x\mod p$

모듈러 $p$ 위에서 위수가 $q$인 부분군에 대해 연산이 진행됩니다.

서명

평문 $m$과 해시 함수 $H(m)$이 있다고 하겠습니다. $k \in_R [1, q - 1]$인 논스값 $k$를 고릅니다.

• $r = H(g^k\parallel m)$를 계산합니다. ($\parallel$은 비트로 표현된 두 수를 이어 붙이는 연산입니다)
• $s = k - xr \mod p$ 을 계산합니다.

$(r, s)$가 서명이 됩니다.

검증

1. $u_1 = g^sy^r$을 계산합니다.
2. $u_2 = H(u_1\parallel m)$을 계산합니다.
3. $u_2 = r$이 성립한다면 서명이 검증된 것입니다.

$u_1 = g^sy^e = g^{k - xr}g^xe = g^k$ 이므로, $u_2 = H(u_1\parallel m) = H(g^k\parallel m) = r$이 성립합니다.

Blind Signature

지금까지 알아본 디지털 서명은 모두 원래의 평문을 포함했습니다. 하지만 원래의 내용을 알지 못하게 하면서 출처만을 공개하고 싶을 때는 어떻게 할까요? 예를 들면 만약 누군가가 은행에서 현금을 인출할 때, 그게 얼마인지는 공개하지 않고 인출을 시도한 사람이 정당하게 인출을 할 수 있는 사람이라는 것만 확인할 수 있게끔 할 수 있을까요? 블라인드 서명(Blind signature)는 이러한 상황에서 사용됩니다.

Blind Signature는 서명하는 사람이 메시지의 내용을 모른채 서명 값을 생성합니다. 따라서 이전의 서명 시스템과 달리 서명자와 작성자가 다릅니다. 서명과 검증 단계에서 작성자, 서명자, 수신자까지 3명이 존재하지만 보통 작성자와 서명자를 구분한 2명으로 이루어진 서명 프로토콜로 설명하고 있습니다. Blind Signature는 공개키 암호 시스템을 이용해서 구현될 수 있습니다. 단순하게 RSA 서명에 기초한 Blind Signgature의 구현을 보겠습니다.

공개키와 개인키 생성 과정은 생략하겠습니다.

위 그림에서 볼 수 있듯이 서명자는 실제 $m$을 알고 있지 못해도 서명이 가능하고 동시에 작성자는 서명자의 개인키를 알 수 없습니다.

$k^{-1}(mk^{\color{red}{e}})^{\color{Green}{d}} = k^{-1}m^{\color{Green}{d}}k^{{\color{red}{e}}{\color{Green}{d}}} = m^{\color{Green}{d}}$ 이므로 $s$가 정당한 서명임을 알 수 있습니다.

정리하자면,

1. 무작위 수를 고르는 단계
2. 내용을 가린 뒤 보내는 단계 (blinding)
3. 서명 (signing)
4. 자신만 가지고 있는 정보를 이용해 서명을 유효하게 바꾸는 단계 (unblinding)

으로 진행된다는 것을 알 수 있습니다. 이를 $f$를 내용을 가리는 함수, $g$를 내용을 다시 복구하는 함수, $S_B$를 서명하는 함수라고 할때, $g(S_B(f(m))) = S_B(m)$가 성립한다고 말할 수 있습니다.

이렇게 어떠한 정보를 모르지만 유효성을 증명할 수 있다는 점에서 다음 글부터 설명드릴 영지식 증명의 영지식성과 비슷하다고 볼 수 있습니다.