RSA
순서
- 256 보다 작은 소수 p와 q를 에라토네스 체 사용해서 구하시오. (단 p > q)
- n = p * q 를 계산하시오.
- phi(n) = phi(p*q) = phi(p)*phi(q) = (p-1) * (q-1)을 계산하시오.
- 암호 키 e, (0 < e < n, gcd(e, phi(n)) = 1)을 선택하시오.
- 복호키 e * d = 1 mod phi(n) 인 d를 구하시오.
- N 보다 작은 수 a 에 대해, a ^ e mod n = c 를 계산하시오.
- 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; }
게시물은 차후 수정하겠습니다.