본문 바로가기

Library/Cryptography

ElGamal Signature

ElGamal Encryption 또한 디지털 서명에 응용될 수 있다. 예를 들어, Alice가 어떤 메세지에 서명을 하려고 한다. 먼저, Alice는 큰 Prime Number p와 Primitive Root α를 선택한다. 그리고, 1 ≤ a ≤ p - 2인 a를 선택하고, β ≡ α^a (mod p)를 계산한다. a는 비밀로 유지해야 한다. 공개키는 (p, α, β)가 된다. Alice가 메세지 m에 서명하기 위해서, 다음의 과정을 따른다.

1. 공개되지 않은 임의의, gcd(k, p - 1) = 1을 만족하는 k를 선택한다.

2. r ≡ α^k (mod p) (0 < r < p)를 계산한다.

3. s ≡ k^(-1) * (m - ar) (mod p - 1)을 계산한다.

서명된 메세지는 (m, r, s)가 된다.


서명을 확인하고자 하는 Bob은 다음의 과정을 따른다.

1. Alice의 공개키 (p, α, β)를 가져온다.

2. v1 ≡ β^r * r^s (mod p)와, v2 ≡ α^m (mod p)를 계산한다.

3. v1 ≡ v2라면, 이 서명은 유효한 것으로 인정할 수 있다.


즉, s ≡ k^(-1) * (m - ar) (mod p - 1)이기 때문에, sk ≡ (m - ar) (mod p - 1)이다. 따라서, m = sk + ar이며, v2 ≡ α^m ≡ α^(sk + ar) ≡ (α^(a))^r * (α^(k))^s ≡ β^r * r^s ≡ v1 (mod p)이다.

만약, Eve가 a를 알아낼 수 있다면 Eve는 위조된 문서 m에 대해 Alice의 서명을 동일하게 할 수 있기 때문에, a를 비밀로 유지하는 것은 중요하다. 즉, 결과적으로 다음과 같은 문제가 되는데,

β^r * r^s ≡ α^m (mod p)

이것을 다시 정리해보면 r^s ≡ β^(-r) * α^m (mod p), 즉 discrete logarithm 문제가 되는데, discrete logarithm 문제를 해결하는 것은 어렵다고 알려져 있다.