디지털 서명 알고리즘
Digital Signature AlgorithmDSA(Digital Signature Algorithm)는 디지털 서명에 대한 연방 정보 처리 표준으로, 모듈러 지수 및 이산 로그 문제에 대한 수학적 개념을 기반으로 합니다.DSA는 Schnorr 및 ElGamal 시그니처 [1]: 486 스킴의 변형입니다.
National Institute of Standards and Technology(NIST; 국립표준기술연구소)는 1991년에 DSA를 디지털 서명 표준(DSS)에 사용할 것을 제안하고 1994년에 [2]FIPS 186으로 채택했습니다.초기 사양에 대한 4가지 개정판이 출시되었습니다.최신 사양은 2013년 [3]7월부터 FIPS 186-4입니다.DSA는 특허를 취득하고 있습니다만, NIST는 이 특허를 로열티 없이 전 세계에 공개하고 있습니다.FIPS 186-5 사양의 초안 버전은 DSA가 디지털 서명 생성에 대해 승인되지 않음을 나타내지만 해당 표준의 구현일 이전에 생성된 서명을 검증하기 위해 사용될 수 있습니다.
개요
DSA는 공개 키 암호 시스템의 프레임워크에서 작동하며, 계산상 난해하다고 간주되는 이산 로그 문제와 함께 모듈식 지수의 대수적 특성에 기초한다.이 알고리즘에서는 공개 키와 개인 키로 구성된 키쌍이 사용됩니다.개인 키는 메시지의 디지털 서명을 생성하기 위해 사용되며, 이러한 서명은 서명자의 대응하는 공용 키를 사용하여 확인할 수 있습니다.디지털 시그니처는 메시지 인증(수신자는 메시지의 발신지를 확인할 수 있음), 무결성(수신자는 서명 후 메시지가 변경되지 않았음을 확인할 수 있음) 및 비거부(발신자는 메시지에 서명하지 않았음을 거짓으로 주장할 수 없음)를 제공합니다.
역사
1982년 미국 정부는 공개키 서명 기준에 대한 제안을 요청했습니다.1991년 8월, National Institute of Standards and Technology(NIST)는 DSS(Digital Signature Standard)에 사용하는 DSA를 제안했습니다.처음에는 특히 RSA 암호 [1]: 484 시스템을 기반으로 한 디지털 서명 소프트웨어 개발에 이미 투자했던 소프트웨어 회사들로부터 상당한 비판이 있었습니다.그럼에도 불구하고 NIST는 1994년에 연방 표준(FIPS 186)으로 DSA를 채택했다.최초 사양에는 FIPS 186–1, [4]2000년 FIPS 186–[5]2, [6]2009년 FIPS 186–3, 2013년 [3]FIPS 186–4의 4가지 리비전이 출시되었습니다.표준 FIPS 186-5의 초안 버전에서는 DSA와의 서명이 금지되어 있습니다.또, 표준의 실장일 이전에 생성된 시그니처를 문서로서 검증할 수 있습니다.이것은 EdDSA와 [7]같은 새로운 시그니처 스킴으로 대체됩니다.
DSA는 미국 특허 5,231,668의 적용을 받고 있으며 1991년 7월 26일에 출원되어 만료되었으며, 전 NSA 직원인 David W. Kravitz의 [8]책임입니다.이 특허는 '워싱턴 D.C. 상무장관으로 대표되는 미국'에 주어졌으며, NIST는 이 특허를 로열티 [9]없이 전 세계에 공개했습니다.Claus P. Schnorr는 자신의 미국 특허 4,995,082(현재 만료됨)가 DSA를 포함한다고 주장하지만,[10] 이 주장은 논란의 여지가 있습니다.
작동
DSA 알고리즘에는 키 생성(키 쌍을 생성), 키 배포, 서명 및 서명 검증의 4가지 작업이 포함됩니다.
1. 키 생성
키 생성에는 두 가지 단계가 있습니다.첫 번째 단계는 시스템의 다른 사용자 간에 공유할 수 있는 알고리즘 매개 변수를 선택하는 단계이며, 두 번째 단계는 한 명의 사용자에 대해 단일 키 쌍을 계산합니다.
파라미터 생성
- 출력 H(\ H 비트의 승인된 암호화 해시 H(\ H를 선택합니다.원래의 DSS에서는 H H는 항상 SHA-1이었지만 보다 강력한 SHA-2 해시함수는 현재의 [3][11]DSS에서 사용할 수 있도록 승인되어 있습니다.H H가 모듈러스 N(\ N보다 클 해시 출력의 맨 왼쪽 N 비트만 사용됩니다.
- 키 Ldisplaystyle을 선택합니다.원래 DSS L({L})은 512~1024 사이의 64의 배수입니다.NIST 800-57은 보안 수명이 2010년(또는 2030년)[12]을 초과하는 키의 길이를 2048(또는 3072)로 권장합니다.
- 계수 길이 N})과 N N H을 선택합니다.FIPS 186-4는 L과N({N}) 중 하나의 값을 지정합니다.
- N N 비트 q를 선택합니다.
- p-({이q({q의 배수가 L(\ L 비트 p p를 선택합니다.
- { - { \ { \ p - 2\}{ { from fromh 를 랜덤으로 선택합니다.
- g : ( -) / p { \ g : = { ( p - ) / q } \ p {g } 다른로 재시도합니다.으로 h { h}가 사용됩니다.이 모듈러형 지수는 값이 크더라도 효율적으로 계산할 수 있습니다.
알고리즘 파라미터는 ( \ p、q \ q、 \ g ) 입니다.이것들은, 시스템의 다른 유저간에 공유할 수 있습니다.
사용자별 키
파라미터 세트를 지정하면 두 번째 단계에서는 단일 사용자의 키쌍이 계산됩니다.
- { - { { \ { \ q 1 \} { { ( x )를 랜덤으로 합니다.
- : p { y : = { x} \ p 를 계산합니다.
x는 개인 키이고 y는 공개 키입니다.
2. 키 배포
서명자는 를발행해야 합니다.즉, 반드시 비밀일 필요는 없지만 신뢰할 수 있는 메커니즘을 통해 키를 수신자에게 전송해야 합니다.서명자는 개인 xx)를 비밀로 해야 합니다.
3. 서명
mm은 다음과 같이 서명됩니다.
- { 1 - { { 1 \ { \q -1 \ } 에서 k 를 랜덤으로 선택합니다.
- : = ( p ) q { \ r : = \ ( { k } { \ { ,}. 0 { \ 0 인 경우는 k { \ k}로 다시 시작합니다.
- : ( -1 ( () + q ( \ s : = \ ( ^ { - \ (^ { - } \ \ { , ). s \ s k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k
시그니처는(,) { 입니다.
k와 r(\ r의 계산은 메시지별 키를 새로 작성하는 것과 같습니다.style r 연산에서의 모듈식 지수화는 서명 조작에서 가장 많은 계산 비용이 드는 부분이지만 메시지가 알려지기 전에 계산될 수 있습니다.모듈러 역 - (\ k의 계산은 두 번째로 비용이 많이 드는 부분이며 메시지가 알려지기 전에 계산할 수도 있습니다. 유클리드 알고리즘을 사용하거나 페르마의 소정리를 k - 2 q \ k^ { - 2 mod \ { , , , q }} 로서 계산할 수 있습니다.
4. 서명 확인
다음과 같이 ,s)(\가 m(\ m에 유효한 시그니처임을 확인할 수 있습니다.
- 0< < \ 0 <r >0 < < \ 0 < sq 인 을 확인합니다.
- : - q { w : = { - } { \ { , , , 를 계산합니다.
- 1: (m q { _ { 1 : =H ( ) \ w , { \ { , , , 。
- 2: w { {2} : = r \ w , { \ { , , , }} 를 계산합니다.
- : ( 1 2 p ) q { v : = \ ( ^ { { 1} } { _ {2} } { \ right } { \ { , , , } } 。
- 시그니처는 v v인에만 유효합니다.
알고리즘의 정확성
이 시그니처 스킴은 검증자가 항상 정규 시그니처를 받아들인다는 점에서 정확합니다.이것은 다음과 같이 표시할 수 있습니다.
g (p -) / p \ { ( p - 1 ) / q { \ { } ~ p} 1 p mod h { p - 1 } \ 1 \ pthat Fermat의 작은 정리에 따른다.g> { g > {\ { q }는 이므로 g { g}의 는q { q 이어야 합니다.
서명자가 계산하다
따라서
g g가 qq)를 가지고 있기
마지막으로 DSA의 정확성은 다음과 같습니다.
감도
DSA에서는 랜덤 시그니처 k k의 엔트로피, 비밀성 및 고유성이 중요합니다.이 세 가지 요건 중 하나를 위반하면 전체 개인 키가 [13]공격자에게 노출될 수 있다는 것은 매우 중요합니다.k k의 비밀을 한 상태에서 같은 값을 2회 사용하거나 예측 가능한 값을 사용하거나 여러 시그니처 각각에 k k의 몇 조각이라도 누설하면 개인 키(\ x[14]를 표시하기에 충분합니다.
이 문제는 DSA와 ECDSA 모두에 영향을 미칩니다.2010년 12월에 Fail0verflow라는 그룹이 PlayStation 3 게임 콘솔용 소프트웨어에 서명하기 위해 Sony가 사용한ECDA 개인 키의 회복을 발표했습니다.이번 공격은 Sony가 각 [15]시그니처에 대해 랜덤k를 생성하지 못했기 때문에 가능했습니다.를 생성하지 못했기 때문에 가능했습니다.
이 문제는 다음 설명에 따라 개인 키와 메시지해시로부터으로 k\k를 으로써 방지할 수 있습니다. RFC6979.이를 통해 kk는 H마다 다르며 x(\ x를 모르는 공격자에게는 예측할 수 .
또한 서명에 의한 정보 유출을 최소화하기 위해 kk를 선택한 DSA 및 ECDSA의 악의적인 구현이 생성될 수 있습니다.예를 들어, 오프라인 개인 키는 순수해 보이는 [16]서명만 릴리스한 완벽한 오프라인 장치에서 유출될 수 있습니다.
실장
다음은 DSA를 지원하는 암호화 라이브러리 목록입니다.
「 」를 참조해 주세요.
레퍼런스
- ^ a b Schneier, Bruce (1996). Applied Cryptography. ISBN 0-471-11709-9.
- ^ "FIPS PUB 186: Digital Signature Standard (DSS), 1994-05-19". qcsrc.nist.gov. Archived from the original on 2013-12-13.
- ^ a b c d "FIPS PUB 186-4: Digital Signature Standard (DSS), July 2013" (PDF). csrc.nist.gov.
- ^ "FIPS PUB 186-1: Digital Signature Standard (DSS), 1998-12-15" (PDF). csrc.nist.gov. Archived from the original (PDF) on 2013-12-26.
- ^ "FIPS PUB 186-2: Digital Signature Standard (DSS), 2000-01-27" (PDF). csrc.nist.gov.
- ^ "FIPS PUB 186-3: Digital Signature Standard (DSS), June 2009" (PDF). csrc.nist.gov.
- ^ "Digital Signature Standard (DSS)". U.S. Department of Commerce. 31 October 2019. Retrieved 21 July 2020.
- ^ David W. Kravitz 박사 2013년 1월 9일 Wayback Machine에서 아카이브
- ^ 베르너 코흐."DSA 및 특허"
- ^ "1994 Annual Report of CSSPAB". 26 August 2009. Archived from the original on 26 August 2009.
- ^ "FIPS PUB 180-4: Secure Hash Standard (SHS), March 2012" (PDF). csrc.nist.gov.
- ^ "NIST Special Publication 800-57" (PDF). csrc.nist.gov. Archived from the original (PDF) on 2014-06-06.
- ^ "The Debian PGP disaster that almost was". root labs rdist.
- ^ kk-값 요건
- ^ Bendel, Mike (2010-12-29). "Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access". Exophase.com. Retrieved 2011-01-05.
- ^ Verbücheln, Stephan (2 January 2015). "How Perfect Offline Wallets Can Still Leak Bitcoin Private Keys". arXiv:1501.00447 [cs.CR].