DSA 개요

DSA(Digital Signature Algorithm)는 미국 NIST(National Institute of Standards and Technology)가 개발한 디지탈 서명을 위한 알고리즘으로, 디지탈 서명과 관련하여 미국에서 처음으로 연방 정보 처리 표준(Federal Information Processing Standard, FIPS)으로 채택된 것이다. 1991년 NIST (National Institute of Standards and Technology)는 디지탈 서명의 표준(Digital Signature Standard, DSS)으로 DSA를 제안하였는데, 당시 RSA 디지탈 서명에 이미 많은 투자를 한 소프트웨어 회사들이 반대했음에도 불구하고, NIST는 1994년 FIPS 186에서 DSA를 디지탈 서명 표준안으로 채택하였다.

FIPS 186은 이후 4개의 개정판을 발표하였는데, FIPS 186-1 (1998년)부터 FIPS 186-4 (2013년)까지 여러 해에 걸쳐 개정되었다. 1998년에 발표된 FIPS 186-1 에서는 DSA와 RSA를 함께 DSS 표준으로 하였으며, 2000년에 발표된 FIPS 186-2 에서는 DSA, RSA와 더불어 ECDSA를 디지탈 서명에 사용할 수 있는 표준으로 정하였다. 최근 2019년에 발표된 FIPS 186-5 초안(draft)에서는 새로운 디지탈 서명을 생성하는 곳에서 더이상 DSA를 사용하지 말고 단지 이전의 DSA 서명을 검증하는 부분에만 DSA를 사용할 것을 제안하였으며, 새로운 디지탈 서명에는 타원곡선(Elliptic curve) 서명의 일종인 EdDSA(Edwards-Curve Digital Signature Algorithm)를 사용하도록 제안하고 있다.

DSA는 비대칭 공개키 방식으로서, DSA 디지탈 서명은 공개키와 개인키를 쌍으로 사용하는데, 개인키를 사용하여 디지탈 서명을 생성하고 공개키를 사용하여 그 서명을 검증한다.

일반적으로 디지탈 서명은 수신자가 메시지 발신자를 확인할 수 있는 메시지 인증(Message Authentication) 기능과 메시지가 서명된 후에 중간에 변경되지 않았다는 점을 확인하는 데이타 무결성(Integrity) 기능, 그리고 송신자 자신이 메시지를 보냈다는 것을 나중에 허위로 부인하지 못하게 하는 부인 방지(Non-repudiation) 기능을 제공한다.

DSA 서명

DSA는 도메인 파라미터(p, q, g)와 개인키/공개키를 사용하여 디지탈 서명을 생성하게 된다. 도메인 파라미터와 공개키(public key)는 기본적으로 공개되는 정보이고, 개인키(private key)만이 공개되지 않는 정보이다.

DSA 서명은 (RSA 서명과 달리 별도의 암호화 과정이 없으며) 메시지 다이제스트와 개인키 등을 혼합하여 서명 요소를 생성하고, 수신자는 메시지 다이제스트와 서명 요소 그리고 공개키를 혼합하여 서명을 검증하게 된다.

DSA는 이산 로그 문제(Discrete logarithm problem, DLP)에 기반한 알고리즘으로, 이산 로그 문제란 식 g^a (mod p) ≡ b 에서 g와 b가 주어졌을 때 a를 구하는 문제로서, g^a 거듭제곱은 쉽게 구할 수 있지만 log_g b (mod p)를 계산해서 a를 구하는 것은 매우 어렵다는 사실에 기반한 것이다. 여기서 주목할 점은 단순히 log_g b 로그 문제를 구하는 것이 아니라, 모듈러 연산 (mod p)가 적용되기 때문에 이를 이산 로그 문제라 하고, 이 모듈러 연산으로 인해 매우 어려운 문제가 된다는 것이다. 특히, 여기서 모듈러스 p가 매우 클 경우, 이러한 이산 로그 문제를 푸는 것은 실용적으로 불가능한(computationally infeasible) 것으로 알려져 있다. 이산 거듭제곱은 쉽게 계산할 수 있는 반면, 이산 로그는 계산하기 매우 어렵기 때문에, 이 이산 로그 문제는 일방향 함수로 인식되어 지난 30년 넘게 암호학에서 활용되고 있다.

DSA 서명과 검증

DSA 서명은 도메인 파라미터와 개인키를 사용하여 (r, s)라는 2개의 서명 요소를 만들어 내는 과정이고, DSA 검증은 도메인 파라미터와 공개키를 사용하여 서명 (r, s)가 올바른 지를 검사하는 것이다.

DSA 서명

DSA 서명은 메시지를 해시하여 메시지 다이제스트를 만든 후 개인키를 사용하여 서명 요소 (r, s)를 만들어 내는 과정이다. DSA 개인키를 x, 서명하고자 하는 메시지를 m, 메시지를 해싱하는 해시함수를 H 라고 했을 때, DSA 서명은 다음과 같은 과정을 통해 서명 (r, s)를 산출한다.

1. {1, ..., q-1} 사이의 랜덤한 수 k를 선택한다.
2. r = (g^k mod p) mod q 식을 사용하여 r을 계산한다. 매우 드물지만 r=0 이면, 다른 k를 선택해서 반복한다.
3. s = (k^-1 (H(m) + xr)) mod q 식을 사용하여 s를 계산한다. 만약 s=0 이면, 다른 k를 선택하여 처음부터 다시 계산한다.
4. (r, s) 쌍이 디지탈 서명이다.

DSA에서 사용하는 해시함수는 초기 FIPS 186에서는 항상 SHA-1을 사용하도록 하였으나, 현재는 SHA-2 해시함수를 사용할 수 있도록 하고 있다. 해시함수의 해시 길이가 q 비트길이(N)보다 크면 해시값에서 왼쪽 N 비트만 취하게 된다.

서명 요소 (r, s)의 길이는 q의 비트길이(N)에 의해 결정되는데, 예를 들어 N = 160 이면 r과 s의 길이는 각각 160 비트가 되어 총 서명의 길이는 160 + 160 = 320 비트가 된다.

DSA 검증

DSA 검증은 메시지(m)와 서명(r, s)를 받아들여 공개키(y)로 메시지에 대한 서명이 맞는지를 검사하는 과정이다.

1. r, s의 범위가 0 < r < q, 0 < s < q 인지 체크한다.
2. w = s^-1 mod q 를 계산한다.
3. u1 = H(m)*w mod q 를 계산한다.
4. u2 = r*w mod q 를 계산한다.
5. v = (g^u1 * y^u2 mod p) mod q 를 계산한다.
6. v가 r과 동일하면 맞는 서명이다.