004. 큰 수

1. 큰 수(數)에 대한 프로그래밍

1.1 큰 수

컴퓨터에서의 수는 메모리에 저장되어 있는 일련의 비트 정보이며, 프로그래밍을 할 때는 해당 컴파일러에 약속된 데이터 타입에 따라 그 크기(몇 바이트 메모리가 할당될 것인지)와, 소수점이 있는 수인지, 그냥 정수형태인지 등이 결정된다.

 

예를 들어 Java에서 int형태의 변수는 4바이트의 메모리 공간을 차지하도록 되어 있다. 따라서, 32비트의 메모리를 사용해서 표현할 수 있는 정 –(2³¹-1) ~ (2³¹-1)까지의 정수를 표현할 수 있을 것이다.

 

컴퓨터 프로그래밍에서 수를 이용하여 연산을 할 때는, 프로그래밍언어에서 제공하는 수의 형태를 지정하고, 기본 제공하는 연산자를 통해서 연산을 수행한다.

 

예를 들어 C언어에서 두 정수의 합을 구하는 것은 다음과 같이 쉽게 프로그래밍할 수 있다.

short a,b;

int c;

a = 100;

b = 100;

c = a + b;

C에서 short와 int형 변수의 크기는 사용되는 CPU와 Compiler에 따라 따르지만, 일반적으로 short는 2 Bytes, int은 4 Bytes의 크기를 가진다. 또한, 좀 더 큰 수의 표현을 위해서 8 Bytes의 메모리가 할당되는 double 혹은 long long 변수를 지원하기도 한다. 따라서, 대부분의 일반 프로그래밍에서 수에 대한 연산(+, -, x, /, % 등)을 할 때는 프로그래밍 언어에서 기본으로 제공하는 자료형과 연산자를 사용해서 하면 된다.

(C, C++, Java에서의 자료형별 할당 메모리 크기는 부록1. 참조)

 

그러나, 암호학관련 프로그래밍을 할 때는 얘기가 달라진다.

암호학에서 다루는 수는 프로그래밍언어에서 기본으로 제공하는 수에 비해 너무 큰 수를 다룬다.

예를들어, 비대칭키 알고리즘인 RSA의 경우, 1024비트 이상의 키를 사용하는데, 이 경우 1024비트보다 큰 수에 대한 더하기, 빼기, 나누기 등의 연산을 해야하고, 이 경우 프로그래밍언어에서 기본으로 제공하는 자료형과 연산자를 사용할 수가 없는 것이다.

 

따라서, 아주 큰 수에 대해 처리할 수 있는 방법을 생각해야 한다.

 

큰 수에 대한 표현방법

아주 큰 수는 기본 자료형으로는 표현할 수 없으므로, 기본 자료형을 연결해서 표현하는 것을 생각할 수 있다.

즉, 기본자료형인 int의 배열로서 큰 수를 표현하는 것인데, 이를 위해서 먼저 우리가 '수'라고 하는것을 표현하는 방법에 대한 기본적인 개념을 수학적으로 살펴볼 필요가 있다.

 

우리는 십진수에 익숙하고, 컴퓨터는 이진수 처리를 잘하도록 설계되어 있다.

십진수라는 것은 0~9까지의 수를 이용해서 각 자리를 표현하며, 각 자리는 10⁰, 10¹, 10²과 같은 10의 거듭제곱으로 나타내진다.

• 십진수 (9871)₁₀ = 9 x 10³ + 8 x 10² + 7 x 10¹ + 1 x 10⁰

이진수는 0,1의 수를 이용해서 각 자리가 표현되면, 각 자리는 2⁰, 2¹, 2²과 같은 2의 거듭제곱으로 나타내진다

• 이진수 (1101)₂ = 1 x 2³ + 1 x 2² + 0 x 2¹ + 1 x 2⁰

여기서 십진수의 경우 10, 이진수의 경우 2와 같은 것을 밑수(base) 혹은 기수(radix)라고 하며, 어떤 수에 대해 밑수(base) b를 이용해서 표현해 보면 다음과 같이 된다.

• (...a₃a₂a₁a₀a_-1a_-2...)_b = ... + a₃b³ + a₂b² + a₁b¹ + a₀ + a_-1b^-1 + a_-2b^-2 + ...

 

예를 들어 (345.7)₈ = 3 x 8² + 4 x 8¹ + 5 + 7 x 8^-1 이다.

 

이제 이것을 프로그래밍 언어의 기본 자료형을 밑수로 가지는 수로 생각해보자. 즉, 밑수 b를 65536(=2¹⁶)으로 가지는 수체계로 보면 다음과 같이 될 것이다.

