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