ElGamal 비대칭키 암호화 알고리즘

ElGamal 비대칭키 암호화 알고리즘

오늘은 비대칭키 암호화 알고리즘 중 하나인 ElGamal 암호화 알고리즘에 대해 알아보겠습니다. ElGamal 암호화는 보안성과 유연성을 제공하는 알고리즘으로, 특히 디지털 서명과 키 교환에 사용됩니다. 이번 포스팅에서는 ElGamal 암호화의 개념을 설명하고, JAVA와 Linux C 언어로 구현된 예제를 공유하겠습니다.

ElGamal 암호화 알고리즘이란?

ElGamal 암호화는 1985년 Taher ElGamal이 제안한 공개 키 암호 시스템입니다. 이 알고리즘은 디피-헬만 키 교환 방식에 기초하며, 큰 소수를 기반으로 한 난수 생성과 지수 연산을 사용하여 보안성을 유지합니다. ElGamal은 암호화, 복호화, 서명 생성 및 검증에 모두 사용할 수 있으며, RSA에 비해 더 큰 키 크기가 필요하지만 보안성 측면에서는 매우 강력한 방법입니다.

ElGamal 암호화의 기본 개념

ElGamal 암호화의 과정은 크게 세 단계로 나눌 수 있습니다.

1. 키 생성
   • 큰 소수 ( p )를 선택하고, 그에 대한 원시 원소 ( g )를 선택합니다.
   • 비밀 키 ( x )는 ( 1 < x < p-1 ) 사이의 임의의 정수로 선택됩니다.
   • 공개 키 ( y )는 ( y = g^x \mod p )로 계산됩니다. 공개 키는 ( (p, g, y) )이고 비밀 키는 ( x )입니다.
2. 암호화
   • 메시지 ( m )을 암호화하려면, 임의의 정수 ( k )를 선택합니다 (( 1 < k < p-1 )).
   • 암호문 ( (c_1, c_2) )는 다음과 같이 계산됩니다.
     • ( c_1 = g^k \mod p )
     • ( c_2 = m \cdot y^k \mod p )
3. 복호화
   • 암호문 ( (c_1, c_2) )를 복호화하려면 비밀 키 ( x )를 사용하여 다음과 같이 계산합니다.
     • ( m = c_2 \cdot (c_1^x)^{-1} \mod p )
   • 여기서 ( (c_1^x)^{-1} )는 ( c_1^x )의 모듈러 역원입니다.

JAVA로 구현된 ElGamal 암호화 예제

다음은 Java 언어를 사용하여 ElGamal 암호화 알고리즘을 구현한 예제 코드입니다. 이 코드는 키 생성, 암호화, 복호화 과정을 보여줍니다.

import java.math.BigInteger;
import java.security.SecureRandom;

public class ElGamal {
    private final BigInteger p, g, y, x;
    private final SecureRandom random = new SecureRandom();

    public ElGamal(int bitLength) {
        p = BigInteger.probablePrime(bitLength, random);
        g = new BigInteger(bitLength - 1, random).mod(p);
        x = new BigInteger(bitLength - 1, random).mod(p);
        y = g.modPow(x, p);
    }

    public BigInteger[] encrypt(BigInteger message) {
        BigInteger k = new BigInteger(p.bitLength() - 1, random);
        BigInteger c1 = g.modPow(k, p);
        BigInteger c2 = message.multiply(y.modPow(k, p)).mod(p);
        return new BigInteger[]{c1, c2};
    }

    public BigInteger decrypt(BigInteger[] cipherText) {
        BigInteger c1 = cipherText[0];
        BigInteger c2 = cipherText[1];
        BigInteger s = c1.modPow(x, p);
        BigInteger sInverse = s.modInverse(p);
        return c2.multiply(sInverse).mod(p);
    }

    public static void main(String[] args) {
        ElGamal elGamal = new ElGamal(512);
        BigInteger message = new BigInteger("123456789");

        BigInteger[] cipherText = elGamal.encrypt(message);
        System.out.println("Cipher Text: " + cipherText[0] + ", " + cipherText[1]);

        BigInteger decryptedMessage = elGamal.decrypt(cipherText);
        System.out.println("Decrypted Message: " + decryptedMessage);
    }
}

