des.c

   1 /**
   2  * \file        des.c
   3  * \author      Daniel Otte
   4  * \date        2007-06-16
   5  * \brief       DES and EDE-DES implementation
   6  * \par License
   7  * GPL
   8  *
   9  */
  10 #include "config.h"
  11 #include "debug.h"
  12 #include "uart.h"
  13 #include <string.h>
  14 #include <util/delay.h>
  15 #include <avr/pgmspace.h>
  16
  17 prog_uint8_t sbox[256]  = {
  18   /* S-box 1 */
  19   0xE4, 0xD1, 0x2F, 0xB8, 0x3A, 0x6C, 0x59, 0x07,
  20   0x0F, 0x74, 0xE2, 0xD1, 0xA6, 0xCB, 0x95, 0x38,
  21   0x41, 0xE8, 0xD6, 0x2B, 0xFC, 0x97, 0x3A, 0x50,
  22   0xFC, 0x82, 0x49, 0x17, 0x5B, 0x3E, 0xA0, 0x6D,
  23   /* S-box 2 */
  24   0xF1, 0x8E, 0x6B, 0x34, 0x97, 0x2D, 0xC0, 0x5A,
  25   0x3D, 0x47, 0xF2, 0x8E, 0xC0, 0x1A, 0x69, 0xB5,
  26   0x0E, 0x7B, 0xA4, 0xD1, 0x58, 0xC6, 0x93, 0x2F,
  27   0xD8, 0xA1, 0x3F, 0x42, 0xB6, 0x7C, 0x05, 0xE9,
  28   /* S-box 3 */
  29   0xA0, 0x9E, 0x63, 0xF5, 0x1D, 0xC7, 0xB4, 0x28,
  30   0xD7, 0x09, 0x34, 0x6A, 0x28, 0x5E, 0xCB, 0xF1,
  31   0xD6, 0x49, 0x8F, 0x30, 0xB1, 0x2C, 0x5A, 0xE7,
  32   0x1A, 0xD0, 0x69, 0x87, 0x4F, 0xE3, 0xB5, 0x2C,
  33   /* S-box 4 */
  34   0x7D, 0xE3, 0x06, 0x9A, 0x12, 0x85, 0xBC, 0x4F,
  35   0xD8, 0xB5, 0x6F, 0x03, 0x47, 0x2C, 0x1A, 0xE9,
  36   0xA6, 0x90, 0xCB, 0x7D, 0xF1, 0x3E, 0x52, 0x84,
  37   0x3F, 0x06, 0xA1, 0xD8, 0x94, 0x5B, 0xC7, 0x2E,
  38   /* S-box 5 */
  39   0x2C, 0x41, 0x7A, 0xB6, 0x85, 0x3F, 0xD0, 0xE9,
  40   0xEB, 0x2C, 0x47, 0xD1, 0x50, 0xFA, 0x39, 0x86,
  41   0x42, 0x1B, 0xAD, 0x78, 0xF9, 0xC5, 0x63, 0x0E,
  42   0xB8, 0xC7, 0x1E, 0x2D, 0x6F, 0x09, 0xA4, 0x53,
  43   /* S-box 6 */
  44   0xC1, 0xAF, 0x92, 0x68, 0x0D, 0x34, 0xE7, 0x5B,
  45   0xAF, 0x42, 0x7C, 0x95, 0x61, 0xDE, 0x0B, 0x38,
  46   0x9E, 0xF5, 0x28, 0xC3, 0x70, 0x4A, 0x1D, 0xB6,
  47   0x43, 0x2C, 0x95, 0xFA, 0xBE, 0x17, 0x60, 0x8D,
  48   /* S-box 7 */
  49   0x4B, 0x2E, 0xF0, 0x8D, 0x3C, 0x97, 0x5A, 0x61,
  50   0xD0, 0xB7, 0x49, 0x1A, 0xE3, 0x5C, 0x2F, 0x86,
  51   0x14, 0xBD, 0xC3, 0x7E, 0xAF, 0x68, 0x05, 0x92,
  52   0x6B, 0xD8, 0x14, 0xA7, 0x95, 0x0F, 0xE2, 0x3C,
  53   /* S-box 8 */
  54   0xD2, 0x84, 0x6F, 0xB1, 0xA9, 0x3E, 0x50, 0xC7,
  55   0x1F, 0xD8, 0xA3, 0x74, 0xC5, 0x6B, 0x0E, 0x92,
  56   0x7B, 0x41, 0x9C, 0xE2, 0x06, 0xAD, 0xF3, 0x58,
  57   0x21, 0xE7, 0x4A, 0x8D, 0xFC, 0x90, 0x35, 0x6B
  58 };
  59
  60 prog_uint8_t e_permtab[] ={
  61          4,  6,                                         /* 4 bytes in 6 bytes out*/
  62         32,  1,  2,  3,  4,  5,
  63          4,  5,  6,  7,  8,  9,
  64          8,  9, 10, 11, 12, 13,
  65         12, 13, 14, 15, 16, 17,
  66         16, 17, 18, 19, 20, 21,
  67         20, 21, 22, 23, 24, 25,
  68         24, 25, 26, 27, 28, 29,
  69         28, 29, 30, 31, 32,  1
  70 };
  71
  72 prog_uint8_t p_permtab[] ={
  73          4,  4,                                         /* 32 bit -> 32 bit */
  74         16,  7, 20, 21,
  75         29, 12, 28, 17,
  76          1, 15, 23, 26,
  77          5, 18, 31, 10,
  78          2,  8, 24, 14,
  79         32, 27,  3,  9,
  80         19, 13, 30,  6,
  81         22, 11,  4, 25
  82 };
  83
  84 prog_uint8_t ip_permtab[] ={
  85          8,  8,                                         /* 64 bit -> 64 bit */
  86         58, 50, 42, 34, 26, 18, 10, 2,
  87         60, 52, 44, 36, 28, 20, 12, 4,
  88         62, 54, 46, 38, 30, 22, 14, 6,
  89         64, 56, 48, 40, 32, 24, 16, 8,
  90         57, 49, 41, 33, 25, 17,  9, 1,
  91         59, 51, 43, 35, 27, 19, 11, 3,
  92         61, 53, 45, 37, 29, 21, 13, 5,
  93         63, 55, 47, 39, 31, 23, 15, 7
  94 };
  95
  96 prog_uint8_t inv_ip_permtab[] ={
  97          8, 8,                                          /* 64 bit -> 64 bit */
  98         40, 8, 48, 16, 56, 24, 64, 32,
  99         39, 7, 47, 15, 55, 23, 63, 31,
 100         38, 6, 46, 14, 54, 22, 62, 30,
 101         37, 5, 45, 13, 53, 21, 61, 29,
 102         36, 4, 44, 12, 52, 20, 60, 28,
 103         35, 3, 43, 11, 51, 19, 59, 27,
 104         34, 2, 42, 10, 50, 18, 58, 26,
 105         33, 1, 41,  9, 49, 17, 57, 25
 106 };
 107
 108 prog_uint8_t pc1_permtab[] ={
 109          8,  7,                                         /* 64 bit -> 56 bit*/
 110         57, 49, 41, 33, 25, 17,  9,
 111          1, 58, 50, 42, 34, 26, 18,
 112         10,  2, 59, 51, 43, 35, 27,
 113         19, 11,  3, 60, 52, 44, 36,
 114         63, 55, 47, 39, 31, 23, 15,
 115          7, 62, 54, 46, 38, 30, 22,
 116         14,  6, 61, 53, 45, 37, 29,
 117         21, 13,  5, 28, 20, 12,  4
 118 };
 119
 120 prog_uint8_t pc2_permtab[] ={
 121          7,      6,                                     /* 56 bit -> 48 bit */
 122         14, 17, 11, 24,  1,  5,
 123          3, 28, 15,  6, 21, 10,
 124         23, 19, 12,  4, 26,  8,
 125         16,  7, 27, 20, 13,  2,
 126         41, 52, 31, 37, 47, 55,
 127         30, 40, 51, 45, 33, 48,
 128         44, 49, 39, 56, 34, 53,
 129         46, 42, 50, 36, 29, 32
 130 };
 131
 132 prog_uint8_t splitin6bitword_permtab[] = {
 133          8,  8,                                         /* 64 bit -> 64 bit */
 134         64, 64,  1,  6,  2,  3,  4,  5,
 135         64, 64,  7, 12,  8,  9, 10, 11,
 136         64, 64, 13, 18, 14, 15, 16, 17,
 137         64, 64, 19, 24, 20, 21, 22, 23,
 138         64, 64, 25, 30, 26, 27, 28, 29,
 139         64, 64, 31, 36, 32, 33, 34, 35,
 140         64, 64, 37, 42, 38, 39, 40, 41,
 141         64, 64, 43, 48, 44, 45, 46, 47
 142 };
 143
 144 prog_uint8_t shiftkey_permtab[] = {
 145          7,  7,                                         /* 56 bit -> 56 bit */
 146          2,  3,  4,  5,  6,  7,  8,  9,
 147         10, 11, 12, 13, 14, 15, 16, 17,
 148         18, 19, 20, 21, 22, 23, 24, 25,
 149         26, 27, 28,  1,
 150         30, 31, 32, 33, 34, 35, 36, 37,
 151         38, 39, 40, 41, 42, 43, 44, 45,
 152         46, 47, 48, 49, 50, 51, 52, 53,
 153         54, 55, 56, 29
 154 };
 155
 156 prog_uint8_t shiftkeyinv_permtab[] = {
 157          7,  7,
 158         28,  1,  2,  3,  4,  5,  6,  7,
 159          8,  9, 10, 11, 12, 13, 14, 15,
 160         16, 17, 18, 19, 20, 21, 22, 23,
 161         24, 25, 26, 27,
 162         56, 29, 30, 31, 32, 33, 34, 35,
 163         36, 37, 38, 39, 40, 41, 42, 43,
 164         44, 45, 46, 47, 48, 49, 50, 51,
 165         52, 53, 54, 55
 166 };
 167
 168 /*
 169 1 0
 170 1 0
 171 2 1
 172 2 1
 173 2 1
 174 2 1
 175 2 1
 176 2 1
 177 ----
 178 1 0
 179 2 1
 180 2 1
 181 2 1
 182 2 1
 183 2 1
 184 2 1
 185 1 0
 186 */
 187 #define ROTTABLE      0x7EFC
 188 #define ROTTABLE_INV  0x3F7E
 189 /******************************************************************************/
 190
 191 void permute(prog_uint8_t *ptable, uint8_t *in, uint8_t *out){
 192         uint8_t ib, ob; /* in-bytes and out-bytes */
 193         uint8_t byte, bit; /* counter for bit and byte */
 194         ib = pgm_read_byte(&(ptable[0]));
 195         ob = pgm_read_byte(&(ptable[1]));
 196         ptable = &(ptable[2]);
 197         for(byte=0; byte<ob; ++byte){
 198                 uint8_t x,t=0;
 199                 for(bit=0; bit<8; ++bit){
 200                         x=pgm_read_byte(&(ptable[byte*8+bit])) -1 ;
 201                                 t<<=1;
 202                         if((in[x/8]) & (0x80>>(x%8)) ){
 203                                 t|=0x01;
 204                         }
 205                 }
 206                 out[byte]=t;
 207         }
 208 }
 209
 210 /******************************************************************************/
 211
 212 void changeendian32(uint32_t * a){
 213         *a = (*a & 0x000000FF) << 24 |
 214                  (*a & 0x0000FF00) <<  8 |
 215                  (*a & 0x00FF0000) >>  8 |
 216                  (*a & 0xFF000000) >> 24;
 217 }
 218
 219 /******************************************************************************/
 220 static inline
 221 void shiftkey(uint8_t *key){
 222         uint8_t k[7];
 223         memcpy(k, key, 7);
 224         permute((prog_uint8_t*)shiftkey_permtab, k, key);
 225 }
 226
 227 /******************************************************************************/
 228 static inline
 229 void shiftkey_inv(uint8_t *key){
 230         uint8_t k[7];
 231         memcpy(k, key, 7);
 232         permute((prog_uint8_t*)shiftkeyinv_permtab, k, key);
 233
 234 }
 235
 236 /******************************************************************************/
 237 static inline
 238 uint64_t splitin6bitwords(uint64_t a){
 239         uint64_t ret=0;
 240         a &= 0x0000ffffffffffffLL;
 241         permute((prog_uint8_t*)splitin6bitword_permtab, (uint8_t*)&a, (uint8_t*)&ret);
 242         return ret;
 243 }
 244
 245 /******************************************************************************/
 246
 247 static inline
 248 uint8_t substitute(uint8_t a, prog_uint8_t * sbp){
 249         uint8_t x;
 250         x = pgm_read_byte(&(sbp[a>>1]));
 251         x = (a&1)?x&0x0F:x>>4;
 252         return x;
 253
 254 }
 255
 256 /******************************************************************************/
 257
 258 uint32_t des_f(uint32_t r, uint8_t* kr){
 259         uint8_t i;
 260         uint32_t t=0,ret;
 261         uint64_t data;
 262         prog_uint8_t *sbp; /* sboxpointer */
 263         permute((prog_uint8_t*)e_permtab, (uint8_t*)&r, (uint8_t*)&data);
 264         for(i=0; i<7; ++i)
 265                 ((uint8_t*)&data)[i] ^= kr[i];
 266
 267         /* Sbox substitution */
 268         data = splitin6bitwords(data);
 269         sbp=(prog_uint8_t*)sbox;
 270         for(i=0; i<8; ++i){
 271                 uint8_t x;
 272                 x = substitute(((uint8_t*)&data)[i], sbp);
 273                 t<<=4;
 274                 t |= x;
 275                 sbp += 32;
 276         }
 277         changeendian32(&t);
 278
 279         permute((prog_uint8_t*)p_permtab,(uint8_t*)&t, (uint8_t*)&ret);
 280
 281         return ret;
 282 }
 283
 284 /******************************************************************************/
 285
 286 void des_encrypt(uint8_t* out, uint8_t* in, uint8_t* key){
 287 #define R *((uint32_t*)&(data[4]))
 288 #define L *((uint32_t*)&(data[0]))
 289
 290         uint8_t data[8],kr[6],k[7];
 291         uint8_t i;
 292
 293         permute((prog_uint8_t*)ip_permtab, in, data);
 294         permute((prog_uint8_t*)pc1_permtab, key, k);
 295         for(i=0; i<8; ++i){
 296                 shiftkey(k);
 297                 if(ROTTABLE&((1<<((i<<1)+0))) )
 298                         shiftkey(k);
 299                 permute((prog_uint8_t*)pc2_permtab, k, kr);
 300                 L ^= des_f(R, kr);
 301
 302                 shiftkey(k);
 303                 if(ROTTABLE&((1<<((i<<1)+1))) )
 304                         shiftkey(k);
 305                 permute((prog_uint8_t*)pc2_permtab, k, kr);
 306                 R ^= des_f(L, kr);
 307
 308         }
 309         /* L <-> R*/
 310         R ^= L;
 311         L ^= R;
 312         R ^= L;
 313
 314         permute((prog_uint8_t*)inv_ip_permtab, data, out);
 315 }
 316
 317 /******************************************************************************/
 318
 319 void des_decrypt(uint8_t* out, uint8_t* in, uint8_t* key){
 320 #define R *((uint32_t*)&(data[4]))
 321 #define L *((uint32_t*)&(data[0]))
 322
 323         uint8_t data[8],kr[6],k[7];
 324         int8_t i;
 325
 326         permute((prog_uint8_t*)ip_permtab, in, data);
 327         permute((prog_uint8_t*)pc1_permtab, key, k);
 328         for(i=7; i>=0; --i){
 329
 330                 permute((prog_uint8_t*)pc2_permtab, k, kr);
 331                 L ^= des_f(R, kr);
 332                 shiftkey_inv(k);
 333                 if(ROTTABLE&((1<<((i<<1)+1))) ){
 334                         shiftkey_inv(k);
 335                 }
 336
 337                 permute((prog_uint8_t*)pc2_permtab, k, kr);
 338                 R ^= des_f(L, kr);
 339                 shiftkey_inv(k);
 340                 if(ROTTABLE&((1<<((i<<1)+0))) ){
 341                         shiftkey_inv(k);
 342                 }
 343
 344         }
 345         /* L <-> R*/
 346         R ^= L;
 347         L ^= R;
 348         R ^= L;
 349
 350         permute((prog_uint8_t*)inv_ip_permtab, data, out);
 351 }
 352
 353 /******************************************************************************/
 354
 355 void tdes_encrypt(uint8_t* out, uint8_t* in, uint8_t* key){
 356         des_encrypt(out,  in, key + 0);
 357         des_decrypt(out, out, key + 8);
 358         des_encrypt(out, out, key +16);
 359 }
 360
 361 /******************************************************************************/
 362
 363 void tdes_decrypt(uint8_t* out, uint8_t* in, uint8_t* key){
 364         des_decrypt(out,  in, key + 0);
 365         des_encrypt(out, out, key + 8);
 366         des_decrypt(out, out, key +16);
 367 }
 368
 369 /******************************************************************************/
 370
 371