부록3. 도우미 함수들

암호화프로그래밍/(Old)C-BIGINT(부록)

부록3. 도우미 함수들

산을좋아한라쯔 2013. 6. 25. 14:40

이 글에서 다루고 있는 메인 주제인 큰 수에 대한 연산 및 암호화 연산에서 사용되는 대표적인 도우미 함수들에 대해서 설명한다.

일반적인 도우미함수들은 doumi.h에 정의하고 doumi.c에 구현할 것이다. 이 때, 함수명은 표준 C라이브러리에서 사용되는 함수들과의 혼돈을 피하기 위해서 "do_"로 시작되도록 한다.

BIGINT관련 도우미함수들은 bigint.c내에 구현한다.

1. 일반 도우미 함수들 (doumi.h에 정의. doumi.c에 구현)

do_compare

/**************************************************************************
compare two bytes(=unsigned char *) value
Input: @a, @b 비교하려는 두 수에 대한 포인터변수 a, b 
       @len   비교하려는 길이
Returns: 
		1 : a > b
		0 : a==b
		-1: a < b
***************************************************************************/
int do_compare(unsigned char *a, unsigned char *b, unsigned short len){
	unsigned char *posA, *posB;
	if(len == 0) return 0;
	posA = a + len;
	posB = b + len;
	while( (*posA == *posB) && (posA > a)){
		posA--;
		posB--;
	}
	if(posA == a) return 0;
	if(*posA > *posB) return 1;
	else	return -1;
}

do_power

/**************************************************************************
int값에 대한 지수승값 구한다. 
Input:	@base 밑 수
		@e 지수       
Returns: power(base,e)의 결과값. long타입
***************************************************************************/
unsigned long do_power(int base, int e){
	unsigned long result = 1;
	while(e--){
		result *= base;
	}
	return result;
}

do_len

/**************************************************************************
주어진 문자열의 크기를 구한다. 즉, char형 갯수
만약, 문자열의 길이가 int변수가 나타낼 수 있는 크기보다 크다면 -1리턴
Input: @s 길이를 알아내려는 문자열 포인터 
       
Returns: 문자열 s의 길이. 만약 int형으로 표현되는 Max보다 크다면 -1리턴
***************************************************************************/
int do_len(char *s){
	unsigned int len=0;
	unsigned int max = do_power(2,(sizeof(int) * 8 - 1)); 
	while(*s++ != '\0') {
		len++;
		if(len >= max) return -1;
	}
	return len;
}

do_tolower

/**************************************************************************
주어진 알파벳 문자에 해당하는 대문자 리턴. 
주어진 것이 이미 대문자이면 그냥 그 대문자 리턴
Input: @c 입력 문자 
       
Returns: 입력문자에 해당하는 대문자
***************************************************************************/
int do_tolower(int c){
	if( (c >= 'A') && (c <= 'Z'))
		return (c - 'A' + 'a');
	else
		return c;
}

do_hex2num

/**************************************************************************
hexa형태의 문자를 숫자로 변환
'1' -> 1, 'a' -> 10, 'A'->10, 
Input: @c hexa형태의 문자 
       
Returns: 
		'0'~'9' : 0 ~ 9
		'a'~'f' : 10 ~ 15
		'A' ~ 'F': 10 ~ 15
		그 외: -1
***************************************************************************/
int do_hex2num(int c){
	if( (c >= 'A') && (c <= 'F'))
		return (c - 'A' + 10);
	else if( (c >= 'a') && (c <= 'f'))
		return (c - 'a' + 10);
	else if( (c >= '0') && (c <= '9'))
		return (c - '0');
	else
		return -1;
}

do_int2hexchar

/**************************************************************************
숫자를 hexa형태의 문자로 변환
1 -> '1' , 10 -> 'A'  
Input: @i hexa형태의 문자로 변환하려는 숫자 
       
Returns: 
		0 ~ 9: '0'~'9' 
		10 ~ 15: 'A'~'F' : 		
		그 외: -1
***************************************************************************/
char do_int2hexchar(int i){
	if(i<0 || i >= 16) return -1;
	if(i < 10) return (char)(i + (int)'0');
	return (char)(i - 10 + (int)'A');
}

do_reverse

