[c] DES 구조 및 코드

DES 메카니즘

현대암호(하이브리드 암호)의 조상님인 DES( Data Encryption Standard )이다.

DES는 feistel 구조로 되어있으며 라운드수는 16이고 64비트 입력(블럭)에 64비트키(사실상 56비트 키)를 가진다.

대략적인 순서는

1. 64비트 입력을 초기 전치한다.

2. 32비트씩 쪼갠다.

3. 오른쪽32비트는 다음 라운드의 왼쪽32비트가 된다.

4. 오른쪽32비트를 라운드 키와함께 F함수에 통과한 후 왼쪽32비트와 xor하여 다음 라운드의 오른쪽32비트가 된다.

5. 3, 4를 16번 반복한다. 단, 마지막 16라운드에는 왼쪽 오른쪽을 교차하지 않는다.

6. 최종 전치( 초기 전치의 역전치 )를 하면 끝.

feistel구조는 원래 des이전부터 있던 구조이며 따라서 feistel구조의 블럭암호들은 보통 F함수를 설계한다.

DES F함수

DES의 F함수의 대략적 순서는

1. 32비트 입력을 48비트로 확장전치한다.

2. 48비트 라운드키와 xor한다.

3. 6비트씩 S박스에 통과시킨다. 이때 박스당 6비트의 입력은 4비트의 출력을 내며 S박스 통과 후 32비트가 된다.

4. 한번 더 전치 끝.

키는 입력 64비트키에서 확장시켜서 라운드키를 생성하는데

대략적 순서는

1. 전치한다. 이때 8의 배수 번째(8, 16, ... , 64)가 없어지며 56비트가 된다.

(이때문에 DES의 키공간은 2^56이다.)

2. 28비트씩 쪼갠다.

3. 라운드별 쉬프트 횟수만큼 왼쪽순환쉬프트를 왼쪽28비트 오른쪽28비트 각각 해준다.

4. 합쳐서 전치하여 라운드키 생성. 이때 48비트가 된다.

5. 3, 4번을 16라운드 반복한다.

코드를 보자

void DES_Encryption(BYTE *p_text, BYTE *result, BYTE *key) {
	int i;
	BYTE data[BLOCK_SIZE] = { 0, };

	BYTE round_key[16][6] = { 0, };
	UINT left = 0, right = 0;

	key_expansion(key, round_key);    // 키 확장
	IP(p_text, data);                        // 초기 전치

	BtoW(data, &left, &right);           // 32비트씩 쪼갬

	for (i = 0;i < DES_ROUND; i++) { 
		left = left ^ f(right, round_key[i]);
		if (i != DES_ROUND - 1)
			swap(&left, &right);
	}

	WtoB(left, right, data);
	In_IP(data, result);                    // 마지막 전치
}

암호화 코드이다. 

복호화 코드는 라운드 키를 역순으로 넣어주는 것 빼고 다른건 없다.( Feistel 구조의 특성 )

void IP(BYTE *in, BYTE *out)
{
	int i;
	BYTE index, bit, mask = 0x80;

	for (i = 0;i<64;i++)
	{
		index = (ip[i] - 1) / 8;
		bit = (ip[i] - 1) % 8;

		if (in[index] & (mask >> bit))
			out[i / 8] |= mask >> (i % 8);
	}
}

초기 전치 코드이다.

마스크값과 &연산을 하여 해당 비트가 1인지 확인하고 1이면 out의 비트 1로 한다.

0으로 초기화되어 있기때문에 0일때는 처리하지 않는다.

UINT f(UINT r, BYTE* rkey)
{
	int i;
	BYTE data[6] = { 0, };
	UINT out;

	EP(r, data);

	for (i = 0;i<6;i++)                                 // 라운드 키와 xor
		data[i] = data[i] ^ rkey[i];

	out = Permutation(S_box_Transfer(data));   // S박스 통과하여 전치함

	return out;
}

F함수 코드이다.

void EP(UINT r, BYTE* out)
{
	int i;
	UINT mask = 0x80000000;

	for (i = 0;i<48;i++)
	{
		if (r & (mask >> (E[i] - 1)))
		{
			out[i / 8] |= (BYTE)(0x80 >> (i % 8));
		}
	}
}

F함수 내 확장 전치 코드이다.

IP코드와 유사하다.

이 외의 전치코드들도 거의 흡사하므로 담지 않았다.

UINT S_box_Transfer(BYTE* in)
{
	int i, row, column, shift = 28;
	UINT temp = 0, result = 0, mask = 0x80;

	for (i = 0;i<48;i++)
	{
		if (in[i / 8] & (BYTE)(mask >> (i % 8)))  // 마스크를 씌워 확인 후 temp에 해당 비트 1로 함
                        temp |= 0x20 >> (i % 6);

		if ((i + 1) % 6 == 0)                        // 6비트마다
		{
			row = ((temp & 0x20) >> 4) + (temp & 0x01);           // 행 값
			column = (temp & 0x1E) >> 1;                               // 열 값

			result += ((UINT)s_box[i / 6][row][column] << shift);    // 값 더하고 쉬프트(4비트씩)

			shift -= 4;
			temp = 0;
		}
	}

	return result;
}

S-box의 코드이다.

C언어에서 최소 데이터형이 8비트이기 때문에 temp에 6비트씩 담아서 처리한다.

비트필드로도 처리해도 되겠지만 귀찮아서 패스.

6비트중 상위 1번째비트와 6번째 비트는 S-box의 행값( 따라서 총 4행 )을 나타내고

중간 4비트는 열값을 나타내며 해당 행, 열에 위치한 값으로 치환된다.

S1 box

void key_expansion(BYTE *key, BYTE round_key[16][6])
{
	int i;
	BYTE pc1_result[7] = { 0, };
	UINT c = 0, d = 0;

	PC1(key, pc1_result);                // 축소 전치(64 -> 56)

	makeBit28(&c, &d, pc1_result);  // 28비트씩 쪼갬

	for (i = 0;i<16;i++)
	{
		c = cir_shift(c, i);             // 순환왼쪽쉬프트
		d = cir_shift(d, i);

		PC2(c, d, round_key[i]);     // 축소 전치(56 -> 48)
	}
}

키 확장 코드이다.

UINT cir_shift(UINT n, int r)
{
	int n_shift[16] = { 1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1 };

	n = (n << n_shift[r]) + (n >> (28 - n_shift[r]));

	return n & 0xFFFFFFF;      // 쓰레기값 제거
}

왼쪽 순환 쉬프트 코드이다.

n_shift 배열에 각 라운드별 순환 횟수가 있다.

그 횟수 만큼 왼쪽 쉬프트를 해주고 순환쉬프트이므로 28비트에서 밀려난 상위비트를 밀려난 만큼 최하위로 밀어준다.

UINT는 32비트이므로 n을 왼쪽으로 밀때 32비트 상위 4비트에 쓰레기값이 생긴다. 따라서 하위 28비트만 취할 수 있게

0xFFFFFFF의 마스크를 씌워 반환한다.

이상 DES의 구조와 핵심 코드들을 살펴 보았다.