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

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

안녕하세요, 소프트웨어 공장의 독자 여러분! 오늘은 비대칭키 암호화 알고리즘 중 하나인 Paillier 암호화 알고리즘에 대해 이야기해보려고 합니다. 이 알고리즘은 특유의 동형성(homomorphism) 덕분에 암호화된 상태에서 연산이 가능하다는 점에서 주목받고 있는데요, 본 포스팅에서는 Paillier 암호화의 원리와 함께 Java 및 Linux C 언어로 구현하는 방법까지 살펴보겠습니다.

Paillier 암호화 알고리즘 소개

Paillier 암호화는 1999년 Pascal Paillier에 의해 개발된 공개 키 암호화 알고리즘입니다. 이 알고리즘은 특이하게도 동형암호화(Homomorphic Encryption)를 지원하는데, 이는 암호화된 데이터에 대한 산술 연산이 가능하다는 것을 의미합니다. 예를 들어, 두 숫자를 각각 암호화한 후 암호화된 상태에서 덧셈 연산을 수행하면, 결과값을 복호화하였을 때 실제 두 숫자의 덧셈 결과와 동일한 결과를 얻을 수 있습니다. 이러한 특성은 민감한 데이터에 대한 연산이 필요할 때 많은 이점을 제공합니다.

알고리즘의 기본 원리

Paillier 암호화 알고리즘은 다음과 같은 주요 단계로 구성됩니다:

1. 키 생성: 두 개의 소수 (p)와 (q)를 선택하고, (n = p \times q), (\lambda = lcm(p-1, q-1))을 계산합니다. 공개 키는 (n)이며, 개인 키는 (\lambda)입니다.
2. 암호화: 메시지 (m)을 암호화하려면 무작위 값 (r)을 선택하여 (c = (g^m \times r^n) \mod n^2)을 계산합니다. 여기서 (g)는 (n^2)에서 선택된 값입니다.
3. 복호화: 암호문 (c)를 복호화하려면, (m = \frac{L(c^{\lambda} \mod n^2)}{L(g^{\lambda} \mod n^2)} \mod n)을 계산합니다. 여기서 함수 (L(u) = \frac{u-1}{n}) 입니다.

Paillier 암호화의 핵심은 모듈러 연산과 동형성을 이용하여 암호화된 데이터를 그대로 연산할 수 있다는 것입니다.

Paillier 암호화 알고리즘의 특징

• 동형성: Paillier 암호화는 덧셈 동형성을 지원하여, 두 암호문을 곱하면 결과적으로 평문에 대한 덧셈이 이루어진 결과를 얻을 수 있습니다.
• 비대칭 키 암호화: 공개 키를 이용해 데이터를 암호화하고, 개인 키를 이용해 데이터를 복호화합니다. 이로 인해 공개적으로 데이터를 암호화할 수 있지만, 복호화는 오직 키 소유자만이 가능합니다.

Java로 Paillier 암호화 구현하기

아래는 Java 언어를 사용하여 Paillier 암호화를 구현한 예제 코드입니다. 이 코드는 키 생성, 암호화, 복호화 기능을 제공합니다.

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

public class Paillier {
    private BigInteger p, q, n, nsquare, g, lambda;
    private int bitLength;

    public Paillier(int bitLengthVal) {
        this.bitLength = bitLengthVal;
        keyGeneration(bitLengthVal);
    }

    public void keyGeneration(int bitLengthVal) {
        SecureRandom random = new SecureRandom();
        p = new BigInteger(bitLengthVal / 2, 100, random);
        q = new BigInteger(bitLengthVal / 2, 100, random);
        n = p.multiply(q);
        nsquare = n.multiply(n);
        g = new BigInteger(bitLengthVal, random).mod(nsquare);
        lambda = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE)).divide(p.subtract(BigInteger.ONE).gcd(q.subtract(BigInteger.ONE)));
    }

    public BigInteger encryption(BigInteger m) {
        SecureRandom random = new SecureRandom();
        BigInteger r = new BigInteger(bitLength, random).mod(n);
        return g.modPow(m, nsquare).multiply(r.modPow(n, nsquare)).mod(nsquare);
    }

    public BigInteger decryption(BigInteger c) {
        BigInteger u = g.modPow(lambda, nsquare).subtract(BigInteger.ONE).divide(n).modInverse(n);
        return c.modPow(lambda, nsquare).subtract(BigInteger.ONE).divide(n).multiply(u).mod(n);
    }

    public static void main(String[] args) {
        Paillier paillier = new Paillier(512);
        BigInteger m = new BigInteger("12345");
        BigInteger c = paillier.encryption(m);
        System.out.println("암호문: " + c);
        System.out.println("복호화된 메시지: " + paillier.decryption(c));
    }
}

