암호학 - 소수 판별

프로그래밍 입문 단계에서 흔히들 과제로 많이 접해보는 문제이다.

특정 수를 입력했을때 이녀석이 소수인지 아닌지 판별하는 알고리즘을 짜보라는 식의 과제.

만약 여러분이라면 어떻게 풀겠는가?

#include <stdio.h>
 
int main()
{
    int i, a;
 
    a = 12312313; /*임의의 수를 입력 받는다. (귀찮)*/
 
    for ( i=2 ; i<a ; i++ ){
        if ( a % i == 0 ){ /*일단 어떤 수랑 딱 맞게 나누어 떨어지면 소수 아님*/
            printf("%d 는 소수가 아닙니다.", a);
            return 0;
        }
    }
 
    /* 2부터 a까지 모두 다 나눠봐도 딱 맞게 나누어 떨어지지 않으면 소수임*/
    printf("%d 는 소수 입니다.", a);
    return 0;
}

하지만 이건 어디까지나 언어의 학습을 위한 기초적인 코드에 불과하다. 이런걸 실무에 써먹을수는 없다. 암호학에 사용되는 숫자들은 단위부터가 다르다. 최적화랍시고 홀수로만 나눠본다거나, 대상 숫자의 제곱근까지만 나눠본다 하더라도 너무 느리다.

그렇다면 실제 업계에서 사용되는 암호화 라이브러리는 어떤식으로 소수 판정을 할까?

전 세계 보안을 책임지는 대표적인 암호학 라이브러리 OpenSSL

 

OpenSSL 에서는 일반화 리만 가설이 맞다는 가정하에서 출발한다. (아직 이 난제는 증명되진 않았으나, 관측된 데이터에 따르면 참으로 보인다.)

OpenSSL의 bn.h 헤더파일의 모습

코드를 잘 살펴보면 빅넘버 계열 함수들이 정의된 헤더파일을 열어볼 수 있다. bn.h 파일을 보면 소수를 생성하는 함수와, 특정 정수가 소수인지 판별하는 함수를 볼 수 있다. 이 함수의 내부를 들여다보면

 

probable_prime 계열 함수로 "아마도 소수일것 같은" 랜덤한 수를 생성하는것을 볼 수 있다. 일단 큰 수를 뽑고나서 1의 자리가 5가 아니면서 짝수도 아니면 일단 소수처럼 보이지 않나? ㅋㅋㅋ 나름대로 가라를 치는 셈이다.

그렇게 가라친 수를 BN_is_prime_fasttest_ex 함수를 호출해, 이놈이 진짜 소수인지 판별하는식이다.

자, 그러면 BN_is_prime_fasttest_ex 함수도 들어가보자.

결과적으로는, 밀러-라빈 소수판별 알고리즘을 사용한다.

ko.wikipedia.org/wiki/%EB%B0%80%EB%9F%AC-%EB%9D%BC%EB%B9%88_%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95

밀러-라빈 소수판별법 - 위키백과, 우리 모두의 백과사전

일반화 리만 가설이 참이라면, 이 수가 소수인지 검사하기 위해서 "이거랑 이거랑 이것! 에 대해서만 검사해도 충분하다!" 라는 느낌으로 검사에 필요한 연산횟수를 획기적으로 단축시키는것이다. 수학적인 소양은 없으므로 여기서 말을 아낀다...

OpenSSL의 밀러-라빈 판별 코드는 다음과 같다.

/*
 * Refer to FIPS 186-4 C.3.2 Enhanced Miller-Rabin Probabilistic Primality Test.
 * OR C.3.1 Miller-Rabin Probabilistic Primality Test (if enhanced is zero).
 * The Step numbers listed in the code refer to the enhanced case.
 *
 * if enhanced is set, then status returns one of the following:
 *     BN_PRIMETEST_PROBABLY_PRIME
 *     BN_PRIMETEST_COMPOSITE_WITH_FACTOR
 *     BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME
 * if enhanced is zero, then status returns either
 *     BN_PRIMETEST_PROBABLY_PRIME or
 *     BN_PRIMETEST_COMPOSITE
 *
 * returns 0 if there was an error, otherwise it returns 1.
 */
