ElGamal Digital Signature Mechanism
엘가말 전자서명 메커니즘
- 무결성을 보장하기 위한, 이산로그 기반 공개키 암호화 방식의 서명 메커니즘이다.
- 디피-헬만 키 교환 메커니즘보다 성능이 우수하다.
Mechanism (원리)
| Value | Description |
| \(p, g\) | - Public Values (공개된 값) |
| \(x\) | - \(A\)의 Private Key |
| \(y = g^x \; \mathrm{mod} \; p\) | - Public Signature Verification Key |
| \(M\) | - 평문 |
| \(m\) | - 평문을 수치화한 값 - Digest_Function을 통해 \(M\)을 \(m\)으로 변환한다. |
| \(k\) | - Random Key |
| \(r = g^k \; \mathrm{mod} \; p\) | - Random Number |
| \(s = k + mx \; \mathrm{mod} \; p-1\) | - Signature |
| \((M, r, s)\) | - 전송 대상 (메시지 원문과 두 계산값) |
- \((M, r, s)\)를 받은 수신측은
\(M\)을 Digest Function을 통해 \(m\)으로 변환하고,
\(g^s = r\cdot y^m \; \mathrm{mod} \; p\) 를 계산한다.
- 이 값이 true이면 Signature가 Valid한 것으로 간주한다.
\(g^s = g^{k+mx} = g^k\cdot g^{mx} = r \cdot(g^x)^m = r\cdot y^m \; \mathrm{mod} \; p\)
- 디피-헬만 키 교환 알고리즘과 마찬가지로,
공격자는 이 값을 통해 지수 역연산을 하여 \(x\)를 알아낼 수 없다.
Vulnerability of ElGamal Digital Signature Mechanism (엘가말 전자서명 메커니즘의 취약점)
- 엘가말 메커니즘은 Low-Modulus Attack과 Known-Plaintext Attack에 취약하다 알려져 있다.
- Low-Modulus Attack (작은 모듈러스 공격)
- \(p\)의 값이 충분히 크지 않으면
공격자가 Brute-Force(전수 조사)나 Discrete Logarithm(이산 로그)의 성질을 이용한 알고리즘을 통해
개인키 혹은 난수(\(r\))을 알아낼 수 있다.
- \(p\)는 적어도 2048bit 이상의 큰 값이어야 한다. - Known-Plaintext Attack (알려진 평문 공격)
Reference: Information Security: Principles and Practice 2nd Edition
(Mark Stamp 저, Pearson, 2011)
Reference: Computer Security: Principles and Practice 3rd Edition
(William Stallings, Lawrie Brown, Pearson, 2014)
Reference: 2022학년도 1학기 홍익대학교 네트워크 보안 강의, 이윤규 교수님
