RSA에 대한 설명과 간단한 구현 (C++)

안녕하세요.

SSL에 대해 공부하던중 RSA가 잘 이해가 안되서 직접 간단하게 구현해 보았습니다.

이해를 돕기위해 색상을 넣었는데요.

노란색은 폐기.

초록색은 공개.

붉은색은 비공개 입니다.

• RSA 준비과정

1. p!=q 인 소수 p,q 를 고릅니다.

2. N=p*q;

3. P=(p-1)*(q-1);

4. P를 바탕으로 다음을 만족하는 e를 찾습니다.

e<P , GCD(P,e) == 1;

5. e와 P를 이용해 다음을 만족하는 d를 찾습니다.

d*e%P==1

6. 이제 p와 q, P는 폐기합니다.

구해진 것들은 다음과 같습니다.

p,q,N,P,d,e

공개키는 N,e
개인키는 N,d

• RSA 암호화

보내려는 메시지 M을 준비합니다. 상대방의 공개키 N,e를 확인합니다.

M을 N보다 작게 m으로 바꾸는데, 바꾸는 방법은 메시지와 함께 보내줍니다.

암호화 메시지 c = m^e % N 입니다.

• RSA 복호화

암호화된 메시지 c를 받았습니다. 개인키 N,d 를 통해 변경된 메시지 m을 찾습니다.

변경된 메시지 m = c^d % N

m을 원래 메시지 M으로 바꾸면 됩니다. (이건 암호화 한 사람이 보내줍니다.)

• 크래커

스니핑을 통해 메시지 c를 얻었다고 칩시다. m을 M으로 변환하는 방법도요.

공개키 N,e는 공개되어있기 때문에 쉽게 얻었습니다.

우리는 암호화 하는 방법을 알고 있습니다.

메시지 c=m^e % N 입니다.

그리고 우리는 c, N, e 를 알고있습니다.

그런데 말입니다. m을 구할 수 있을까요?


그러나 불행히도 c, N, e를 알아도 m을 구할 수는 없습니다.

왜냐하면 저 식을 만족하는 m의 개수가 엄청나게 많기 때문입니다.

예를들면, c가 8, N이 33, e가 3인경우

m은 2 , 35 ...등등이 될 수 있습니다.

또, 수가 크면 계산하는데 시간이 굉장히 오래 걸립니다.


그러므로

꼭 d를 알아야하는데, d*e%P==1 에서 나왔죠.

꼭 P를 알아야하는데, P=(p-1)*(q-1) 에서 나왔죠.

꼭 p, q를 알아야하는데, N = p * q이 보통 굉장히 크므로

N을 통해 p, q를 구하려면 굉장히 많은 시간이 걸립니다.

•  증명 : m == c^d % N

c = m^e % N 이니까 (암호화 하는 부분 참조)

m = c^d % N 에 c를 대입하면 (m^e % N)^d % N 이죠.

mod연산의 특성에 따라

(m^e % N)^d % N == m^(e*d) % N

준비과정 5번에서 d*e%P==1 이었기 때문에 d*e=k*P+1 (k는 상수) 이고,

P=(p-1)*(q-1) 이기 때문에 m^(e*d) % N 에 대입하면

m^(k*(p-1)*(q-1)+1) % N 이 됩니다.


m^(k*(p-1)*(q-1)+1) % N == (m^(p-1))^(k*(q-1))*M % N

(m^(p-1))^k*(q-1))*m % N== 1^(k*(q-1))*m % N==m % N

이므로 c^d % N == m % N


m은 N보다 작으므로 m % N == m.

따라서 c^d % N == m


어떻게 이런걸 생각해 냈을까요?

결국 이 공로로  Rivest, Shamir, Adleman

세 사람은 2002년 튜링상을 받게됩니다.

부럽죠......

• 안전성

1999. 8. 22 에 암호키 155자리 수가 네덜란드, 캐나다, 미국 등 구미 6개국의

11개 연구기관으로 이루어진 공동연구팀에 의해 292대의 PC와 워크스테이션 등을 활용해

작업 개시 7개월 반만에 RSA의 암호화에 사용하는 암호키(열쇠)인 512비트의 숫자

