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; }