C언어로 RSA 암호화 프로그램 만들기

 

RSA는 대표적인 비대칭 키 암호화 기법이다. SSL/TSL에 가장 많이 사용되는 비대칭 키 암호화 알고리즘이라고 한다. 

 

비대칭 키 암호화 방식은 암호화와 복호화에 사용하는 키가 서로 다르다. 따라서 하나는 공개해서 공개키(public key)로 사용하고 다른 하나는 개인이 비밀로 가지고 있어 개인 키(private key)라 부른다. 이렇게 되면 공개 키로 암호화한 내용은 개인키로만, 개인키로 암호화한 내용은 공개키로만 해독할 수 있다. 

 

RSA 암호화는 엄청 큰 숫자는 소인수분해하기 힘들다는 것을 이용하여 암호화한다. 두 소수를 곱하는 것은 누구나 할 수 있는 쉬운 연산이지만 두 소수를 곱한 값에서 그 소수를 찾아내는 것은 어렵다.

예를 들어 22,637 곱하기 58,391은 1,321,797,067이지만 1,321,797,067이 무얼 곱해서 만들어졌는지는 알기 힘들다.

 

RSA-2048은 1024비트 소수를 2개 사용하는데 무려 308자리 숫자라니 이를 알아내기란 사실상 불가능하다. 

 

RSA 방식으로 암호화하기 위해선 먼저 키를 만들어야 한다. 그 과정은 다음과 같다.

 

1. 매우 큰 두 소수  p , q를 준비한다.
2. p - 1, q - 1과 각각 서로소인 정수 e를 준비한다.
3. ed를 (p - 1)(q - 1)으로 나눈 나머지가 1이 되도록 하는 d를 찾는다.
4. n = pq를 계산한 후, n과 e를 공개한다. 이들이 바로 공개키이다. 한편 d는 숨겨두는데, 이 수가 바로 개인키이다.
5. 이제 p, q, (p-1)(q-1)는 필요 없거니와 있어 봐야 보안에 오히려 문제를 일으킬 수 있으니, 파기한다.

복잡하지만 요약하자면 키 생성 과정은 매우 큰 두 소수 p와 q를 이용해 n, e, d를 계산하는 과정이다. 그 중 n과 e를 공개키로 사용하고 d를 개인키로 사용한다. 

 

n과 e를 이용하여 다음과 같이 암호화 할 수 있다.

매우 간단하다. 여기서 m은 원문(암호화 하려는 대상)이고 c는 암호문이다. 여기서 반드시 m < n이어야 한다. 

 

암호화문은 다음과 같이 복호화 할 수 있다.

이 역시도 간단하다. 어떻게 이게 가능한지 다시봐도 신기하다. 이게 가능하도록 키 생성 방식을 고안한 Ron Rivest, Adi Shamir, Leonard Adleman에게 respect..

 

이제 이를 어떻게 코드로 구현할지 살펴보자. 여러 언어로 구현할 수 있겠지만 C로 구현하는 방법이 궁금했다. 매우 큰 두 소수를 이용해야 되는데 이를 어떻게 처리할지. 

 

지금까지 검색한 결과 GMP를 사용하는 게 최선인거 같다. GMP는 The GNU Multiple Precision Arithmetic Library의 약자로 암호학 등에 사용하는 고정밀 연산을 제공한다. 오픈소스이므로 주의해서 사용하자.

 

rsa 구현 코드는 https://gist.github.com/akosma/865b887f993de462369a04f4e81596b8 을 참고하였다. 

 

wsl2, Ubuntu 20.04 LTS에서 실행하였다. gmp.h가 설치 되어 있지 않다면 다음의 방식으로 설치하면 된다.

yum install  libgmp3-dev

apt-get install  libgmp3-dev

 

먼저, GMP에서 int형(multiple precision int) 변수를 선언하기 위해서는 mpt_t를 사용한다. mpz_t 데이터는 사용하기 전에 초기화를 해줘야 한다.

int main() {
    mpz_t msg, n, d, e;
	
    mpz_init_set_ui(msg, 123);
    mpz_init_set_ui(n, 323);
    mpz_init_set_ui(e, 5);
    mpz_init_set_ui(d, 29);
    display_gmp(msg, n, e, d);
    
   }

암복호화 과정을 살펴보자. 암호화 과정에는 암호화 할 원문 msg와 n과 e가 필요했다. 복호화 시에는 암호문 c와 n, d가 필요했다.

void encrypt(mpz_t encrypted, const mpz_t message, const mpz_t e, const mpz_t n) {
    mpz_powm(encrypted, message, e, n);
}

void decrypt(mpz_t original, const mpz_t encrypted, const mpz_t d, const mpz_t n) {
    mpz_powm(original, encrypted, d, n);
}

