[c++] 알고리즘 RSA

공개 키 암호화 시스템(public-key cryptosystem)

- 안전하게 키를 분배하는 문제를 해결하기 위해 개발됨

- 메시지를 보낼 때

   >> 송신자는 수신자의 공개 키를 찾아 사용하여 암호화한 후 전송

- 메시지를 읽을 때

   >> 수신자는 자신이 가진 비밀 키(secret key)를 사용하여 복호화

- 공개 키 암호화 시스템의 구성 조건

   >> P 공개 키, S 비밀 키, M 메시지

① S(P(M)) = M

② 모든 (S, P) 쌍은 유일해야 한다.

③ P로부터 S를 알아내는 것은 M을 해독하는 것만큼 어려워야 한다.

④ S와 P는 쉽게 계산할 수 있어야 한다.

 

 

 

공개 키 암호화 시스템의 기본적인 전제

- 주어진 큰 숫자가 소수인지를 결정하는 빠른 알고리즘은 있지만, 주어진 큰 비소수의 소수 인자를 찾아내는 빠른 알고리즘은 없음

•예 1)

>> 130자리 수가 소수인지 검사하는 데는 7분이 소요

>> 63자리 두 소수를 곱해서 얻은 수의 두 소수 인자를 찾아내는 데는 4*106년이 소요

•예 2)

>> 200자리 숫자가 어떤 두 소수의 곱으로 이루어지는지 알아내는 알고리즘은 수백만 년의 시간이 소요

 

 

 

RSA (Rivest, Shamir and Adleman) 알고리즘

- 공개 키 암호화 시스템에서 사용되는 대표적인 알고리즘

- 메시지를 선형 시간에 암호화

- 암호화 :

- 복호화 :

 

 

 

암호화 과정

- SAVE PRIVATE RYAN을 A는 01, B는 02, C는 03 등의 십진수로 인코딩

•190122050016180922012005001825011400

>> 암호화 계산

•190137 mod 3713 = 0335

•220537 mod 3713 = 1472

•001637 mod 3713 = 1447

•180937 mod 3713 = 3060

•220137 mod 3713 = 1548

•200537 mod 3713 = 1608

•001837 mod 3713 = 3091

•250137 mod 3713 = 0654

•140037 mod 3713 = 1414

>> 암호화된 메시지

•033514721447306015481608309106541414 

 

 

복호화 과정 

- 복호화 계산

•033597 mod 3713 = 1901

•147297 mod 3713 = 2205

•144797 mod 3713 = 0016

•…

- 복호화된 메시지

•190122050016180922012005001825011400

 

 

 

소스 코드

#include<iostream>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>

using namespace std;

int p=0, q=0, n, t, flag, e[100], d[100], temp[100], j, m[100], en[100], i;
char msg[100];

int prand() //난수로 소수 생성
{
 int j;
 srand((unsigned)time(NULL));

 while(1)
 {
  j = (rand()%98)+2; //2~99
  if(j==2)
   return j;
  for(int l=2; l<j; l++)
  {
   if(j%l == 0)
    break;
   if((l+1)==j)
    return j;
  }
 }
}

int prime(int pr) //p와 q에 저장
{
 int i;
 j = sqrtl(pr);

 for (i = 2;i <= j;i++)
  if (pr % i == 0) //나머지가 0일경우 -> 소수가 아님
   return 0;

 return 1;
}

int cd(int x)
{
 int k=1;
 while(1)
 {
  k = k + t;
  if (k % x == 0)
   return(k/x);
 }
}

void ce()
{
 int k;
 k = 0;

 for (i = 2; i < t; i++)
 {
  if (t % i == 0)
   continue;
  flag = prime(i);
  if (flag == 1 && i != p && i != q)
  {
   e[k] = i;
   flag = cd(e[k]);
   if (flag > 0)
   {
    d[k] = flag;
    k++;
   }
   if (k == 99)
    break;
  }
 }
}

void encrypt()
{
 int pt, ct, key = e[0], k, len;
 i = 0;
 len = strlen(msg);

 while(i != len)
 {
  pt = m[i];
  pt = pt - 96;
  k = 1;

  for (j = 0;j < key;j++)
  {
   k = k * pt;
   k = k % n;
  }
  temp[i] = k;
  ct = k + 96;
  en[i] = ct;
  i++;
 }

 en[i] = -1;
 cout<<"\nTHE ENCRYPTED MESSAGE IS"<<endl;

 for (i = 0;en[i] != -1;i++)
  cout<<(char)en[i];
 cout<<endl;
}

void decrypt()
{
 int pt, ct, key = d[0], k;
 i = 0;
 while (en[i] != -1)
 {
  ct = temp[i];
  k = 1;
  for (j = 0;j < key;j++)
  {
   k = k *ct;
   k = k % n;
  }
  pt = k + 96;
  m[i] = pt;
  i++;
 }
 m[i] = -1;
 cout<<"THE DECRYPTED MESSAGE IS"<<endl;

 for (i = 0;m[i] != -1;i++)
  cout<<(char)m[i];
 cout<<endl;
}

int main()
{
 cout<<"First Number"<<endl;
 p=prand();
 cout<<p<<endl;

 cout<<"Second Number"<<endl;
 while(1)
 {
  q=prand();
  if(q != p)
   break;
 }
 cout<<q<<endl;

 cout<<"ENTER MESSAGE"<<endl;
 fflush(stdin);
 cin>>msg;

 for (i = 0;msg[i] != NULL;i++)
  m[i] = msg[i];
 n = p * q;
 t = (p - 1)*(q -1);
 ce();

 encrypt();
 decrypt();
 return 0;
}