PUSH_PUSH Video

[onedrivefile id=”file.c18eeaaf089d2b4b.c18eeaaf089d2b4b!10735″]

Main Func

[onedrivefile id=”file.c18eeaaf089d2b4b.c18eeaaf089d2b4b!10734″]

Move Func

[onedrivefile id=”file.c18eeaaf089d2b4b.c18eeaaf089d2b4b!10732″]

AddRandomBlock Func

[onedrivefile id=”file.c18eeaaf089d2b4b.c18eeaaf089d2b4b!10731″]

Display & FinishCheck Func

[onedrivefile id=”file.c18eeaaf089d2b4b.c18eeaaf089d2b4b!10733″]

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

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

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

고속 누승 알고리즘과 모듈러 연산

누승 알고리즘이란 거듭 제곱을 의미하고 모듈러 연산이란 % 연산자이다.

거듭 제곱은 while 문으로 계속 a를 곱하면 되고
모듈러는 % 연산자로 해결 하면 되니 바로 코드를 짜보자.

int expo_algorism(int a, int b, int n)
{
    int result = 1;

    while( b > 0 )
   {
      result  = (result * a) % n ;
      b--;
    }
     return result;
}

a ^ b mod n 의 값을 계산 해주는 코드가 바로 완성 됬다.

하지만 여기서 문제가 하나 있다. 암호 수학 에서 쓰는 수는 매우 큰 숫자를 사용한다.
그렇기에 a ^ b 에서 b=1000이 넘어가 버리면 약 10^300 년 정도 걸리기에 실 사용이 불가능하다.

그렇기에 위와 같은 문제점을 해결한 알고리즘을 짜보도록 하자.

a ^ 30 = (a ^ 15) ^2          : 제곱셈 1회
a ^ 15 =  (a ^ 7 )^2 *  a    : 제곱셈 1회 + 곱셈 1회
a ^ 7   = (a ^3 ) ^ 2 * a     : 제곱셈 1회 + 곱셈 1회
a ^ 3   = (a ^ 2 ) ^ a          : 제곱셈 1회 + 곱셈 1회

               총                        : 제곱셈 4회 + 곱셈 3회 = 7회

이렇게 계산 한다면 계산 횟수가 확실히 적어지게 된다.

그럼 위의 알고리즘을 이용하여 코드를 만들어 보도록 하자.

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

이 코드도 a ^ b mod n 을 계산해 주는 프로그램이지만 개선된 알고리즘을 사용해 더 빠른 속도로 연산을 해낼 수 있게 되었다.

간단히 분석해보자면

1.

 if(b & 1)
      {
         result = (result * a) % n ;
      }

이 부분은 b&1(=b가 홀수) 일 때 × a를 하고 mod n 값을 구한다.

2.

       b /= 2;   
       a  = (a * a) % n ;

지수 (b)를 절반씩 줄이고 a에 a^2을 한 뒤 mod n 의 값을 넣는다.

이것으로 RSA를 만들기 위한 준비는 끝이 났다.

다음 글에선 부가적인 설명 없이 바로 RSA를 만들도록 하겠다.

확장 유클리드 알고리즘

m, n이 gcd(m,n) = 1인 경우 유용한데, 그럼 위의 식은 am + bn = 1이 되고, 여기서 a는 모듈로 연산의 곱의 역원(modular multiplicative inverse)이 되기 때문이다.
출처 : 위키백과

확장 유클리드 알고리즘은 RSA를 만들기 위한 과정 중 복호키(또는 비밀키 라고도 부른다)를 구하기 위해 필요한 알고리즘이다.
일단 지금은 이 정도만 알고 넘어가도록 하자.

확장 유클리드 알고리즘은 정말 단순히 유클리드 알고리즘(gcd)연산을 거꾸로 한 것이다.
수식으로 설명을 들어보자,

a , b = 서로소인 두 정수(알기 쉽게 설명하기 위해서 서로소로 정했다\\ 원래는 어떤 수 라도 상관 없다.)
r(1),r(2),r(3)… = 나머지
q(1),q(2),q(3)… = 몫

라고 하면, 유클리드 알고리즘은

