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
  31 const uint8_t sbox[256]  = {
  32   /* S-box 1 */
  33   0xE4, 0xD1, 0x2F, 0xB8, 0x3A, 0x6C, 0x59, 0x07,
  34   0x0F, 0x74, 0xE2, 0xD1, 0xA6, 0xCB, 0x95, 0x38,
  35   0x41, 0xE8, 0xD6, 0x2B, 0xFC, 0x97, 0x3A, 0x50,
  36   0xFC, 0x82, 0x49, 0x17, 0x5B, 0x3E, 0xA0, 0x6D,
  37   /* S-box 2 */
  38   0xF1, 0x8E, 0x6B, 0x34, 0x97, 0x2D, 0xC0, 0x5A,
  39   0x3D, 0x47, 0xF2, 0x8E, 0xC0, 0x1A, 0x69, 0xB5,
  40   0x0E, 0x7B, 0xA4, 0xD1, 0x58, 0xC6, 0x93, 0x2F,
  41   0xD8, 0xA1, 0x3F, 0x42, 0xB6, 0x7C, 0x05, 0xE9,
  42   /* S-box 3 */
  43   0xA0, 0x9E, 0x63, 0xF5, 0x1D, 0xC7, 0xB4, 0x28,
  44   0xD7, 0x09, 0x34, 0x6A, 0x28, 0x5E, 0xCB, 0xF1,
  45   0xD6, 0x49, 0x8F, 0x30, 0xB1, 0x2C, 0x5A, 0xE7,
  46   0x1A, 0xD0, 0x69, 0x87, 0x4F, 0xE3, 0xB5, 0x2C,
  47   /* S-box 4 */
  48   0x7D, 0xE3, 0x06, 0x9A, 0x12, 0x85, 0xBC, 0x4F,
  49   0xD8, 0xB5, 0x6F, 0x03, 0x47, 0x2C, 0x1A, 0xE9,
  50   0xA6, 0x90, 0xCB, 0x7D, 0xF1, 0x3E, 0x52, 0x84,
  51   0x3F, 0x06, 0xA1, 0xD8, 0x94, 0x5B, 0xC7, 0x2E,
  52   /* S-box 5 */
  53   0x2C, 0x41, 0x7A, 0xB6, 0x85, 0x3F, 0xD0, 0xE9,
  54   0xEB, 0x2C, 0x47, 0xD1, 0x50, 0xFA, 0x39, 0x86,
  55   0x42, 0x1B, 0xAD, 0x78, 0xF9, 0xC5, 0x63, 0x0E,
  56   0xB8, 0xC7, 0x1E, 0x2D, 0x6F, 0x09, 0xA4, 0x53,
  57   /* S-box 6 */
  58   0xC1, 0xAF, 0x92, 0x68, 0x0D, 0x34, 0xE7, 0x5B,
  59   0xAF, 0x42, 0x7C, 0x95, 0x61, 0xDE, 0x0B, 0x38,
  60   0x9E, 0xF5, 0x28, 0xC3, 0x70, 0x4A, 0x1D, 0xB6,
  61   0x43, 0x2C, 0x95, 0xFA, 0xBE, 0x17, 0x60, 0x8D,
  62   /* S-box 7 */
  63   0x4B, 0x2E, 0xF0, 0x8D, 0x3C, 0x97, 0x5A, 0x61,
  64   0xD0, 0xB7, 0x49, 0x1A, 0xE3, 0x5C, 0x2F, 0x86,
  65   0x14, 0xBD, 0xC3, 0x7E, 0xAF, 0x68, 0x05, 0x92,
  66   0x6B, 0xD8, 0x14, 0xA7, 0x95, 0x0F, 0xE2, 0x3C,
  67   /* S-box 8 */
  68   0xD2, 0x84, 0x6F, 0xB1, 0xA9, 0x3E, 0x50, 0xC7,
  69   0x1F, 0xD8, 0xA3, 0x74, 0xC5, 0x6B, 0x0E, 0x92,
  70   0x7B, 0x41, 0x9C, 0xE2, 0x06, 0xAD, 0xF3, 0x58,
  71   0x21, 0xE7, 0x4A, 0x8D, 0xFC, 0x90, 0x35, 0x6B
  72 };
  73
  74 const uint8_t e_permtab[] ={
  75          4,  6,                                         /* 4 bytes in 6 bytes out*/
  76         32,  1,  2,  3,  4,  5,
  77          4,  5,  6,  7,  8,  9,
  78          8,  9, 10, 11, 12, 13,
  79         12, 13, 14, 15, 16, 17,
  80         16, 17, 18, 19, 20, 21,
  81         20, 21, 22, 23, 24, 25,
  82         24, 25, 26, 27, 28, 29,
  83         28, 29, 30, 31, 32,  1
  84 };
  85
  86 const uint8_t p_permtab[] ={
  87          4,  4,                                         /* 32 bit -> 32 bit */
  88         16,  7, 20, 21,
  89         29, 12, 28, 17,
  90          1, 15, 23, 26,
  91          5, 18, 31, 10,
  92          2,  8, 24, 14,
  93         32, 27,  3,  9,
  94         19, 13, 30,  6,
  95         22, 11,  4, 25
  96 };
  97
  98 const uint8_t ip_permtab[] ={
  99          8,  8,                                         /* 64 bit -> 64 bit */
 100         58, 50, 42, 34, 26, 18, 10, 2,
 101         60, 52, 44, 36, 28, 20, 12, 4,
 102         62, 54, 46, 38, 30, 22, 14, 6,
 103         64, 56, 48, 40, 32, 24, 16, 8,
 104         57, 49, 41, 33, 25, 17,  9, 1,
 105         59, 51, 43, 35, 27, 19, 11, 3,
 106         61, 53, 45, 37, 29, 21, 13, 5,
 107         63, 55, 47, 39, 31, 23, 15, 7
 108 };
 109
 110 const uint8_t inv_ip_permtab[] ={
 111          8, 8,                                          /* 64 bit -> 64 bit */
 112         40, 8, 48, 16, 56, 24, 64, 32,
 113         39, 7, 47, 15, 55, 23, 63, 31,
 114         38, 6, 46, 14, 54, 22, 62, 30,
 115         37, 5, 45, 13, 53, 21, 61, 29,
 116         36, 4, 44, 12, 52, 20, 60, 28,
 117         35, 3, 43, 11, 51, 19, 59, 27,
 118         34, 2, 42, 10, 50, 18, 58, 26,
 119         33, 1, 41,  9, 49, 17, 57, 25
 120 };
 121
 122 const uint8_t pc1_permtab[] ={
 123          8,  7,                                         /* 64 bit -> 56 bit*/
 124         57, 49, 41, 33, 25, 17,  9,
 125          1, 58, 50, 42, 34, 26, 18,
 126         10,  2, 59, 51, 43, 35, 27,
 127         19, 11,  3, 60, 52, 44, 36,
 128         63, 55, 47, 39, 31, 23, 15,
 129          7, 62, 54, 46, 38, 30, 22,
 130         14,  6, 61, 53, 45, 37, 29,
 131         21, 13,  5, 28, 20, 12,  4
 132 };
 133
 134 const uint8_t pc2_permtab[] ={
 135          7,      6,                                     /* 56 bit -> 48 bit */
 136         14, 17, 11, 24,  1,  5,
 137          3, 28, 15,  6, 21, 10,
 138         23, 19, 12,  4, 26,  8,
 139         16,  7, 27, 20, 13,  2,
 140         41, 52, 31, 37, 47, 55,
 141         30, 40, 51, 45, 33, 48,
 142         44, 49, 39, 56, 34, 53,
 143         46, 42, 50, 36, 29, 32
 144 };
 145
 146 const uint8_t splitin6bitword_permtab[] = {
 147          8,  8,                                         /* 64 bit -> 64 bit */
 148         64, 64,  1,  6,  2,  3,  4,  5,
 149         64, 64,  7, 12,  8,  9, 10, 11,
 150         64, 64, 13, 18, 14, 15, 16, 17,
 151         64, 64, 19, 24, 20, 21, 22, 23,
 152         64, 64, 25, 30, 26, 27, 28, 29,
 153         64, 64, 31, 36, 32, 33, 34, 35,
 154         64, 64, 37, 42, 38, 39, 40, 41,
 155         64, 64, 43, 48, 44, 45, 46, 47
 156 };
 157
 158 const uint8_t shiftkey_permtab[] = {
 159          7,  7,                                         /* 56 bit -> 56 bit */
 160          2,  3,  4,  5,  6,  7,  8,  9,
 161         10, 11, 12, 13, 14, 15, 16, 17,
 162         18, 19, 20, 21, 22, 23, 24, 25,
 163         26, 27, 28,  1,
 164         30, 31, 32, 33, 34, 35, 36, 37,
 165         38, 39, 40, 41, 42, 43, 44, 45,
 166         46, 47, 48, 49, 50, 51, 52, 53,
 167         54, 55, 56, 29
 168 };
 169
 170 const uint8_t shiftkeyinv_permtab[] = {
 171          7,  7,
 172         28,  1,  2,  3,  4,  5,  6,  7,
 173          8,  9, 10, 11, 12, 13, 14, 15,
 174         16, 17, 18, 19, 20, 21, 22, 23,
 175         24, 25, 26, 27,
 176         56, 29, 30, 31, 32, 33, 34, 35,
 177         36, 37, 38, 39, 40, 41, 42, 43,
 178         44, 45, 46, 47, 48, 49, 50, 51,
 179         52, 53, 54, 55
 180 };
 181
 182 /*
 183 1 0
 184 1 0
 185 2 1
 186 2 1
 187 2 1
 188 2 1
 189 2 1
 190 2 1
 191 ----
 192 1 0
 193 2 1
 194 2 1
 195 2 1
 196 2 1
 197 2 1
 198 2 1
 199 1 0
 200 */
 201 #define ROTTABLE      0x7EFC
 202 #define ROTTABLE_INV  0x3F7E
 203 /******************************************************************************/
 204
 205 void permute(uint8_t *ptable, const uint8_t *in, uint8_t *out){
 206         uint8_t ib, ob; /* in-bytes and out-bytes */
 207         uint8_t byte, bit; /* counter for bit and byte */
 208         ib = ptable[0];
 209         ob = 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=*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 = 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 *((uint32_t*)&(data[4]))
 302 #define L *((uint32_t*)&(data[0]))
 303
 304         uint8_t data[8],kr[6],k[7];
 305         uint8_t i;
 306
 307         permute((uint8_t*)ip_permtab, (uint8_t*)in, data);
 308         permute((uint8_t*)pc1_permtab, (const uint8_t*)key, k);
 309         for(i=0; i<8; ++i){
 310                 shiftkey(k);
 311                 if(ROTTABLE&((1<<((i<<1)+0))) )
 312                         shiftkey(k);
 313                 permute((uint8_t*)pc2_permtab, k, kr);
 314                 L ^= des_f(R, kr);
 315
 316                 shiftkey(k);
 317                 if(ROTTABLE&((1<<((i<<1)+1))) )
 318                         shiftkey(k);
 319                 permute((uint8_t*)pc2_permtab, k, kr);
 320                 R ^= des_f(L, kr);
 321
 322         }
 323         /* L <-> R*/
 324         R ^= L;
 325         L ^= R;
 326         R ^= L;
 327
 328         permute((uint8_t*)inv_ip_permtab, data, (uint8_t*)out);
 329 }
 330
 331 /******************************************************************************/
 332
 333 void des_dec(void* out, const void* in, const uint8_t* key){
 334 #define R *((uint32_t*)&(data[4]))
 335 #define L *((uint32_t*)&(data[0]))
 336
 337         uint8_t data[8],kr[6],k[7];
 338         int8_t i;
 339         permute((uint8_t*)ip_permtab, (uint8_t*)in, data);
 340         permute((uint8_t*)pc1_permtab, (const uint8_t*)key, k);
 341         for(i=7; i>=0; --i){
 342
 343                 permute((uint8_t*)pc2_permtab, k, kr);
 344                 L ^= des_f(R, kr);
 345                 shiftkey_inv(k);
 346                 if(ROTTABLE&((1<<((i<<1)+1))) ){
 347                         shiftkey_inv(k);
 348                 }
 349
 350                 permute((uint8_t*)pc2_permtab, k, kr);
 351                 R ^= des_f(L, kr);
 352                 shiftkey_inv(k);
 353                 if(ROTTABLE&((1<<((i<<1)+0))) ){
 354                         shiftkey_inv(k);
 355                 }
 356
 357         }
 358         /* L <-> R*/
 359         R ^= L;
 360         L ^= R;
 361         R ^= L;
 362
 363         permute((uint8_t*)inv_ip_permtab, data, (uint8_t*)out);
 364 }
 365
 366 /******************************************************************************/
 367
 368 void tdes_enc(void* out, void* in, const void* key){
 369         des_enc(out,  in, (uint8_t*)key + 0);
 370         des_dec(out, out, (uint8_t*)key + 8);
 371         des_enc(out, out, (uint8_t*)key +16);
 372 }
 373
 374 /******************************************************************************/
 375
 376 void tdes_dec(void* out, void* in, const uint8_t* key){
 377         des_dec(out,  in, (uint8_t*)key +16);
 378         des_enc(out, out, (uint8_t*)key + 8);
 379         des_dec(out, out, (uint8_t*)key + 0);
 380 }
 381
 382 /******************************************************************************/
 383
 384