mpz_powm 함수는 암복호화 과정에서 필요한 지수 연산과 나머지 연산을 한번에 해준다. (powm = pow + modulo)

mpz_powm(encrypted, message, e, n) 이면 변수 encryped에  message를 e승한 것을 n으로 나눈 나머지가 저장된다.

 

 

이제 키 생성 부분을 살펴보자. 키 생성 과정은 위에서 살펴봤었다.

1. 매우 큰 두 소수  p , q를 준비한다.
2. p - 1, q - 1과 각각 서로소인 정수 e를 준비한다.
3. ed를 (p - 1)(q - 1)으로 나눈 나머지가 1이 되도록 하는 d를 찾는다.
4. n = pq를 계산한 후, n과 e를 공개한다. 이들이 바로 공개키이다. 한편 d는 숨겨두는데, 이 수가 바로 개인키이다.
5. 이제 p, q, (p-1)(q-1)는 필요 없거니와 있어 봐야 보안에 오히려 문제를 일으킬 수 있으니, 파기한다.

void rsa_keys(mpz_t n, mpz_t d, const mpz_t p, const mpz_t q, const mpz_t e) {
    mpz_mul(n, p, q);								

    mpz_t p_1, q_1, lambda, gcd, mul, mod;
    mpz_inits(p_1, q_1, lambda, gcd, mul, mod, NULL);
    mpz_sub_ui(p_1, p, 1);
    mpz_sub_ui(q_1, q, 1);
    mpz_lcm(lambda, p_1, q_1);

    printf("lambda = %s\n", mpz_get_str(NULL, 0, lambda));
    // e must be bigger than 1
    assert(mpz_cmp_ui(e, 1) > 0);

    // e must be smaller than lambda
    assert(mpz_cmp(lambda, e) > 0);

    // GCD(e, lambda) must be 1
    mpz_gcd(gcd, e, lambda);
    assert(mpz_cmp_ui(gcd, 1) == 0);

    mpz_invert(d, e, lambda);

    // e * d MOD lambda must be 1
    mpz_mul(mul, e, d);
    mpz_mod(mod, mul, lambda);
    assert(mpz_cmp_ui(mod, 1) == 0);

    mpz_clears(gcd, p_1, q_1, mul, mod, lambda, NULL);
}

재밌는 건 이 코드에서 p, q, e를 생성하는 코드는 작성하지 않았다는 점이다. 구현이 어려워서 그랬나? p, q는 보통 랜덤으로 큰 두수를 뽑고 그 수가 소수인지 판별하는 방식으로 찾는다고 한다. 소수가 나올 때 까지 반복해서 랜덤으로 수를 뽑는다. 

e는 lambda와 서로소인 값을 찾아야 되는데 1 < e < lambda 조건만 검사하였다.

 

2 : n = p * q

5: p_1에 p - 1 저장

6: q_1에 q - 1 저장

8: p-1과 q-1의 최소 공배수를 lambda에 저장

12, 15: 1 < e < lambda 조건 검사

21: e를 lambda로 나눈 나머지를 뒤집는다.

28: 메모리 할당을 해제한다

 

키 생성을 호출하는 함수는 다음과 같다.

void display_num(const number msg, const number pi, const number qi, const number ei) {
    printf("Initializing with p = %llu, q = %llu, e = %llu\n", pi, qi, ei);
    mpz_t n, d, p, q, e, original;
    mpz_init_set_ui(p, pi);
    mpz_init_set_ui(q, qi);
    mpz_init_set_ui(e, ei);
    mpz_init_set_ui(original, msg);
    mpz_inits(n, d, NULL);
    rsa_keys(n, d, p, q, e);

    display_gmp(original, n, e, d);
    mpz_clears(n, d, e, p, q, original, NULL);
}

다만 32 비트 보다 작은 수에 대해서는 이 함수를 호출하면 되지만 더 큰 수에 대해서는 사용할 수 없다.

 

32비트 보다 큰 수는 다음 함수를 호출한다.

void display_str(const char *msg, const char *pi, const char *qi, const char *ei) {
    printf("Initializing with p = %s, q = %s, e = %s\n", pi, qi, ei);
    mpz_t n, d, p, q, e, original;
    mpz_init_set_str(p, pi, 10);
    mpz_init_set_str(q, qi, 10);
    mpz_init_set_str(e, ei, 10);
    mpz_init_set_str(original, msg, 10);
    mpz_inits(n, d, NULL);
    rsa_keys(n, d, p, q, e);

    display_gmp(original, n, e, d);
    mpz_clears(n, d, e, p, q, original, NULL);
}

 

 

*reference 

RSA 암호화 나무위키

rsa 코드

POCU 알고리듬 및 자료구조 강의

[C언어] gmp.h를 이용한 RSA 프로그램 만들기