• (...a₃a₂a₁a₀a_-1a_-2...)₆₅₅₃₆ = ... + a₃65536³ + a₂65536² + a₁65536¹ + a₀ + a_-165536^-1 + a_-265536^-2 + ...

여기서 각 자리의 계수인 a₃a₂a₁a₀a_-1a_-2는 2바이트 메모리크기를 할당받는 short형 배열로 나태낼 수 있을 것이다.

 

정리해보면, 컴퓨터 프로그래밍에서 큰 수의 표현은, 프로그래밍언어에서 기본 제공하는 자료형의 배열로서 나타낼 수 있고, 이때 배열의 값들은 최대값을 밑수로하는 진법에서의 계수가 되는 것이다.

 

어떤 기본 자료형을 밑수로 사용할 것인가?

큰 수에 대한 표현을 기본 자료형의 배열로서 나타낼 수 있다고 위에서 얘기했는데, 그렇다면 어떤 자료형을 사용하는 것이 좋은가?

두 가지 면에서 살펴봐야할 것이다. 첫째는 수행속도. 둘째는 호환성.

 

첫째 수행속도면에서는 기본형의 크기가 가능한 큰 것을 사용하는 것이 낫다. 즉, 1바이트 크기의 기본형(char)보다는 2바이트 크기의 자료형이 연산 수행속도면에서 빠른 성능을 보일 것이다. 왜냐하면, 1바이트의 기본형으로 100개의 배열인자로 표현이 가능한 큰 수에 대해서, 2바이트의 기본형으로는 50개의 배열인자만으로 표현이 가능할 것이고, 이는 연산 회수가 2배로 작아진다는 것과 동일하기 때문이다. (1 바이트 자료형에 대한 연산이든, 2바이트 자료형에 대한 연산이든 CPU에서 처리되는 명령 사이클 수는 동일하기에)

따라서, 수행속도만을 고려한다면(대부분 수행속도가 중요), 기본 자료형으로 가능한 큰 메모리를 차지하는 것을 사용한다. 예를 들어, 8바이트의 long long 타입이 지원되는 CPU라면, 4바이트의 int의 배열로 큰 수를 표현하는 것이 2바이트의 short형 배열로 표현하는 것보다 낫다. 여기서 8바이트의 long long타입이 지원되야 하는 것은, int와 int의 연산(+ 혹은 x) 결과를 저장하기 위해서는 int보다 큰 기본 연산자가 필요하기 때문이다.

 

둘째 호환성 측면은, CPU와 그에 따른 컴파일러에 따라 int라고 지정하더라도(C의 경우) 확보되는 메모리크기가 다를 수 있고, 8바이트 크기의 자료형을 지원하지 않는 경우도 있기에, 이를 고려해야한다는 것이다.

 

위의 두가지를 고려한 현실적인 방안은, 배열의 기본형으로 2바이트 혹은 4바이트로 전환할 수 있게 코딩을 하고, 컴파일할 때 해당 CPU에 따라서 2바이트 혹은 4바이트로 전환하게 하는 것이 좋을 듯하다. 왜냐하면 대부분의 CPU들이 최소한 4바이트의 자료형을 지원하고 있고(따라서 2바이트 자료형의 배열 사용 가능), 8바이트의 자료형을 지원하는 것도 있기 때문.

#define BASE_IS_4_BYTES //8바이트 자료형이 존재하는 경우 정의. 그렇지 않은 경우는 주석처리

#ifdef BASE_IS_4_BYTES

typedef BASE 0x100000000 //8바이트 자료형 지원되는 경우 Base는 2¹⁶

#else

typedef BASE 0x10000

#endif

 

수의 배열 방향

큰 수를 기본 자료형의 배열로 표현할 때, 한 가지 더 고려해야할 것이 있다.

그것은, 배열의 첨자가 작은 쪽에다가 표현할 수의 큰 계수(자릿수가 큰)를 넣을 것인지, 작은 계수(자릿수가 작은)를 넣을 것인가 하는 것이다.

예를들어, (a₃a₂a₁a₀)₆₅₅₃₆ = a₃65536³ + a₂65536² + a₁65536¹ + a₀과 같은 수를, 2바이트 short형 배열을 사용해서 값을 저장할 때 다음과 같이 두가지 방법이 가능하다.

• (방법1)A[0]=a₃, A[1]=a₂, A[2]=a₁, A[3]=a₀ ; {a₃ , a₂ , a₀}
• (방법2)A[0]=a₀, A[1]=a₁, A[2]=a₂, A[3]=a₃ ; {a₀ , a₁ , a₂}

