005. 큰 수에 대한 프로그래밍

1.1 프로그래밍

앞 장에서 큰 수에 대해서 왜 별도의 프로그래밍을 해야하는지 살펴봤다. 별도라는 것은, 프로그래밍 언어에서 지원하는 기본 자료형과 연산자를 사용하지 않고 새로운 표현방법과 연산함수들을 만들어야 함을 의미한다. (Java에서는 BigInter라는 클래스를 기본으로 제공해서, 이 클래스를 사용하면 큰 수에 대한 연산을 할 수 있긴 하다. 그렇지만 C, C#에서는 기본으로 존재하지 않음)

 

이 글에서는 알고리즘에 대한 구현을 주로 C언어를 사용해서 할 것이다. 

• GUI가 필요한 응용프로그램은 C#으로 할 것임. 이 때 C로 짠 부분을 DLL로 만들어서 사용할 것임
• Java로도 짜볼 생각이나, 진행되는 것을 보면서 가변
• 프로그래밍 툴은 Visual Studio 2010 사용

이제 앞장에서 얘기한 큰 수에 대한 프로그래밍을 해보자.

먼저 큰 수를 처리하기 위해서 필요한 사항들을 정의한 헤더파일을 만들어야할 것이다. 프로그래밍이 진행되면서 최종 헤더는 좀 더 복잡한 형태가 될 것이나, 가장 기본적인 사항은 다음과 같을 것이다.

5개 부분으로 나눠서 살펴보자

//01. CPU, 컴파일러에 따라서 조정할 값들
#define MAX_BIT_LEN 4096  //최대 비트수
typedef unsigned char u8;
typedef unsigned short u16;
typedef unsigned long u32;
typedef unsigned long long u64;
#define BASE_IS_4_BYTES  
#ifdef BASE_IS_4_BYTES
	typedef u32	INT;
	typedef u64	DINT;
	#define MAX_INT		0xffffffff
	#define BASE		0x100000000
	#define MAX_DINT	0xffffffffffffffff
	#define MAX_POSITIVE 0x7fffffff	
#else
	typedef u16	INT;
	typedef u32	DINT;
	#define MAX_INT		0xffff
	#define BASE		0x10000
	#define MAX_DINT	0xffffffff
	#define MAX_POSITIVE 0x7fff
#endif

 

MAX_BIT_LEN

MAX_BIT_LEN은 이 프로그램에서 사용될 수 있는 최대 비트수를 나타낸다. 4096정도이면 충분할 것이고, 만약 메모리공간이 부족한 Embedded System에서의 프로그래밍이면 2048, 1024 혹은 더 작은 수로 지정하면 된다.

 

크기별 자료형 정의(typedef)

CPU, 컴파일러 별로 자료형 크기가 다를 수 있으므로, 혼돈되서 사용되지 않도록 크기별 자료형을 별도로 지정한다. 별도로 만든는 큰수에 대한 기본연산 및 암호화 연산 함수들에서는 부호구분없는 자료형을 사용하는 것이 편리하므로, 전부 부호구분없는 unsigned를 사용한다.

만약 사용하려는 시스템이 64비트 연산자인 unsigned long long을 지원하지 않는다면, u64에 대한 정의부분을 없애고, 또한 BASE_IS_4_BYTES를 정의하지 않고, 큰 수를 표현하는 배열의 자료형을 16비트를 사용하도록 한다.

 

BASE_IS_4_BYTES

64비트 자료형을 지원하는 시스템에서는 #define BASE_IS_4_BYTES 하도록 하고, 그렇지 않은 경우는 정의되지 않도록 주석처리한다.

배열의 자료형으로 32비트의 long 자료형을 사용하는 경우, 배열의 초기값을 특정 상수값으로 지정해야할 필요가 있다. (예를 들어 0으로 초기화)

이 경우, 컴파일러에 따라, 0L로 표현해야 컴파일할 때 warning이 안 뜬다. 따라서, warning이 뜨는 것을 막아주기 위해 별도로 ZERO를 알맞게 정의

 

//02. 큰수(BIGINT)에 대한 정의들. CPU에 따라 재정의할 필요 없음

#define MAX_INT_LEN (MAX_BIT_LEN / (sizeof(INT) * 8) ) //INT자료형 최대 갯수 4096/32 = 128

typedef INT BIGINT[MAX_INT_LEN + 1]; //[0]위치에 크기정보 담고 있으므로 + 1

MAX_INT_LEN

MAX_INT_LEN은 큰 수를 배열로 표현할 때, 최대 몇개의 배열인자가 생성되는지를 보여주는 값이다. 이 값은 위에서 정의한 MAX_BIT_LEN을 배열에서 사용하는 기본자료형의 비트수로 나눠서 얻어진다.

예를들어, MAX_BIT_LEN이 4096이고, 배열 기본자료형으로 32비트를 사용한다면, MAX_BIT_LEN = 4096/32 = 128

 

BIGINT

큰 수를 표현하기 위해 만든 자료형이다. "BIGINT a; "와 같이 정의 되었다면, 이것은 다음과 같이 선언된 것과 동일하게 된다.

    unsigned long  a[129];

 

129개 크기의 unsigned long형 배열인것이다. 이 배열의 첫번째 위치에는 크기정보가 들어갈 것이다. 예를들어 a[0]의 값이 2이면 a[1]과 a[2]의 값만 유효한 값(나머지는 0으로 채워져 있을 것임)

수는 배열첨자가 큰 쪽에서 채워짐. 즉, 0x1122334455667788을 BIGINT로 표현하면 다음과 같이 됨

  [0]=2

  [1] = 0x55667788

  [2] = 0x11223344

 

사족 ;

주소의 첫번째 위치에 크기정보가 들어가 있으므로, 배열이 아닌 포인터로 처리하면 작은 수를 표현할 때 메모리를 아낄 수 있을 것이다.(a[129]처럼 배열의 크기를 129로 지정했기에, 위에서 처럼 배열의 2개값만 유효한 작은 수를 표현할 때도, 메모리는 129개 unsigned long으로 할당)

    즉, #define *INT BIGINT;

그러나, 이 프로그램에서는 확정된 크기를 가지는 배열로 BIGINT를 정의할 것이다. 이유는, buffer overflow 등 사용자의 실수 혹은 악의적인 공격을 맞기 위해서이다. 아래예를 보자.

두 큰 수 a와 b의 곱을 c에 저장하는 multiply(BIGINT a, BIGINT b, BIGINT c)라는 함수의 구현을 생각해 봤을 때, 만약 BIGINT가 포인터형 변수라면, 사용자가 a와 b의 곱에 의해 생성되는 값보다 적은 메모리만큼을 c에 할당하고 함수콜을 한 경우에 overflow가 발생할 것이다. (함수내에서는 이것을 방지하기 위해서 c의 크기를 확인하는 번거로운 작업이 필요. 이런게 없다면 문제 발생)

반면에 확정된 크기를 가지는 배열로 BIGINT를 사용하면, 메모리의 낭비일 수는 있으나 현재 각 방면에서 사용되고 있는 컴퓨터 시스템들이 몇백 바이트의 메모리사용에 문제되지 않을것이라 생각하고, 암호화연산이 주로 안정성이 최우선시되는 보안시스템에 주로 사용되므로, 포인터로 접근했을 때 부주의로 인해 야기될 수 있는 위험성이 없는 배열로 사용함

 

//03. 매크로들
#define SIZE(n)			((unsigned short)*(n)) 
#define SET_SIZE(n,m)	(*(n) = (unsigned short)(m))
#define REMOVE_ZERO(n)		while((SIZE(n)>0) && (*((n) + SIZE(n)) == 0)) --*(n);

 

 

BIGINT관련 유용한 매크로들은 더 추가될 것이나, 가장 기본적인 두 가지만을 살표본다.

 

SIZE

SIZE는 BIGINT의 크기를 리턴한다. 즉, BIGINT의 크기정보는 해당 배열의 첫번째 인자에 위치하므로, 배열의 첫번째 인자를 읽으면 되는 것이다.

배열의 자료형은 BASE_IS_4_BYTES의 정의 여부에 따라 2바트의 unsigend short 혹은 4바이트의 unsigend long이고, 배열의 크기는 MAX_BIT_LEN에 의해 결정되기는 하나 16비트로 표현할 수 있는 65536에는 충분히 미치지 못할 것이기에, 배열의 크기 표현을 unsigned short로 한다.(즉, 배열의 첫번째 인자를 읽어서 unsigned short로 캐스팅)

사용은 다음과 같이 하게 된다.

   BIGINT a, BIGINT b;

   ...

   if(SIZE(a) > SIZE(b){

 

SET_SIZE

BIGINT의 크기를 세팅한다. 즉, 해당 배열의 첫번째 인자에 크기정보를 넣는다.

사용예는 다음과 같다.

   BIGINT c;

   ...

   SET_SIZE(c, 3);

 

REMOVE_ZERO

수의 앞쪽에 있는 zero들을 없애서, 실제 유효한 값들만을 가진 BIGINT로 만들어 준다.

예를 들어 size가 5이지만 앞 두 자리가 0인 수는, 앞에 있는 두 자리 0을 없애서 size가 3이 되게 한다.

0005 1111 2222 3333 0000 0000 --> 0003 1111 2222 3333

 

 

//04. Error

#define OK            0

#define E_Overflow   -1

BIGINT관련 함수에서 리턴하는 에러코드를 정의한다.

성공했을 경우는 0을, 그 외에는 0이아닌 다른 값으로 정의한다.

여기선 가장 기본적인 OK와 Overflow가 발생했을 때의 코드만을 정의했는데, 프로그래밍이 진행되면서 더 추가될  것이다.

 

//05. 함수정의

int add(BIGINT A, BIGINT B, BIGINT C);

외부에서 호출되는 함수들이 정의될 것이다. add, substract, multiply 등 등.

 

다음 장부터는 두 큰 수의 합을 구하는 함수부터 시작해서, 기본적인 연산함수들을 만들어 나갈 것이다.