/**************************************************************************
문자열의 차례를 뒤 바꿈
"abcd" -> "dcba"
Input: @s 바꾸려는 문자열. 순서가 바뀌어서 다시 입력 문자열에 저장됨 
       
Returns: 
		0  성공
		-1 에러 
***************************************************************************/
int do_reverse(char* s){
	int i;
	char t;
	int len = do_len(s);
	if(len < 0) return -1;
	for(i=0;i<(len/2);++i){
		t = s[i];
		s[i] = s[len - i];
		s[len - i] = t;
	}
	return 0;
}

do_copy

/**************************************************************************
short형 두 배열에 대해, 한 쪽 배열값을 다른 쪽 배열에 카피
Input:	@tgt		Target 포인터
		@tgtStart	Paste하려는 Target포인터의 첫번째 위치. 만약 2라면. tgt[2]에다 paset. 첨자 시작은 0
		@src		Source 포인터
		@srcStart	Copy시작하는 src배열의 위치. 만약 2라면 src[2]부터 copy
		@len		copy할 길이. src[srcStart]부터 len길이만큼 copy해서, tgt[tgtStart]에 paste    
***************************************************************************/
void do_copy(unsigned char *tgt, unsigned short tgtStart, unsigned char *src, unsigned short srcStart, unsigned short len){
	int i=0;
	tgt += tgtStart;
	src += srcStart;
	while(len-- > 0)
		*(tgt++) = *(src++);
}

doumi.h에 정의된 함수들

int do_compare(unsigned char *a, unsigned char *b, unsigned short len);
unsigned long do_power(int , int );
int do_len(char*);
int do_hex2num(int);
char do_int2hexchar(int);
int do_reverse(char*);
void do_copy(unsigned char *tgt, unsigned short tgtStart, unsigned char *src, unsigned short srcStart, unsigned short len);

2. BIGINT관련 도우미 함수들 (bigint.c에 정의)

compare_big

/**************************************************************************
compare two BIGINT value
음수에 대한 고려하지 않음.
즉, 양수인 BIGINT값에 대해서만 유의한 결과를 보임
Input: @a, @b
Returns: 
		1 : a > b
		0 : a==b
		-1: a < b
***************************************************************************/
int compare_big(BIGINT a, BIGINT b){	
	int lenA, lenB;
	INT *posA, *posB; 
  
	//1. check len is not zero
	lenA = (int)*a;
	lenB = (int)*b;
	if(lenA == 0 && lenB == 0) return 0;
  
	//2. check non zero value len and compare length
	while(a[lenA]==0 && lenA>0) --lenA;
	while(b[lenB]==0 && lenB>0) --lenB;
	if(lenA == 0 && lenB == 0) return 0;
	if(lenA > lenB) return 1;
	if(lenA < lenB) return -1;
  
	//3. case:lenA == lenB
	posA = a + lenA;
	posB = b + lenB;
	while( (*posA == *posB) && (posA > a)){
		posA--;
		posB--;
	}
	if(posA == a) return 0;
	if(*posA > *posB) return 1;
	else	return -1;
}

increse

/**************************************************************************
1을 더함
Input: @A
Output: (A+1) A에 1을 더한 값. A = A + 1
Returns: 
		OK : no error
		E_Overflow: Overflow. if larger than MAX_INT_LEN(=128. in case of INT is u32)	
***************************************************************************/
int increse(BIGINT A){
	INT *a,	*ae;	
	DINT carry = BASE;
	//01. A에 대한 포인터얻기
	a = A + 1;
	ae = A + SIZE(A);
	//02. if(A == zero)
	if(a > ae){
		SET_SIZE(A,1);
		*a = (INT)1;
		return OK;
	}
	//03. loop
	while((a <= ae) && (carry & BASE)){
		*a = (INT)(carry = (DINT)*a + (DINT)1);
		a++;
	}
	//04. if carry exist --> increse len
	if((a > ae) && (carry & BASE)){		
		if( (SIZE(A)+1) > MAX_INT_LEN){			
			*A = 0;  //set zero			
		}else{
			*a = 1;
			SET_SIZE(A, (SIZE(A))+1);	
		} 
	}
	//05. if(A == 양의 최대값) -> +1이면 overflow
	if((SIZE(A) == MAX_INT_LEN) && (A[MAX_INT_LEN] == ((INT)MAX_POSITIVE+1))){
		ae = A+SIZE(A);
		while((*ae == 0) && (--ae > A));  //모두 zero라면
		if(ae == A) return E_Overflow;
	}
	return OK;
}

