lib/des.c

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