(방법1)은 메모리에 배열이 저장될 때, 첨자가 작은 것에서부터 큰 순으로 저장되고, 또한 배열값을 표현할 때 첨자가 작은 것에서 큰 순으로 표현하기에, 메모리에 저장되어 있는 배열값을 읽는 다던가, 배열로 표현된 수를 읽을 때 직관적으로 읽을 수 있어 편리하다. (우리가 수를 적을 때 왼쪽부터 큰 수를 적고 오른쪽으로 가면서 작은수를 적기에)

 

(방법2)는 첨자가 작은쪽에 작은수가 있기에 배열의 값을 읽어야할 때 직관적이지 않으나, 위의 수의 표현에서 처럼, 수에서 표현된 첨자와 배열의 첨자가 같기 때문에, 일반적인 수의 표현에 대한 알고리즘이 주어졌을 때, 이를 코딩화할 때 수월하다. (위에서 A[0]=a₀ 처럼 첨자가 같기에 알고리즘으로 A[i]에 대해서 표현할 때, 그 i값과 배열에서의 i값이 같아지기에)

 

이 글에서는, (방법2)와 같이 수를 표현할 것이다.

 

최대값

이론상으로는 배열의 크기를 계속해서 늘린다면, 위의 배열에 의한 수의 표현방법에서, 거의 무한대에 가까운 수를 표현할 수 있다. 그러나, 실제 컴퓨터 프로그래밍에서는 메모리의 한계에 의해 제약을 받게 된다. 즉, 메인메모리가 1KB인 시스템에서는 1KBytes내에서 연산이 이뤄져야하기에 그보다 더 큰 배열을 사용할 수 없는 것이다. 따라서, 사용할 수 있는 최대 크기를 지정해 주는 것이 좋다. (다른 가상메모리를 사용해서 확장할 수 있을 때는 더 확장 가능) (현 PC의 기본 사양이 RAM 4GB 정도 되기에, 사실 PC의 경우는 암호학에서 사용되는 4096비트= 512바이트 정도의 수를 다루는 것은 전혀 문제가 되지 않는다. RAM용량에 제한을 받는 Embedded System에서의 얘기)

 

현실에서 RSA의 가장 큰 Key가 4096비트 정도이므로, 최대값으로 4096비트로 하고, 동작되는 CPU에 따라 컴파일타임에 조정하도록 하는 것이 좋을 것이다.

 

#define MAX_BIT_LEN 4096

 

크기정보

큰 수를 배열로 표현할 때, 위에서와 같이 최대값(최대 비트수)이 정해졌다면, 최대비트수 만큼의 메모리를 할당해놓고(최대값을 표현할 수 있는 큰 배열로 선언해 놓고), 그 배열을 사용하면 될 것이다. 그러나, 이렇게 하는 경우, 실제 작은 수에 대해서도 최대비트수 만큼의 메모리가 할당되어 사용되므로, 메모리 낭비가 발생한다.

 

메모리 낭비를 없애려면 가장 좋은 것이 필요한 비트수 만큼만 메모리를 할당하고 그 수를 표현하는 것이다. 이 경우, 해당 수를 표현하는 배열내에 해당 수의 크기정보를 가지고 있어야 한다.

 

크기 정보를 표현한다면, 가장 정밀한 것은 해당 비트수를 명시하는 것이다.

이 글에서는 바이트수를 명시하는 것으로 설계하고자 한다. 이론적으로는 비트수를 적는 것보다 큰 수당 최대 7비트정도의 손해를 볼 수 있지만, 어차피 기본 자료형의 최소단위가 바이트이기에 실제 메모리낭비는 없을 것이고, 바이트단위로 크기를 표현하는 것이 코딩이 간단해지기 때문.

 

크기정보를 배열의 어디에 위치하는 것이 좋을까? 맨 앞 아니면 맨 뒤일 것이다.

맨 앞에 위치하게 되면, 배열의 첫번째 값을 읽어 그 수의 크기를 알고, 그 크기만큼의 메모리를 읽으면 될 것이기에 편리하다. 그러나, 실제 수가 배열 첨자의 두번째(zero부터 첨자가 시작된다면 1) 부터 실제 수가 시작되기에, 알고리즘에서 명시하는 첨자순서와 1만큼 어긋나게 되기에, 알려진 알고리즘을 코딩할 때 주의해야 한다.

 

맨 뒤에 크기정보를 놓는다면, 알고리즘을 구현할 때 편리할 것이나, C언어로 구현할 때 정의된 배열에 대해서 그 끝을 찾아가기가 사실 불가능하다. (C에서는 정의된 배열내에 크기정보 없음. Java의 경우는 가능)

 