negative

/***************************************************************************************
주어진 BIGINT값을 음수로 변환
이 때 음수의 표현은 2의 보수 형태
즉,
00101 -> 11010 -> 11011
input:	BIGINT A 음수로 변환할 BIGINT값
output: BIGINT A 2의보수 형태로 변환된 값
return:	OK	
****************************************************************************************/
int negative(BIGINT A){
	INT *a = A;
	INT *ae = A + SIZE(A);
	//1. if zero --> do nothing
	if(*(a+1) == 0) return OK;
	//2. 1's complement
	while(++a <= ae){
		*a = ~(*a);
	}
	//1. +1
	//앞에서 zero인 경우에 대해서 처리했기에, 1의 보수에 의해 MAX된 후, 
    //increse에 의해 overflow가 발생되는 경우 없음
	increse(A);
	//2. fill with FF upto the MAX
	SET_SIZE(A,MAX_INT_LEN);
	while(++ae <= (A+MAX_INT_LEN)){
		*ae = MAX_INT;
	}
	return OK;
}

hexstr2bigint

/**************************************************************************
convert hex string to BIGINT 
음수부호가 있는 hexa string값은 처리하지 않음.
음수부호가 있을 경우는 hexstr2bigint함수 사용해야함
Input: @str: should be big endian style notation.
			 ex)ff12 = f x 4096 + f x 256 + 1 x 16 + 2
			 1234567890 ==> [0]2 [1]12 [2]34567890
								 = 0x12 x B^0 + 0x34567890 x B^1              
Output: @a: converted BIGINT value
			ex)"112233445566"	-> {2,   0x00005566, 0x11223344}
		
Returns: 
		OK : no error
		E_NotSupported: not supported. possible BIGINT type is u8, u16, u32			
***************************************************************************/
int hexstr2bigint_engine(char* str, BIGINT a){
	int sizeofINT= sizeof(INT), result=OK;
	int strLen;
	int i,j,len,n;
	INT t;
	unsigned long strStart;
	unsigned short byteLen, bigIntLen;
	//1. 초기값 세팅
	*a = 0;
	strLen = do_len(str);
	if(strLen < 0) return E_Overflow;
	strStart = (unsigned long)str;
	byteLen = strLen / 2;
	bigIntLen = ((byteLen % sizeofINT)==0) ? byteLen/sizeofINT : (byteLen/sizeofINT)+1;
	if(bigIntLen > MAX_INT_LEN) return E_Overflow;
	//2. loop	
	str = str + strLen-1;
	for(i=1;i <= bigIntLen ;i++){
		t=0;
		len = (((unsigned long)str - strStart+1) > (unsigned long)(sizeofINT * 2)) ? (int)(sizeofINT * 2) : (int)((unsigned long)str - strStart+1);
		for(j=0;j<len;j++){
			n = do_hex2num(*(str - j));
			if(n<0) return E_WrongFormat;
			t += (INT)(n * do_power(16,j));
		}
		*(a+i) = t;
		str -= (sizeofINT * 2);
	}
	*a = bigIntLen;
	return result;
}
/**************************************************************************
convert string to BIGINT 
입력값으로 부호(+ 혹은 -) 붙여서 변환 시킬 수 있음
case 1)부호없는 hexa string: "112233445566" -> {2,   0x00005566, 0x11223344}
case 2)양수 부호 있는 hexa string = 부호없는 hexa string
case 3)음수 부호 있는 hexa string: 
       "-112233445566" -> {0x80,0xFFFFAA9A, 0xEEDDCCBB, 0xFFFFFFFF, ..., 0xFFFFFFFF}
Input: @str: should be big endian style notation.
			 ex)ff12 = f x 4096 + f x 256 + 1 x 16 + 2
			 1234567890 ==> [0]2 [1]12 [2]34567890
								 = 0x12 x B^0 + 0x34567890 x B^1              
Output: @a: converted BIGINT value
			ex1)"112233445566"	-> {2,   0x00005566, 0x11223344}
			ex2)"-112233445566" -> {0x80,0xFFFFAA9A, 0xEEDDCCBB, 0xFFFFFFFF, ..., 0xFFFFFFFF}
Returns: 
		OK : no error
		E_NotSupported: not supported. possible BIGINT type is u8, u16, u32			
***************************************************************************/
int hexstr2bigint(char* str, BIGINT a){
	char *strNum;	
	int ret=-1;
	//음수 부호가 있는 지 확인
	if(*str == '-'){
		strNum = (str + 1);
		ret = hexstr2bigint_engine(strNum, a);
		if(ret != OK) return ret;
		else{
			return negative(a);
		}		
	}else if(*str == '+'){
		strNum = (str + 1);
		return hexstr2bigint_engine(strNum, a);
	}else{		
		return hexstr2bigint_engine(str, a);
	}
}

