RSA암호화

(n,e)는 공개 키로 상대방(Alice)과 내가(Bob) 가지고 있습니다.
d는 개인 키입니다.
공개 키는 암호화 or 복호화하는 사람 입장에서 필요합니다!
개인 키는 복호화하는 사람 입장에서 필요합니다!

< 두 키의 관계 >

BOB: 내가 공개 키(n,e)를 줄테니까 공개 키와 암호화 공식을 이용해서 암호문(C)을 보내면 돼!
Alice: 응. 메시지(M)을 암호화해서 보낼게!
BOB: 암호문(C)을 받으면 내 개인 키(d)와 복호화 공식으로 메시지를 알아내야지!

< RSA 공식 >

d값(개인 키) : e mod(p-1)(q-1)의 역
n값(공개 키) : p x q (단, p, q는 소수)
e값(공개 키) : (p-1)*(q-1)과 서로소 (1 < e < n)
암호화 공식 : M이 메시지일 때, M^e mod n = C (0 <= M <=n-1)
복호화 공식 : C가 암호문일 때, C^d mod n = M
참고 : (서로소 : 1이외의 공약수가 없는 관계)

< 공개 키로 개인 키 구하기 >

e *d mod(p-1)(q-1)=1 일 때 d값을 구하면 됩니다.

이 때, n 값이 간단하면 위의 공식대로 d를 구해서 암호문을 누구나 해독할 수 있습니다.

그러나 n 값이 복잡하면 암호문을 푸는데 수십년이 걸릴 수 있습니다.
컴퓨터는 수치가 클수록 연산 과정이 오래 걸리는데, 엄청나게 큰 수치를 주면 연산 과정이 기하급수적으로 올라갑니다.

소수(a)*소수(b)=10^100+5^100+9^99이라고 생각해보세요. 컴퓨터 입장에서 단순히 a와 b를 끼워 맞춰서 풀기에는 한계가 있는거죠!!

컴퓨터 연산 과정의 한계를 이용해서 만든 최강의 보안 RSA는 세 수학자인 로널드 라이베스트(Ron Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman)이 만들었습니다.

현존 최강인 만큼 전 세계 보안 유지 기업에는 같은 방식의 RSA가 쓰입니다.
그러나, 금융 기관의 n자릿수는 617자릿수(2048비트)이므로 슈퍼 컴퓨터로도 풀어낼 수 없습니다.

아래 알고리즘은 컴퓨터 무작위 대입 연산으로, n이 작은 수(열 자릿수 이하)일 때 적절합니다.

1. 적당한 크기 이하의 소수들 구하기 (ex) 6000이하의 소수)
2. 소수 2개를 곱해서 n을 찾기 / n이 나오면 해당 소수 2개를 p,q로 설정
3. 기본적으로 주어진 n,e 그리고 새로 구한 p,q를 이용해서 d값을 구하기 (d는 무작위 대입)

#include <stdio.h>
#include <stdlib.h>
#define size 3000 // 동적 메모리 크기 
#define n 6012707 // 공개 키 
#define e 3000037 // 지수
// 나눗셈 연산 
long long mod(long long a, long long b) {
	if (a > 0)
		return a % b; // a-b*(a/b)
	else {
		return a - b * -((-a / b) + 1);
	}
}
int main(void) {
	printf("□ RSA 암호가 주어졌다. n은 %d이고 e=%d일 때 d를 계산하라.\n", n,e);
	// e mod (p-1)(q-1)의 역(=d)을 구할 것 (단, p,q는 소수)
	// 소수 찾고 저장하는 알고리즘
	int *store = (int)malloc(sizeof(int)*size);
	int length = 0;
	for (int i = 2; i < 2 * size; i++) {
		for (int j = 1; j <= i; j++) {
			if (j != 1 && j != i && i%j == 0)
				break;
			else if (j == i) {
				store[length++] = i;
			}
		}
	}
	// 저장한 소수간의 곱셈으로 p,q찾기 
	long long p = 0;
	long long q = 0;
	for (int i = 0; i < length; i++) {
		for (int j = i; j < length; j++) {
			if (store[i] > 0 && store[j] > 0) { // 쓰레기값 처리 안 함 
				if (store[i] * store[j] == n) {
					p = store[i]; q = store[j];
					break;
				}
			}
		}
	}
	free(store); // 저장한거 버리기
	// e mod (p-1)(q-1)의 역 구하기 -> e*d mod (p-1)(q-1)=1일 때 d가 역
	for (long long d = 1; d < 500000; d++) {
		if (mod(e*d, (p - 1)*(q - 1)) == 1) {
			printf("\np=%lld\n", p);
			printf("q=%lld\n",q);
			printf("d=%lld\n",d);
			printf("%d * %lld mod (%lld-1)(%lld-1) = %lld\n", e,d,p,q,mod(e*d, (p - 1)*(q - 1)));
			break;
		}
	}
}