lib/des.c

   1 /* des.c --- DES and Triple-DES encryption/decryption Algorithm
   2  * Copyright (C) 1998, 1999, 2001, 2002, 2003, 2004, 2005
   3  *    Free Software Foundation, Inc.
   4  *
   5  * This file is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published
   7  * by the Free Software Foundation; either version 2, or (at your
   8  * option) any later version.
   9  *
  10  * This file is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this file; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  18  * 02110-1301, USA.
  19  *
  20  */
  21
  22 /* Adapted for gnulib by Simon Josefsson, based on Libgcrypt. */
  23
  24 /*
  25  * For a description of triple encryption, see:
  26  *   Bruce Schneier: Applied Cryptography. Second Edition.
  27  *   John Wiley & Sons, 1996. ISBN 0-471-12845-7. Pages 358 ff.
  28  * This implementation is according to the definition of DES in FIPS
  29  * PUB 46-2 from December 1993.
  30  *
  31  * Written by Michael Roth <mroth@nessie.de>, September 1998
  32  */
  33
  34 /*
  35  *  U S A G E
  36  * ===========
  37  *
  38  * For DES or Triple-DES encryption/decryption you must initialize a proper
  39  * encryption context with a key.
  40  *
  41  * A DES key is 64bit wide but only 56bits of the key are used. The remaining
  42  * bits are parity bits and they will _not_ checked in this implementation, but
  43  * simply ignored.
  44  *
  45  * For Triple-DES you could use either two 64bit keys or three 64bit keys.
  46  * The parity bits will _not_ checked, too.
  47  *
  48  * After initializing a context with a key you could use this context to
  49  * encrypt or decrypt data in 64bit blocks in Electronic Codebook Mode.
  50  *
  51  * DES Example
  52  * -----------
  53  *     unsigned char key[8];
  54  *     unsigned char plaintext[8];
  55  *     unsigned char ciphertext[8];
  56  *     unsigned char recoverd[8];
  57  *     des_ctx context;
  58  *
  59  *     // Fill 'key' and 'plaintext' with some data
  60  *     ....
  61  *
  62  *     // Set up the DES encryption context
  63  *     des_setkey(&context, key);
  64  *
  65  *     // Encrypt the plaintext
  66  *     des_ecb_encrypt(&context, plaintext, ciphertext);
  67  *
  68  *     // To recover the orginal plaintext from ciphertext use:
  69  *     des_ecb_decrypt(&context, ciphertext, recoverd);
  70  *
  71  *
  72  * Triple-DES Example
  73  * ------------------
  74  *     unsigned char key1[8];
  75  *     unsigned char key2[8];
  76  *     unsigned char key3[8];
  77  *     unsigned char plaintext[8];
  78  *     unsigned char ciphertext[8];
  79  *     unsigned char recoverd[8];
  80  *     tripledes_ctx context;
  81  *
  82  *     // If you would like to use two 64bit keys, fill 'key1' and'key2'
  83  *     // then setup the encryption context:
  84  *     tripledes_set2keys(&context, key1, key2);
  85  *
  86  *     // To use three 64bit keys with Triple-DES use:
  87  *     tripledes_set3keys(&context, key1, key2, key3);
  88  *
  89  *     // Encrypting plaintext with Triple-DES
  90  *     tripledes_ecb_encrypt(&context, plaintext, ciphertext);
  91  *
  92  *     // Decrypting ciphertext to recover the plaintext with Triple-DES
  93  *     tripledes_ecb_decrypt(&context, ciphertext, recoverd);
  94  */
  95
  96
  97 #ifdef HAVE_CONFIG_H
  98 # include <config.h>
  99 #endif
 100
 101 #include "des.h"
 102
 103 #include <stdio.h>
 104 #include <string.h>             /* memcpy, memcmp */
 105
 106 /*
 107  * The s-box values are permuted according to the 'primitive function P'
 108  * and are rotated one bit to the left.
 109  */
 110 static const uint32_t sbox1[64] = {
 111   0x01010400, 0x00000000, 0x00010000, 0x01010404, 0x01010004, 0x00010404,
 112   0x00000004, 0x00010000, 0x00000400, 0x01010400, 0x01010404, 0x00000400,
 113   0x01000404, 0x01010004, 0x01000000, 0x00000004, 0x00000404, 0x01000400,
 114   0x01000400, 0x00010400, 0x00010400, 0x01010000, 0x01010000, 0x01000404,
 115   0x00010004, 0x01000004, 0x01000004, 0x00010004, 0x00000000, 0x00000404,
 116   0x00010404, 0x01000000, 0x00010000, 0x01010404, 0x00000004, 0x01010000,
 117   0x01010400, 0x01000000, 0x01000000, 0x00000400, 0x01010004, 0x00010000,
 118   0x00010400, 0x01000004, 0x00000400, 0x00000004, 0x01000404, 0x00010404,
 119   0x01010404, 0x00010004, 0x01010000, 0x01000404, 0x01000004, 0x00000404,
 120   0x00010404, 0x01010400, 0x00000404, 0x01000400, 0x01000400, 0x00000000,
 121   0x00010004, 0x00010400, 0x00000000, 0x01010004
 122 };
 123
 124 static const uint32_t sbox2[64] = {
 125   0x80108020, 0x80008000, 0x00008000, 0x00108020, 0x00100000, 0x00000020,
 126   0x80100020, 0x80008020, 0x80000020, 0x80108020, 0x80108000, 0x80000000,
 127   0x80008000, 0x00100000, 0x00000020, 0x80100020, 0x00108000, 0x00100020,
 128   0x80008020, 0x00000000, 0x80000000, 0x00008000, 0x00108020, 0x80100000,
 129   0x00100020, 0x80000020, 0x00000000, 0x00108000, 0x00008020, 0x80108000,
 130   0x80100000, 0x00008020, 0x00000000, 0x00108020, 0x80100020, 0x00100000,
 131   0x80008020, 0x80100000, 0x80108000, 0x00008000, 0x80100000, 0x80008000,
 132   0x00000020, 0x80108020, 0x00108020, 0x00000020, 0x00008000, 0x80000000,
 133   0x00008020, 0x80108000, 0x00100000, 0x80000020, 0x00100020, 0x80008020,
 134   0x80000020, 0x00100020, 0x00108000, 0x00000000, 0x80008000, 0x00008020,
 135   0x80000000, 0x80100020, 0x80108020, 0x00108000
 136 };
 137
 138 static const uint32_t sbox3[64] = {
 139   0x00000208, 0x08020200, 0x00000000, 0x08020008, 0x08000200, 0x00000000,
 140   0x00020208, 0x08000200, 0x00020008, 0x08000008, 0x08000008, 0x00020000,
 141   0x08020208, 0x00020008, 0x08020000, 0x00000208, 0x08000000, 0x00000008,
 142   0x08020200, 0x00000200, 0x00020200, 0x08020000, 0x08020008, 0x00020208,
 143   0x08000208, 0x00020200, 0x00020000, 0x08000208, 0x00000008, 0x08020208,
 144   0x00000200, 0x08000000, 0x08020200, 0x08000000, 0x00020008, 0x00000208,
 145   0x00020000, 0x08020200, 0x08000200, 0x00000000, 0x00000200, 0x00020008,
 146   0x08020208, 0x08000200, 0x08000008, 0x00000200, 0x00000000, 0x08020008,
 147   0x08000208, 0x00020000, 0x08000000, 0x08020208, 0x00000008, 0x00020208,
 148   0x00020200, 0x08000008, 0x08020000, 0x08000208, 0x00000208, 0x08020000,
 149   0x00020208, 0x00000008, 0x08020008, 0x00020200
 150 };
 151
 152 static const uint32_t sbox4[64] = {
 153   0x00802001, 0x00002081, 0x00002081, 0x00000080, 0x00802080, 0x00800081,
 154   0x00800001, 0x00002001, 0x00000000, 0x00802000, 0x00802000, 0x00802081,
 155   0x00000081, 0x00000000, 0x00800080, 0x00800001, 0x00000001, 0x00002000,
 156   0x00800000, 0x00802001, 0x00000080, 0x00800000, 0x00002001, 0x00002080,
 157   0x00800081, 0x00000001, 0x00002080, 0x00800080, 0x00002000, 0x00802080,
 158   0x00802081, 0x00000081, 0x00800080, 0x00800001, 0x00802000, 0x00802081,
 159   0x00000081, 0x00000000, 0x00000000, 0x00802000, 0x00002080, 0x00800080,
 160   0x00800081, 0x00000001, 0x00802001, 0x00002081, 0x00002081, 0x00000080,
 161   0x00802081, 0x00000081, 0x00000001, 0x00002000, 0x00800001, 0x00002001,
 162   0x00802080, 0x00800081, 0x00002001, 0x00002080, 0x00800000, 0x00802001,
 163   0x00000080, 0x00800000, 0x00002000, 0x00802080
 164 };
 165
 166 static const uint32_t sbox5[64] = {
 167   0x00000100, 0x02080100, 0x02080000, 0x42000100, 0x00080000, 0x00000100,
 168   0x40000000, 0x02080000, 0x40080100, 0x00080000, 0x02000100, 0x40080100,
 169   0x42000100, 0x42080000, 0x00080100, 0x40000000, 0x02000000, 0x40080000,
 170   0x40080000, 0x00000000, 0x40000100, 0x42080100, 0x42080100, 0x02000100,
 171   0x42080000, 0x40000100, 0x00000000, 0x42000000, 0x02080100, 0x02000000,
 172   0x42000000, 0x00080100, 0x00080000, 0x42000100, 0x00000100, 0x02000000,
 173   0x40000000, 0x02080000, 0x42000100, 0x40080100, 0x02000100, 0x40000000,
 174   0x42080000, 0x02080100, 0x40080100, 0x00000100, 0x02000000, 0x42080000,
 175   0x42080100, 0x00080100, 0x42000000, 0x42080100, 0x02080000, 0x00000000,
 176   0x40080000, 0x42000000, 0x00080100, 0x02000100, 0x40000100, 0x00080000,
 177   0x00000000, 0x40080000, 0x02080100, 0x40000100
 178 };
 179
 180 static const uint32_t sbox6[64] = {
 181   0x20000010, 0x20400000, 0x00004000, 0x20404010, 0x20400000, 0x00000010,
 182   0x20404010, 0x00400000, 0x20004000, 0x00404010, 0x00400000, 0x20000010,
 183   0x00400010, 0x20004000, 0x20000000, 0x00004010, 0x00000000, 0x00400010,
 184   0x20004010, 0x00004000, 0x00404000, 0x20004010, 0x00000010, 0x20400010,
 185   0x20400010, 0x00000000, 0x00404010, 0x20404000, 0x00004010, 0x00404000,
 186   0x20404000, 0x20000000, 0x20004000, 0x00000010, 0x20400010, 0x00404000,
 187   0x20404010, 0x00400000, 0x00004010, 0x20000010, 0x00400000, 0x20004000,
 188   0x20000000, 0x00004010, 0x20000010, 0x20404010, 0x00404000, 0x20400000,
 189   0x00404010, 0x20404000, 0x00000000, 0x20400010, 0x00000010, 0x00004000,
 190   0x20400000, 0x00404010, 0x00004000, 0x00400010, 0x20004010, 0x00000000,
 191   0x20404000, 0x20000000, 0x00400010, 0x20004010
 192 };
 193
 194 static const uint32_t sbox7[64] = {
 195   0x00200000, 0x04200002, 0x04000802, 0x00000000, 0x00000800, 0x04000802,
 196   0x00200802, 0x04200800, 0x04200802, 0x00200000, 0x00000000, 0x04000002,
 197   0x00000002, 0x04000000, 0x04200002, 0x00000802, 0x04000800, 0x00200802,
 198   0x00200002, 0x04000800, 0x04000002, 0x04200000, 0x04200800, 0x00200002,
 199   0x04200000, 0x00000800, 0x00000802, 0x04200802, 0x00200800, 0x00000002,
 200   0x04000000, 0x00200800, 0x04000000, 0x00200800, 0x00200000, 0x04000802,
 201   0x04000802, 0x04200002, 0x04200002, 0x00000002, 0x00200002, 0x04000000,
 202   0x04000800, 0x00200000, 0x04200800, 0x00000802, 0x00200802, 0x04200800,
 203   0x00000802, 0x04000002, 0x04200802, 0x04200000, 0x00200800, 0x00000000,
 204   0x00000002, 0x04200802, 0x00000000, 0x00200802, 0x04200000, 0x00000800,
 205   0x04000002, 0x04000800, 0x00000800, 0x00200002
 206 };
 207
 208 static const uint32_t sbox8[64] = {
 209   0x10001040, 0x00001000, 0x00040000, 0x10041040, 0x10000000, 0x10001040,
 210   0x00000040, 0x10000000, 0x00040040, 0x10040000, 0x10041040, 0x00041000,
 211   0x10041000, 0x00041040, 0x00001000, 0x00000040, 0x10040000, 0x10000040,
 212   0x10001000, 0x00001040, 0x00041000, 0x00040040, 0x10040040, 0x10041000,
 213   0x00001040, 0x00000000, 0x00000000, 0x10040040, 0x10000040, 0x10001000,
 214   0x00041040, 0x00040000, 0x00041040, 0x00040000, 0x10041000, 0x00001000,
 215   0x00000040, 0x10040040, 0x00001000, 0x00041040, 0x10001000, 0x00000040,
 216   0x10000040, 0x10040000, 0x10040040, 0x10000000, 0x00040000, 0x10001040,
 217   0x00000000, 0x10041040, 0x00040040, 0x10000040, 0x10040000, 0x10001000,
 218   0x10001040, 0x00000000, 0x10041040, 0x00041000, 0x00041000, 0x00001040,
 219   0x00001040, 0x00040040, 0x10000000, 0x10041000
 220 };
 221
 222 /*
 223  * These two tables are part of the 'permuted choice 1' function.
 224  * In this implementation several speed improvements are done.
 225  */
 226 static const uint32_t leftkey_swap[16] = {
 227   0x00000000, 0x00000001, 0x00000100, 0x00000101,
 228   0x00010000, 0x00010001, 0x00010100, 0x00010101,
 229   0x01000000, 0x01000001, 0x01000100, 0x01000101,
 230   0x01010000, 0x01010001, 0x01010100, 0x01010101
 231 };
 232
 233 static const uint32_t rightkey_swap[16] = {
 234   0x00000000, 0x01000000, 0x00010000, 0x01010000,
 235   0x00000100, 0x01000100, 0x00010100, 0x01010100,
 236   0x00000001, 0x01000001, 0x00010001, 0x01010001,
 237   0x00000101, 0x01000101, 0x00010101, 0x01010101,
 238 };
 239
 240 /*
 241  * Numbers of left shifts per round for encryption subkeys.  To
 242  * calculate the decryption subkeys we just reverse the ordering of
 243  * the calculated encryption subkeys, so there is no need for a
 244  * decryption rotate tab.
 245  */
 246 static const unsigned char encrypt_rotate_tab[16] = {
 247   1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
 248 };
 249
 250 /*
 251  * Table with weak DES keys sorted in ascending order.  In DES there
 252  * are 64 known keys which are weak. They are weak because they
 253  * produce only one, two or four different subkeys in the subkey
 254  * scheduling process.  The keys in this table have all their parity
 255  * bits cleared.
 256  */
 257 static const unsigned char weak_keys[64][8] = {
 258   {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00},     /*w */
 259   {0x00, 0x00, 0x1e, 0x1e, 0x00, 0x00, 0x0e, 0x0e},
 260   {0x00, 0x00, 0xe0, 0xe0, 0x00, 0x00, 0xf0, 0xf0},
 261   {0x00, 0x00, 0xfe, 0xfe, 0x00, 0x00, 0xfe, 0xfe},
 262   {0x00, 0x1e, 0x00, 0x1e, 0x00, 0x0e, 0x00, 0x0e},     /*sw */
 263   {0x00, 0x1e, 0x1e, 0x00, 0x00, 0x0e, 0x0e, 0x00},
 264   {0x00, 0x1e, 0xe0, 0xfe, 0x00, 0x0e, 0xf0, 0xfe},
 265   {0x00, 0x1e, 0xfe, 0xe0, 0x00, 0x0e, 0xfe, 0xf0},
 266   {0x00, 0xe0, 0x00, 0xe0, 0x00, 0xf0, 0x00, 0xf0},     /*sw */
 267   {0x00, 0xe0, 0x1e, 0xfe, 0x00, 0xf0, 0x0e, 0xfe},
 268   {0x00, 0xe0, 0xe0, 0x00, 0x00, 0xf0, 0xf0, 0x00},
 269   {0x00, 0xe0, 0xfe, 0x1e, 0x00, 0xf0, 0xfe, 0x0e},
 270   {0x00, 0xfe, 0x00, 0xfe, 0x00, 0xfe, 0x00, 0xfe},     /*sw */
 271   {0x00, 0xfe, 0x1e, 0xe0, 0x00, 0xfe, 0x0e, 0xf0},
 272   {0x00, 0xfe, 0xe0, 0x1e, 0x00, 0xfe, 0xf0, 0x0e},
 273   {0x00, 0xfe, 0xfe, 0x00, 0x00, 0xfe, 0xfe, 0x00},
 274   {0x1e, 0x00, 0x00, 0x1e, 0x0e, 0x00, 0x00, 0x0e},
 275   {0x1e, 0x00, 0x1e, 0x00, 0x0e, 0x00, 0x0e, 0x00},     /*sw */
 276   {0x1e, 0x00, 0xe0, 0xfe, 0x0e, 0x00, 0xf0, 0xfe},
 277   {0x1e, 0x00, 0xfe, 0xe0, 0x0e, 0x00, 0xfe, 0xf0},
 278   {0x1e, 0x1e, 0x00, 0x00, 0x0e, 0x0e, 0x00, 0x00},
 279   {0x1e, 0x1e, 0x1e, 0x1e, 0x0e, 0x0e, 0x0e, 0x0e},     /*w */
 280   {0x1e, 0x1e, 0xe0, 0xe0, 0x0e, 0x0e, 0xf0, 0xf0},
 281   {0x1e, 0x1e, 0xfe, 0xfe, 0x0e, 0x0e, 0xfe, 0xfe},
 282   {0x1e, 0xe0, 0x00, 0xfe, 0x0e, 0xf0, 0x00, 0xfe},
 283   {0x1e, 0xe0, 0x1e, 0xe0, 0x0e, 0xf0, 0x0e, 0xf0},     /*sw */
 284   {0x1e, 0xe0, 0xe0, 0x1e, 0x0e, 0xf0, 0xf0, 0x0e},
 285   {0x1e, 0xe0, 0xfe, 0x00, 0x0e, 0xf0, 0xfe, 0x00},
 286   {0x1e, 0xfe, 0x00, 0xe0, 0x0e, 0xfe, 0x00, 0xf0},
 287   {0x1e, 0xfe, 0x1e, 0xfe, 0x0e, 0xfe, 0x0e, 0xfe},     /*sw */
 288   {0x1e, 0xfe, 0xe0, 0x00, 0x0e, 0xfe, 0xf0, 0x00},
 289   {0x1e, 0xfe, 0xfe, 0x1e, 0x0e, 0xfe, 0xfe, 0x0e},
 290   {0xe0, 0x00, 0x00, 0xe0, 0xf0, 0x00, 0x00, 0xf0},
 291   {0xe0, 0x00, 0x1e, 0xfe, 0xf0, 0x00, 0x0e, 0xfe},
 292   {0xe0, 0x00, 0xe0, 0x00, 0xf0, 0x00, 0xf0, 0x00},     /*sw */
 293   {0xe0, 0x00, 0xfe, 0x1e, 0xf0, 0x00, 0xfe, 0x0e},
 294   {0xe0, 0x1e, 0x00, 0xfe, 0xf0, 0x0e, 0x00, 0xfe},
 295   {0xe0, 0x1e, 0x1e, 0xe0, 0xf0, 0x0e, 0x0e, 0xf0},
 296   {0xe0, 0x1e, 0xe0, 0x1e, 0xf0, 0x0e, 0xf0, 0x0e},     /*sw */
 297   {0xe0, 0x1e, 0xfe, 0x00, 0xf0, 0x0e, 0xfe, 0x00},
 298   {0xe0, 0xe0, 0x00, 0x00, 0xf0, 0xf0, 0x00, 0x00},
 299   {0xe0, 0xe0, 0x1e, 0x1e, 0xf0, 0xf0, 0x0e, 0x0e},
 300   {0xe0, 0xe0, 0xe0, 0xe0, 0xf0, 0xf0, 0xf0, 0xf0},     /*w */
 301   {0xe0, 0xe0, 0xfe, 0xfe, 0xf0, 0xf0, 0xfe, 0xfe},
 302   {0xe0, 0xfe, 0x00, 0x1e, 0xf0, 0xfe, 0x00, 0x0e},
 303   {0xe0, 0xfe, 0x1e, 0x00, 0xf0, 0xfe, 0x0e, 0x00},
 304   {0xe0, 0xfe, 0xe0, 0xfe, 0xf0, 0xfe, 0xf0, 0xfe},     /*sw */
 305   {0xe0, 0xfe, 0xfe, 0xe0, 0xf0, 0xfe, 0xfe, 0xf0},
 306   {0xfe, 0x00, 0x00, 0xfe, 0xfe, 0x00, 0x00, 0xfe},
 307   {0xfe, 0x00, 0x1e, 0xe0, 0xfe, 0x00, 0x0e, 0xf0},
 308   {0xfe, 0x00, 0xe0, 0x1e, 0xfe, 0x00, 0xf0, 0x0e},
 309   {0xfe, 0x00, 0xfe, 0x00, 0xfe, 0x00, 0xfe, 0x00},     /*sw */
 310   {0xfe, 0x1e, 0x00, 0xe0, 0xfe, 0x0e, 0x00, 0xf0},
 311   {0xfe, 0x1e, 0x1e, 0xfe, 0xfe, 0x0e, 0x0e, 0xfe},
 312   {0xfe, 0x1e, 0xe0, 0x00, 0xfe, 0x0e, 0xf0, 0x00},
 313   {0xfe, 0x1e, 0xfe, 0x1e, 0xfe, 0x0e, 0xfe, 0x0e},     /*sw */
 314   {0xfe, 0xe0, 0x00, 0x1e, 0xfe, 0xf0, 0x00, 0x0e},
 315   {0xfe, 0xe0, 0x1e, 0x00, 0xfe, 0xf0, 0x0e, 0x00},
 316   {0xfe, 0xe0, 0xe0, 0xfe, 0xfe, 0xf0, 0xf0, 0xfe},
 317   {0xfe, 0xe0, 0xfe, 0xe0, 0xfe, 0xf0, 0xfe, 0xf0},     /*sw */
 318   {0xfe, 0xfe, 0x00, 0x00, 0xfe, 0xfe, 0x00, 0x00},
 319   {0xfe, 0xfe, 0x1e, 0x1e, 0xfe, 0xfe, 0x0e, 0x0e},
 320   {0xfe, 0xfe, 0xe0, 0xe0, 0xfe, 0xfe, 0xf0, 0xf0},
 321   {0xfe, 0xfe, 0xfe, 0xfe, 0xfe, 0xfe, 0xfe, 0xfe}      /*w */
 322 };
 323 static const unsigned char weak_keys_chksum[20] = {
 324   0xD0, 0xCF, 0x07, 0x38, 0x93, 0x70, 0x8A, 0x83, 0x7D, 0xD7,
 325   0x8A, 0x36, 0x65, 0x29, 0x6C, 0x1F, 0x7C, 0x3F, 0xD3, 0x41
 326 };
 327
 328 bool
 329 des_is_weak_key (const char * key)
 330 {
 331   char work[8];
 332   int i, left, right, middle, cmp_result;
 333
 334   /* clear parity bits */
 335   for (i = 0; i < 8; ++i)
 336     work[i] = ((unsigned char)key[i]) & 0xfe;
 337
 338   /* binary search in the weak key table */
 339   left = 0;
 340   right = 63;
 341   while (left <= right)
 342     {
 343       middle = (left + right) / 2;
 344
 345       if (!(cmp_result = memcmp (work, weak_keys[middle], 8)))
 346         return -1;
 347
 348       if (cmp_result > 0)
 349         left = middle + 1;
 350       else
 351         right = middle - 1;
 352     }
 353
 354   return 0;
 355 }
 356
 357 /*
 358  * Macro to swap bits across two words.
 359  */
 360 #define DO_PERMUTATION(a, temp, b, offset, mask)        \
 361     temp = ((a>>offset) ^ b) & mask;                    \
 362     b ^= temp;                                          \
 363     a ^= temp<<offset;
 364
 365
 366 /*
 367  * This performs the 'initial permutation' of the data to be encrypted
 368  * or decrypted. Additionally the resulting two words are rotated one bit
 369  * to the left.
 370  */
 371 #define INITIAL_PERMUTATION(left, temp, right)          \
 372     DO_PERMUTATION(left, temp, right, 4, 0x0f0f0f0f)    \
 373     DO_PERMUTATION(left, temp, right, 16, 0x0000ffff)   \
 374     DO_PERMUTATION(right, temp, left, 2, 0x33333333)    \
 375     DO_PERMUTATION(right, temp, left, 8, 0x00ff00ff)    \
 376     right =  (right << 1) | (right >> 31);              \
 377     temp  =  (left ^ right) & 0xaaaaaaaa;               \
 378     right ^= temp;                                      \
 379     left  ^= temp;                                      \
 380     left  =  (left << 1) | (left >> 31);
 381
 382 /*
 383  * The 'inverse initial permutation'.
 384  */
 385 #define FINAL_PERMUTATION(left, temp, right)            \
 386     left  =  (left << 31) | (left >> 1);                \
 387     temp  =  (left ^ right) & 0xaaaaaaaa;               \
 388     left  ^= temp;                                      \
 389     right ^= temp;                                      \
 390     right  =  (right << 31) | (right >> 1);             \
 391     DO_PERMUTATION(right, temp, left, 8, 0x00ff00ff)    \
 392     DO_PERMUTATION(right, temp, left, 2, 0x33333333)    \
 393     DO_PERMUTATION(left, temp, right, 16, 0x0000ffff)   \
 394     DO_PERMUTATION(left, temp, right, 4, 0x0f0f0f0f)
 395
 396
 397 /*
 398  * A full DES round including 'expansion function', 'sbox substitution'
 399  * and 'primitive function P' but without swapping the left and right word.
 400  * Please note: The data in 'from' and 'to' is already rotated one bit to
 401  * the left, done in the initial permutation.
 402  */
 403 #define DES_ROUND(from, to, work, subkey)               \
 404     work = from ^ *subkey++;                            \
 405     to ^= sbox8[  work      & 0x3f ];                   \
 406     to ^= sbox6[ (work>>8)  & 0x3f ];                   \
 407     to ^= sbox4[ (work>>16) & 0x3f ];                   \
 408     to ^= sbox2[ (work>>24) & 0x3f ];                   \
 409     work = ((from << 28) | (from >> 4)) ^ *subkey++;    \
 410     to ^= sbox7[  work      & 0x3f ];                   \
 411     to ^= sbox5[ (work>>8)  & 0x3f ];                   \
 412     to ^= sbox3[ (work>>16) & 0x3f ];                   \
 413     to ^= sbox1[ (work>>24) & 0x3f ];
 414
 415 /*
 416  * Macros to convert 8 bytes from/to 32bit words.
 417  */
 418 #define READ_64BIT_DATA(data, left, right)                                 \
 419     left  = (data[0] << 24) | (data[1] << 16) | (data[2] << 8) | data[3];  \
 420     right = (data[4] << 24) | (data[5] << 16) | (data[6] << 8) | data[7];
 421
 422 #define WRITE_64BIT_DATA(data, left, right)                                \
 423     data[0] = (left >> 24) &0xff; data[1] = (left >> 16) &0xff;            \
 424     data[2] = (left >> 8) &0xff; data[3] = left &0xff;                     \
 425     data[4] = (right >> 24) &0xff; data[5] = (right >> 16) &0xff;          \
 426     data[6] = (right >> 8) &0xff; data[7] = right &0xff;
 427
 428 /*
 429  * Handy macros for encryption and decryption of data
 430  */
 431 #define des_ecb_encrypt(ctx, from, to)        des_ecb_crypt(ctx, from, to, 0)
 432 #define des_ecb_decrypt(ctx, from, to)        des_ecb_crypt(ctx, from, to, 1)
 433 #define tripledes_ecb_encrypt(ctx, from, to) tripledes_ecb_crypt(ctx,from,to,0)
 434 #define tripledes_ecb_decrypt(ctx, from, to) tripledes_ecb_crypt(ctx,from,to,1)
 435
 436 /*
 437  * des_key_schedule():    Calculate 16 subkeys pairs (even/odd) for
 438  *                        16 encryption rounds.
 439  *                        To calculate subkeys for decryption the caller
 440  *                        have to reorder the generated subkeys.
 441  *
 442  *    rawkey:       8 Bytes of key data
 443  *    subkey:       Array of at least 32 uint32_ts. Will be filled
 444  *                  with calculated subkeys.
 445  *
 446  */
 447 static void
 448 des_key_schedule (const char * _rawkey, uint32_t * subkey)
 449 {
 450   const unsigned char *rawkey = _rawkey;
 451   uint32_t left, right, work;
 452   int round;
 453
 454   READ_64BIT_DATA (rawkey, left, right)
 455     DO_PERMUTATION (right, work, left, 4, 0x0f0f0f0f)
 456     DO_PERMUTATION (right, work, left, 0, 0x10101010)
 457     left = ((leftkey_swap[(left >> 0) & 0xf] << 3)
 458             | (leftkey_swap[(left >> 8) & 0xf] << 2)
 459             | (leftkey_swap[(left >> 16) & 0xf] << 1)
 460             | (leftkey_swap[(left >> 24) & 0xf])
 461             | (leftkey_swap[(left >> 5) & 0xf] << 7)
 462             | (leftkey_swap[(left >> 13) & 0xf] << 6)
 463             | (leftkey_swap[(left >> 21) & 0xf] << 5)
 464             | (leftkey_swap[(left >> 29) & 0xf] << 4));
 465
 466   left &= 0x0fffffff;
 467
 468   right = ((rightkey_swap[(right >> 1) & 0xf] << 3)
 469            | (rightkey_swap[(right >> 9) & 0xf] << 2)
 470            | (rightkey_swap[(right >> 17) & 0xf] << 1)
 471            | (rightkey_swap[(right >> 25) & 0xf])
 472            | (rightkey_swap[(right >> 4) & 0xf] << 7)
 473            | (rightkey_swap[(right >> 12) & 0xf] << 6)
 474            | (rightkey_swap[(right >> 20) & 0xf] << 5)
 475            | (rightkey_swap[(right >> 28) & 0xf] << 4));
 476
 477   right &= 0x0fffffff;
 478
 479   for (round = 0; round < 16; ++round)
 480     {
 481       left = ((left << encrypt_rotate_tab[round])
 482               | (left >> (28 - encrypt_rotate_tab[round]))) & 0x0fffffff;
 483       right = ((right << encrypt_rotate_tab[round])
 484                | (right >> (28 - encrypt_rotate_tab[round]))) & 0x0fffffff;
 485
 486       *subkey++ = (((left << 4) & 0x24000000)
 487                    | ((left << 28) & 0x10000000)
 488                    | ((left << 14) & 0x08000000)
 489                    | ((left << 18) & 0x02080000)
 490                    | ((left << 6) & 0x01000000)
 491                    | ((left << 9) & 0x00200000)
 492                    | ((left >> 1) & 0x00100000)
 493                    | ((left << 10) & 0x00040000)
 494                    | ((left << 2) & 0x00020000)
 495                    | ((left >> 10) & 0x00010000)
 496                    | ((right >> 13) & 0x00002000)
 497                    | ((right >> 4) & 0x00001000)
 498                    | ((right << 6) & 0x00000800)
 499                    | ((right >> 1) & 0x00000400)
 500                    | ((right >> 14) & 0x00000200)
 501                    | (right & 0x00000100)
 502                    | ((right >> 5) & 0x00000020)
 503                    | ((right >> 10) & 0x00000010)
 504                    | ((right >> 3) & 0x00000008)
 505                    | ((right >> 18) & 0x00000004)
 506                    | ((right >> 26) & 0x00000002)
 507                    | ((right >> 24) & 0x00000001));
 508
 509       *subkey++ = (((left << 15) & 0x20000000)
 510                    | ((left << 17) & 0x10000000)
 511                    | ((left << 10) & 0x08000000)
 512                    | ((left << 22) & 0x04000000)
 513                    | ((left >> 2) & 0x02000000)
 514                    | ((left << 1) & 0x01000000)
 515                    | ((left << 16) & 0x00200000)
 516                    | ((left << 11) & 0x00100000)
 517                    | ((left << 3) & 0x00080000)
 518                    | ((left >> 6) & 0x00040000)
 519                    | ((left << 15) & 0x00020000)
 520                    | ((left >> 4) & 0x00010000)
 521                    | ((right >> 2) & 0x00002000)
 522                    | ((right << 8) & 0x00001000)
 523                    | ((right >> 14) & 0x00000808)
 524                    | ((right >> 9) & 0x00000400)
 525                    | ((right) & 0x00000200)
 526                    | ((right << 7) & 0x00000100)
 527                    | ((right >> 7) & 0x00000020)
 528                    | ((right >> 3) & 0x00000011)
 529                    | ((right << 2) & 0x00000004)
 530                    | ((right >> 21) & 0x00000002));
 531     }
 532 }
 533
 534 void
 535 des_setkey (des_ctx *ctx, const char * key)
 536 {
 537   int i;
 538
 539   des_key_schedule (key, ctx->encrypt_subkeys);
 540
 541   for (i = 0; i < 32; i += 2)
 542     {
 543       ctx->decrypt_subkeys[i] = ctx->encrypt_subkeys[30 - i];
 544       ctx->decrypt_subkeys[i + 1] = ctx->encrypt_subkeys[31 - i];
 545     }
 546 }
 547
 548 bool
 549 des_makekey (des_ctx *ctx, const char * key, size_t keylen)
 550 {
 551   if (keylen != 8)
 552     return false;
 553
 554   des_setkey (ctx, key);
 555
 556   return !des_is_weak_key (key);
 557 }
 558
 559 void
 560 des_ecb_crypt (des_ctx *ctx, const char * _from, char * _to, int mode)
 561 {
 562   const unsigned char *from = _from;
 563   unsigned char *to = _to;
 564   uint32_t left, right, work;
 565   uint32_t *keys;
 566
 567   keys = mode ? ctx->decrypt_subkeys : ctx->encrypt_subkeys;
 568
 569   READ_64BIT_DATA (from, left, right)
 570     INITIAL_PERMUTATION (left, work, right)
 571     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 572     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 573     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 574     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 575     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 576     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 577     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 578     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 579     FINAL_PERMUTATION (right, work, left)
 580     WRITE_64BIT_DATA (to, right, left)
 581 }
 582
 583 void
 584 tripledes_set2keys (tripledes_ctx *ctx, const char * key1, const char * key2)
 585 {
 586   int i;
 587
 588   des_key_schedule (key1, ctx->encrypt_subkeys);
 589   des_key_schedule (key2, &(ctx->decrypt_subkeys[32]));
 590
 591   for (i = 0; i < 32; i += 2)
 592     {
 593       ctx->decrypt_subkeys[i] = ctx->encrypt_subkeys[30 - i];
 594       ctx->decrypt_subkeys[i + 1] = ctx->encrypt_subkeys[31 - i];
 595
 596       ctx->encrypt_subkeys[i + 32] = ctx->decrypt_subkeys[62 - i];
 597       ctx->encrypt_subkeys[i + 33] = ctx->decrypt_subkeys[63 - i];
 598
 599       ctx->encrypt_subkeys[i + 64] = ctx->encrypt_subkeys[i];
 600       ctx->encrypt_subkeys[i + 65] = ctx->encrypt_subkeys[i + 1];
 601
 602       ctx->decrypt_subkeys[i + 64] = ctx->decrypt_subkeys[i];
 603       ctx->decrypt_subkeys[i + 65] = ctx->decrypt_subkeys[i + 1];
 604     }
 605 }
 606
 607 void
 608 tripledes_set3keys (tripledes_ctx *ctx, const char * key1,
 609                     const char * key2, const char * key3)
 610 {
 611   int i;
 612
 613   des_key_schedule (key1, ctx->encrypt_subkeys);
 614   des_key_schedule (key2, &(ctx->decrypt_subkeys[32]));
 615   des_key_schedule (key3, &(ctx->encrypt_subkeys[64]));
 616
 617   for (i = 0; i < 32; i += 2)
 618     {
 619       ctx->decrypt_subkeys[i] = ctx->encrypt_subkeys[94 - i];
 620       ctx->decrypt_subkeys[i + 1] = ctx->encrypt_subkeys[95 - i];
 621
 622       ctx->encrypt_subkeys[i + 32] = ctx->decrypt_subkeys[62 - i];
 623       ctx->encrypt_subkeys[i + 33] = ctx->decrypt_subkeys[63 - i];
 624
 625       ctx->decrypt_subkeys[i + 64] = ctx->encrypt_subkeys[30 - i];
 626       ctx->decrypt_subkeys[i + 65] = ctx->encrypt_subkeys[31 - i];
 627     }
 628 }
 629
 630 void
 631 tripledes_ecb_crypt (tripledes_ctx *ctx,
 632                      const char * _from,
 633                      char * _to, int mode)
 634 {
 635   const unsigned char *from = _from;
 636   unsigned char *to = _to;
 637   uint32_t left, right, work;
 638   uint32_t *keys;
 639
 640   keys = mode ? ctx->decrypt_subkeys : ctx->encrypt_subkeys;
 641
 642   READ_64BIT_DATA (from, left, right)
 643     INITIAL_PERMUTATION (left, work, right)
 644     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 645     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 646     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 647     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 648     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 649     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 650     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 651     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 652     DES_ROUND (left, right, work, keys) DES_ROUND (right, left, work, keys)
 653     DES_ROUND (left, right, work, keys) DES_ROUND (right, left, work, keys)
 654     DES_ROUND (left, right, work, keys) DES_ROUND (right, left, work, keys)
 655     DES_ROUND (left, right, work, keys) DES_ROUND (right, left, work, keys)
 656     DES_ROUND (left, right, work, keys) DES_ROUND (right, left, work, keys)
 657     DES_ROUND (left, right, work, keys) DES_ROUND (right, left, work, keys)
 658     DES_ROUND (left, right, work, keys) DES_ROUND (right, left, work, keys)
 659     DES_ROUND (left, right, work, keys) DES_ROUND (right, left, work, keys)
 660     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 661     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 662     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 663     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 664     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 665     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 666     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 667     DES_ROUND (right, left, work, keys) DES_ROUND (left, right, work, keys)
 668     FINAL_PERMUTATION (right, work, left)
 669     WRITE_64BIT_DATA (to, right, left)
 670 }
 671
 672 bool
 673 tripledes_makekey (tripledes_ctx *ctx, const char * key, size_t keylen)
 674 {
 675   if (keylen != 24)
 676     return false;
 677
 678   tripledes_set3keys (ctx, key, key + 8, key + 16);
 679
 680   return !(des_is_weak_key (key)
 681            || des_is_weak_key (key + 8)
 682            || des_is_weak_key (key + 16));
 683 }