gcd(a,b)
=> a = b*q(1) + r(1)           >> gcd(b,r(1))
=> b = r(1)*q(2) + r(2)       >> gcd(r(1),r(2))
=> r(1) = r(2)*q(3) + r(3)   >> gcd(r(2),r(3))
……
=> r(n-1) = r(n)*q(n+1) + r(n+1)     >> gcd(r(n),r(n+1))
=> r(n) = r(n+1)*q(n+2) + 1             >> gcd(r(n+1),r(n+2))
=> r(n+1) = 1*r(n+1) + 0                  >> gcd(1,0)
∴ gcd(a,b) = 1

이렇게 진행 된다.

=====================================================

이제 확장된 유클리드 알고리즘 이용해 보자.
방법은 단순히 위에 연산을 거꾸로하고 대입하여 한 식으로 계산하면 된다, 아래를 참고하자.

[원래는 1 부터지만 거꾸로 계산했다는 것을 보여주기 위해 0부터 시작하겠다.]
0 = r(n+1) – 1*r(n+1) <=> r(n+1) = 1*r(n+1) + 0
1 = r(n) – r(n+1)*q(n+2) <=> r(n) = r(n+1)*q(n+2) + 1
r(n+1) = r(n-1) – r(n)*q(n+1) <=> r(n-1) = r(n)*q(n+1) + r(n+1)
……
r(3) = r(1) – r(2)*q(3) <=> r(1) = r(2)*q(3) + r(3)
r(2) = b – r(1)*q(2) <=> b = r(1)*q(2) + r(2)
r(1) = a – b*q(1)  <=> a = b*q(1) + r(1)

이제 거꾸로 구한 식을 한 식에 모두 대입하자. (복잡하니 n = 2 라고 두자)  (a, b, q(),r() 은 모두 상수 이다. )

[“0 = ~”은 양변이 모두 0 이므로 사용 할 수 없으니 “1 = ~”를 사용했다]
1 = r(2) – [r(1) – [b – [a – b*q(1)]*q(2)]*q(3)]*q(4)

이렇게 식을 만들고 정리 하면 1 = ☆×a + ★×b  이런 모양이 된다.

∴   1 ≡ ☆×a + ★×b (mod a) 라면, ★값이 역원(우리가 찾는 값) 이고
　  1 ≡ ☆×a + ★×b (mod b) 라면, ☆ 값이 역원 이다.

즉, mod a 라면 b에 곱해진 수가 역원 mod b라면 그 반대 라는 것이다.

(∵  A≡R (mod P) 이면. A = A*X + R 양변에 P를 더해 준다면 => A + P = P* (X + 1) + R이다.
따라서 나머지(다른)값은 변화가 없음으로, 위에서 mod a 일때, ☆×a 값을 무시 할 수 있다.)

자 이렇게 확장 유클리드 알고리즘에 대한 기본 설명은 끝났다.

이해가 잘 가지 않을 수도 있으니 간단한 예를 들어보자.

a = 576, b = 31

유클리드 알고리즘

576 = 31 × 18 + 18
31 = 18 × 1 + 13
18 = 13 × 1 + 5
13 = 5 × 2 + 3
5 = 3 × 1 + 2
3 = 2 × 1 + 1         ∴ gcd(576,31) = 1, 서로소 이다.

확장 유클리드 알고리즘(빠르게 계산 하기 위해 바로 “1 = ~”으로 시작하겠다.)

1 = 3 – 2 × 1
   = 3 – [5 – 3 × 1] × 1
   = 3 – [5 – [13 – 5 × 2] × 1] × 1
   = 3 – [5 – [13 – [18 – 13 × 1] × 2] × 1] × 1
   = 3 – [5 – [13 – [18 – [31 – 18 × 1] × 1] × 2] × 1] × 1
   = 3 – [5 – [13 – [18 – [31 – [576 – 31 × 18] × 1] × 1] × 2] × 1] × 1
──────────이해를 위한 순서──────────┘
   = 1 = 3 – 2
   = 3 – (5 – 3)
=> 2 * 3 – 5                                   << 정리를 해야 나중에 원하는 모양이 나옴
   = 2 * ( 13 – 5 * 2 ) – 5
=> 2 * ( 13 ) – 5 * 5
   = 2 * 13 – 5 * ( 18 – 13 )
=> -5 * ( 18 ) + 7 * 13
   = -5 * 18 + 7 * ( 31 – 18 )
=> 7 * 31 – 12 * ( 18 )
   = 7 * 31 – 12 * ( 576 – (31 * 18) )
=> -12 * 576 + 223 * 31
──────────실제 계산 순서──────────┘

   => -12 × 576 + 223 × 31 ≡ 1 (mod 576)
