길리랩blog

ElGamal 공개키 암호화의 구조와 운영 보안

ElGamal 공개키 암호의 이산 로그 기반 구조, 키 생성과 암복호화, 디지털 서명, RSA 비교 및 운영 보안 고려사항을 정리한다.

2026-08-14 · 최초 발행 2025-06-08

이산 로그 문제에서 출발한 공개키 암호

ElGamal은 타허 엘가멜(Taher ElGamal)이 1985년에 제안한 공개키 암호화 알고리즘이다. 비대칭 암호 방식이며, 이산 로그 문제(Discrete Logarithm Problem)를 계산하기 어렵다는 성질에 안전성을 둔다.

RSA와 함께 널리 쓰이는 공개키 암호 체계로 분류되며, 데이터 암호화뿐 아니라 디지털 서명과 키 교환을 포함한 보안 응용에 활용된다.

유한체(Finite Field)에서 주어진 (g)와 (h)에 대해 (g^x = h)를 만족하는 (x)를 찾는 문제가 이산 로그 문제다. 대형 소수에 대한 이산 로그는 현재의 계산 능력으로 해결하기 어려운 문제로 분류된다. ElGamal은 타원곡선 암호화(ECC)에도 적용할 수 있어 타원곡선 ElGamal 방식도 존재한다.

공개키를 만들고 암호문을 복원하는 흐름

키 생성에서는 먼저 큰 소수 (p)를 고르고, (p)의 원시근(primitive root) (g)를 정한다. 개인키 (x)를 선택한 뒤 (y = g^x \mod p)를 계산한다. 공개키는 ((p, g, y)), 개인키는 (x)다.

  1. 큰 소수 (p) 선택 (일반적으로 1024비트 이상)
  2. (p)에 대한 원시근 (g) 선택 ((1 < g < p))
  3. 개인키 (x) 선택 ((1 < x < p-1))
  4. (y = g^x \mod p) 계산
  5. 공개키: ((p, g, y)), 개인키: (x)

평문 (M)은 (0 < M < p)를 만족하는 정수로 변환한다. 이후 임의의 (k)를 선택해 두 값으로 이뤄진 암호문을 만든다.

  1. 메시지 (M)을 (0 < M < p)를 만족하는 정수로 변환
  2. 임의의 (k) 선택 ((1 < k < p-1))
  3. (a = g^k \mod p) 계산
  4. (b = M·y^k \mod p) 계산
  5. 암호문 (C = (a, b)) 생성

수신자는 개인키 (x)를 사용해 암호문 ((a, b))에서 평문을 복원한다.

  1. 암호문 (C = (a, b)) 수신
  2. (M = b·(a^x)^{-1} \mod p) 계산
    = (b·(a^x)^{-1} \mod p)
    = (M·y^k·(g^{(k·x)})^{-1} \mod p)
    = (M·g^{(k·x)}·(g^{(k·x)})^{-1} \mod p)
    = (M \mod p)
⤢✕수신자송신자수신자송신자키 생성- 소수 p, 원시근 g 선택- 개인키 x 선택- y = g^x mod p 계산- 공개키: (p, g, y)암호화- 메시지 M 준비- 랜덤 k 선택- a = g^k mod p 계산- b = M·y^k mod p 계산복호화- M = b·(a^x)^(-1) mod p 계산공개키(p, g, y) 전송암호문 (a, b) 전송

서명 체계로 확장되는 방식

ElGamal 암호화 알고리즘은 디지털 서명 체계로도 확장할 수 있다. 미국 DSA(Digital Signature Algorithm)의 기반이 된 알고리즘이기도 하다.

서명을 만들 때는 메시지 (M)의 해시값 (h(M))을 구하고, (gcd(k, p-1) = 1)을 만족하는 임시 키 (k)를 선택한다.

  1. 메시지 (M)에 대한 해시값 (h(M)) 계산
  2. 임시 키 (k) 선택 ((gcd(k, p-1) = 1))
  3. (r = g^k \mod p) 계산
  4. (s = (h(M) - x·r) · k^{-1} \mod (p-1)) 계산
  5. 서명 = ((r, s))

검증자는 (r)과 (s)의 범위를 확인한 뒤, 공개키를 이용해 두 계산값이 같은지 비교한다.

  1. (0 < r < p) 및 (0 < s < p-1) 확인
  2. (v1 = g^{h(M)} \mod p) 계산
  3. (v2 = y^r · r^s \mod p) 계산
  4. (v1 = v2)이면 서명 유효

RSA와 다른 선택 지점

