C로 DES 구현!

2015.06.19. 09:54

학교에서 정보보호 시간에 DES에 대해 배웠는데 한번 직접 짜 봤습니다.

약 2시간 정도 걸렸네요~

선생님이 만드신 PPT자료를 보고 만들었는데 자료에는 비트순서가 잘 나와있지 않아...

실제 사용되는 DES알고리즘과는 차이가 있습니다.

(2016-03-21 수정 - Standard에 맞게 수정함)

이건 그냥 DES알고리즘 자체만 구현한 것이니 그냥 참고용으로만 보세요~

절대! 이 소스를 실제상황에서 사용하면 안됩니다!

솔직히 효율성도 떨어지는 소스구요...ㅠ

비트 순서 바꾸는 방법이 잘 생각이 안나 미리 지정된 테이블을 통해 막무가네로 바꿔버립니다.ㅎ

#include <stdio.h> #include <stdlib.h> #include <string.h> unsigned char DES_IP_TABLE[64] = { 57,49,41,33,25,17,9,1, 59,51,43,35,27,19,11,3, 61,53,45,37,29,21,13,5, 63,55,47,39,31,23,15,7, 56,48,40,32,24,16,8,0, 58,50,42,34,26,18,10,2, 60,52,44,36,28,20,12,4, 62,54,46,38,30,22,14,6, }; unsigned char DES_IP_inverse_TABLE[64] = { 39,7,47,15,55,23,63,31, 38,6,46,14,54,22,62,30, 37,5,45,13,53,21,61,29, 36,4,44,12,52,20,60,28, 35,3,43,11,51,19,59,27, 34,2,42,10,50,18,58,26, 33,1,41,9,49,17,57,25, 32,0,40,8,48,16,56,24, }; unsigned char DES_E_TABLE[48] = { 31,0,1,2,3,4, 3,4,5,6,7,8, 7,8,9,10,11,12, 11,12,13,14,15,16, 15,16,17,18,19,20, 19,20,21,22,23,24, 23,24,25,26,27,28, 27,28,29,30,31,0 }; unsigned char DES_P[32] = { 15,6,19,20, 28,11,27,16, 0,14,22,25, 4,17,30,9, 1,7,23,13, 31,26,2,8, 18,12,29,5, 21,10,3,24, }; unsigned char DES_PC1_TABLE[8][7]= { 56,48,40,32,24,16, 8, 0,57,49,41,33,25,17, 9, 1,58,50,42,34,26, 18,10, 2,59,51,43,35, 62,54,46,38,30,22,14, 6,61,53,45,37,29,21, 13, 5,60,52,44,36,28, 20,12, 4,27,19,11, 3 }; unsigned char DES_PC2_TABLE[8][6]= { 13,16,10,23, 0, 4, 2,27, 14, 5,20, 9,22,18,11, 3, 25, 7,15, 6,26,19,12, 1, 40,51,30,36,46,54,29,39, 50,44,32,47,43,48,38,55, 33,52,45,41,49,35,28,31 }; unsigned char DES_SubkeyRotaion_TABLE[] = { 1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1 }; unsigned char DES_S_TABLE[8][4][16] = { { {14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7}, {0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8}, {4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0}, {15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13} }, { {15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10}, {3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5}, {0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15}, {13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9} }, { {10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8}, {13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1}, {13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7}, {1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12} }, { {7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15}, {13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9}, {10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4}, {3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14} }, { {2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9}, {14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6}, {4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14}, {11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3} }, { {12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11}, {10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8}, {9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6}, {4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13} }, { {4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1}, {13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6}, {1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2}, {6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12} }, { {13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7}, {1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2}, {7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8}, {2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11} } }; #define DES_GETBIT(data, i) ((data&(1<<(i))) ? 1 : 0) #define DES_SETBIT(data, i) data |= (1<<(i)) #define DES_CLRBIT(data, i) data &= ~(1<<(i)) void my_dump_hex(unsigned char *data, int length) { int i; for(i=0;i<length;i++) printf("%02x ", data[i]); } void my_dump_bin(unsigned char *data, int length, int split) { int i, j; for(i=0;i<length;) { for(j=0; j<split; j++, i++) { char c = data[i/8]; char b = (c >> (7-(i%8))) & 1; printf("%d", b); } printf(" "); } printf("\n"); } void my_dump_int2bin(long data, int split) { int i, j; for(i=0;i<32;) { for(j=0; j<split; j++, i++) { char b = (data >> (31-i)) & 1; printf("%d", b); } printf(" "); } printf("\n"); } void DES_ChangeBits(unsigned char *matrix, int destbitslength, unsigned char *source, unsigned char *dest) { int i; memset(dest, 0, destbitslength/8); for(i=0;i<destbitslength;i++) { int s = matrix[i]; int si = s / 8; int sj = s % 8; int di = i / 8; int dj = i % 8; if(DES_GETBIT(source[si], 7-sj)) DES_SETBIT(dest[di], 7-dj); //else // DES_CLRBIT(dest[di], dj); } } void DES_ChangeBitsInverseInput(unsigned char *matrix, int destbitslength, unsigned char *source, unsigned char *dest) { int i; memset(dest, 0, destbitslength/8); for(i=0;i<destbitslength;i++) { int s = 31 - matrix[i]; int si = s / 8; int sj = s % 8; int d = i; int di = d / 8; int dj = d % 8; if(DES_GETBIT(source[si], sj)) DES_SETBIT(dest[di], 7-dj); //else // DES_CLRBIT(dest[di], dj); } } void DES_ChangeBitsInverseBoth(unsigned char *matrix, int destbitslength, unsigned char *source, unsigned char *dest) { int i; memset(dest, 0, destbitslength/8); for(i=0;i<destbitslength;i++) { int s = 31 - matrix[i]; int si = s / 8; int sj = s % 8; int d = 31 - i; int di = d / 8; int dj = d % 8; if(DES_GETBIT(source[si], sj)) DES_SETBIT(dest[di], dj); //else // DES_CLRBIT(dest[di], dj); } } void DES_IP(unsigned char *source, unsigned char *dest) { DES_ChangeBits(DES_IP_TABLE, 64, source, dest); } void DES_IP_inverse(unsigned char *source, unsigned char *dest) { DES_ChangeBits(DES_IP_inverse_TABLE, 64, source, dest); } // Expansion // Input : 32bit // Output : 48bit void DES_E(unsigned long source, unsigned char *dest) { DES_ChangeBitsInverseInput(DES_E_TABLE, 48, (unsigned char *)&source, dest); } unsigned char DES_S(int index, unsigned char input) { unsigned char i = (input>>4 & 0x02) | (input & 0x01); unsigned char j = (input>>1)&0x0F; return DES_S_TABLE[index][i][j]; } unsigned long DES_f(unsigned char *RoundKey, unsigned long input) { unsigned char a[6] = {0}; unsigned long sbox = 0; unsigned long P = 0; int i, j, k; DES_E(input, a); for(i=0; i<6; i++) a[i] ^= RoundKey[i]; for(i=0, k=0; i<48; k++) { unsigned char b = 0, c; for(j=0; j<6; j++, i++) { int bytei = i / 8; int biti = i % 8; b <<= 1; if((a[bytei] >> (7-biti)) & 1) b|=1; } c = DES_S(k, b); sbox <<= 4; sbox |= c; } DES_ChangeBitsInverseBoth((unsigned char*)DES_P, 32, (unsigned char*)&sbox, (unsigned char*)&P); return P; } // Key : 64bit // RoundKey : 48bit * 16 void DES_RoundKey(unsigned char *Key, unsigned char *RoundKey) { int i; unsigned char Key_PC1[7]; unsigned char Key_PC2[7]; unsigned long t, C=0, D=0; // 28bit (24+4) DES_ChangeBits((unsigned char *)DES_PC1_TABLE, 56, Key, Key_PC1); ///////////////////////////// C = 0; C |= ((unsigned long)Key_PC1[0] << 20); C |= ((unsigned long)Key_PC1[1] << 12); C |= ((unsigned long)Key_PC1[2] << 4); C |= (((unsigned long)Key_PC1[3] >> 4) & 0x0F); D = 0; D |= (((unsigned long)Key_PC1[3]&0x0F) << 24); D |= ((unsigned long)Key_PC1[4] << 16); D |= ((unsigned long)Key_PC1[5] << 8); D |= ((unsigned long)Key_PC1[6]); for(i=0;i<16;i++) { if(DES_SubkeyRotaion_TABLE[i]==1) { //1 C = (C << 1); t = C&0x10000000; C &= 0x0FFFFFFE; C |= t >> 28; D = (D << 1); t = D&0x10000000; D &= 0x0FFFFFFE; D |= t >> 28; }else{ //2 C = (C << 2); t = C&0x30000000; C &= 0x0FFFFFFC; C |= t >> 28; D = (D << 2); t = D&0x30000000; D &= 0x0FFFFFFC; D |= t >> 28; } Key_PC2[0] = (unsigned char)(C >> 20); Key_PC2[1] = (unsigned char)(C >> 12); Key_PC2[2] = (unsigned char)(C >> 4); Key_PC2[3] = (unsigned char)((C & 0x0F)<<4); Key_PC2[3]|= (unsigned char)((D >> 24) & 0x0F); Key_PC2[4] = (unsigned char)(D >> 16); Key_PC2[5] = (unsigned char)(D >> 8); Key_PC2[6] = (unsigned char)(D); DES_ChangeBits((unsigned char*)DES_PC2_TABLE, 48, Key_PC2, &RoundKey[i*6]); } } void DES_BlockEncrypt(unsigned char *RoundKey, unsigned char *PlainText, unsigned char *CipherText) { int i; unsigned char PlainText2[8]; unsigned char CipherText2[8]; unsigned long tmp; unsigned long L, R; DES_IP(PlainText, PlainText2); L = (((unsigned long) PlainText2[0])<<24)|(((unsigned long) PlainText2[1])<<16)| (((unsigned long) PlainText2[2])<<8)|(((unsigned long) PlainText2[3]) << 0); R = (((unsigned long) PlainText2[4])<<24)|(((unsigned long) PlainText2[5])<<16)| (((unsigned long) PlainText2[6])<<8)|(((unsigned long) PlainText2[7]) <<0); for(i=0;i<16;i++) { tmp = R; R = L ^ DES_f(&RoundKey[i*6], tmp); L = tmp; } tmp = R; R = L; L = tmp; CipherText2[0] = (unsigned char)((L >> 24) & 0xFF); CipherText2[1] = (unsigned char)((L >> 16) & 0xFF); CipherText2[2] = (unsigned char)((L >> 8) & 0xFF); CipherText2[3] = (unsigned char)((L >> 0) & 0xFF); CipherText2[4] = (unsigned char)((R >> 24) & 0xFF); CipherText2[5] = (unsigned char)((R >> 16) & 0xFF); CipherText2[6] = (unsigned char)((R >> 8) & 0xFF); CipherText2[7] = (unsigned char)((R >> 0) & 0xFF); DES_IP_inverse(CipherText2, CipherText); } void DES_BlockDecrypt(unsigned char *RoundKey, unsigned char *PlainText, unsigned char *CipherText) { int i; unsigned char PlainText2[8]; unsigned char CipherText2[8]; unsigned long tmp; unsigned long L, R; DES_IP(CipherText, CipherText2); L = (((unsigned long) CipherText2[0])<<24)|(((unsigned long) CipherText2[1])<<16)| (((unsigned long) CipherText2[2])<<8)|(((unsigned long) CipherText2[3]) << 0); R = (((unsigned long) CipherText2[4])<<24)|(((unsigned long) CipherText2[5])<<16)| (((unsigned long) CipherText2[6])<<8)|(((unsigned long) CipherText2[7]) <<0); for(i=0;i<16;i++) { tmp = R; R = L ^ DES_f(&RoundKey[(15-i)*6], tmp); L = tmp; } tmp = R; R = L; L = tmp; PlainText2[0] = (unsigned char)((L >> 24) & 0xFF); PlainText2[1] = (unsigned char)((L >> 16) & 0xFF); PlainText2[2] = (unsigned char)((L >> 8) & 0xFF); PlainText2[3] = (unsigned char)((L >> 0) & 0xFF); PlainText2[4] = (unsigned char)((R >> 24) & 0xFF); PlainText2[5] = (unsigned char)((R >> 16) & 0xFF); PlainText2[6] = (unsigned char)((R >> 8) & 0xFF); PlainText2[7] = (unsigned char)((R >> 0) & 0xFF); DES_IP_inverse(PlainText2, PlainText); } int main() { char PlainText[8] = {0x02,0x46,0x8a,0xce,0xec,0xa8,0x64,0x20}; char CipherText[8] = {0}; char DecodeText[8] = {0}; unsigned char Key[8] = {0x0f,0x15,0x71,0xc9,0x47,0xd9,0xe8,0x59}; unsigned char RoundKey[96]; //16*6 DES_RoundKey(Key, RoundKey); DES_BlockEncrypt(RoundKey, &PlainText[0], &CipherText[0]); DES_BlockDecrypt(RoundKey, &DecodeText[0], &CipherText[0]); printf("KEY : \n"); my_dump_hex(Key, 8); printf("\n"); printf("\n"); printf("ROUND KEY : "); my_dump_hex(RoundKey, 96); printf("\n"); printf("\n"); printf("PLAIN TEXT : \n"); my_dump_hex(PlainText, 8); printf("\n"); printf("\n"); printf("CIPHER TEXT : "); my_dump_hex(CipherText, 8); printf("\n"); printf("\n"); printf("DECODE TEXT : \n"); my_dump_hex(DecodeText, 8); printf("\n"); printf("\n"); return 0; }

KEY         : 0f 15 71 c9 47 d9 e8 59 ROUND KEY : 78 33 c3 20 da 70 2b 1a 74 ca 48 d8 8c 78 d8 81 d3 1d 16 67 78 93 16 a0 ce 5d 01 d8 0b 25 4b ab 4d 12 6a 9c 09 f4 8b 71 31 91 71 0d ea a3 20 2b 12 9a b8 33 47 c3 9c 38 66 1e 81 03 a2 6e 4c c6 65 44 48 77 24 68 a3 c8 c0 9d 79 f0 d4 0b c5 e2 63 4e 16 2a a3 df 82 9c 79 68 a6 12 0b 4d 4c 25 PLAIN  TEXT : 02 46 8a ce ec a8 64 20 CIPHER TEXT : da 02 ce 3a 89 ec ac 3b DECODE TEXT : 02 46 8a ce ec a8 64 20

대충 잘 되네요~ㅎ

아 근데 전 DES가 56bit key size을 사용해서 진짜 56bit(7byte)을 입력키로 사용하는 줄 알았는데

DES을 배우다 보니 key 입력을 64bit(8byte)으로 받고 중간중간8bit을 잘라 56bit으로 바꿔 사용하네요~