RSA 암호 알고리즘

RSA 암호 알고리즘

공개키 암호시스템의 하나

 

다양한 분야에서 가장 보편적으로 사용되는 암호 알고리즘이다.

 

아주 큰 두 소수의 곱으로 이루어진 합성수를 인수분해하기 어렵다는 인수분해 문제의 어려움에 기반한 안전성을 가진다!

 

많은 데이터를 여러 번 암호화해야 하는 네트워크 통신에서는 잘 사용되지 않는다.

(많은 연산을 필요로 하기 때문)

 

 

 

 

 

RSA 암호 알고리즘은 두 개의 키를 사용한다.

- 공개키 (Public Key)

- 개인키 (Private Key)

 

공개키는 모든 사용자에게 공개되며, 평문을 암호화할 때 사용한다.

 

개인키는 타인에게 노출되어서는 안 되며, 공개키로 암호화된 암호문을 복호화할 때 사용한다.

 

 

 

 

 

오일러 정리

서로소인 양의 정수 m이 아래의 식을 만족한다는 정리

 

 

오일러 파이 함수 (Euler's phi function)

임의의 n 이하의 양의 정수 중 n과 서로소인 수의 개수

 

 

 

example 1.

6 이하의 양의 정수 중 6과 서로소인 수: 1, 5

φ(6) = 2

소수 p의 경우 1부터 p-1까지 모두 p와 서로소이기 때문에 φ(p) = p-1

 

 

 

 

 

키 생성

1. 임의의 두 소수 p, q 선택 (1024 비트 이상에서 비트 길이가 같은 수)

2. n= p x q

 

φ(n) = p x q - p - q + 1 = (p-1)(q-1)

 

3. φ(n)보다 작은 수 중 φ(n)과 서로소인 e 선택

4. d 구하기

 

n, e는 공개키

d는 개인키

 

 

 

 

 

[c++ 코드 예제]

 

#include <iostream>
#include <math.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);
		if (j == 2)
			return j;
		for (int I = 2; I < j; I++) {
			if (j % I == 0)
				break;
			if ((I + 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 ";
	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 ";
	for (i = 0; m[i] != -1; i++)
		cout << (char)m[i];
	cout << endl;
}
int main() {
	cout << "First Number: ";
	p = prand();
	cout << p << endl;
	cout << "Second Number: ";
	while (1) {
		q = prand();
		if (q != p)
			break;
	}
	cout << q << endl;
	cout << "ENTER MESSAGE: ";
	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;
}

참고: https://coyagi.tistory.com/entry/c-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-RSA

 

 

 

 

 

[코드 실행]