hexstr2bytes

/**************************************************************************
convert string to bytes 
Input: @str: should be big endian style notation.
             ex)ff12 = f x 4096 + f x 256 + 1 x 16 + 2
			 1234567890 ==> [0]2 [1]12 [2]34567890
			                     = 0x12 x B^0 + 0x34567890 x B^1
Output: @a: converted bytes(unsigned char*) value
            "112233445566"
			-> {0x11223344, 0x5566}
Returns: 
		OK : no error
		E_WrongFormat: if str contains wrong character. should be between 0~9, a~f, A~F			
***************************************************************************/
int hexstr2bytes(char* str, unsigned char* a){
	int strLen,bytesLen;
	int i,n;
	unsigned char c;
	strLen = do_len(str);
	bytesLen = strLen / 2;
	for(i=0;i < bytesLen ;i++){
		n = do_hex2num(*str);
		if(n<0) return E_WrongFormat;
		c = n * 16;
		n = s_hex2num(*(str+1));
		if(n<0) return E_WrongFormat;
		c += n;
		*(a+i) = c;
		str += 2;		
	}
	//*(a+bytesLen) = '\0';
	return 0;
}

bytes2bigint

/**************************************************************************
convert unsigned char to BIGINT 
Input: @c: unsigned char pointer
       @len: length of bytes of c      
Output: @a: converted BIGINT value
            0x11 0x22 0x33 0x44 0x55 0x66
			-> {2, 0x00005566, 0x11223344}
Returns: 
		OK : no error
		E_NotSupported: not supported. possible BIGINT type is u8, u16, u32			
***************************************************************************/
int bytes2bigint(unsigned char* c, unsigned short bytesLen, BIGINT a){
	int sizeofINT= sizeof(INT), result=OK;	
	int i,j,n,len;
	INT t;
	unsigned long cStart;
	unsigned short bigIntLen;
	//1. 초기값 세팅
	*a = 0;		
	if(bytesLen < 0) return E_Underflow;
	cStart = (unsigned long)c;
	bigIntLen = ((bytesLen % sizeofINT)==0) ? bytesLen/sizeofINT : (bytesLen/sizeofINT)+1;
	if(bigIntLen > MAX_INT_LEN) return E_Overflow;
	//2. loop	
	//str = str + strLen-1;
	c = c + bytesLen-1;
	for(i=1;i <= bigIntLen ;i++){
		t=0;
		len = (((unsigned long)c - cStart+1) > (unsigned long)sizeofINT) ? (int)sizeofINT : (int)((unsigned long)c - cStart+1);		
		for(j=0;j<len;j++){
			n = *(c-j);			
			t += (INT)(n * do_power(256,j));
		}
		*(a+i) = t;
		c -= sizeofINT;
	}
	*a = bigIntLen;
	return result;
}

bigint2hexstr

/**************************************************************************
convert BIGINT to hex string  
Input: @a: BIGINT value             
Returns : hex string of input BIGINT a
         a = {2, 0x00005566, 0x11223344}
		 str = "112233445566"
***************************************************************************/
char* bigint2hexstr(BIGINT a){
	int i,j,k;
	int sizeofINT= sizeof(INT), intBitLen, result=OK;
	unsigned short aLen = (unsigned short)(*a);
	static char s[MAX_BIT_LEN/4];
	//error 처리
	if(aLen == 0) {
		s[0] = '0';
		s[1] = '\0';
		return s;
	}
	//loop from the end of BIGINT a except a[1]
	intBitLen = sizeofINT * 8;
	k=0;	
	for(i=aLen;i>=1;i--){
		for(j=1;j<=(sizeofINT * 2);j++){
			s[k++] = do_int2hexchar( (a[i] >> (intBitLen - 4 * j)) & 0x0f );
		}			
	}	
	s[k] = '\0';
	return s;
}

