문제
공개키 알고리즘 중 Rivest, Shamir, Adleman에 의해 설계된 RSA 알고리즘을 구현하라
로직
- 2개의 소수 (p, q)가 필요하다
- n = p * q
- ϕ(n) = (p-1) * (q-1)
- e = e와 ϕ(n)의 서로소
- d = e*d mod ϕ(n) = 1
- c = m^e mod n
- m = c^d mod n
주의 사항
- 암호화하는 평문은 n의 자릿수보다 작은 자릿수를 가져야한다. a. 평문이 '123456789'이고, n이 '1234'이면 평문을 '123', '456', 789'로 나눠서 암호화해야한다.
- p와 q는 다음 조건을 만족해야 한다. a. p와 q는 같지 않고 거의 같은 크기의 자릿수야야 한다. b. p-1과 q-1은 커다란 소인수를 각각 가져야 한다. c. p-1과 q-1의 최대 공약수는 작은 수여야 한다
구현하지 않았지만, TMI
- 실제 RSA에서 사용하는 p와 q는 100자리 정도의 소수로 거의 같은 크기의 자릿수를 가지는 수를 선택한다.
코드
rsa.h
#ifndef _RSA
#define _RSA
typedef struct key
{
long pkey; // 초기 2개의 소수 p와 q가 곱해서 나오는 n이 저장될 변수
long ekey; // public-key
long dkey; // private-key
int pkey_size;
} Key;
class Rsa
{
public:
Rsa();
virtual ~Rsa();
public:
Key produce_keys();
long endecrypt(const long msg, const long key, const long pkey);
int sizeof_int(long data);
private:
long produce_pkey(const long prime1, const long prime2);
long produce_ekey(const long orla);
long produce_dkey(const long ekey, const long orla);
long produce_prime();
long produce_orla(const long prime1, const long prime2);
long produce_gcd(const long a, const long b);
bool is_prime(const long digit);
};
#endif
main.cpp
#include "rsa.h"
#include <iostream>
using namespace std;
int main(void)
{
Rsa rsa;
Key key = rsa.produce_keys();
cout << "=============================" << endl;
cout << "=========== R S A ===========" << endl;
cout << "=============================\n" << endl;
cout << "=====================================" << endl;
cout << "암호화 후 얻은 키는 다음과 같습니다."<< endl;
cout << "n 키 : " << key.pkey << endl;
cout << "암호화 키 (공개키) : " << key.ekey << endl;
cout << "암호 해독 키 (개인키) : " << key.dkey << endl;
cout << "=====================================\n" << endl;
long msg;
cout << "암호화할 정보를 입력하십시오 (숫자, 너무 클 수 없음) : ";
cin >> msg;
cout << "\n=====================================" << endl;
long msg_des = rsa.endecrypt(msg, key.ekey, key.pkey);
cout << "암호화된 정보는 다음과 같습니다 : " << msg_des << endl;
msg_des = rsa.endecrypt(msg_des, key.dkey, key.pkey);
cout << "암호 해독된 메시지는 다음과 같습니다 : " << msg_des << endl;
cout << "=====================================" << endl;
return 0;
}
rsa.cpp
#include "rsa.h"
#include <cstdlib>
#include <ctime>
#include <string>
#include <bitset>
#include <iostream>
using namespace std;
Rsa::Rsa()
{
}
Rsa::~Rsa()
{
}
/***********************************************************************
암호화 복호화를 동시에 진행하는 메소드
c = m^e mod n
m = c^d mod n
라는 식은 같고 변수만 매개값만 바뀌면 되므로 하나의 메소드에서 처리함
***********************************************************************/
long Rsa::endecrypt(const long msg, const long key, const long pkey)
{
long msg_des = 1;
long root = msg;
long index = key;
//int n_size = sizeof_int(pkey);
//int msg_size = sizeof_int(msg);
//int size = msg_size / n_size;
//if (msg_size % n_size)
// size = size + 1;
while (index)
{
//cout << bitset<32>(index) << endl;
if (index & 1) {
msg_des = (msg_des * root) % pkey;
//cout << "msg_des : " << msg_des << endl;
}
index >>= 1;
//cout << "b root : " << root << endl;
root = (root * root) % pkey;
//cout << "a root : " << root << endl;
}
return msg_des;
}
/************************************
p와 q를 생성해서
n, e, d 키를 생성
* *********************************/
Key Rsa::produce_keys()
{
long prime1 = produce_prime(); // p
long prime2 = produce_prime(); // q
while (prime2 == prime1) // p와 q는 n을 만들고 폐기해야 하기 때문에
prime2 = produce_prime(); // 따로 저장해서 메소드 밖으로 빼지 않음
Key key;
long orla = produce_orla(prime1, prime2); // 오일러 n 생성
key.pkey = produce_pkey(prime1, prime2); // n 생성
key.ekey = produce_ekey(orla); // e 생성
key.dkey = produce_dkey(key.ekey, orla); // d 생성
return key;
}
/************************************
N 키 생성
p * q
* *********************************/
long Rsa::produce_pkey(const long prime1, const long prime2)
{
return prime1 * prime2;
}
/************************************
오일러 n 생성
************************************/
long Rsa::produce_orla(const long prime1, const long prime2)
{
return (prime1 - 1) * (prime2 - 1);
}
/************************************
암호화 키 (공개키) e 생성
* *********************************/
long Rsa::produce_ekey(const long orla)
{
long ekey;
while (true)
{
ekey = rand() % orla; // 랜덤 수를 오일러 n으로 나머지 연산
if (ekey >= 2 && produce_gcd(ekey, orla) == 1) // e-key와 오일러 n이 서로소인지 판별
break;
}
return ekey;
}
/************************************
복호화 키 (개인키) d 생성
* *********************************/
long Rsa::produce_dkey(const long ekey, const long orla)
{
long dkey = orla / ekey;
while (true)
{
if (((dkey * ekey) % orla) == 1)
break;
else
++dkey;
}
return dkey;
}
/************************************
[100, 200] 범위에서 임의의 소수 생성
* *********************************/
long Rsa::produce_prime()
{
long prime = 0;
srand(time(0));
while (true)
{
prime = rand() % 100 + 100;
if (is_prime(prime))
break;
}
return prime;
}
/************************************
두 숫자의 최대 공약수 생성
* *********************************/
long Rsa::produce_gcd(const long a, const long b)
{
long dividend = a;
long divisor = b;
long residual = dividend % divisor;
while (residual)
{
dividend = divisor;
divisor = residual;
residual = dividend % divisor;
}
return divisor;
}
/************************************
소수인지 판단
* *********************************/
bool Rsa::is_prime(const long digit)
{
int tmp = 2;
while (tmp < digit)
if (!(digit % tmp++))
break;
if (tmp == digit)
return true;
return false;
}
/************************************
입력값의 자릿수 판단
* *********************************/
int Rsa::sizeof_int(long data)
{
int pos = 1;
if (data < 0)
data *= (-1);
for (int i = 0; ; i++, pos++) {
if ((data /= 10) <= 0)
break;
}
return pos;
}
결과
참고문헌
GitHub, "RSA Encryption Decryption", https://github.com/cassvin/Rsa, (2020.06.05.)