이 코드에서는 512비트 길이의 소수 ( p )와 그에 대한 공개 키와 비밀 키를 생성한 후, 주어진 메시지를 암호화하고 복호화하는 과정을 보여줍니다.

Linux C 언어로 구현된 ElGamal 암호화 예제

다음은 C 언어를 사용하여 ElGamal 암호화를 구현한 간단한 예제입니다. 이 코드는 GNU MP Bignum 라이브러리(GMP)를 사용하여 큰 수 연산을 처리합니다.

#include <gmp.h>
#include <stdio.h>
#include <stdlib.h>

void elgamal_keygen(mpz_t p, mpz_t g, mpz_t y, mpz_t x) {
    gmp_randstate_t state;
    gmp_randinit_default(state);
    mpz_urandomb(x, state, 512);
    mpz_urandomb(g, state, 511);
    mpz_nextprime(p, g);
    mpz_powm(y, g, x, p);
}

void elgamal_encrypt(mpz_t c1, mpz_t c2, const mpz_t m, const mpz_t p, const mpz_t g, const mpz_t y) {
    mpz_t k;
    mpz_init(k);
    gmp_randstate_t state;
    gmp_randinit_default(state);
    mpz_urandomb(k, state, 511);

    mpz_powm(c1, g, k, p);
    mpz_t yk;
    mpz_init(yk);
    mpz_powm(yk, y, k, p);
    mpz_mul(c2, m, yk);
    mpz_mod(c2, c2, p);

    mpz_clear(k);
    mpz_clear(yk);
}

void elgamal_decrypt(mpz_t m, const mpz_t c1, const mpz_t c2, const mpz_t p, const mpz_t x) {
    mpz_t s;
    mpz_init(s);
    mpz_powm(s, c1, x, p);

    mpz_t s_inv;
    mpz_init(s_inv);
    mpz_invert(s_inv, s, p);

    mpz_mul(m, c2, s_inv);
    mpz_mod(m, m, p);

    mpz_clear(s);
    mpz_clear(s_inv);
}

int main() {
    mpz_t p, g, y, x, m, c1, c2, decrypted_m;
    mpz_inits(p, g, y, x, m, c1, c2, decrypted_m, NULL);

    // 키 생성
    elgamal_keygen(p, g, y, x);

    // 메시지 설정
    mpz_set_ui(m, 123456789);

    // 암호화
    elgamal_encrypt(c1, c2, m, p, g, y);
    gmp_printf("Cipher Text: (%Zd, %Zd)\n", c1, c2);

    // 복호화
    elgamal_decrypt(decrypted_m, c1, c2, p, x);
    gmp_printf("Decrypted Message: %Zd\n", decrypted_m);

    mpz_clears(p, g, y, x, m, c1, c2, decrypted_m, NULL);
    return 0;
}

이 C 코드에서는 GMP 라이브러리를 사용하여 큰 수 연산을 처리하며, 키 생성, 암호화, 복호화의 과정을 포함하고 있습니다. 각 단계에서 큰 소수와 난수를 사용하여 보안성을 유지합니다.

마무리

ElGamal 암호화 알고리즘은 높은 보안성을 제공하지만, 큰 키 크기를 요구하기 때문에 연산 비용이 큽니다. RSA와 비교했을 때 키 교환과 디지털 서명 등에 더 적합하며, 현대 보안 시스템에서도 널리 사용됩니다. 이번 포스팅에서는 ElGamal 암호화의 기본 개념을 살펴보고, JAVA와 Linux C 언어를 사용하여 구현된 예제를 통해 실제로 어떻게 동작하는지 알아보았습니다.

ElGamal에 대한 더 깊은 이해를 위해 직접 구현해 보거나, 실생활의 적용 사례들을 조사해 보는 것을 추천드립니다. 다음 포스팅에서도 다양한 암호화 알고리즘을 다룰 예정이니 많은 관심 부탁드립니다!