bigint2bytes

/**************************************************************************
convert BIGINT to bytes
Input: @a: BIGINT value 
Returns : 
		bytes value converted from BIGINT
        {2, 0x00005566, 0x11223344}
		-> 0x11, 0x22, 0x33, 0x44, 0x55, 0x66
***************************************************************************/
unsigned char * bigint2bytes(BIGINT a){
	int i,j,k;
	int sizeofINT= sizeof(INT), intBitLen, result=OK;
	unsigned short aLen = (unsigned short)(*a);
	static unsigned char b[MAX_BIT_LEN/8]={0,};
	//return zero
	if(aLen == 0) {
		return b;
	}
	//loop from the end of BIGINT a except a[1]
	intBitLen = sizeofINT * 8;
	k=0;	
	for(i=aLen;i>=1;i--){
		for(j=1;j<= sizeofINT;j++){
			b[k++] = (a[i] >> (intBitLen-(8 * j))) & 0xff ;
		}			
	}	
	return b;
}

copy_big

/**************************************************************************
copy BIGINT
Input: @tgt: Target BIGINT to be copy
	   @src: Source BIGINT to copy
Returns : void
***************************************************************************/
void copy_big(BIGINT tgt, BIGINT src){
	int len = *src;
	if(len < 0 ) return; //do nothing
	while(len >= 0){
		*tgt++ = *src++;
		len--;
	}	
}

setmax

/**************************************************************************
주어진 BIGINT를 max값으로 채움. 
만약 INT가 4Bytes라면, 0xffffffff로 모든 BIGINT값이 채워짐
Input: @A: BIGINT to be filled with Max value       
Returns : void
***************************************************************************/
void setmax(BIGINT A){
	INT *a = A;
	INT *ae = A + MAX_INT_LEN;
	while(++a <= ae){
		*a = MAX_INT; //0xffffffff
	}
	SET_SIZE(A,MAX_INT_LEN);
	return;
}

complement

/**************************************************************************
주어진 BIGINT의 비트값을 0이면 1로, 1이면 0으로 바꿈
Input: @A: BIGINT to convert all bits to complement bit
Returns : void
***************************************************************************/
void complement(BIGINT A){
	INT *a = A;
	INT *ae = A + SIZE(A);
	while(++a <= ae){
		*a = ~(*a);
	}
	return;
}

isPositive

/**************************************************************************
주어진 BIGINT가 양수인지 판별
Input: @A: BIGINT to determine whether it's positive or not
Returns : 1 if BIGINT is positive value including zero
          -1 if BIGINT is negative value. 
***************************************************************************/
int isPositive(BIGINT A){
	if( (*A == MAX_INT_LEN) && (*(A+MAX_INT_LEN) > MAX_POSITIVE))
		return -1;
	else
		return 1;	
}

* Add프로젝트에서는 에러코드로 OK와 E_Overflow만이 bigint.h에 정의되어 사용되었으나, 위 도우미 함수에서는 그 외에도 몇 개의 에러코드를 사용한다. 이 에러코드를 포함해서 bigint.h에 다음과 같이 에러코드를 추가 정의한다.

#define OK	0
#define E_Overflow -1
#define E_NotSupported	-2
#define E_WrongFormat	-3
#define E_ZeroLength	-4
#define E_DivideByZero	-5
#define E_Underflow		-6

저작자표시 비영리 변경금지

'암호화프로그래밍 > (Old)C-BIGINT(부록)' 카테고리의 다른 글

부록2. Visual Studio를 이용한 C 프로그래밍 예제 (0)	2013.06.20
부록1. 각 언어의 자료형별 크기 (0)	2013.06.19

현재글부록3. 도우미 함수들

FFT, 비트코인 논문 번역, 시트보호, bitcoin 번역, 파장, DFT, 비트코인 번역, Block Chain, excel vba, Fourier, 사토시 논문, 블록체인 번역, protection remove, RGB, 비트코인 번역본, excel crack, 보호 해제, wavelength, CIE, 엑셀 크렉,

Today :
Yesterday :

컴퓨터 프로그래밍(암호학, 알고리즘)