git.maemo.org Git - qemu/blob - d3des.c

   1 /*
   2  * This is D3DES (V5.09) by Richard Outerbridge with the double and
   3  * triple-length support removed for use in VNC.  Also the bytebit[] array
   4  * has been reversed so that the most significant bit in each byte of the
   5  * key is ignored, not the least significant.
   6  *
   7  * These changes are:
   8  *  Copyright (C) 1999 AT&T Laboratories Cambridge.  All Rights Reserved.
   9  *
  10  * This software is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  13  */
  14
  15 /* D3DES (V5.09) -
  16  *
  17  * A portable, public domain, version of the Data Encryption Standard.
  18  *
  19  * Written with Symantec's THINK (Lightspeed) C by Richard Outerbridge.
  20  * Thanks to: Dan Hoey for his excellent Initial and Inverse permutation
  21  * code;  Jim Gillogly & Phil Karn for the DES key schedule code; Dennis
  22  * Ferguson, Eric Young and Dana How for comparing notes; and Ray Lau,
  23  * for humouring me on.
  24  *
  25  * Copyright (c) 1988,1989,1990,1991,1992 by Richard Outerbridge.
  26  * (GEnie : OUTER; CIS : [71755,204]) Graven Imagery, 1992.
  27  */
  28
  29 #include "d3des.h"
  30
  31 static void scrunch(unsigned char *, unsigned long *);
  32 static void unscrun(unsigned long *, unsigned char *);
  33 static void desfunc(unsigned long *, unsigned long *);
  34 static void cookey(unsigned long *);
  35
  36 static unsigned long KnL[32] = { 0L };
  37
  38 static unsigned short bytebit[8]        = {
  39         01, 02, 04, 010, 020, 040, 0100, 0200 };
  40
  41 static unsigned long bigbyte[24] = {
  42         0x800000L,      0x400000L,      0x200000L,      0x100000L,
  43         0x80000L,       0x40000L,       0x20000L,       0x10000L,
  44         0x8000L,        0x4000L,        0x2000L,        0x1000L,
  45         0x800L,         0x400L,         0x200L,         0x100L,
  46         0x80L,          0x40L,          0x20L,          0x10L,
  47         0x8L,           0x4L,           0x2L,           0x1L    };
  48
  49 /* Use the key schedule specified in the Standard (ANSI X3.92-1981). */
  50
  51 static unsigned char pc1[56] = {
  52         56, 48, 40, 32, 24, 16,  8,      0, 57, 49, 41, 33, 25, 17,
  53          9,  1, 58, 50, 42, 34, 26,     18, 10,  2, 59, 51, 43, 35,
  54         62, 54, 46, 38, 30, 22, 14,      6, 61, 53, 45, 37, 29, 21,
  55         13,  5, 60, 52, 44, 36, 28,     20, 12,  4, 27, 19, 11,  3 };
  56
  57 static unsigned char totrot[16] = {
  58         1,2,4,6,8,10,12,14,15,17,19,21,23,25,27,28 };
  59
  60 static unsigned char pc2[48] = {
  61         13, 16, 10, 23,  0,  4,  2, 27, 14,  5, 20,  9,
  62         22, 18, 11,  3, 25,  7, 15,  6, 26, 19, 12,  1,
  63         40, 51, 30, 36, 46, 54, 29, 39, 50, 44, 32, 47,
  64         43, 48, 38, 55, 33, 52, 45, 41, 49, 35, 28, 31 };
  65
  66 void deskey(key, edf)   /* Thanks to James Gillogly & Phil Karn! */
  67 unsigned char *key;
  68 int edf;
  69 {
  70         register int i, j, l, m, n;
  71         unsigned char pc1m[56], pcr[56];
  72         unsigned long kn[32];
  73
  74         for ( j = 0; j < 56; j++ ) {
  75                 l = pc1[j];
  76                 m = l & 07;
  77                 pc1m[j] = (key[l >> 3] & bytebit[m]) ? 1 : 0;
  78                 }
  79         for( i = 0; i < 16; i++ ) {
  80                 if( edf == DE1 ) m = (15 - i) << 1;
  81                 else m = i << 1;
  82                 n = m + 1;
  83                 kn[m] = kn[n] = 0L;
  84                 for( j = 0; j < 28; j++ ) {
  85                         l = j + totrot[i];
  86                         if( l < 28 ) pcr[j] = pc1m[l];
  87                         else pcr[j] = pc1m[l - 28];
  88                         }
  89                 for( j = 28; j < 56; j++ ) {
  90                     l = j + totrot[i];
  91                     if( l < 56 ) pcr[j] = pc1m[l];
  92                     else pcr[j] = pc1m[l - 28];
  93                     }
  94                 for( j = 0; j < 24; j++ ) {
  95                         if( pcr[pc2[j]] ) kn[m] |= bigbyte[j];
  96                         if( pcr[pc2[j+24]] ) kn[n] |= bigbyte[j];
  97                         }
  98                 }
  99         cookey(kn);
 100         return;
 101         }
 102
 103 static void cookey(raw1)
 104 register unsigned long *raw1;
 105 {
 106         register unsigned long *cook, *raw0;
 107         unsigned long dough[32];
 108         register int i;
 109
 110         cook = dough;
 111         for( i = 0; i < 16; i++, raw1++ ) {
 112                 raw0 = raw1++;
 113                 *cook    = (*raw0 & 0x00fc0000L) << 6;
 114                 *cook   |= (*raw0 & 0x00000fc0L) << 10;
 115                 *cook   |= (*raw1 & 0x00fc0000L) >> 10;
 116                 *cook++ |= (*raw1 & 0x00000fc0L) >> 6;
 117                 *cook    = (*raw0 & 0x0003f000L) << 12;
 118                 *cook   |= (*raw0 & 0x0000003fL) << 16;
 119                 *cook   |= (*raw1 & 0x0003f000L) >> 4;
 120                 *cook++ |= (*raw1 & 0x0000003fL);
 121                 }
 122         usekey(dough);
 123         return;
 124         }
 125
 126 void cpkey(into)
 127 register unsigned long *into;
 128 {
 129         register unsigned long *from, *endp;
 130
 131         from = KnL, endp = &KnL[32];
 132         while( from < endp ) *into++ = *from++;
 133         return;
 134         }
 135
 136 void usekey(from)
 137 register unsigned long *from;
 138 {
 139         register unsigned long *to, *endp;
 140
 141         to = KnL, endp = &KnL[32];
 142         while( to < endp ) *to++ = *from++;
 143         return;
 144         }
 145
 146 void des(inblock, outblock)
 147 unsigned char *inblock, *outblock;
 148 {
 149         unsigned long work[2];
 150
 151         scrunch(inblock, work);
 152         desfunc(work, KnL);
 153         unscrun(work, outblock);
 154         return;
 155         }
 156
 157 static void scrunch(outof, into)
 158 register unsigned char *outof;
 159 register unsigned long *into;
 160 {
 161         *into    = (*outof++ & 0xffL) << 24;
 162         *into   |= (*outof++ & 0xffL) << 16;
 163         *into   |= (*outof++ & 0xffL) << 8;
 164         *into++ |= (*outof++ & 0xffL);
 165         *into    = (*outof++ & 0xffL) << 24;
 166         *into   |= (*outof++ & 0xffL) << 16;
 167         *into   |= (*outof++ & 0xffL) << 8;
 168         *into   |= (*outof   & 0xffL);
 169         return;
 170         }
 171
 172 static void unscrun(outof, into)
 173 register unsigned long *outof;
 174 register unsigned char *into;
 175 {
 176         *into++ = (unsigned char)((*outof >> 24) & 0xffL);
 177         *into++ = (unsigned char)((*outof >> 16) & 0xffL);
 178         *into++ = (unsigned char)((*outof >>  8) & 0xffL);
 179         *into++ = (unsigned char)(*outof++       & 0xffL);
 180         *into++ = (unsigned char)((*outof >> 24) & 0xffL);
 181         *into++ = (unsigned char)((*outof >> 16) & 0xffL);
 182         *into++ = (unsigned char)((*outof >>  8) & 0xffL);
 183         *into   =  (unsigned char)(*outof        & 0xffL);
 184         return;
 185         }
 186
 187 static unsigned long SP1[64] = {
 188         0x01010400L, 0x00000000L, 0x00010000L, 0x01010404L,
 189         0x01010004L, 0x00010404L, 0x00000004L, 0x00010000L,
 190         0x00000400L, 0x01010400L, 0x01010404L, 0x00000400L,
 191         0x01000404L, 0x01010004L, 0x01000000L, 0x00000004L,
 192         0x00000404L, 0x01000400L, 0x01000400L, 0x00010400L,
 193         0x00010400L, 0x01010000L, 0x01010000L, 0x01000404L,
 194         0x00010004L, 0x01000004L, 0x01000004L, 0x00010004L,
 195         0x00000000L, 0x00000404L, 0x00010404L, 0x01000000L,
 196         0x00010000L, 0x01010404L, 0x00000004L, 0x01010000L,
 197         0x01010400L, 0x01000000L, 0x01000000L, 0x00000400L,
 198         0x01010004L, 0x00010000L, 0x00010400L, 0x01000004L,
 199         0x00000400L, 0x00000004L, 0x01000404L, 0x00010404L,
 200         0x01010404L, 0x00010004L, 0x01010000L, 0x01000404L,
 201         0x01000004L, 0x00000404L, 0x00010404L, 0x01010400L,
 202         0x00000404L, 0x01000400L, 0x01000400L, 0x00000000L,
 203         0x00010004L, 0x00010400L, 0x00000000L, 0x01010004L };
 204
 205 static unsigned long SP2[64] = {
 206         0x80108020L, 0x80008000L, 0x00008000L, 0x00108020L,
 207         0x00100000L, 0x00000020L, 0x80100020L, 0x80008020L,
 208         0x80000020L, 0x80108020L, 0x80108000L, 0x80000000L,
 209         0x80008000L, 0x00100000L, 0x00000020L, 0x80100020L,
 210         0x00108000L, 0x00100020L, 0x80008020L, 0x00000000L,
 211         0x80000000L, 0x00008000L, 0x00108020L, 0x80100000L,
 212         0x00100020L, 0x80000020L, 0x00000000L, 0x00108000L,
 213         0x00008020L, 0x80108000L, 0x80100000L, 0x00008020L,
 214         0x00000000L, 0x00108020L, 0x80100020L, 0x00100000L,
 215         0x80008020L, 0x80100000L, 0x80108000L, 0x00008000L,
 216         0x80100000L, 0x80008000L, 0x00000020L, 0x80108020L,
 217         0x00108020L, 0x00000020L, 0x00008000L, 0x80000000L,
 218         0x00008020L, 0x80108000L, 0x00100000L, 0x80000020L,
 219         0x00100020L, 0x80008020L, 0x80000020L, 0x00100020L,
 220         0x00108000L, 0x00000000L, 0x80008000L, 0x00008020L,
 221         0x80000000L, 0x80100020L, 0x80108020L, 0x00108000L };
 222
 223 static unsigned long SP3[64] = {
 224         0x00000208L, 0x08020200L, 0x00000000L, 0x08020008L,
 225         0x08000200L, 0x00000000L, 0x00020208L, 0x08000200L,
 226         0x00020008L, 0x08000008L, 0x08000008L, 0x00020000L,
 227         0x08020208L, 0x00020008L, 0x08020000L, 0x00000208L,
 228         0x08000000L, 0x00000008L, 0x08020200L, 0x00000200L,
 229         0x00020200L, 0x08020000L, 0x08020008L, 0x00020208L,
 230         0x08000208L, 0x00020200L, 0x00020000L, 0x08000208L,
 231         0x00000008L, 0x08020208L, 0x00000200L, 0x08000000L,
 232         0x08020200L, 0x08000000L, 0x00020008L, 0x00000208L,
 233         0x00020000L, 0x08020200L, 0x08000200L, 0x00000000L,
 234         0x00000200L, 0x00020008L, 0x08020208L, 0x08000200L,
 235         0x08000008L, 0x00000200L, 0x00000000L, 0x08020008L,
 236         0x08000208L, 0x00020000L, 0x08000000L, 0x08020208L,
 237         0x00000008L, 0x00020208L, 0x00020200L, 0x08000008L,
 238         0x08020000L, 0x08000208L, 0x00000208L, 0x08020000L,
 239         0x00020208L, 0x00000008L, 0x08020008L, 0x00020200L };
 240
 241 static unsigned long SP4[64] = {
 242         0x00802001L, 0x00002081L, 0x00002081L, 0x00000080L,
 243         0x00802080L, 0x00800081L, 0x00800001L, 0x00002001L,
 244         0x00000000L, 0x00802000L, 0x00802000L, 0x00802081L,
 245         0x00000081L, 0x00000000L, 0x00800080L, 0x00800001L,
 246         0x00000001L, 0x00002000L, 0x00800000L, 0x00802001L,
 247         0x00000080L, 0x00800000L, 0x00002001L, 0x00002080L,
 248         0x00800081L, 0x00000001L, 0x00002080L, 0x00800080L,
 249         0x00002000L, 0x00802080L, 0x00802081L, 0x00000081L,
 250         0x00800080L, 0x00800001L, 0x00802000L, 0x00802081L,
 251         0x00000081L, 0x00000000L, 0x00000000L, 0x00802000L,
 252         0x00002080L, 0x00800080L, 0x00800081L, 0x00000001L,
 253         0x00802001L, 0x00002081L, 0x00002081L, 0x00000080L,
 254         0x00802081L, 0x00000081L, 0x00000001L, 0x00002000L,
 255         0x00800001L, 0x00002001L, 0x00802080L, 0x00800081L,
 256         0x00002001L, 0x00002080L, 0x00800000L, 0x00802001L,
 257         0x00000080L, 0x00800000L, 0x00002000L, 0x00802080L };
 258
 259 static unsigned long SP5[64] = {
 260         0x00000100L, 0x02080100L, 0x02080000L, 0x42000100L,
 261         0x00080000L, 0x00000100L, 0x40000000L, 0x02080000L,
 262         0x40080100L, 0x00080000L, 0x02000100L, 0x40080100L,
 263         0x42000100L, 0x42080000L, 0x00080100L, 0x40000000L,
 264         0x02000000L, 0x40080000L, 0x40080000L, 0x00000000L,
 265         0x40000100L, 0x42080100L, 0x42080100L, 0x02000100L,
 266         0x42080000L, 0x40000100L, 0x00000000L, 0x42000000L,
 267         0x02080100L, 0x02000000L, 0x42000000L, 0x00080100L,
 268         0x00080000L, 0x42000100L, 0x00000100L, 0x02000000L,
 269         0x40000000L, 0x02080000L, 0x42000100L, 0x40080100L,
 270         0x02000100L, 0x40000000L, 0x42080000L, 0x02080100L,
 271         0x40080100L, 0x00000100L, 0x02000000L, 0x42080000L,
 272         0x42080100L, 0x00080100L, 0x42000000L, 0x42080100L,
 273         0x02080000L, 0x00000000L, 0x40080000L, 0x42000000L,
 274         0x00080100L, 0x02000100L, 0x40000100L, 0x00080000L,
 275         0x00000000L, 0x40080000L, 0x02080100L, 0x40000100L };
 276
 277 static unsigned long SP6[64] = {
 278         0x20000010L, 0x20400000L, 0x00004000L, 0x20404010L,
 279         0x20400000L, 0x00000010L, 0x20404010L, 0x00400000L,
 280         0x20004000L, 0x00404010L, 0x00400000L, 0x20000010L,
 281         0x00400010L, 0x20004000L, 0x20000000L, 0x00004010L,
 282         0x00000000L, 0x00400010L, 0x20004010L, 0x00004000L,
 283         0x00404000L, 0x20004010L, 0x00000010L, 0x20400010L,
 284         0x20400010L, 0x00000000L, 0x00404010L, 0x20404000L,
 285         0x00004010L, 0x00404000L, 0x20404000L, 0x20000000L,
 286         0x20004000L, 0x00000010L, 0x20400010L, 0x00404000L,
 287         0x20404010L, 0x00400000L, 0x00004010L, 0x20000010L,
 288         0x00400000L, 0x20004000L, 0x20000000L, 0x00004010L,
 289         0x20000010L, 0x20404010L, 0x00404000L, 0x20400000L,
 290         0x00404010L, 0x20404000L, 0x00000000L, 0x20400010L,
 291         0x00000010L, 0x00004000L, 0x20400000L, 0x00404010L,
 292         0x00004000L, 0x00400010L, 0x20004010L, 0x00000000L,
 293         0x20404000L, 0x20000000L, 0x00400010L, 0x20004010L };
 294
 295 static unsigned long SP7[64] = {
 296         0x00200000L, 0x04200002L, 0x04000802L, 0x00000000L,
 297         0x00000800L, 0x04000802L, 0x00200802L, 0x04200800L,
 298         0x04200802L, 0x00200000L, 0x00000000L, 0x04000002L,
 299         0x00000002L, 0x04000000L, 0x04200002L, 0x00000802L,
 300         0x04000800L, 0x00200802L, 0x00200002L, 0x04000800L,
 301         0x04000002L, 0x04200000L, 0x04200800L, 0x00200002L,
 302         0x04200000L, 0x00000800L, 0x00000802L, 0x04200802L,
 303         0x00200800L, 0x00000002L, 0x04000000L, 0x00200800L,
 304         0x04000000L, 0x00200800L, 0x00200000L, 0x04000802L,
 305         0x04000802L, 0x04200002L, 0x04200002L, 0x00000002L,
 306         0x00200002L, 0x04000000L, 0x04000800L, 0x00200000L,
 307         0x04200800L, 0x00000802L, 0x00200802L, 0x04200800L,
 308         0x00000802L, 0x04000002L, 0x04200802L, 0x04200000L,
 309         0x00200800L, 0x00000000L, 0x00000002L, 0x04200802L,
 310         0x00000000L, 0x00200802L, 0x04200000L, 0x00000800L,
 311         0x04000002L, 0x04000800L, 0x00000800L, 0x00200002L };
 312
 313 static unsigned long SP8[64] = {
 314         0x10001040L, 0x00001000L, 0x00040000L, 0x10041040L,
 315         0x10000000L, 0x10001040L, 0x00000040L, 0x10000000L,
 316         0x00040040L, 0x10040000L, 0x10041040L, 0x00041000L,
 317         0x10041000L, 0x00041040L, 0x00001000L, 0x00000040L,
 318         0x10040000L, 0x10000040L, 0x10001000L, 0x00001040L,
 319         0x00041000L, 0x00040040L, 0x10040040L, 0x10041000L,
 320         0x00001040L, 0x00000000L, 0x00000000L, 0x10040040L,
 321         0x10000040L, 0x10001000L, 0x00041040L, 0x00040000L,
 322         0x00041040L, 0x00040000L, 0x10041000L, 0x00001000L,
 323         0x00000040L, 0x10040040L, 0x00001000L, 0x00041040L,
 324         0x10001000L, 0x00000040L, 0x10000040L, 0x10040000L,
 325         0x10040040L, 0x10000000L, 0x00040000L, 0x10001040L,
 326         0x00000000L, 0x10041040L, 0x00040040L, 0x10000040L,
 327         0x10040000L, 0x10001000L, 0x10001040L, 0x00000000L,
 328         0x10041040L, 0x00041000L, 0x00041000L, 0x00001040L,
 329         0x00001040L, 0x00040040L, 0x10000000L, 0x10041000L };
 330
 331 static void desfunc(block, keys)
 332 register unsigned long *block, *keys;
 333 {
 334         register unsigned long fval, work, right, leftt;
 335         register int round;
 336
 337         leftt = block[0];
 338         right = block[1];
 339         work = ((leftt >> 4) ^ right) & 0x0f0f0f0fL;
 340         right ^= work;
 341         leftt ^= (work << 4);
 342         work = ((leftt >> 16) ^ right) & 0x0000ffffL;
 343         right ^= work;
 344         leftt ^= (work << 16);
 345         work = ((right >> 2) ^ leftt) & 0x33333333L;
 346         leftt ^= work;
 347         right ^= (work << 2);
 348         work = ((right >> 8) ^ leftt) & 0x00ff00ffL;
 349         leftt ^= work;
 350         right ^= (work << 8);
 351         right = ((right << 1) | ((right >> 31) & 1L)) & 0xffffffffL;
 352         work = (leftt ^ right) & 0xaaaaaaaaL;
 353         leftt ^= work;
 354         right ^= work;
 355         leftt = ((leftt << 1) | ((leftt >> 31) & 1L)) & 0xffffffffL;
 356
 357         for( round = 0; round < 8; round++ ) {
 358                 work  = (right << 28) | (right >> 4);
 359                 work ^= *keys++;
 360                 fval  = SP7[ work                & 0x3fL];
 361                 fval |= SP5[(work >>  8) & 0x3fL];
 362                 fval |= SP3[(work >> 16) & 0x3fL];
 363                 fval |= SP1[(work >> 24) & 0x3fL];
 364                 work  = right ^ *keys++;
 365                 fval |= SP8[ work                & 0x3fL];
 366                 fval |= SP6[(work >>  8) & 0x3fL];
 367                 fval |= SP4[(work >> 16) & 0x3fL];
 368                 fval |= SP2[(work >> 24) & 0x3fL];
 369                 leftt ^= fval;
 370                 work  = (leftt << 28) | (leftt >> 4);
 371                 work ^= *keys++;
 372                 fval  = SP7[ work                & 0x3fL];
 373                 fval |= SP5[(work >>  8) & 0x3fL];
 374                 fval |= SP3[(work >> 16) & 0x3fL];
 375                 fval |= SP1[(work >> 24) & 0x3fL];
 376                 work  = leftt ^ *keys++;
 377                 fval |= SP8[ work                & 0x3fL];
 378                 fval |= SP6[(work >>  8) & 0x3fL];
 379                 fval |= SP4[(work >> 16) & 0x3fL];
 380                 fval |= SP2[(work >> 24) & 0x3fL];
 381                 right ^= fval;
 382                 }
 383
 384         right = (right << 31) | (right >> 1);
 385         work = (leftt ^ right) & 0xaaaaaaaaL;
 386         leftt ^= work;
 387         right ^= work;
 388         leftt = (leftt << 31) | (leftt >> 1);
 389         work = ((leftt >> 8) ^ right) & 0x00ff00ffL;
 390         right ^= work;
 391         leftt ^= (work << 8);
 392         work = ((leftt >> 2) ^ right) & 0x33333333L;
 393         right ^= work;
 394         leftt ^= (work << 2);
 395         work = ((right >> 16) ^ leftt) & 0x0000ffffL;
 396         leftt ^= work;
 397         right ^= (work << 16);
 398         work = ((right >> 4) ^ leftt) & 0x0f0f0f0fL;
 399         leftt ^= work;
 400         right ^= (work << 4);
 401         *block++ = right;
 402         *block = leftt;
 403         return;
 404         }
 405
 406 /* Validation sets:
 407  *
 408  * Single-length key, single-length plaintext -
 409  * Key    : 0123 4567 89ab cdef
 410  * Plain  : 0123 4567 89ab cde7
 411  * Cipher : c957 4425 6a5e d31d
 412  *
 413  * Double-length key, single-length plaintext -
 414  * Key    : 0123 4567 89ab cdef fedc ba98 7654 3210
 415  * Plain  : 0123 4567 89ab cde7
 416  * Cipher : 7f1d 0a77 826b 8aff
 417  *
 418  * Double-length key, double-length plaintext -
 419  * Key    : 0123 4567 89ab cdef fedc ba98 7654 3210
 420  * Plain  : 0123 4567 89ab cdef 0123 4567 89ab cdff
 421  * Cipher : 27a0 8440 406a df60 278f 47cf 42d6 15d7
 422  *
 423  * Triple-length key, single-length plaintext -
 424  * Key    : 0123 4567 89ab cdef fedc ba98 7654 3210 89ab cdef 0123 4567
 425  * Plain  : 0123 4567 89ab cde7
 426  * Cipher : de0b 7c06 ae5e 0ed5
 427  *
 428  * Triple-length key, double-length plaintext -
 429  * Key    : 0123 4567 89ab cdef fedc ba98 7654 3210 89ab cdef 0123 4567
 430  * Plain  : 0123 4567 89ab cdef 0123 4567 89ab cdff
 431  * Cipher : ad0d 1b30 ac17 cf07 0ed1 1c63 81e4 4de5
 432  *
 433  * d3des V5.0a rwo 9208.07 18:44 Graven Imagery
 434  **********************************************************************/