디지털 서명 알고리즘

3. 작동 방식

디지털 서명 알고리즘(DSA)은 공개 키 암호 시스템의 프레임워크 내에서 작동하며, 모듈러 지수화의 대수적 속성과 이산 로그 문제를 기반으로 하는 알고리즘이다. DSA는 공개 키와 개인 키로 구성된 키 쌍을 사용한다. 개인 키는 메시지에 대한 디지털 서명을 생성하는 데 사용되며, 생성된 서명은 서명자의 해당 공개 키를 사용하여 확인할 수 있다. 디지털 서명은 메시지 인증(수신자는 메시지의 출처를 확인할 수 있음), 데이터 무결성(수신자는 메시지가 서명된 이후로 수정되지 않았음을 확인할 수 있음) 및 부인 방지(발신자는 자신이 메시지에 서명하지 않았다고 거짓으로 주장할 수 없음)를 제공한다.

DSA 알고리즘은 키 생성, 키 분배, 서명, 서명 검증의 네 가지 연산으로 구성된다.

• 키 생성: 시스템 매개변수를 선택하고, 사용자별 공개 키와 개인 키를 계산한다.
• 키 분배: 서명자는 공개 키를 공개하고, 개인 키는 비밀로 유지한다.
• 서명: 메시지에 대한 서명을 생성한다.
• 서명 검증: 서명이 유효한지 확인한다.

3. 1. 키 생성

• 승인된 암호화 해시 함수 ''H''를 선택한다. 원래의 DSS에서는 ''H''가 항상 SHA-1이었지만, 현재의 DSS에서는 더 강력한 SHA-2 해시 함수 사용이 승인되었다.^[6][14] 해시 출력의 가장 왼쪽 ''N'' 비트만 사용한다.
• 키 길이 ''L''을 선택한다. 원래의 DSS는 ''L''을 512에서 1024 사이의 64의 배수로 제한했다. NIST 800-57은 2010년(또는 2030년) 이후까지 보안 수명이 연장되는 키에 대해 2048(또는 3072)의 길이를 권장한다.^[15]
• 이고 $N\; \backslash leq\; |H|$가 되도록 모듈러스 길이 ''N''을 선택한다. FIPS 186-4는 ''L''과 ''N''이 (1024, 160), (2048, 224), (2048, 256), 또는 (3072, 256)의 값 중 하나를 갖도록 지정한다.^[6]
• ''N''비트 소수 ''q''를 선택한다.
• ''p'' - 1이 ''q''의 배수가 되도록 ''L''비트 소수 ''p''를 선택한다.
• $\backslash \{\; 2\; \backslash ldots\; p-2\; \backslash \}$에서 정수 ''h''를 무작위로 선택한다.
• $g\; :=\; h^\{(p\; -\; 1)/q\}\; \backslash mod\; p$를 계산한다. 드물게 $g=1$인 경우 다른 ''h''로 다시 시도한다. 일반적으로 $h=2$가 사용된다. 이 모듈러 지수 연산은 값이 커도 효율적으로 계산할 수 있다.

• 정수 ''x''를 $\backslash \{\; 1\; \backslash ldots\; q-1\; \backslash \}$에서 무작위로 선택한다.
• $y\; :=\; g^x\; \backslash mod\; p$를 계산한다.

3. 2. 키 분배

• 0 < ''x'' < ''q''인 ''x''를 무작위로 선택한다.
• ''y'' = ''g''^''x'' mod ''p''를 계산한다. ''x''와 ''y''의 대응은 1대1이며, ''x''로부터 ''y''를 계산하는 것은 비교적 쉽지만, ''y''로부터 ''x''를 계산하는 것은 실질적으로 불가능하다(이산 대수 문제). 즉, ''x''와 ''y''의 대응은 일방향 함수가 된다.
• 공개 키는 (''p'', ''q'', ''g'', ''y''), 비밀 키는 ''x''이다.

3. 3. 서명

3. 4. 서명 검증

• 0 < r < q 및 0 < s < q인지 확인한다.
• w := s^-1 mod q를 계산한다.
• u₁ := H(m) · w mod q를 계산한다.
• u₂ := r · w mod q를 계산한다.
• v := (g^u₁y^u₂ mod p) mod q를 계산한다.
• 서명은 v = r일 때만 유효하다.

4. 알고리즘의 정당성

먼저, g^영어 = h^{영어(p-1)/q} mod p 이므로, 페르마의 소정리에 의해 g^영어q ≡ h^p-1 ≡ 1 (mod p)가 성립한다. g^영어 > 0 이고 q 가 소수이므로, g^영어는 위수 q를 갖는다.

서명자는 다음을 계산한다.

:s = k^-1(H(m) + xr) mod q

따라서 다음이 성립한다.

:k ≡ H(m)s^-1 + xrs^-1 ≡ H(m)w + xrw (mod q)

g^영어가 위수 q를 가지므로, 다음 역시 성립한다.

:g^k ≡ g^H(m)wg^xrw ≡ g^H(m)wy^rw ≡ g^u1y^u2 (mod p)

마지막으로, DSA의 정당성은 다음으로부터 유도된다.

:r = (g^k mod p) mod q = (g^u1y^u2 mod p) mod q = v

5. 취약점 및 안전성