int bn_miller_rabin_is_prime(const BIGNUM *w, int iterations, BN_CTX *ctx,
                             BN_GENCB *cb, int enhanced, int *status)
{
    int i, j, a, ret = 0;
    BIGNUM *g, *w1, *w3, *x, *m, *z, *b;
    BN_MONT_CTX *mont = NULL;
 
    /* w must be odd */
    if (!BN_is_odd(w))
        return 0;
 
    BN_CTX_start(ctx);
    g = BN_CTX_get(ctx);
    w1 = BN_CTX_get(ctx);
    w3 = BN_CTX_get(ctx);
    x = BN_CTX_get(ctx);
    m = BN_CTX_get(ctx);
    z = BN_CTX_get(ctx);
    b = BN_CTX_get(ctx);
 
    if (!(b != NULL
            /* w1 := w - 1 */
            && BN_copy(w1, w)
            && BN_sub_word(w1, 1)
            /* w3 := w - 3 */
            && BN_copy(w3, w)
            && BN_sub_word(w3, 3)))
        goto err;
 
    /* check w is larger than 3, otherwise the random b will be too small */
    if (BN_is_zero(w3) || BN_is_negative(w3))
        goto err;
 
    /* (Step 1) Calculate largest integer 'a' such that 2^a divides w-1 */
    a = 1;
    while (!BN_is_bit_set(w1, a))
        a++;
    /* (Step 2) m = (w-1) / 2^a */
    if (!BN_rshift(m, w1, a))
        goto err;
 
    /* Montgomery setup for computations mod a */
    mont = BN_MONT_CTX_new();
    if (mont == NULL || !BN_MONT_CTX_set(mont, w, ctx))
        goto err;
 
    if (iterations == BN_prime_checks)
        iterations = BN_prime_checks_for_size(BN_num_bits(w));
 
    /* (Step 4) */
    for (i = 0; i < iterations; ++i) {
        /* (Step 4.1) obtain a Random string of bits b where 1 < b < w-1 */
        if (!BN_priv_rand_range_ex(b, w3, ctx)
                || !BN_add_word(b, 2)) /* 1 < b < w-1 */
            goto err;
 
        if (enhanced) {
            /* (Step 4.3) */
            if (!BN_gcd(g, b, w, ctx))
                goto err;
            /* (Step 4.4) */
            if (!BN_is_one(g)) {
                *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR;
                ret = 1;
                goto err;
            }
        }
        /* (Step 4.5) z = b^m mod w */
        if (!BN_mod_exp_mont(z, b, m, w, ctx, mont))
            goto err;
        /* (Step 4.6) if (z = 1 or z = w-1) */
        if (BN_is_one(z) || BN_cmp(z, w1) == 0)
            goto outer_loop;
        /* (Step 4.7) for j = 1 to a-1 */
        for (j = 1; j < a ; ++j) {
            /* (Step 4.7.1 - 4.7.2) x = z. z = x^2 mod w */
            if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx))
                goto err;
            /* (Step 4.7.3) */
            if (BN_cmp(z, w1) == 0)
                goto outer_loop;
            /* (Step 4.7.4) */
            if (BN_is_one(z))
                goto composite;
        }
        /* At this point z = b^((w-1)/2) mod w */
        /* (Steps 4.8 - 4.9) x = z, z = x^2 mod w */
        if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx))
            goto err;
        /* (Step 4.10) */
        if (BN_is_one(z))
            goto composite;
        /* (Step 4.11) x = b^(w-1) mod w */
        if (!BN_copy(x, z))
            goto err;
composite:
        if (enhanced) {
            /* (Step 4.1.2) g = GCD(x-1, w) */
            if (!BN_sub_word(x, 1) || !BN_gcd(g, x, w, ctx))
                goto err;
            /* (Steps 4.1.3 - 4.1.4) */
            if (BN_is_one(g))
                *status = BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME;
            else
                *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR;
        } else {
            *status = BN_PRIMETEST_COMPOSITE;
        }
        ret = 1;
        goto err;
outer_loop: ;
        /* (Step 4.1.5) */
        if (!BN_GENCB_call(cb, 1, i))
            goto err;
    }
    /* (Step 5) */
    *status = BN_PRIMETEST_PROBABLY_PRIME;
    ret = 1;
err:
    BN_clear(g);
    BN_clear(w1);
    BN_clear(w3);
    BN_clear(x);
    BN_clear(m);
    BN_clear(z);
    BN_clear(b);
    BN_CTX_end(ctx);
    BN_MONT_CTX_free(mont);
    return ret;
}
 

OpenSSL만의 빅넘버 함수들로 정직하게 구현 되어있다.

이 판정법이 끝나고, 성공적으로 반환하게되면 "아마도 이 수는 소수일것이다" 라는 다소 애매한 결과가 반환되는데, 이 판정법은 아까 "가라친 수" 의 조건과 겹치게되면 일반화 리만가설이 참이라는 가정하에, 소수임이 확정된다.

-> 2021.07.07 수정사항 : 밀러 라빈의 현재 알고리즘은 리만가설 기반이 아니다. 밀러의 알고리즘이 리만가설 기반의 결정론적 알고리즘이었고, 이후 라빈이 확률적 알고리즘으로 수정했다. 따라서 지정한 정확도만큼만 반복해서 충분히 소수임을 신뢰 할 수 있을때까지 반복하는 방식이 지금의 밀러라빈 판정법이다.

숫자를 가라칠때도 마구잡이로 가라치는게 아닌 셈이다.

대충 이런 조건에 부합하는 수를 생성하는 모양이다. 이 조건으로 만들어진 "가라 소수"가 밀러-라빈 판정도 통과하면 그때는 암호학적으로 실제로 사용 할 수 있는 정수임이 보증된다.

이런 작업으로 소수 p와 q를 구해 RSA 시스템을 구현 할 수 있다.

 

RSA를 간단하게나마 만들어 보고 싶다면, 아래의 블로그 글이 어느정도 도움이 될 것이다.

hwan001.tistory.com/75?category=903645

[암호화] RSA C로 구현하기?