PushPush 순서도(알고리즘) 만들기

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″]

 

제 7-1강 RSA_완성(Code Only)

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

 

[제 7강] RSA

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

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

[제 6강] 고속 누승 알고리즘과 모듈러

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

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

거듭 제곱은 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를 만들도록 하겠다.

[제 5강][수정됨] 확장 유클리드 알고리즘.function

확장 유클리드 알고리즘

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 일때,

t1 << 우리가 찾는 값
t2
a r1
b r2
t, q, r 임시 저장 공간(단, q는 몫을 임시 저장한다)

 

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

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

 

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

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

 

참고 글 : 123

[제 4강] 최대공약수.function

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

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를 만들기 위한 기본적인 함수 준비는 모두 끝나게 된다.

 

 

 

[제 3강] 소수 찾기.function

소수 찾기

소수를 찾는 방법을 찾기 위해서 에라토스테네스의 체를 사용하겠다.

에라토스테네스의 체란 소수를 찾는 가장 간단한 방법이다.
예를 들어, 1 ~ 10 까지의 정수 중에서 소수를 찾는다면,

1. 1은 소수도 합성수도 아니므로 제외
2. 다음 수인 2는 소수, 2의 배수는 모두 지운다.
3. 다음 수인 3는 소수, 3의 배수는 모두 지운다.
4. 다음 수인 5는 소수, 5의 배수는 모두 지운다.
5. 다음 수인 7는 소수, 7의 배수는 모두 지운다.
6. 다음 수가 없다. 따라서 10 이하의 소수는 {2, 3, 5, 7}이다.

이렇게 구할 수 있다.

또한 한 가지 더 있다. 만약 에라토스테네스의 체를 이용하여 1 ~ N 까지의 소수를 구한다면, n까지 모든 수의 배수를 다 나누지 않아도 된다.
n이하의 어떤 수 a, b에 대해서 a와 b중 적어도 하나는 n 이하 이다.
즉, n보다 작은 합성수 m(a×b)n​ 보다 작은 수배수만 체크해도 전부 지워진다는 의미이다.
_조금 설명을 위해선 더 이해가 필요하다_

 

이제 알고리즘을 짜보자.

 

Find Prime Number Algorism

1. 시작 숫자는 3 이고 마지막 숫자는 fn(Final Number) 이다.
(∵ 2 이하의 수는 이미 소수 인 것을 알고 있고, fn는 정의 참고)
2. 수는 2더해 간다.(∵ 짝수는 이미 소수가 아니기 때문이다.)
3. 다음 소수의 배수를 모두 지운다.
4. 다음 소수까지 증가한 후, 위 내용을 반복하여 fn 까지의 소수를 구한다.

 

그럼 위 알고리즘을 C언어로 구현해 보자.

#include <stdio.h>
#include <stdlib.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 main(void) {
	char * num_str;
	INT fn, i;
	fn = 100;

	num_str = calloc(fn, sizeof(char));

	Find_Prime_Number(num_str, fn);
	
	/* 소수 출력 {{ */
	for (i = 3; i < fn; i+=2) {
		if(0==num_str[i])
			printf("%u ", i);
	}
	/* }} */
	
	free(num_str);
	return 0;
}

변수 설명

start 시작 값
fn 마지막 값
num_str start~fn 까지의 수

잠시 주목할 점은 “num_str[i]
배열 안에 들어 있는 수는 0(소수) 1(합성수)로, 판단시에만 쓰이고
그 배열의 이름인 “i” 값이 바로 소수가 됨

 

 

[제 2강] RSA

   RSA

기본 개요
        공개키 암호화 방식으로 공개키와, 비밀키를 가지고 암호화 하는 방식이다.
        공개키로 누구나 사용하여 파일을 암호화 시킬 수 있지만, 복호화(해독) 하기 위해선 비밀키가 필요한 암호화 방식이다.

RSA의 키를 생성하는 방법

1. 서로 다른 두 소수 p , q 를 구한다.
2. 값이 p × qN(=p × q)을 구한다.
3. (N) = (p-1)(q-1)를 구한다.                                          = phi
4. (N)보단 작고, (N)서로소인 정수 e를 찾는다.
5. 확장된 유클리드 호제법을 이용하여 d·e ≡ 1 (mod (N))

이를 통해 필요한 함수를 생각해 본다면

1. 소수를 찾는 함수
2. N=p×q, (N) = (p-1)(q-1)를 구하는 함수.
3. 제곱 승을 구할 수 있는 함수.
4. 서로소를 찾는 함수. 즉, 최대공약수를 구하는 함수.
5. mod (나머지 연산)을 구하는 함수.
6. 확장된 유클리드 호제법 함수.

이렇게 6가지 이다.

RSA의 키를 생성하는 순서에 따라
그에 필요한 함수 코드를 가지고 공부해보자.