DSA의 안전성은 이산 로그 문제의 어려움에 기반한다. DSA에서 서명 시 사용되는 임의 값 ''k''는 엔트로피(무작위성), 기밀성, 유일성이라는 세 가지 조건을 만족해야 한다. 이 중 하나라도 위반되면 공격자가 개인 키를 알아낼 수 있다.^[16] 동일한 ''k'' 값을 두 번 사용하거나, 예측 가능한 값을 사용하거나, 여러 서명에서 ''k''의 몇 비트만 유출되어도 개인 키 ''x''가 노출될 수 있다.^[17]

• 엔트로피: ''k''는 1부터 ''q''-1 사이에서 선택되며, 무작위성이 높을수록 좋다.
• 기밀성: ''k''는 서명 과정에서만 사용되는 비밀 값이며, 외부로 유출되어서는 안 된다.
• 유일성: 서로 다른 메시지에 대해 동일한 ''k'' 값을 사용해서는 안 된다.

6. 구현 라이브러리

• 보탄
• 바운시 캐슬
• 크립트립
• 크립토++
• libgcrypt
• 네틀
• OpenSSL
• wolfCrypt
• GnuTLS
• Libsodium

참조

_[1] 서적 Applied Cryptography https://archive.org/[...] Wiley 1996
_[2] 웹사이트 FIPS PUB 186: Digital Signature Standard (DSS), 1994-05-19 http://www.itl.nist.[...]
_[3] 웹사이트 FIPS PUB 186-1: Digital Signature Standard (DSS), 1998-12-15 http://csrc.nist.gov[...]
_[4] 웹사이트 FIPS PUB 186-2: Digital Signature Standard (DSS), 2000-01-27 http://csrc.nist.gov[...]
_[5] 웹사이트 FIPS PUB 186-3: Digital Signature Standard (DSS), June 2009 http://csrc.nist.gov[...]
_[6] 웹사이트 FIPS PUB 186-4: Digital Signature Standard (DSS), July 2013 http://nvlpubs.nist.[...]
_[7] 웹사이트 FIPS PUB 186-5: Digital Signature Standard (DSS), February 2023 https://nvlpubs.nist[...]
_[8] 웹사이트 Digital Signature Standard (DSS) https://csrc.nist.go[...] U.S. Department of Commerce 2020-07-21
_[9] 웹사이트 Dr. David W. Kravitz https://web.archive.[...] 2013-01-09
_[10] 문서 DSA and patents https://lists.gnupg.[...] Werner Koch
_[11] 웹사이트 1994 Annual Report of CSSPAB http://csrc.nist.gov[...] 2009-08-26
_[12] 웹사이트 The RISKS Digest Volume 14 Issue 59 https://catless.ncl.[...] 2023-10-03
_[13] 웹사이트 OpenSSH announces DSA-removal timeline [LWN.net] https://lwn.net/Arti[...] 2024-01-11
_[14] 웹사이트 FIPS PUB 180-4: Secure Hash Standard (SHS), March 2012 http://csrc.nist.gov[...]
_[15] 웹사이트 NIST Special Publication 800-57 http://csrc.nist.gov[...]
_[16] 웹사이트 The Debian PGP disaster that almost was http://rdist.root.or[...] 2009-05-18
_[17] 문서 DSA $k$-value Requirements https://rdist.root.o[...]
_[18] 뉴스 Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access http://exophase.com/[...] Exophase.com 2011-01-05
_[19] 논문 How Perfect Offline Wallets Can Still Leak Bitcoin Private Keys 2015-01-02
_[20] 간행물 FIPS PUB 186 http://www.itl.nist.[...] 1994-05-19
_[21] 간행물 FIPS PUB 186-1 http://csrc.nist.gov[...] 1998-12-15
_[22] 간행물 FIPS PUB 186-2 http://csrc.nist.gov[...] 2000-01-27
_[23] 간행물 FIPS PUB 186-3 http://csrc.nist.gov[...] 2009-06
_[24] 간행물 FIPS PUB 186-4 http://nvlpubs.nist.[...] 2013-07
_[25] 웹사이트 FIPS 186-5: Digital Signature Standard (DSS) https://csrc.nist.go[...] NIST 2024-03-03
_[26] 문서 Minutes of the Sept. 94 meeting of the Computer System Security and Privacy Advisory Board http://csrc.nist.gov[...]
_[27] 간행물 FIPS PUB 180-4 http://csrc.nist.gov[...] 2012-03
_[28] 문서 The Debian PGP disaster that almost was http://rdist.root.or[...]
_[29] 문서 DSA k-value Requirements https://rdist.root.o[...]
_[30] 뉴스 Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access http://exophase.com/[...] Exophase.com 2011-01-05
_[31] 웹인용 FIPS PUB 186]: Digital Signature Standard (DSS), 1994-05-19 http://www.itl.nist.[...] 2012-04-07
_[32] 웹인용 FIPS PUB 186-1: Digital Signature Standard (DSS), 1998-12-15 http://csrc.nist.gov[...]
_[33] 웹인용 FIPS PUB 186-2: Digital Signature Standard (DSS), 2000-01-27 http://csrc.nist.gov[...]
_[34] 웹인용 FIPS PUB 186-3: Digital Signature Standard (DSS), June 2009 http://csrc.nist.gov[...]
_[35] 웹인용 FIPS PUB 186-4: Digital Signature Standard (DSS), July 2013 http://nvlpubs.nist.[...]
_[36] 웹사이트 Dr. David W. Kravitz http://www.certicom.[...] 2013-01-09