RSA 알고리즘

머리말

이 알고리즘을 개발한 Rivest, Shamir, Adleman의 앞 글자를 따서 만든 RSA 알고리즘은 키 암호화 알고리즘입니다.

대칭키 방식은 키를 생성하는 속도가 빠르지만, 암호화와 복호화에 사용되는 키가 같아서 키가 탈취되는 경우 암호화된 문서를 아무나 복호화할 수 있다는 단점이 있습니다.

이 대칭키 암호화의 키 교환 방식의 문제점을 해결하기 위해서 나온 방식이 비대칭키 암호화입니다.

비대칭키 암호화는 공개키(public key)와 개인키(private key) 2가지를 사용합니다. 공개키(public key)는 대중에게 공개되는 key이고, 개인키(private key)는 자신만 가지는 key입니다.

정보를 전달할 때 공개키로 암호화를 진행합니다. 이 암호화는 누구나 진행할 수 있습니다. 하지만 복호화 과정에서는 개인키로만 할 수 있습니다. 즉, 문서를 열어보는 것은 개인키만 가진 사람이 할 수 있다는 뜻입니다.

이 RSA도 비대칭키 암호화 알고리즘의 하나입니다.

RSA 알고리즘

RSA는 비밀 키와 공개 키라는 2가지 다른 키를 사용합니다.
RSA는 두 가지 중요한 수학적 원리를 통해 보안성을 제공합니다.

첫 번째, 두 큰 소수를 곱한 결과로 매우 큰 수를 생성합니다. 소수를 구하는 것은 쉽지만 특정 수를 두 소수로 소인수분해하는 과정은 굉장히 어렵기 때문에 암호화에 도움이 됩니다.

두 번째, 수학적인 함수들의 계산의 값이 굉장히 크기 때문에 암호화 및 해독 과정이 복잡합니다.

pseudo code

다음은 의사 코드(pseudo code)로 작성한 예시입니다.

1. 소수 생성
   - 소수 p, q를 랜덤하게 선택 (p ≠ q)
   - p, q는 충분히 큰 소수이어야 함

2. 공개 키 및 비밀 키 생성
   - n = p * q (공개 키 및 비밀 키에서 공통으로 사용되는 모듈로)
   - φ(n) = (p-1) * (q-1) (오일러 피 함수)
   - 1 < e < φ(n)인 e를 선택 (e와 φ(n)은 서로소)
   - d ≡ e^(-1) (mod φ(n)) (확장 유클리드 알고리즘을 통해 d 계산)

3. 암호화
   - 평문 m을 입력받음
   - c ≡ m^e (mod n) (암호문 생성)
   - 암호문 c 반환

4. 해독
   - 암호문 c를 입력받음
   - m ≡ c^d (mod n) (평문 복원)
   - 평문 m 반환

// mod 는 %(나머지) 연산을 사용합니다.

실제 값 c(crpyto), n(p * q), e를 안다고 평문 m을 구할 수는 없습니다.

   - c ≡ m^e (mod n) (암호문 생성)

위의 식을 만족하는 m의 개수가 무수히 많기 때문입니다.

C++ 코드

#include <iostream>
#include <string>
#include <vector>
#include <cmath>

// 함수: 최대공약수 계산 (유클리드 호제법)
int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

// 함수: 모듈러 역원 계산 (확장 유클리드 알고리즘)
int modInverse(int a, int m) {
    int m0 = m, t, q;
    int x0 = 0, x1 = 1;

    if (m == 1)
        return 0;

    while (a > 1) {
        q = a / m;
        t = m;
        m = a % m;
        a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }

    if (x1 < 0)
        x1 += m0;

    return x1;
}

// 함수: RSA 암호화
std::vector<int> encrypt(const std::string& plainText, int e, int n) {
    std::vector<int> cipherText;
    for (char c : plainText) {
        int encryptedChar = std::pow(c, e);
        encryptedChar %= n;
        cipherText.push_back(encryptedChar);
    }
    return cipherText;
}

// 함수: RSA 해독
std::string decrypt(const std::vector<int>& cipherText, int d, int n) {
    std::string decryptedText;
    for (int encryptedChar : cipherText) {
        int decryptedChar = std::pow(encryptedChar, d);
        decryptedChar %= n;
        decryptedText += static_cast<char>(decryptedChar);
    }
    return decryptedText;
}

int main() {
    // 소수 p, q 설정
    int p = 11;
    int q = 13;

    // 모듈로 n, 오일러 피 함수 φ(n) 계산
    int n = p * q;
    int phi = (p - 1) * (q - 1);

    // 공개 키 e 선택 (1 < e < φ(n), e와 φ(n)은 서로소)
    int e = 7;

    // 비밀 키 d 계산 (e * d ≡ 1 (mod φ(n)))
    int d = modInverse(e, phi);

    // 평문 입력
    std::string plainText;
    std::cout << "평문을 입력하세요: ";
    std::getline(std::cin >> std::ws, plainText);

    // 암호화
    std::vector<int> cipherText = encrypt(plainText, e, n);
    std::cout << "암호문: ";
    for (int encryptedChar : cipherText) {
        std::cout << encryptedChar << " ";
    }
    std::cout << std::endl;

    // 해독
    std::string decryptedText = decrypt(cipherText, d, n);
    std::cout << "해독된 평문: " << decryptedText << std::endl;

    return 0;
}