| 1 | /********************************************************************* |
| 2 | * Filename: des.c |
| 3 | * Author: Brad Conte (brad AT radconte.com) |
| 4 | * Copyright: |
| 5 | * Disclaimer: This code is presented "as is" without any guarantees. |
| 6 | * Details: Implementation of the DES encryption algorithm. |
| 7 | Modes of operation (such as CBC) are not included. |
| 8 | The formal NIST algorithm specification can be found here: |
| 9 | * http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf |
| 10 | *********************************************************************/ |
| 11 | |
| 12 | /*************************** HEADER FILES ***************************/ |
| 13 | #include <stdlib.h> |
| 14 | #include <string.h> |
| 15 | #include "des.h" |
| 16 | |
| 17 | /****************************** MACROS ******************************/ |
| 18 | // Obtain bit "b" from the left and shift it "c" places from the right |
| 19 | #define BITNUM(a,b,c) (((a[(b)/8] >> (7 - (b%8))) & 0x01) << (c)) |
| 20 | #define BITNUMINTR(a,b,c) ((((a) >> (31 - (b))) & 0x00000001) << (c)) |
| 21 | #define BITNUMINTL(a,b,c) ((((a) << (b)) & 0x80000000) >> (c)) |
| 22 | |
| 23 | // This macro converts a 6 bit block with the S-Box row defined as the first and last |
| 24 | // bits to a 6 bit block with the row defined by the first two bits. |
| 25 | #define SBOXBIT(a) (((a) & 0x20) | (((a) & 0x1f) >> 1) | (((a) & 0x01) << 4)) |
| 26 | |
| 27 | /**************************** VARIABLES *****************************/ |
| 28 | static const BYTE sbox1[64] = { |
| 29 | 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7, |
| 30 | 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8, |
| 31 | 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0, |
| 32 | 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13 |
| 33 | }; |
| 34 | static const BYTE sbox2[64] = { |
| 35 | 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10, |
| 36 | 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5, |
| 37 | 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15, |
| 38 | 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9 |
| 39 | }; |
| 40 | static const BYTE sbox3[64] = { |
| 41 | 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8, |
| 42 | 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1, |
| 43 | 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7, |
| 44 | 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12 |
| 45 | }; |
| 46 | static const BYTE sbox4[64] = { |
| 47 | 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15, |
| 48 | 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9, |
| 49 | 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4, |
| 50 | 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14 |
| 51 | }; |
| 52 | static const BYTE sbox5[64] = { |
| 53 | 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9, |
| 54 | 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6, |
| 55 | 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14, |
| 56 | 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3 |
| 57 | }; |
| 58 | static const BYTE sbox6[64] = { |
| 59 | 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11, |
| 60 | 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8, |
| 61 | 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6, |
| 62 | 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13 |
| 63 | }; |
| 64 | static const BYTE sbox7[64] = { |
| 65 | 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1, |
| 66 | 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6, |
| 67 | 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2, |
| 68 | 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12 |
| 69 | }; |
| 70 | static const BYTE sbox8[64] = { |
| 71 | 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7, |
| 72 | 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2, |
| 73 | 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8, |
| 74 | 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11 |
| 75 | }; |
| 76 | |
| 77 | /*********************** FUNCTION DEFINITIONS ***********************/ |
| 78 | // Initial (Inv)Permutation step |
| 79 | void IP(WORD state[], const BYTE in[]) |
| 80 | { |
| 81 | state[0] = BITNUM(in,57,31) | BITNUM(in,49,30) | BITNUM(in,41,29) | BITNUM(in,33,28) | |
| 82 | BITNUM(in,25,27) | BITNUM(in,17,26) | BITNUM(in,9,25) | BITNUM(in,1,24) | |
| 83 | BITNUM(in,59,23) | BITNUM(in,51,22) | BITNUM(in,43,21) | BITNUM(in,35,20) | |
| 84 | BITNUM(in,27,19) | BITNUM(in,19,18) | BITNUM(in,11,17) | BITNUM(in,3,16) | |
| 85 | BITNUM(in,61,15) | BITNUM(in,53,14) | BITNUM(in,45,13) | BITNUM(in,37,12) | |
| 86 | BITNUM(in,29,11) | BITNUM(in,21,10) | BITNUM(in,13,9) | BITNUM(in,5,8) | |
| 87 | BITNUM(in,63,7) | BITNUM(in,55,6) | BITNUM(in,47,5) | BITNUM(in,39,4) | |
| 88 | BITNUM(in,31,3) | BITNUM(in,23,2) | BITNUM(in,15,1) | BITNUM(in,7,0); |
| 89 | |
| 90 | state[1] = BITNUM(in,56,31) | BITNUM(in,48,30) | BITNUM(in,40,29) | BITNUM(in,32,28) | |
| 91 | BITNUM(in,24,27) | BITNUM(in,16,26) | BITNUM(in,8,25) | BITNUM(in,0,24) | |
| 92 | BITNUM(in,58,23) | BITNUM(in,50,22) | BITNUM(in,42,21) | BITNUM(in,34,20) | |
| 93 | BITNUM(in,26,19) | BITNUM(in,18,18) | BITNUM(in,10,17) | BITNUM(in,2,16) | |
| 94 | BITNUM(in,60,15) | BITNUM(in,52,14) | BITNUM(in,44,13) | BITNUM(in,36,12) | |
| 95 | BITNUM(in,28,11) | BITNUM(in,20,10) | BITNUM(in,12,9) | BITNUM(in,4,8) | |
| 96 | BITNUM(in,62,7) | BITNUM(in,54,6) | BITNUM(in,46,5) | BITNUM(in,38,4) | |
| 97 | BITNUM(in,30,3) | BITNUM(in,22,2) | BITNUM(in,14,1) | BITNUM(in,6,0); |
| 98 | } |
| 99 | |
| 100 | void InvIP(WORD state[], BYTE in[]) |
| 101 | { |
| 102 | in[0] = BITNUMINTR(state[1],7,7) | BITNUMINTR(state[0],7,6) | BITNUMINTR(state[1],15,5) | |
| 103 | BITNUMINTR(state[0],15,4) | BITNUMINTR(state[1],23,3) | BITNUMINTR(state[0],23,2) | |
| 104 | BITNUMINTR(state[1],31,1) | BITNUMINTR(state[0],31,0); |
| 105 | |
| 106 | in[1] = BITNUMINTR(state[1],6,7) | BITNUMINTR(state[0],6,6) | BITNUMINTR(state[1],14,5) | |
| 107 | BITNUMINTR(state[0],14,4) | BITNUMINTR(state[1],22,3) | BITNUMINTR(state[0],22,2) | |
| 108 | BITNUMINTR(state[1],30,1) | BITNUMINTR(state[0],30,0); |
| 109 | |
| 110 | in[2] = BITNUMINTR(state[1],5,7) | BITNUMINTR(state[0],5,6) | BITNUMINTR(state[1],13,5) | |
| 111 | BITNUMINTR(state[0],13,4) | BITNUMINTR(state[1],21,3) | BITNUMINTR(state[0],21,2) | |
| 112 | BITNUMINTR(state[1],29,1) | BITNUMINTR(state[0],29,0); |
| 113 | |
| 114 | in[3] = BITNUMINTR(state[1],4,7) | BITNUMINTR(state[0],4,6) | BITNUMINTR(state[1],12,5) | |
| 115 | BITNUMINTR(state[0],12,4) | BITNUMINTR(state[1],20,3) | BITNUMINTR(state[0],20,2) | |
| 116 | BITNUMINTR(state[1],28,1) | BITNUMINTR(state[0],28,0); |
| 117 | |
| 118 | in[4] = BITNUMINTR(state[1],3,7) | BITNUMINTR(state[0],3,6) | BITNUMINTR(state[1],11,5) | |
| 119 | BITNUMINTR(state[0],11,4) | BITNUMINTR(state[1],19,3) | BITNUMINTR(state[0],19,2) | |
| 120 | BITNUMINTR(state[1],27,1) | BITNUMINTR(state[0],27,0); |
| 121 | |
| 122 | in[5] = BITNUMINTR(state[1],2,7) | BITNUMINTR(state[0],2,6) | BITNUMINTR(state[1],10,5) | |
| 123 | BITNUMINTR(state[0],10,4) | BITNUMINTR(state[1],18,3) | BITNUMINTR(state[0],18,2) | |
| 124 | BITNUMINTR(state[1],26,1) | BITNUMINTR(state[0],26,0); |
| 125 | |
| 126 | in[6] = BITNUMINTR(state[1],1,7) | BITNUMINTR(state[0],1,6) | BITNUMINTR(state[1],9,5) | |
| 127 | BITNUMINTR(state[0],9,4) | BITNUMINTR(state[1],17,3) | BITNUMINTR(state[0],17,2) | |
| 128 | BITNUMINTR(state[1],25,1) | BITNUMINTR(state[0],25,0); |
| 129 | |
| 130 | in[7] = BITNUMINTR(state[1],0,7) | BITNUMINTR(state[0],0,6) | BITNUMINTR(state[1],8,5) | |
| 131 | BITNUMINTR(state[0],8,4) | BITNUMINTR(state[1],16,3) | BITNUMINTR(state[0],16,2) | |
| 132 | BITNUMINTR(state[1],24,1) | BITNUMINTR(state[0],24,0); |
| 133 | } |
| 134 | |
| 135 | WORD f(WORD state, const BYTE key[]) |
| 136 | { |
| 137 | BYTE lrgstate[6]; //,i; |
| 138 | WORD t1,t2; |
| 139 | |
| 140 | // Expantion Permutation |
| 141 | t1 = BITNUMINTL(state,31,0) | ((state & 0xf0000000) >> 1) | BITNUMINTL(state,4,5) | |
| 142 | BITNUMINTL(state,3,6) | ((state & 0x0f000000) >> 3) | BITNUMINTL(state,8,11) | |
| 143 | BITNUMINTL(state,7,12) | ((state & 0x00f00000) >> 5) | BITNUMINTL(state,12,17) | |
| 144 | BITNUMINTL(state,11,18) | ((state & 0x000f0000) >> 7) | BITNUMINTL(state,16,23); |
| 145 | |
| 146 | t2 = BITNUMINTL(state,15,0) | ((state & 0x0000f000) << 15) | BITNUMINTL(state,20,5) | |
| 147 | BITNUMINTL(state,19,6) | ((state & 0x00000f00) << 13) | BITNUMINTL(state,24,11) | |
| 148 | BITNUMINTL(state,23,12) | ((state & 0x000000f0) << 11) | BITNUMINTL(state,28,17) | |
| 149 | BITNUMINTL(state,27,18) | ((state & 0x0000000f) << 9) | BITNUMINTL(state,0,23); |
| 150 | |
| 151 | lrgstate[0] = (t1 >> 24) & 0x000000ff; |
| 152 | lrgstate[1] = (t1 >> 16) & 0x000000ff; |
| 153 | lrgstate[2] = (t1 >> 8) & 0x000000ff; |
| 154 | lrgstate[3] = (t2 >> 24) & 0x000000ff; |
| 155 | lrgstate[4] = (t2 >> 16) & 0x000000ff; |
| 156 | lrgstate[5] = (t2 >> 8) & 0x000000ff; |
| 157 | |
| 158 | // Key XOR |
| 159 | lrgstate[0] ^= key[0]; |
| 160 | lrgstate[1] ^= key[1]; |
| 161 | lrgstate[2] ^= key[2]; |
| 162 | lrgstate[3] ^= key[3]; |
| 163 | lrgstate[4] ^= key[4]; |
| 164 | lrgstate[5] ^= key[5]; |
| 165 | |
| 166 | // S-Box Permutation |
| 167 | state = (sbox1[SBOXBIT(lrgstate[0] >> 2)] << 28) | |
| 168 | (sbox2[SBOXBIT(((lrgstate[0] & 0x03) << 4) | (lrgstate[1] >> 4))] << 24) | |
| 169 | (sbox3[SBOXBIT(((lrgstate[1] & 0x0f) << 2) | (lrgstate[2] >> 6))] << 20) | |
| 170 | (sbox4[SBOXBIT(lrgstate[2] & 0x3f)] << 16) | |
| 171 | (sbox5[SBOXBIT(lrgstate[3] >> 2)] << 12) | |
| 172 | (sbox6[SBOXBIT(((lrgstate[3] & 0x03) << 4) | (lrgstate[4] >> 4))] << 8) | |
| 173 | (sbox7[SBOXBIT(((lrgstate[4] & 0x0f) << 2) | (lrgstate[5] >> 6))] << 4) | |
| 174 | sbox8[SBOXBIT(lrgstate[5] & 0x3f)]; |
| 175 | |
| 176 | // P-Box Permutation |
| 177 | state = BITNUMINTL(state,15,0) | BITNUMINTL(state,6,1) | BITNUMINTL(state,19,2) | |
| 178 | BITNUMINTL(state,20,3) | BITNUMINTL(state,28,4) | BITNUMINTL(state,11,5) | |
| 179 | BITNUMINTL(state,27,6) | BITNUMINTL(state,16,7) | BITNUMINTL(state,0,8) | |
| 180 | BITNUMINTL(state,14,9) | BITNUMINTL(state,22,10) | BITNUMINTL(state,25,11) | |
| 181 | BITNUMINTL(state,4,12) | BITNUMINTL(state,17,13) | BITNUMINTL(state,30,14) | |
| 182 | BITNUMINTL(state,9,15) | BITNUMINTL(state,1,16) | BITNUMINTL(state,7,17) | |
| 183 | BITNUMINTL(state,23,18) | BITNUMINTL(state,13,19) | BITNUMINTL(state,31,20) | |
| 184 | BITNUMINTL(state,26,21) | BITNUMINTL(state,2,22) | BITNUMINTL(state,8,23) | |
| 185 | BITNUMINTL(state,18,24) | BITNUMINTL(state,12,25) | BITNUMINTL(state,29,26) | |
| 186 | BITNUMINTL(state,5,27) | BITNUMINTL(state,21,28) | BITNUMINTL(state,10,29) | |
| 187 | BITNUMINTL(state,3,30) | BITNUMINTL(state,24,31); |
| 188 | |
| 189 | // Return the final state value |
| 190 | return(state); |
| 191 | } |
| 192 | |
| 193 | void des_key_setup(const BYTE key[], BYTE schedule[][6], DES_MODE mode) |
| 194 | { |
| 195 | WORD i, j, to_gen, C, D; |
| 196 | const WORD key_rnd_shift[16] = {1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1}; |
| 197 | const WORD key_perm_c[28] = {56,48,40,32,24,16,8,0,57,49,41,33,25,17, |
| 198 | 9,1,58,50,42,34,26,18,10,2,59,51,43,35}; |
| 199 | const WORD key_perm_d[28] = {62,54,46,38,30,22,14,6,61,53,45,37,29,21, |
| 200 | 13,5,60,52,44,36,28,20,12,4,27,19,11,3}; |
| 201 | const WORD key_compression[48] = {13,16,10,23,0,4,2,27,14,5,20,9, |
| 202 | 22,18,11,3,25,7,15,6,26,19,12,1, |
| 203 | 40,51,30,36,46,54,29,39,50,44,32,47, |
| 204 | 43,48,38,55,33,52,45,41,49,35,28,31}; |
| 205 | |
| 206 | // Permutated Choice #1 (copy the key in, ignoring parity bits). |
| 207 | for (i = 0, j = 31, C = 0; i < 28; ++i, --j) |
| 208 | C |= BITNUM(key,key_perm_c[i],j); |
| 209 | for (i = 0, j = 31, D = 0; i < 28; ++i, --j) |
| 210 | D |= BITNUM(key,key_perm_d[i],j); |
| 211 | |
| 212 | // Generate the 16 subkeys. |
| 213 | for (i = 0; i < 16; ++i) { |
| 214 | C = ((C << key_rnd_shift[i]) | (C >> (28-key_rnd_shift[i]))) & 0xfffffff0; |
| 215 | D = ((D << key_rnd_shift[i]) | (D >> (28-key_rnd_shift[i]))) & 0xfffffff0; |
| 216 | |
| 217 | // Decryption subkeys are reverse order of encryption subkeys so |
| 218 | // generate them in reverse if the key schedule is for decryption useage. |
| 219 | if (mode == DES_DECRYPT) |
| 220 | to_gen = 15 - i; |
| 221 | else /*(if mode == DES_ENCRYPT)*/ |
| 222 | to_gen = i; |
| 223 | // Initialize the array |
| 224 | for (j = 0; j < 6; ++j) |
| 225 | schedule[to_gen][j] = 0; |
| 226 | for (j = 0; j < 24; ++j) |
| 227 | schedule[to_gen][j/8] |= BITNUMINTR(C,key_compression[j],7 - (j%8)); |
| 228 | for ( ; j < 48; ++j) |
| 229 | schedule[to_gen][j/8] |= BITNUMINTR(D,key_compression[j] - 28,7 - (j%8)); |
| 230 | } |
| 231 | } |
| 232 | |
| 233 | void des_crypt(const BYTE in[], BYTE out[], const BYTE key[][6]) |
| 234 | { |
| 235 | WORD state[2],idx,t; |
| 236 | |
| 237 | IP(state,in); |
| 238 | |
| 239 | for (idx=0; idx < 15; ++idx) { |
| 240 | t = state[1]; |
| 241 | state[1] = f(state[1],key[idx]) ^ state[0]; |
| 242 | state[0] = t; |
| 243 | } |
| 244 | // Perform the final loop manually as it doesn't switch sides |
| 245 | state[0] = f(state[1],key[15]) ^ state[0]; |
| 246 | |
| 247 | InvIP(state,out); |
| 248 | } |
| 249 | |
| 250 | void three_des_key_setup(const BYTE key[], BYTE schedule[][16][6], DES_MODE mode) |
| 251 | { |
| 252 | if (mode == DES_ENCRYPT) { |
| 253 | des_key_setup(&key[0],schedule[0],mode); |
| 254 | des_key_setup(&key[8],schedule[1],!mode); |
| 255 | des_key_setup(&key[16],schedule[2],mode); |
| 256 | } |
| 257 | else /*if (mode == DES_DECRYPT*/ { |
| 258 | des_key_setup(&key[16],schedule[0],mode); |
| 259 | des_key_setup(&key[8],schedule[1],!mode); |
| 260 | des_key_setup(&key[0],schedule[2],mode); |
| 261 | } |
| 262 | } |
| 263 | |
| 264 | void three_des_crypt(const BYTE in[], BYTE out[], const BYTE key[][16][6]) |
| 265 | { |
| 266 | des_crypt(in,out,key[0]); |
| 267 | des_crypt(out,out,key[1]); |
| 268 | des_crypt(out,out,key[2]); |
| 269 | } |