RSA 완성 Only Code

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define INT unsigned int 

void Find_Prime_Number(char * num_str, INT fn) {
	INT start = 3;
	int i = 2;
	for (start = 3; start < fn; start += 2) {
		if (0 == num_str[start]) {
			while (start * i < fn) {
				num_str[start*i] = 1;
				i++;
			}
			i = 2;
		}
	}
}
// 소수를 찾는 함수
INT gcd(INT a, INT b) {
	if (0 == b) return a;
	return gcd(b, a % b);
}
// 유클리드 알고리즘을 이용하여 최대공약수 구하는 함수
INT inverse(INT a, INT b) {
	int r1, r2, q, r, t, t1, t2;
	r1 = a;
	r2 = b;
	t1 = 0;
	t2 = 1;

	while (r1 != 1)
	{
		q = r2 / r1;
		r = r2 - r1*q;
		t = t1 - t2*q;
		r2 = r1;
		r1 = r;
		t1 = t2;
		t2 = t;
	}
	if (t2 < 0)
		t2 = t2 + b;
	return t2;
}
// 확장되 유클리드 알고리즘을 이용한 모듈러 연산의 역원을 구하는 함수
INT expo_algorism(INT a, INT b, INT n)
{
	INT result = 1;

	while (b)
	{
		if (b & 1)
		{
			result = (result * a) % n;
		}
		b /= 2;
		a = (a * a) % n;
	}
	return result;
}
// 고속 누승 알고리즘
INT phi(INT p, INT q) {
	return (p - (INT)1)*(q - (INT)1);
}       
// phi(n) = (p-1)*(q-1)

int main(void) {
	INT fn = 256, i, j = 0, k;
	INT * _str;
	char * str;
	INT p, q;
	//	2	3	  4		 5		6
	INT n, phi_n, e = 3, d = 3, a, c;
	/* 1. 임의의 소수 찾기 {{ */
	str = (char*)calloc((fn + 1), sizeof(char));
	Find_Prime_Number(str, fn);
	if (str == NULL) {
		printf("메모리 영역 오류 입니다.\n");
		free(str);
		return 0;
	}
	for (i = 3; i < fn; i += 2) {
		if (str[i] == 0) {
			j++;		// 소수의 갯수 저장
		}
	}

	_str = (INT*)calloc(j + 1, sizeof(INT));
	if (_str == NULL) {
		printf("메모리 영역 오류 입니다.\n");
		free(str);
		free(_str);
		return 0;
	}
	j = 0;

	for (i = 3; i < fn; i += 2) {
		if (str[i] == 0) {
			_str[j] = i;
			j++;
		}
	}
	srand(time(NULL));
	k = rand() % j;
	p = _str[k];
	k = rand() % j;
	q = _str[k];
	/* }} */

	// 2.
	n = p * q;
	// 3.
	phi_n = phi(p, q);
	
	// 4.
	while (gcd(e, phi_n) != 1) {
		e++;
		if (e > n) {
			free(str);
			free(_str);
			return 0;
		}
	}

	// 5.
	d = inverse(e, phi_n);
	// 6.
	a = rand() % n;
	c = expo_algorism(a, e, n);
	if (expo_algorism(c, d, n) == a)
		printf("공개키: %u, 비밀키: %u\n",e,d);
	printf("p: %u, q: %u\n", p, q);

	free(str);
	free(_str);
	return 0;
}