RSA 암호[RSA cryptosystem]

RSA 암호[RSA cryptosystem]

 이 글은 RSA 암호 과정 및 증명 그리고 필요한 모든 정리를 다룬다. (유클리드 알고리즘 정리 및 증명, 페르마의 소정리, 오일러 정리)

그리고 암호 과정 전반에 필요한 소스코드(c++)를 포함한다.

개요

 공개 키 암호 방식 중 하나이며 널리 쓰이는 함호 방식이다. 대칭키 암호방식과 다르게 암호화 할 때와 복호화 할 때 사용하는 키가 다른 비대칭 암호 방식이다.

그리고 RSA 암호시스템은 일반적인 공개키 암호시스템과 다르게 공개키(public key)뿐만 아니라 개인키(private key)로 암호화하여 공개키(public key)로 복호화 할 수 있다. 

키 생성

① 서로 다르며 큰 두 소수 p, q를 고른다. 그리고 p, q에 대해 아래 값을 구한다. ( φ(n)은  오일러 피 함수이다.)

② 아래 식을 만족하는 e를 구한다. (여러 e 값들 중에서 하나 임의로 선택)

③ 아래 식을 만족하는 d를 구한다. (확장된 유클리드 알고리즘 이용)

④ 공개키는 <n, e>이며 개인키는 <n, d>이다. (p, q, φ(n) 값은 보안상 파기)

확장된 유클리드 알고리즘

 먼저 유클리드 알고리즘은 두 개의 자연수의 최대공약수를 구하는 알고리즘 중 하나다. 정의는 "두 수 a, b (b > a)의 최대공약수는 a와 r(b를 a로 나눈 나머지)의 최대공약수와 같다" 이다.

- 유클리드 알고리즘 증명

① 정의를 식으로 나타내면 아래와 같다. (gcd는 최대공약수 의미)

② gcd(a, b) = G 그리고 a = G*α, b = G*β를 만족하는 자연수 α, β에 대해 아래식으로 정리. (α와  β는 서로소)

③ 위 식을 통해 G는 r의 약수임을 확인. β-α*q가 α와 서로소임을 증명하면 gcd(a, r) = G이므로 증명 끝.

 여기서 β-α*q와 α의 최대공약수 M이 α와 β의 약수임을 알 수 있다. 그리고 α와 β는 서로소이므로 M = 1이다.

따라서  β-α*q와 α도 서로소이다.

 유클리드 알고리즘을 반복해서 이용하면 두 자연수의 최대공약수를 간단하게 구할 수 있다. 코드로 나타내면 아래와 같다.

uint32_t gcd(uint32_t a, uint32_t b) {
    if (b > a) swap(a, b);
    if (a % b == 0) return b;
    return gcd(b, a % b);
}

 위 코드는 φ(n)와 서로소인 e값 들을 구하는데 쓰이며 e*d ≡ 1 (mod φ(n))을 만족하는 d를 구하기 위해선 확장된 유클리드 알고리즘이 필요하다. 확장된 유클리드 알고리즘이란 a, b의 최대공약수를 유클리드 알고리즘을 이용하여 구할 때 반복되는 식을 정리해서 a*x + b*y = gcd(a, b)를 만족하는 정수 x, y를 구하는 것이다.

 a, b의 최대공약수를 구하는 과정은 위와 같이 표현할 수 있으며 rn이 gcd(a, b)이다. 여기서 q값 들은 각 스탭별 구할 수 있는 상수이므로 r값들은 a, b로 풀어서 표현할 수 있다.

 이렇게 보면 계산과정이 복잡해 보이지만 a, b의 계수들을 상수 s, t들로 표현해보면

 이와 같으며 이를 코드로 표현하면 다음과 같다.

// 유클리드 호제법 확장
// a*x + b*y = gcd(a, b), a < b 일 때 정수 x, y를 반환
std::pair<int64_t, int64_t> xgcd(int64_t a, int64_t b) {
    int64_t x[3] = {0, 1, 1}, y[3] = {1, 0, 0};

    while (b % a) {
        int64_t q = b / a;

        x[2] = x[0] - q*x[1];
        y[2] = y[0] - q*y[1];

        x[0] = x[1]; x[1] = x[2];
        y[0] = y[1]; y[1] = y[2];

        int64_t rest = b % a;
        b = a;
        a = rest;
    }

    return std::make_pair(x[2], y[2]);
}

// 재귀적으로 구하는 함수
std::pair<int64_t, int64_t> xgcd2(int64_t a, int64_t b) {
    if (a == 0)
        return std::make_pair(0, 1);

    auto next = xgcd2(b % a, a);

    int64_t x = next.first;
    int64_t y = next.second;

    return std::make_pair(y - (b/a)*x, x);
}

 이 코드는 키 생성과정의 e*d ≡ 1 (mod φ(n))에서 d를 구하는데 쓰인다. a*x + b*y = gcd(a, b) 에서 a는 e, b는 φ(n)이면 gcd(a, b) = gcd(e,  φ(n)) = 1 이다.

따라서 d값은 위 xgcd 함수에서 반환한 x값에서 mod φ(n)으로 나머지 연산한 값이다.

 

 필자는 나머지 연산에서 역원을 구하는 것이므로 오일러 정리를 이용하면 편하게 구할 수 있지 않을까 생각했었다. 하지만 오일러 정리를 이용하면 d ≡ e^(φ(φ(n))) 이 되는데 이는 φ(n)에 대한  오일러 피 함수를 구해야 함을 뜻한다. φ(n)은 (p-1)*(q-1)이고 p, q는 아주 큰 소수이므로 φ(n)은 아주 큰 두 짝수의 곱이 된다. 따라서 φ(φ(n))를 구하는 비용은 매우 커서 확장된 유클리드 알고리즘을 이용해서 d값을 구하는 편이 더 쉽다.

