Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 RSA 암호화 알고리즘 – 원리부터 예제 코드까지

RSA(Rivest–Shamir–Adleman)는 공개 키(Public Key)와 개인 키(Private Key), 두 개의 키를 사용하는 대표적인 비대칭 암호화 알고리즘입니다. 공개 키로 암호화한 데이터는 짝이 되는 개인 키로만 복호화할 수 있기 때문에, 네트워크를 통해 안전하게 정보를 주고받아야 하는 환경에서 널리 활용됩니다.

이번 글에서는 RSA 알고리즘의 동작 원리를 단계별로 살펴보고, 이를 C++로 구현한 예제 코드와 실제 실행 결과까지 함께 확인해 보겠습니다.

RSA 알고리즘의 동작 단계

시작
  1. 두 개의 소수 p와 q를 선택한다.
  2. n = p * q 를 계산한다.
  3. phi = (p-1) * (q-1) 을 계산한다.
  4. 1 < e < phi(n) 이면서 gcd(e, phi(n)) = 1 인 정수 e를 선택한다.
     즉, e와 phi(n)은 서로소(coprime) 관계여야 한다.
  5. d ≡ e^-1 (mod phi(n)) 을 만족하는 d를 계산한다.
     여기서 d는 phi(n)에 대한 e의 모듈러 곱셈 역원이다.
  6. 암호화 : c = m^e mod n  (m은 원본 메시지)
  7. 복호화 : m = c^d mod n
종료

C++ 구현 예제 코드

#include<iostream>
#include<math.h>
using namespace std;

// 최대공약수(gcd)를 구하는 함수
int gcd(int a, int b) {
  int t;
  while(1) {
    t = a % b;
    if(t == 0)
      return b;
    a = b;
    b = t;
  }
}

int main() {
  // 임의로 선택한 두 소수
  double p = 13;
  double q = 11;
  double n = p*q;             // n 계산
  double track;
  double phi = (p-1)*(q-1);   // phi(오일러 피 함수) 계산

  // 공개 키 (e는 'encrypt', 즉 암호화를 의미)
  double e = 7;
  // 1 < e < phi(n) 이고 gcd(e, phi(n)) = 1,
  // 즉 e와 phi(n)이 서로소인지 검사
  while(e<phi) {
    track = gcd(e,phi);
    if(track==1)
      break;
    else
      e++;
  }

  // 개인 키 (d는 'decrypt', 즉 복호화를 의미)
  // d*e = 1 (mod phi) 를 만족하는 d를 선택
  double d1 = 1/e;
  double d = fmod(d1,phi);

  double message = 9;
  double c = pow(message,e);  // 메시지 암호화
  double m = pow(c,d);
  c = fmod(c,n);
  m = fmod(m,n);

  cout<<"Original Message = "<<message;
  cout<<"\n"<<"p = "<<p;
  cout<<"\n"<<"q = "<<q;
  cout<<"\n"<<"n = pq = "<<n;
  cout<<"\n"<<"phi = "<<phi;
  cout<<"\n"<<"e = "<<e;
  cout<<"\n"<<"d = "<<d;
  cout<<"\n"<<"Encrypted message = "<<c;
  cout<<"\n"<<"Decrypted message = "<<m;
  return 0;
}

실행 결과

p = 13
q = 11
n = pq = 143
phi = 120
e = 7
d = 0.142857
Original Message = 9

Encrypted message = 48
Decrypted message = 9

결과 해석

  • p, q : 임의로 선택한 두 소수입니다. 예제에서는 13과 11을 사용했습니다.
  • n = 143 : 두 소수의 곱으로, 암호화와 복호화 연산의 기준이 되는 모듈러 값입니다.
  • phi = 120 : 오일러 피 함수 값으로, (13−1) × (11−1) = 120 입니다.
  • e = 7 : phi(120)와 서로소 관계에 있는 공개 지수입니다.
  • d : 공개 지수 e에 대응하는 개인 지수로, 외부에 절대 노출되어서는 안 됩니다.

원본 메시지 9는 공개 키(e = 7, n = 143)로 암호화되어 48이 되었으며, 이 값을 다시 복호화하면 원래의 9가 그대로 복원되는 것을 확인할 수 있습니다.

실무 적용 시 유의 사항

위 예제는 학습 목적으로 아주 작은 소수와 double 자료형을 사용했습니다. 실제 서비스 환경에 RSA를 적용할 때는 다음 사항을 반드시 고려해야 합니다.

  • 최소 1024비트, 권장 2048비트 이상의 큰 소수를 사용해야 보안성을 확보할 수 있습니다.
  • 큰 수 연산 시 발생하는 오버플로를 방지하기 위해 빅 정수(Big Integer) 라이브러리나 모듈러 거듭제곱(modular exponentiation) 기법을 활용해야 합니다.
  • 키 생성과 패딩(OAEP 등) 같은 세부 구현은 OpenSSL처럼 검증된 암호화 라이브러리를 사용하는 것이 안전합니다.