설명

• 키 생성: keyGeneration 메서드에서 두 개의 큰 소수 (p), (q)를 생성하고, 공개 키 (n)과 개인 키 (\lambda)를 계산합니다.
• 암호화: encryption 메서드는 메시지 (m)을 받아 무작위 값 (r)을 이용해 암호문 (c)를 생성합니다.
• 복호화: decryption 메서드는 암호문 (c)를 받아 원래의 메시지 (m)을 복호화합니다.

Linux C로 Paillier 암호화 구현하기

다음은 Linux 환경에서 사용할 수 있는 C 언어로 Paillier 암호화를 구현한 간단한 예제입니다. GNU MP Bignum 라이브러리를 사용하여 큰 정수 연산을 처리합니다.

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

void key_generation(mpz_t n, mpz_t g, mpz_t lambda, int bit_length) {
    mpz_t p, q;
    gmp_randstate_t state;
    gmp_randinit_default(state);
    gmp_randseed_ui(state, time(NULL));

    mpz_inits(p, q, NULL);
    mpz_urandomb(p, state, bit_length / 2);
    mpz_urandomb(q, state, bit_length / 2);
    mpz_mul(n, p, q);

    mpz_t p1, q1;
    mpz_inits(p1, q1, NULL);
    mpz_sub_ui(p1, p, 1);
    mpz_sub_ui(q1, q, 1);
    mpz_lcm(lambda, p1, q1);

    mpz_mul(n, p, q);
    mpz_mul(g, n, n);

    mpz_clears(p, q, p1, q1, NULL);
    gmp_randclear(state);
}

void encryption(mpz_t c, mpz_t m, mpz_t n, mpz_t g) {
    gmp_randstate_t state;
    gmp_randinit_default(state);
    gmp_randseed_ui(state, time(NULL));

    mpz_t r, nsquare;
    mpz_inits(r, nsquare, NULL);
    mpz_mul(nsquare, n, n);
    mpz_urandomm(r, state, n);

    mpz_t gm, rn;
    mpz_inits(gm, rn, NULL);
    mpz_powm(gm, g, m, nsquare);
    mpz_powm(rn, r, n, nsquare);
    mpz_mul(c, gm, rn);
    mpz_mod(c, c, nsquare);

    mpz_clears(r, nsquare, gm, rn, NULL);
    gmp_randclear(state);
}

int main() {
    mpz_t n, g, lambda, m, c;
    mpz_inits(n, g, lambda, m, c, NULL);

    int bit_length = 512;
    key_generation(n, g, lambda, bit_length);

    gmp_printf("Public Key (n): %Zd\n", n);
    gmp_printf("Public Key (g): %Zd\n", g);

    mpz_set_ui(m, 12345);
    encryption(c, m, n, g);
    gmp_printf("Ciphertext: %Zd\n", c);

    mpz_clears(n, g, lambda, m, c, NULL);
    return 0;
}

설명

• 키 생성: key_generation 함수에서 두 개의 큰 소수 (p), (q)를 생성하고, 공개 키 (n)과 개인 키 (\lambda)를 계산합니다.
• 암호화: encryption 함수는 메시지 (m)을 받아 암호문 (c)를 생성합니다.

마치며

Paillier 암호화 알고리즘은 동형성을 지원하기 때문에 데이터 프라이버시를 유지하면서도 연산이 필요한 다양한 분야에서 매우 유용하게 사용될 수 있습니다. 특히 금융 데이터나 개인 정보와 같은 민감한 데이터를 다루는 경우, 이러한 암호화 방식은 강력한 보안을 제공합니다.

이번 포스팅에서는 Paillier 암호화 알고리즘의 기본 개념과 함께 Java와 Linux C 언어를 이용한 구현 방법을 소개해드렸습니다. 알고리즘의 동작 원리를 이해하고 직접 구현해보면서 암호화 기술에 대한 이해를 높이시길 바랍니다.

다음에도 흥미로운 암호화 알고리즘과 그 구현 방법에 대해 다루어보도록 하겠습니다.