2.8 나머지(mod)
나머지식 산술에 대해서 알아보자
a가 정수일때, 자연수 m에 대해서 다음과 같은 식이 성립한다고 할 때,
a = qm + r, 0 ≤ r < m
r을 "a를 m으로 나눌 때의 나머지라 하고, r = a mod m 혹은 a ≡ r mod m으로 표현한다.
나머지식 산술은 덧셈, 뺄셈, 곱셈에 대해 유효한데 하나씩 구현해 나가면서, 최종에는 RSA암호에서 사용되는 mod_exp함수를 구현할 것이다.
나머지 산술관련 구현할 함수 리스트
mod(A,N,R): R = A mod N
mod_add: 두 수의 modular 합
mod_subtract: 두 수의 mudular 차
mod_square: 주어진 수에 대한 modular 제곱
mod_multiply: 두 수의 modular 곱
mod_exp(A,e,N,C): C = A^e mod N
mod(A,N,R)
A를 N으로 나눴을 때의 나머지인 R을 구한다.
기 구현한 divide함수를 이용해서 나머지를 구한다.
나머지의 부호는 A에 의해 결정된다. 만약 A가 양수이면 R도 양수이고, A가 음수이면 R은 음수가 된다.
N의 부호는 상관 없다.
/************************************************************************** calculate modular remainder for a BIGINT A. R = A mod N if(A < 0) R is negative value Input: @A = BIGINT number @N = divisor Output:@R = Remainder. R = A mod N Returns: OK : no error E_DivideByZero: in case of divisor(B) is zero Comment: ***************************************************************************/ int mod(BIGINT A, BIGINT N, BIGINT R){ BIGINT Q; int ret;ret = divide(A,N,Q,R); if(ret != OK) return ret;
if(isPositive(A) == 1){ return OK; }else { return negative(R); } }
mod_add(A,B,N,R)
두 수의 modular 합을 구한다.
기 구현된 add함수를 이용해서 합을 구한 후, mod연산을 해서 나머지를 구한다.
/************************************************************************** modular add. A+B mod N Input: @A, @B = BIGINT number to add @N = BIGINT type modulus Output:@R = Remainder R = A+B mod N Returns: OK : no error E_DivideByZero: in case of divisor(B) is zero Comment: ***************************************************************************/ int mod_add(BIGINT A, BIGINT B, BIGINT N, BIGINT R){ BIGINT D; int result; if (N[0] == 0) return E_DivideByZero; if( (result = add(A,B, D)) != OK) return result; return mod(D,N,R); }
mod_subtract(A,B,N,R)
두 수의 modular 차을 구한다.
기 구현된 subtract함수를 이용해서 차을 구한 후, mod연산을 해서 나머지를 구한다.
/************************************************************************** modular subtract. A-B mod N Input: @A, @B = BIGINT number to subtract @N = BIGINT type modulus Output:@R = Remainder R = A-B mod N Returns: OK : no error E_DivideByZero: in case of divisor(N) is zero Comment: ***************************************************************************/ int mod_subtract(BIGINT A, BIGINT B, BIGINT N, BIGINT R){ BIGINT D; int result; if (N[0] == 0) return E_DivideByZero; if( (result = subtract(A,B, D)) != OK) return result; return mod(D,N,R); }
mod_square(A, N, R)
주어진 수의 modular 제곱을 구한다.
기 구현된 square함수를 이용해서 제곱을 구하고, mod를 해서 나머지를 구한다.
************************************************************************** modular square. A^2 mod N Input: @A = BIGINT number to modulus_square @N = BIGINT type modulus Output:@R = Remainder R = A^2 mod N Returns: OK : no error E_DivideByZero: in case of divisor(N) is zero Comment: ***************************************************************************/ int mod_square(BIGINT A, BIGINT N, BIGINT C){ BIGINT D; int result; if (N[0] == 0) return E_DivideByZero; if( (result = square(A,D)) != OK) return result; return mod(D,N,C); }
mod_multiply(A, B, N, R)
주어진 수의 modular 곱을 구한다.
기 구현된 multiply함수를 이용해서 곱을 구하고, mod를 해서 나머지를 구한다.
/************************************************************************** modular multiply. (A * B) mod N Input: @A, @B = BIGINT number to modulus_multiply @N = BIGINT type modulus Output:@C = Result of multiplying. C = (A*B) mod N Returns: OK : no error E_DivideByZero: in case of modulus(N) is zero E_Overflow: overflow while multiplying Comment: ***************************************************************************/ int mod_multiply(BIGINT A, BIGINT B, BIGINT N, BIGINT C){ BIGINT D; int result; //Case1. if N==0 -> E_DivideByZero if (N[0] == 0) return E_DivideByZero; // Case2. A==0 or B==0 --> C = 0 if(A[0] == 0 || B[0] == 0) { C[0]=0; return OK; } if( (result = multiply(A, B, D)) != OK) return result; return mod(D,N,C); }
mod_exp(A,e,N,R)
모듈라 멱승(modular exponentiation)을 구한다.
모듈라 멱승은 나머지식 산술의 꽃이라 할 수 있다. 왜냐하면 일반 산술에 있어서 멱승은 지수값이 커짐에 따라 결과값이 계속해서 증가하여, 지수값이 조금만 크더라도 결과값이 너무 커져서 컴퓨터의 CPU와 메모리의 처리범위를 벗어나 버린다.
반면 모듈라멱승은 지수가 아무리 커지더라도 그 결과값이 나머지이기에 밑수보다 작은 값으로 컴퓨터가 충분히 처리 가능하다.
ae는 a를 e번 곱하는 것이다. a가 BIGINT값으로 큰 값일 때 e가 조금만 커져도 BIGINT값 범위내에서 처리가 불가능한다. 따라서, 모듈라 멱승을 구할 때는, 모듈라 합, 차, 곱을 구할 때와 같이 먼저 산술식을 하고 그 결과값에 대한 mod연산을 하는 것이 불가하다.
쉽게 생각할 수 있는 방법은 mod_multiply를 e-1회 하는 것이다. a16의 경우 15번의 mod_multiply가 필요하다.
더 효과적인 방법이 있다. a16를 (((a2)2)2)2으로 생각할 수 있고, 그렇다면 mod_square 4회로 계산이 줄어든다.
아래 표를 생각해 보자
a1 = a0001 = a
a2 = a0010 = a2
a3 = a0011 = a2a
a4 = a0100 = (a2)2
a5 = a0101 = (a2)2a
a6 = a0110 = (a2a)2
a7 = a0111 = (a2a)2a
a8 = a1000 = ((a2)2)2
a9 = a1001 = ((a2)2)2a
a10 = a1010 = ((a2)2a)2
a11 = a1011 = ((a2)2a)2a
a12 = a1100 = ((a2a)2)2
a13 = a1101 = ((a2a)2)2a
a14 = a1110 = ((a2a)2a)2
a15 = a1111 = ((a2a)2a)2a
a16 = a10000 = (((a2)2)2)2
규칙성을 발견할 수 있다. e >=2에 대해서 a2을하고, 그 다음 비트가 1인 경우는 a를 곱하고, 0인 경우는 그대로 제곱만을 한다.
이것을 일반화해서 알고리즘으로 만들어 보자
알고리즘
e=(en-1 ... e1 e0)2이고 en-1은 값이 1인 최상위 비트를 가르킬 때, Ae mod N은 다음과 같이 구할 수 있다.
S1. 초기화
t ←A mod N
i ← n-2
S2. 루프(i)
S3. 판단
if(ei == 1) t = t2A mod N
if(ei == 0) t = t2 mod N
S4 루프종료
i ← i-1
if(i >= 0) goto S2
S1. 초기화
먼저 A mod N을 계산해서 t에 저장해 두고, e를 이진수로 나타내었을 때 값이 1인 가장 최상위비트의 위치를 n-1로 했을 때, n-2값을 i로 둔다. 예를들어 e15 의 경우 15 = (1111)2이므로 n=3이되고 i=3-2=1이 된다.
S2. 루프(i)
(i >= 0)인 조건엣 대해서 루프를 계속 돌며 S3 루틴을 수행한다.
S3. 판단 & 계산
루프내에서 ei가 1이라면 t = t2 mod N이 되도록 한다.
0(zero)라면 t = t2 mod N인 상태가 된다.
S4. 루프종료
i를 감소시키면서 i가 0가 될 때가지 루프를 계속 돌린다.
소스 해설
함수이름은 mod_exp로 하고, BIGINT인 밑수와 지수 나눔수, 그리고 나머지를 저장할 변수를 파라미터로 받는다.
/**************************************************************************
modulus exponentiation with BIGINT type E. A^E mod N
Input: @A = base number. 양수, 음수 구분하지 않음
@E = exponent number. BIGINT type
@N = BIGINT type modulus
Output:@R = Result of modulus exponentiation. R = (A^E) mod N
Returns:
OK : no error
E_DivideByZero: in case of divisor(N) is zero
Comment:
***************************************************************************/
int mod_exp(BIGINT A, BIGINT E, BIGINT N, BIGINT R){
BIGINT t, b;
INT *e;
u8 isFirst;
INT k;
b는 A mod N을 계산해서 넣어두게 되고, t는 계속해서 나머지값이 갱신되며 계산되는 버퍼로 사용된다.
*e는 지수값 E의 값을 가르키는 포인트 변수.
isFirst는 E에서 비트값이 1인 위를 찾았는지의 여부를 나타낸다. 한 번 찾아냈으면 그 다음은 찾는 과정을 안하기 위한 플래그로 사용된다.
k는 *e값에서 각 비트값이 1인지 0인지를 알아내기위한 값으로 사용된다.
//Case1. modulus(N)=0 -> E_DivideByZero if(N[0] == 0) return E_DivideByZero; //Case2. A==0 or N==1-> R=0 if(A[0]==0 || (N[0]==1 && N[1]==1)){ R[0]=0; return OK; } //Case3. E=0 -> R=1 REMOVE_ZERO(E); if(E[0] == 0){ R[0] = 1; R[1] = 1; return OK; } //Case4. otherwise,
Case1은 modulus N이 zero인 경우로, E_divideByZero 에러 리턴한다.
Case2는 A가 0 혹은 N이 1인 경우로, 나머지는 zero가 된다.
Case 3은 지수 E가 0인 경우로, 나머지는 1이된다.
그 외의 경우는 Case 4로 위에서 검토한 알고리즘을 적용하여 구현된다.
//1. b = t = A^1 mod N
mod(A,N,t);
copy_big(b,t);먼저 A mod N을 계산해서 b와 t에 넣어둔다.
그 다음, E의 가장 큰 값에서 부터 0가 될때까지, *e를 이동시키면 루프를 돈다.
//2. Loop for entire E e = E + SIZE(E); isFirst = 0; while(e > E){ //3. 값이 1인 최상위비트 위치를 찾음 k = (INT)MAX_POSITIVE + 1; //8000 0000 if(isFirst == 0){ while( (*e & k) == 0) k >>= 1; k >>= 1; isFirst = -1; } //4. 비트값 1 ? (square and multi) : (square) while( k != 0){ if(*e & k) { mod_square(t,N,t); mod_multiply(t,b,N,t); }else{ mod_square(t,N,t); } k >>= 1; } e--; } copy_big(R,t); return OK; }
BIGINT의 구조가, 큰 값이 메모리번지가 큰 쪽에 위치하도록 되어 있기에, 가장 큰 비트가 위치한 곳은 E + SIZE(E)가 가르키는 INT값 중 한 비트이다.
여기서 주의해야할 것은 컴퓨터가 메모리에 값을 저장하는 방식이 빅인디언인지 리틀인디언인지에 상관없이 동일하게 동작하도록 해야하는 것이다. 예를들어 E의 값이 0x1122 3344 5566 7788 99일 때, 대부분의 PC인인텔계열 CPU에서 채택하고 있는 리틀인디언 방식의 메모리에 저장된 구조를 도식화해보면 다음과 같을 것이다. (INT가 4바이트 u32인 경우)
빅인디언의 경우는 저장되는 순서가 달라질 것이다. 그러나, 각 배열값을 읽으면 그 값은 빅이든 리틀이든 동일한 값이 된다. 왜냐하면 컴파일러들이 변환해서 읽어주기 때문이다. 즉, E[1]의 값은 빅이나 리틀에 따라 바이트들이 저장되는 순서는 다르겠으나 읽힌값은 0x66778899로 동일하다.
따라서, 빅/리틀 인디언 구조에 따라 동일하게 동작시키려면 각 INT배열값을 읽은 후, 그 값에서 어느 비트가 1인지를 파악하는 것이다. 이러한 고민으로 작성된 것이 위 코드이다.
코드에서 보면, 먼저 가장 상위 length에서 (그림에서는 E[3]) 어느 비트가 1인지를 찾아낸다. 이 과정은 while(e>E)루프에서 오직 한번만 수행되도록 한다. (isFirst 이용)
1인 최상위 비트를 찾아냈으면, 그 다음은 한비트씩 이동하면서 1이면 square and multiply, 0이면 square를 계산하면서 루프를 반복한다.
프로젝트 파일
008.Modular.zip
'암호화프로그래밍 > (Old)C-BIGINT' 카테고리의 다른 글
| 016. 비트연산 (0) | 2013.08.12 |
|---|---|
| 015. 최대공약수(gcd) (0) | 2013.08.09 |
| 013. 나눗셈(divide) (0) | 2013.08.02 |
| 012. 제곱(square) (0) | 2013.07.31 |
| 011. 곱셈(multiply) (0) | 2013.07.30 |