RSA

순서

1. 256 보다 작은 소수 p와 q를 에라토네스 체 사용해서 구하시오. (단 p > q)
2. n =  p * q 를 계산하시오. 
3. phi(n) = phi(p*q) = phi(p)*phi(q) = (p-1) * (q-1)을 계산하시오.
4. 암호 키 e, (0 < e < n, gcd(e, phi(n)) = 1)을 선택하시오.
5. 복호키 e * d = 1 mod phi(n) 인 d를 구하시오. 
6. N 보다 작은 수 a 에 대해, a ^ e mod n = c 를 계산하시오.
7. c ^ d mod n = a 인지 확인하시오.

코드

#include "Self_Cryptograph_Math.h"

INT phi(INT p, INT q) {
	return (p - (INT)1)*(q - (INT)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;
	/* 임의의 소수 찾기 {{ */
	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(time(NULL)) % 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;
}

추가적 내용

inverse 코드가 잘 못 되어 답이 나오지 않았습니다.
만약 2015 / 10 / 22 일자 inverse 코드를 보고 오신 분은 아래의 코드로 바꾸어 주시면 정확한 결과가 나옵니다. 죄송합니다.

INT inverse(INT a, INT b) {
	long E, N, q, r, s, t, u;
	E = a;
	N = b;
	t = 0; u = 1;

	while (E != 1)
	{
		q = N / E;
		r = N - E*q;
		s = t - u*q;
		N = E;
		E = r;
		t = u;
		u = s;
	}
	if (u < 0)
		u = u + b;
	return u;
}

게시물은 차후 수정하겠습니다.