des.c

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