[9-5] The Digital Signature Algorithm

미국 국립표준기술원은 1991년 디지털 서명 알고리즘(DSA)을 제안했고 1994년 이를 표준으로 채택했다.

 

이 케이스에서 해시 함수는 160bit output을 가지고 메세지 m이 이미 해시되었다는 가정 하에 그 output에 서명을 진행하려고 한다.

 

DSA용 키 생성에 대해서 알아보자

먼저 초기화 단계가 있다.

1. 엘리스는 160bit 길이의 소수 q를 찾고 q|p-1를 만족하는소수 p를 찾는다. 이산 로그 문제는 p의 선택에 대해서 어려워야한다. (초기 버전에서 p는 512bit를 가졌고 이후 버전의 알고리즘은 더 긴 소수를 허용한다.)

2. mod p에 대해서 g를 원시근으로 하고, alpha는

를 만족하고 그러면

 

이 된다.

3. 엘리스는 1 <= a <= q-1인 비밀키 a를 골라서 beta ≡ alpha^a(mod p)를 계산한다.

4. 엘리스는 (p, q, alpha, beta)-공개키를 게시하고 a를 비밀로 유지한다.

 

엘리스가 m에 대해서 sign하는 과정에 대해서 알아보자

1. 랜덤으로 0 < k < q-1을 만족하는 시크릿 키인 k를 선택한다.

2.

 

를 계산한다.

3.

를 계산한다.

 

4. m에 대한 엘리스의 서명이 (r, s)이고 m과 함께 bob에게 보낸다.

 

밥이 증명하는 과정을 알아보자

1. 엘리스의 공개키인 (p, q, alpha, beta)를 다운받는다.

2.

를 계산한다.

 

3.

를 계산한다.

 

4. v = r인 경우에만 서명을 승인한다.

 

*증명

엘리스가 m에 대해서 sign하는 과정의 3번째 수식에서 우리는 m ≡ (-ar + ks) (mod q) 을 얻을 수 있었고 이는

s^-1*m ≡ (-ar*s^-1+k) (mod q)이다. 즉 k ≡ s^-1*m +ar*s^-1이고 이는 u(1)+au(2)이다.(밥이 증명하는 과정 2번째 내용)

이다. (beta ≡ alpha^a(mod p)이기 때문) 그래서 v = r이 된다.

 

 

ElGamal에서처럼 정수 a는 비밀로 유지해야한다. a에 대해서 knowledge가 있는 사람은 자신이 원하는 문서에 서명할 수 있다. 또 k값이 두번 사용된다면 동일한 절차에 의해 a를 찾는 것이 가능하다.

그리고 ElGamal과 대조적으로 정수 r은 k에 대한 전체 정보를 포함하지 않는다. 그래서 r을 알면 그냥 mod q의 value만 찾을 수 있다. 

원시근을 사용하는 것보다 alpha^q ≡ 1 (mod p)를 사용하는 것의 이점은 a에 대한 mod q정보를 제외하고 모든 정보를 제거해 문제를 방지한다는 것이다.

▼문제

이산 로그 문제를 해결하기 위한 Pohlig-hellman 공격을 다시 생각해보자.

그 공격은 mod p - 1이 작은 수로 이루어졌다면 가능하지만 큰 소수 q와 같은 경우에는 불가능하다.

ElGamal에서 공격자는 a (mod 2^t), (2^t 가  p - 1을 나누는 2의 거듭제곱) 를 결정할 수 있다. 이것은 a를 찾는 데 근접하지 않지만 일반적인 철학, 진리는 이런 작은 정보들이 모이면 집합적으로 유용할 수 있다는 것이다. 

ElGamal는 검증 단계에서 3개의 modular exponentiations 가 필요했는데 DSA에서는 2개의 모듈식 지수만 필요하게 수정되었다.  modular exponentiation이 계산의 느린 부분 중 하나이기 때문에 이 변경으로 검증 속도가 ElGamal보다 빨라졌다.