∴ 역원(우리가 찾는 값)은 223 이다.

위 알고리즘을 이용해 C언어로 코딩 하기전에 잠깐 생각해야 되는 부분이 있다.
우리가 필요한 값은 결과로 나오는 1 = ☆×a + ★×b 중에서 ☆or★이라는 점을 기억 해야 한다.

이제 한번 코딩해 보자.

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

INT inverse(INT a, INT b) {
	long 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;
}

1 = ☆×a + ★×b 일때,

이렇게 정리 할 수 있다. 이번 글은 이해하기 어려웠다. 하지만 차근차근 하다 보면 이해 할 수 있을 것이다.

다음 글에선 이것 보다 간단한 고속 누승 알고리즘에 대해 알아보도록 하자.

부록 _ RSA에선 어떻게 쓸까?

e × d ≡ 1 (mod (N))에 이미 알고 있는
N [= p×q, 임의의 두 소수p, q] \\ (N)[= (p-1)(q-1)] \\ e (= gcd(e,(N)) = 1이 되는 e)의 값을 대입하여 확장 유클리드 알고리즘을 이용해 비밀키 d 값을 구한다.

참고 글 : 1, 2, 3

최대공약수 (유클리드 알고리즘을 이용)

gcd(a,b)로 표현 하기도 하는 이번 글에선 최대공약수를 다뤄보려고 한다.

우리가 보통 최대공약수를 구하는 방법음 다음과 같다.

2 │ 48  18
3 │ 24   9
   └────
         8     3
이렇게 구한 뒤에 세로로 곱한다면 최대공약수가 나오는 방식으로 여태까지 구해 왔다.

하지만 컴퓨터는 이러한 방법으로는 최대공약수를 구하지 못한다.
또한 각 수를 모두 소수로 분해해야 하기에 매우 비효율적이다.

지금부터 컴퓨터가 해결할 수 있도록 위에서 구한 식을 함수 gcd(a,b)를 이용해 풀어보자.

======================================================================

그전에 먼저 mod(모듈러)에 대해 알아야 한다.
mod 계산은 C언어의 %연산자와 같은 역할은 한다. 즉, 나머지를 구하는 연산자라는 것이다. 

예를 들어,

105 mod 10 = 5 이다.

또한 mod연산자는 양쪽에 쓰지 않고 한쪽으로 몰 수 있는데,
105 = 15 (mod 10) 이렇게쓰여 있다면,
105 mod 10 = 15 mod 10
5 = 5가 된다.

======================================================================

그럼 이제 다시 최대공약수로 돌아가서 함수 gcd(a,b)에 대해 알아보자.

함수 gcd(a,b)의 작동 방식은 gcd(a,b) = gcd(b,a mod b)로 매우 단순하다.
예를 들어, a=48, b=18 이라면,

gcd(48,18) = gcd(18,12) = gcd(12,6) = gcd(6,0) 이 된다.
그리고 b=0이므로 gcd(48,18) = gcd(6,0)= 6 이다.
즉, b자리가 0이되면 최대공약수는 a인 것이다.

자 이제 알고리즘을 만들어 보자 (유클리드 알고리즘)

1. gcd(a,b)에서 b값이 0이 아니라면, a mod b 연산을 실행
2. a 자리에 b를 넣고 a mod b의 결과를 b의 자리에 넣는다.
3. 1,2를 반복한다. 만약 b=0이라면 a값이 최대공약수이다.

알고리즘은 mod 만 안다면 매우 간단하다.
이제 알고리즘을 C로 코딩해보자.

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

INT gcd(INT a, INT b) {
	if (0 == b) return a;
	return gcd(b, a % b);
}

끝이다. 정말 이게 끝이다.
솔직히 이런 방법은 생각치도 못했었다. 하지만 누가 2줄로 완성했다는 소리를 듣고 어떻게 짜야 2줄 이내로 짤 수 있을까 고민 하던 중

“반환 값을 함수로 주면 되겠다.” 라는 생각에 실제로 해보니 결과는 성공적이였다. 여기서 한 수 알아갔다.

이로써 최대공약수와 소수를 찾을 수 있게 되었다.

이제 N=p×q, (N) = (p-1)(q-1)와 유클리드 호제법만 만들면 RSA를 만들기 위한 기본적인 함수 준비는 모두 끝나게 된다.