des/des.c

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