티스토리 뷰
안녕하세요. 경희대 2차 면접에서 비록 떨어졌지만 1차 서류평가에서 만들어 둔 실적물 내용이 너무 아까워서 여기에라도 올리려고 포스팅합니다. 전기, 전자, 컴퓨터공학과 같은 공대나 수학과 같은 자연계열 대학에 진학을 위해 생기부에 넣을 내용이 없다 싶으면 해당 본문을 참고해서 적으셔도 상관없습니다. 마음데로 쓰세요. 이 소스를 짤 때 위키백과와 많은 분들의 자료를 참고했습니다.
RSA 암호란?
RSA암호는 공개키 암호 시스템의 하나로, 이미 많은 곳에서 사용되고 있는 암호 시스템입니다. 먼저 암호 시스템을 이해해 봅시다. 암호 시스템은 대표적으로 두 개의 키가 사용되는데 대표적으로 공개키와 비밀키가 있습니다. 공개키는 말 그대로 누구든지 이 키를 알아도 상관이 없는 공개된 키라고 이해하면 편합니다. 공개키는 전달하고자 하는 값을 암호화하는 역할을 수행합니다. 즉 누구든지 공개키를 가지고 어떤 값이든 암호화를 할 수 있겠죠? 하지만 복호화는 자유롭지 않습니다. 공개키에 대응하는 비밀키를 가지고 있어야만 복호화가 가능하기 때문입니다.
즉, RSA암호 알고리즘은 소인수분해의 어려움을 이용하여 비밀키를 찾기 힘들도록 만든 알고리즘입니다. 여기서 "중학교 때 배운 소인수분해가 왜 어렵지?"라는 의문을 가질 수도 있을 겁니다. 30이라는 수를 소인수분해하면 2x3x5 이겠죠. 그럼 2132341이라는 수를 소인수분해 해볼까요? 나누어 떨어지는 작은 수부터 찾아가면서 소인수를 찾기에는 매우 오랜 시간이 걸립니다. RSA암호는 이러한 아이디어를 이용해 만들어졌습니다.
※ 개인키 = 비밀키
RSA 암호 공개키 & 비밀키 생성
그럼 이제 RSA암호의 공개키와 비밀키 생성 알고리즘에 따라 C언어로 코드를 작성해 봅시다.
void Generate_Key(int p, int q){
int i;
int n, e, d, f; // 공개키: (n, e) 비밀키: (n, d)
n = p * q;
f = (p-1) * (q-1); // f == 𝛗(n)
for (i = 2; i < f; i++) {
if (gcd(p-1, i) == 1 && gcd(q-1, i) == 1) {
e = i;
break;
}
}
for (i = 1; i < n; i++) {
if ((f*i + 1) % e == 0) {
d = (f*i + 1) / e;
break;
}
}
printf("Public Key: (%d, %d)\n", n, e);
printf("Private Key: (%d, %d)", n, d);
}
int gcd(int a, int b){
return b ? gcd(b, a%b) : a;
}
먼저 인자로 받은 p와 q를 곱하여 n을 구합니다. 여기서 p와 q는 서로 다른 두 소수여야 합니다.
두 번째로는 𝛗(n)을 구해야 합니다. 𝛗(오일러 파이 함수)는 임의의 양의 정수 n에 대하여, n 이하의 양의 정수 중 n과 서로소인 양의 정수의 개수를 함숫값으로 갖는 함수입니다. 만약 오일러 파이 함수에서 독립변수로 소수 n을 입력받으면, 함숫값은 n-1이 나오겠죠? 왜냐하면 소수는 자기 자신을 빼고는 자기보다 작은 수 중 어떤 것을 선택해도 서로소이기 때문입니다. 즉 오일러 파이 함수에서 받은 임의의 양의 정수 n이 소수일 경우 함숫값은 무조건 n-1입니다. 그럼 𝛗(p)와 𝛗(q)는 각각 p-1과 q-1입니다. n은 p와 q를 곱한 것이기 때문에 오일러 파이 함수의 성질에 의해 𝛗(n)은 (p-1)(q-1)이 됩니다.
세 번째로, 𝛗(n)보단 작고 𝛗(n)과 서로소인 수 e를 구합니다. 서로소는 그냥 반복문 돌려서 나눠보면 나오겠죠? 이 정도는 누구나 다 만들 수 있을 거라 믿습니다. 여기서 저는 𝛗(n) 값이 (p-1)(q-1)이기 때문에 p-1과 q-1 각각으로 소인수를 확인함으로써 미세하지만 살짝의 효율을 높였습니다.
마지막으로 확장된 유클리드 호제법을 이용해 de ≡ 1 (mod 𝛗(n)) 을 만족하는 d를 구합니다. 확장된 유클리드 호제법에 대한 내용은 따로 찾아보시길 권장합니다. 대충 설명하자면 임의의 미지수 x에 대하여 d*e + 𝛗(n)*x = 1이라는 부정방정식 형태에서 반복문을 이용해 미지수 x값을 변화시킴으로써 d를 도출합니다.
RSA암호 암호화하기
void Encryption(char *string, int n, int e){
int i, j;
int k = 1;
for (i = 0; i < strlen(string); i++) {
if ((int)string[i] < 0 || (int)string[i] > n) {
printf("Error Occurred by 'm' value.... Out Of range (0<m<n)\n");
printf("Choose p and q as large enough.");
return;
}
for (j = 0; j < e; j++) {
k *= (int)string[i];
k %= n;
}
printf("%d ", k);
k = 1;
}
}다음 함수는 원문 m을 암호화하는 함수입니다. 여기서 저는 문자열도 암호화하고 싶다는 생각을 가졌는데요. 그래서 저는 문자열을 매개변수(string)로 입력받아 각 자리의 문자에 대응하는 아스키코드 값을 암호화하고자 했습니다. 여기서 가장 중요한 것은 원문 m의 범위인데요. RSA 암호 알고리즘을 보면 알 수 있듯이 무조건 원문 m은 0보다 크고 공개키의 첫 번째 자리에 들어가는 n값보다 작아야 합니다. 그러므로 조건문을 통해 범위를 지정했습니다. (실제로 이 부분에서 암호화가 정상적으로 진행되지 않아 한참 막혔습니다...)
위 조건이 만족하면 암호화를 진행해야 합니다. 암호화는 단순하게 m^e mod n을 하면 됩니다.
RSA암호 복호화하기
void Decryption(char *string, int n, int d){
int j;
int k = 1;
char *str = strtok(string, " ");
while (str != NULL) {
for (j = 0; j < d; j++) {
k *= atoi(str);
k %= n;
}
printf("%c", k);
k = 1;
str = strtok(NULL, " ");
}
}마지막으로 이 함수는 암호를 입력받아 복호화하는 함수입니다. 여기서 주의할 점은 각 자리의 암호를 띄어쓰기 단위로 입력받는 것입니다. 그냥 쭉 나열하게 되면 구분이 힘들겠죠?
"안녕"이라는 문자를 암호화한다고 가정해 봅시다. 그 결과로 "안"은 "12", "녕"은 "23"으로 암호화 결과가 나왔습니다. 그럼 복호화하기 위해서는 복호화하고자 하는 암호를 입력받아야겠죠? 만약 "1223"으로 입력받을 경우 이 값이 12와 23으로 나뉘는 건지 아니면 1223 전체를 나타내는지, 아니면 122와 3으로 나뉘는지 아무도 모릅니다. 그렇기 때문에 12와 23 사이를 띄어쓰기로 구분하여 입력받습니다.
즉 띄어쓰기로 입력받은 암호를 strtok를 통해 각각 잘라서 저장합니다. 각 자리의 암호들을 atoi함수를 통해 정수형으로 바꾸고 복호화 수식인 c^d mod n을 실행합니다. (여기서 c는 암호를 뜻합니다)
마지막으로
이번 활동을 하면서 가장 중요한 건 RSA 암호 알고리즘을 논리적으로 수학적으로 이해하는 것이 가장 중요합니다. 저 또한 일반고에 나온 저로써는 아직 배우지 않은 수학적 기호가 많이 나와 이해하기 힘든 부분도 많았지만 하나하나 찾아보면서 이해했습니다. 수학적으로 이해하지 않을 경우 중간중간에 오류를 범하는 순간이 많이 발생하고 결코 해결하지 못할 수도 있습니다. 특히 저는 암호화과정에서 원문 m의 범위를 잡는 부분을 모르고 지나가서 고생을 했습니다. 단순히 코드를 퍼가는 것보다도 RSA 암호에 대해 공부한다는 생각으로 사용해 주시면 감사하겠습니다.