암호화 및 복호화 과정

 전송하려는 메시지를 특정 길이로 잘라서 정수로 표현했을 때 n보다 작은 값이 되도록 한다.

정수로 표현한 특정 메시지를 m이라 할 때 공개키 <n, e>로 암호화한 메시지 c값은 아래 식으로 구한다.

 전달받은 메시지 c는 개인키 <n, d>로 아래와 같이 복호화 한다.

 공개키 및 개인키에 포함된 n은 나머지 연산에 쓰이며 e, d는 지수로 쓰인다. 위 과정은 아래 식이 참임을 전제로 한다. (아래 RSA 증명 참고)

그리고 d를 먼저 사용하여 암호화한 메시지를 만들 수 있기 때문에 개인키로 암호화하여 공개키로 복호화가 가능하다.

// base^exp를 거듭제곱을 통해 빠르게 구하는 코드
uint64_t fastPow(uint64_t base, uint64_t exp, uint32_t mod) {
    uint64_t result = 1;

    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result*base) % mod;
        }
        base = (base * base) % mod;
        exp = exp / 2;
    }
    return result;
}

RSA 증명

① RSA 증명은 다음 식이 참임을 증명하는 데 있다.

② d값은 아래 식으로 부터 나왔으며 따라서 e*d를  φ(n)으로 표현할 수 있다.

③ 오일러 정리에 의해 m과 n이 서로소일 때 ①번 식을 증명한다.

 사실 오일러 정리만을 이용하면 m이 p또는 q의 배수일 때 증명 못한다. 이 경우 대부분 위키에서 m이 p또는 q의 배수일 확률이 1/p + 1/q 이고 페르마의 소정리로 증명했기 때문에 넘어간다. RSA 논문에서도 페르마의 소정리를 이용하여 증명하였다.

④ 페르마의 소정리를 이용하려면 mod n을 mod p일 때 mod q일 때 나눠서 증명해야하며 이를 위해 아래 식이 성립함을 먼저 증명한다.

(이 증명의 일반화 및 자세한 내용은 중국인의 나머지 정리 참고)

 

if 조건에 따라 a - b는 p의 배수면서 q의 배수다. 그리고 p, q가 서로소라고 했으므로 a - b는 p*q의 배수이기도 하다.

따라서 위 조건에 따른 결과 식은 참이다. 이를 ①식에 적용하면 다음과 같다.

⑤ mod p, mod q에 대해 ①식이 참임을 증명하면 mod p*q에 대해 ①식이 참이다.

페르마의 소정리에 의해 아래 식은 참이다.

이를 적용하기 위해 ①식을 p, q에 대해 각각 정리하면

m이 mod p일 때 p의 배수이거나 mod q일 때 q의 배수일 때는 아래 식은 0이다. 따라서 모든 m에 대해 ①식은 참이다.

테스트 코드

 데이터를 특정길이로 나누고 n보다 작은 자연수로 변환하여 암호화, 복호화 과정을 진행해야 하지만 편의상 자연수를 받아서 처리하는 테스트 코드이다. (c++11 이상)

 https://github.com/JangTaeHwan/AlgorithmTraining/blob/master/Mathematical/rsa.cpp

심화

 RSA의 안정성 및 공격에 대한 글은 RSA - 리브레 위키에서 자세히 설명한다.

 이외에 필자는 공개키 하나에 개인키가 꼭 하나만 있는지 의문이 들었다. 즉 공개키를 먼저 하나 만들고 다음 만들 수 있는 개인키가 여러 개 있을 수 있다고 생각했다.

 이 가정이 맞으려면 위 식에서 특정 e에 대해 만족하는 d값이 여러 개 있어야 한다. (e와 φ(n)은 서로소)

하지만 페르마의 소정리나 오일러 정리의 증명 과정을 반복하다 보면 직관적으로 그럴 수 없다는 것을 안다.

증명과정에서 자주 등장했던 0 < i < j < φ(n) 일 때 i*e와 j*e이 mod φ(n)에서 같다고 가정하면 (j - i)*e 가 φ(n)의 배수여야 한다.

그런데 e가 φ(n)와 서로소이므로 j - i가 φ(n)의 배수여야 하지만 j-i < φ(n) 이기 때문에 j = i가 아니면 φ(n)의 배수가 아니다.

따라서 mod φ(n)에서 e*d는 모두 다른 값이 나오며 e*d ≡ 1 를 만족하는 d값은 유일하다.

 위에 따라 공개키<n, e>와 개인키<n, d>는 서로 유일하다.

마치며

 이번 포스팅은 증명해야할 것도 테스트 코드 작성 및 검증도 그리고 궁금한 점도 많아 꽤나 오래 작업했습니다. 큰 수의 소인수 분해가 어렵다는 것을 기반으로 둔 만큼 쇼어 알고리즘 등 공격 및 취약점에 관심이 있고 더 공부해보고 싶기도 합니다~ 하지만 지금은 기본적인 암호화 방식 및 수학적 알고리즘을 더 공부하고 포스팅 하겠습니다. 다음시간에는 안전한 해시 알고리즘으로 알려진 SHA에 대해 포스팅할까 합니다!