이 글에서는, C로 구현하는 것을 기본으로 할 것이므로, 배열의 맨 앞에 바이트 수를 적는 것으로 할 것이다.

(이 글에서는 배열에 대한 기본형으로 16비트 혹은 32비트로 할 것이므로, 표현 가능한 바이트 수는 65535바이트 이상으로 충분. 그러나 만약 배열의 기본 자료형을 8비트로 하는 경우는, 표현 가능한 바이트수가 255로 한정됨에 유의)

 

음수

메모리에 저장되는 일련의 수는, 그 자체로는 양수, 음수 구분이 없다. 약속에 의해서 음수를 표시해야 할 뿐이다.

예를 들어 1바이트로 수를 표현할 때(byte 혹은 unsigned byte), 1바이트로 표현할 수 있는 가지 수는 256가지이고, 이를 16진수로 나타내면 {00,01,...,FE,FF}가 되는데, 여기에는 어디에도 양수,음수 구분이 없다. 다만 프로그래밍을 할 때 byte로 선언했다면 음수를 2의 보수로 나타내도록 되어 있어서, 16진수값으로 0x80이상일 때 음수가 되도록 약속되어 있는 것 뿐이다.

 

<1바이트 메모리에 대한 부호있는 값 표시방법>

메모리[16진수]	값[10진수]
00	0
01	1
...	...
7F	127
80	-128
81	-127
...	...
FE	-2
FF	-1

 

위의 경우는 대부분의 프로그래밍 언어에서(C,Java) 사용하고 있는 2의 보수를 이용한 음수의 표현방법이다. 1바이트내에서, 어떤 수 A에 대한 2의 보수 A' = 0x100 - A 이다. 

실제 보수를 구할 때는(음수를 구할 때), 위에서 처럼 해당 수체계에서 가장 큰 값보다 1큰 수(1바이트의 경우 0x100)에서 값을 빼서 구하는 것보다, 각 비트를 역전시킨 후(1의 보수) 1을 더하는 것이 쉽다.

즉, 1에 대한 2의 보수는, 0x01(=0000 0001)의 비트를 역전시키고(1111 1110), 여기에 1을 더한 1111 1111(=0xFF)가 되고, 위 표의 약속에서와 같이 -1이 됨을 알 수 있다.

 

큰 수에 대해서도 부호를 고려할 것이다. (일반적으로 큰 수를 사용하는 이유는 암호학인데, 암호학 알고리즘에서는 대부분 부호화 상관없기에 고려하지 않아도 별 문제 없다. 그러나, 이 글에서는 Calculator까지 만들 작정이므로, 음수에 대한 고려도 한다.)

음수를 표현하는 방법은, 위에서 처럼 2의 보수로 나타내거나, 각 비트를 역전시킨 1의 보수, 혹은 별도의 부호바이트(가장 앞 혹은 뒤)를 두는 3가지 방법이 있을 수 있겠다.

1의 보수는 덧셈과 뺄셈을 하고나서 다시 1을 보정해줘야하는 번거로움이 있고, 별도의 부호를 두는 것은 산술연산에서는 편하지만 다른 암호학 알고즘을 구현할 때는 불편한 부분이어서, 2의 보수로 음수를 표현하기로 한다.

 

따라서, 큰 수 BigInt의 수 체계는 다음과 같이 될 것이다.

<4096비트  BIGINT에 대한 부호있는 값 표시방법(2바이트 INT의 경우)>

메모리[16진수]	값[10진수]
0000	0
0001 0001	1
0001 0002	2
...	...
0100 FFFF ...7FFF	양수 최대값
0100 0000...8000	음수 최소값
...	...
0100 FFFE ... FFFF	-2
0100 FFFF...FFFF	-1

양수로서 가장 큰 값은, 자릿수가 256(0x0100)이고 값이 7FFF FFFF...FFFF(메모리에 배치될 때는 FFFF...FFFF 7FFF)이고, 이보다 더 큰 수는 음수가 된다.

 

큰 수에 대한 프로그래밍

지금까지 컴퓨터 프로그래밍에서 어떻게 큰 수를 사용할 것인가에 대한 것을 얘기했다. 이제부터 이것을 실제로 프로그래밍을 해볼텐데, 주된 설명은 C를 이용해서 하고, Java와 C#으로도 구현해볼 예정이다.

 

프로그래밍 구조는, 큰 수를 표현할 때 필요한 정의/상수들을 bigint.h에서 정의해 놓고, 큰 수의 연산을 하는 함수(function)들을 bigint.c에서 하도록 할 것이다. 구현되는 함수들에 대한 동작시험은 test.c에서 하도록 하자.

 

이제 다음장부터 실제 프로그래밍이다.