RSA( BOJ 13618 )

문제 : https://www.acmicpc.net/problem/13618

13618번: RSA

 

문제 파악하기

포르투갈 언어로 작성되어 있는 문제라 조금 읽기 어려웠지만, 단순히 RSA 알고리즘을 기반으로 만든 문제이기 때문에 문제를 푸는 데에는 큰 무리가 없습니다. 이 문제는 RSA 알고리즘으로 암호화된 값(C)을 복호화하는 문제입니다. 만약 RSA 알고리즘을 잘 모르겠다면 위키피디아의 설명을 먼저 읽어보면 쉽게 문제를 풀 수 있습니다.

 

우선 RSA 알고리즘에서 키를 생성하는 과정은 다음과 같습니다.

 

• 두 수를 곱하여 N = p*q( p와 q는 서로 다른 소수)를 찾는다.
• φ( N ) = ( p − 1 ) ( q − 1 ) 를 구한다.
• φ( N ) 보단 작고, φ( N ) 와 서로소인 정수 E (1 < E < φ( N ))를 찾는다.
• E 를 φ( N ) 으로 나누었을 때 나머지가 1인 정수 d를 구한다. ( E*d ≡ 1 ( mod φ( N ) )

이렇게 생성한 값을 가지고 공개키(N, e)와 비밀키(N, d)를 가지고 암호화/복호화를 할 수 있습니다. 우선 암호화는 공개키를 가지고 다음과 같이 진행합니다. (M은 원문, C는 암호화된 원문을 의미한다)

 

C = M^e (mod N)

 

암호화된 메세지를 복호화하기 위해서는 다음 과정을 거치면 됩니다.

 

M = C^d (mod N)

 

따라서, 원문(M)을 구하기 위해서는 N을 통해 d를 구한 다음, C^d를 구하면 됩니다. 하나씩 단계를 거치면서 원문(M)을 구해봅시다.

 

문제 해결하기

우선, 정수 d를 구하기 위해서는 φ( N )를 구해야 합니다. φ( N )을 구하는 방법은 우선 N의 약수를 살펴본 다음, 짝을 이루는 두 약수(p, q)가 모두 소수이며, φ( N )의 값((p-1)*(q-1))과 입력된 값 E가 서로소인지 확인하면 됩니다. 빠른 계산을 위해 약수를 구할 때에는 O(√N) 알고리즘을 사용하면 됩니다.

 

φ( N )을 구했으면 다음으로는 E*d ≡ 1 ( mod φ( N ) )를 만족하는 d를 구하면 됩니다. 이는 확장 유클리드 호제법을 활용하면 쉽게 구할 수 있습니다. 다만, d만큼 거듭제곱 해야하기 때문에 d의 값을 0 이상으로 구해주어야 나중에 계산할 때 오류가 발생하지 않습니다. d를 구했다면 마지막으로 거듭제곱을 빠르게 계산해야 합니다. 이 때, 우리는 분할정복 기법을 사용할 수 있습니다. 분할정복 기법으로 거듭제곱을 빠르게 구하면 우리가 원하는 원문(M)을 구할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <utility>
using namespace std;
typedef long long int lint;
typedef pair<int, int> PAIR;
 
lint N, E, C, D, M;
lint p, q, phi;
 
lint pow(lint val, lint k) {
    if(k == 1) return val;
    else {
        if(k%2 == 0) return pow((val*val)%N, k/2);
        else return ( pow((val*val)%N, k/2)*val )%N;
    }
}
 
lint gcd(lint a, lint b) {
    if(a == 0) return b;
    else if(b == 0) return a;
    else return gcd(b, a%b);
}
 
// ax + by = 1
PAIR EEA(lint a, lint b) {
    if(a == 0) return make_pair(0, 1);
    else if(b == 0) return make_pair(1, 0);
    else {
        PAIR prev = EEA(b, a%b);
        lint x = (prev.second%phi + phi)%phi;
        lint y = ((prev.first - (a/b)*x)%phi + phi)%phi;
 
        return make_pair(x, y);
    }
}
 
bool isPrime(lint k) {
    if(k%2 == 0) return 0;
 
    for(lint i=3;i*i<=k;i+=2) {
        if(k%i == 0) return 0;
    }
 
    return 1;
}
 
int main() {
    // 입력
    scanf("%lld %lld %lld", &N, &E, &C);
 
    // p, q 구하기 >> 오일러 피함수 구하기
    for(lint i=2;i*i<N;i++) {
        if(N%i > 0) continue;
 
        p = i;
        q = N/i;
        phi = (p-1)*(q-1);
        if(isPrime(p) and isPrime(q) and gcd(phi, E) == 1) break;
    }
 
    // D 구하기
    D = EEA(E, phi).first;
 
    // C^D (mod N) 구하기
    M = pow(C, D);
 
    // M 출력하기(복호화)
    printf("%lld", M);
}

후기

소수 판별, 유클리드 호제법, 확장 유클리드 호제법, 그리고 분할정복 기법을 활용한 거듭제곱 계산까지 수학적 알고리즘을 한 번에 실습할 수 있는 문제입니다. 수학 알고리즘을 연습하고 싶은 사람에게 추천하고 싶은 문제입니다.