특성 ElGamal RSA
안전성 기반 이산 로그 문제 소인수분해 문제
암호문 크기 평문의 2배 평문과 동일
연산 속도 상대적으로 느림 상대적으로 빠름
확률적 암호화 지원 (동일 평문도 다른 암호문) 기본적으로 미지원
특허 없음 (자유롭게 사용 가능) 특허 만료 (2000년)
표준 NIST DSA의 기반 PKCS, X.509 등 다수 표준 채택

ElGamal은 암호화할 때마다 임의의 (k)를 사용하므로, 같은 평문이라도 다른 암호문이 만들어진다. 반면 암호문은 원본 평문의 2배 크기가 되고 RSA보다 계산량이 많다는 점을 함께 고려해야 한다.

유한체와 타원곡선 등 다양한 수학적 구조에 적용할 수 있고 특허 제한 없이 구현할 수 있다. 다만 올바른 구현은 상대적으로 복잡하며, 부적절한 파라미터 선택은 취약점으로 이어질 수 있다.

적용되는 보안 시스템

PGP(Pretty Good Privacy)는 ElGamal을 선택적 암호화 알고리즘으로 지원하며 이메일 암호화와 디지털 서명에 활용한다. GNU Privacy Guard(GPG)는 OpenPGP 표준의 자유 소프트웨어 구현체로, ElGamal 암호화와 서명을 지원한다.

특정 SSL/TLS 암호 스위트에서도 ElGamal 기반 알고리즘을 사용하며 웹 통신 보안에 적용한다. 전자투표 시스템에서는 ElGamal의 준동형 암호화(homomorphic encryption) 특성을 이용해 투표 내용을 보호하면서 집계할 수 있다. 일부 암호화폐는 트랜잭션 서명에 ElGamal 기반 알고리즘을 활용한다.

구현에서 놓치기 쉬운 조건

소수 (p)는 최소 2048비트 이상을 사용하는 것이 권장되며, 보안 요구사항에 따라 3072비트 또는 그 이상으로 확장할 수 있다.

암호화와 서명에 쓰는 (k)는 암호학적으로 안전한 난수발생기(CSPRNG)로 생성해야 한다. 약한 난수는 개인키 노출 위험을 만든다. 또한 (p)가 실제 소수인지, (g)가 적절한 위수(order)를 갖는지도 검증 대상이다.

타이밍 공격과 전력 분석 공격 같은 부채널 공격을 고려해야 하며, 상수 시간(constant-time) 구현이 권장된다.

Python으로 본 암복호화 구조

import random
from sympy import isprime, mod_inverse

# 키 생성
def generate_keys(bits=1024):
    # 소수 p 생성
    while True:
        p = random.getrandbits(bits)
        if isprime(p):
            break

    # 원시근 g 찾기 (간단한 구현, 실제로는 더 복잡)
    g = 2

    # 개인키 x 생성
    x = random.randint(2, p-2)

    # 공개키 y 계산
    y = pow(g, x, p)

    return (p, g, y), x

# 암호화
def encrypt(public_key, message):
    p, g, y = public_key
    k = random.randint(2, p-2)
    a = pow(g, k, p)
    b = (message * pow(y, k, p)) % p
    return (a, b)

# 복호화
def decrypt(private_key, public_key, ciphertext):
    x = private_key
    p = public_key[0]
    a, b = ciphertext
    s = pow(a, x, p)
    m = (b * mod_inverse(s, p)) % p
    return m

# 예제 실행
if __name__ == "__main__":
    # 키 생성 (실제로는 더 큰 비트 수 사용)
    public_key, private_key = generate_keys(bits=64)

    # 메시지 (정수 형태)
    message = 12345

    # 암호화
    ciphertext = encrypt(public_key, message)
    print(f"암호문: {ciphertext}")

    # 복호화
    decrypted = decrypt(private_key, public_key, ciphertext)
    print(f"복호화된 메시지: {decrypted}")

양자 컴퓨팅 이후를 대비하는 과제

Shor 알고리즘은 이산 로그 문제를 다항 시간 내에 해결할 수 있으므로, 양자 컴퓨팅은 ElGamal에 위협이 된다. 격자 기반, 코드 기반, 다변수 다항식 기반 암호 등 포스트 양자 암호로의 전환이 필요한 이유다.

기존 ElGamal과 양자 내성 암호화 기법을 병행하는 하이브리드 접근법도 가능하다. 더 짧은 키 길이로 동등한 보안성을 제공하는 ECEG(Elliptic Curve ElGamal)의 활용도 증가하고 있다. 디지털 트랜스포메이션과 정보보호 강화 추세에 따라 암호화 알고리즘의 중요성은 계속 증가할 전망이다.

ElGamal공개키 암호이산 로그디지털 서명암호학