(암호코드 RSA­155)를 General Number Field Sieve방법을 이용하여

소인수 분해하는데 성공했습니다.


또한 소인수분해 알고리즘을 이용하지 않고도 공격이 가능한데,

그것은 RSA서명에 의한 RSA암호 공격입니다.

이것은 다음 글을 참고하길 바랍니다.

RSA 서명에 의한 RSA 암호 공격

따라서 취약해 지지 않기 위해서는 두 소수를 선택할 때 규칙을 따라야 합니다.

1. p, q의 크기가 거의 같을 것.

2. p-q 가 클 것.

3. p-1 이 큰 수를 인수로 가질 것.

4. p+1 이 큰 수를 인수로 가질 것.

이외에도 1993년 피터 쇼어는 쇼어 알고리즘을 발표,

양자 컴퓨터를 이용하여 임의의 정수를 다항 시간 안에

소인수 분해하는 방법을 발표하였기 때문에,

미래에 양자 컴퓨터가 상용화 된다면

결국 RSA는 무용지물이 될 것으로 예상됩니다.

• 코드

//RSA 암호화 -> 해독하는 간단한 프로그램입니다.

#include
#include  
using namespace std;

int GCD(int a, int b)
{
 int tmp;
 while (1)
 {
  if (a < b) swap(a, b);

  if (a%b == 0) return b;
  else
  {
   tmp = a%b;
   a = b;
   b = tmp;
  }
 }
}


int Get_e(int P)
{
 int e;
 for (e = 2; e < P; e++)
 {
  if (GCD(P, e) == 1)
  {
   return e;
  }
 }
}

int Get_d(int P,int e)
{
 int d;
 for (d = 1;; d++)
 {
  if ((d*e) % P == 1)
  {
   return d;
  }
 }
}
int Get_m(int M, int N)
{
 int cnt=0;
 while (M > N)
 {
  M -= N;
  cnt++;
 }
 return cnt;
}


int PowWithMod(int x, int y, int mod)
{
 //x의 y승
 int ret = 1;
 int i;
 for (i = 0; i < y; i++)
 {
  ret = ret*(x%mod);
  ret %= mod;
 }
 return ret%mod;
}



void main()
{
 int p,q;
 int e, N, P, d, c;
 int m, M;
 int mf;
 int cnt;
 cout << "두 소수 p,q 입력 :"< cin >> p >> q;
 
 N = p*q;
 P = (p - 1)*(q - 1);
 e=Get_e(P);
 d = Get_d(P, e);
 system("cls");

 cout << "-RSA 암호화-" << endl;
 cout << "공개키는 <" < 입니다."< cout << "개인키는 <" << N << "," << d << "> 입니다." << endl;
 cout << "보내고 싶은 메시지를 입력하세요(M)" << endl;
 cin >> M;
 //임의의 방법으로 M->m으로 변환시킵니다. m은 N보다 작아야합니다.
 //이 코드에서 임의의 변환방법은 m이 N보다 클 때마다 N으로 빼주는 것입니다.
 //실제로는 더 복잡한 방법들이 사용됩니다.
 //또한 이 방법은 미리 메시지를 보낼 사람에게도 알려주어야 합니다.
 cnt = Get_m(M, N);
 m = M - cnt*N;
 //cout << "메시지 M이 N보다 작은 m으로 변환되었습니다. (N=" << N << ",m=" << m << ",cnt=" < system("cls");

 c = PowWithMod(m, e, N);

 cout << "-RSA 복호화-" << endl;
 cout << "당신은 암호화된 메시지를 얻었습니다." << endl;
 cout << "암호화된 메시지는 " << c << "입니다."< cout << "공개키는 입니다." << endl;
 cout << "복호화 한 후 cnt*N를 더하면 실제 메시지가 됩니다. (cnt*N="< cout << "실제 메시지는 무엇일까요?" << endl;
 cin >> p;
 m = PowWithMod(c, d, N);

 if (p == m + cnt*N) cout << "맞았습니다! ";
 else cout << "틀렸습니다! ";
 cout << "실제 메시지는 ("<< m + cnt*N << ") 입니다."<< endl;
 cout << "개인키는 였습니다." << endl;
}