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 const unsigned short bytebit[8]  = {
  39         01, 02, 04, 010, 020, 040, 0100, 0200 };
  40
  41 static const 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 const 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 const unsigned char totrot[16] = {
  58         1,2,4,6,8,10,12,14,15,17,19,21,23,25,27,28 };
  59
  60 static const 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 /* Thanks to James Gillogly & Phil Karn! */
  67 void deskey(unsigned char *key, int edf)
  68 {
  69         register int i, j, l, m, n;
  70         unsigned char pc1m[56], pcr[56];
  71         unsigned long kn[32];
  72
  73         for ( j = 0; j < 56; j++ ) {
  74                 l = pc1[j];
  75                 m = l & 07;
  76                 pc1m[j] = (key[l >> 3] & bytebit[m]) ? 1 : 0;
  77                 }
  78         for( i = 0; i < 16; i++ ) {
  79                 if( edf == DE1 ) m = (15 - i) << 1;
  80                 else m = i << 1;
  81                 n = m + 1;
  82                 kn[m] = kn[n] = 0L;
  83                 for( j = 0; j < 28; j++ ) {
  84                         l = j + totrot[i];
  85                         if( l < 28 ) pcr[j] = pc1m[l];
  86                         else pcr[j] = pc1m[l - 28];
  87                         }
  88                 for( j = 28; j < 56; j++ ) {
  89                     l = j + totrot[i];
  90                     if( l < 56 ) pcr[j] = pc1m[l];
  91                     else pcr[j] = pc1m[l - 28];
  92                     }
  93                 for( j = 0; j < 24; j++ ) {
  94                         if( pcr[pc2[j]] ) kn[m] |= bigbyte[j];
  95                         if( pcr[pc2[j+24]] ) kn[n] |= bigbyte[j];
  96                         }
  97                 }
  98         cookey(kn);
  99         return;
 100         }
 101
 102 static void cookey(register unsigned long *raw1)
 103 {
 104         register unsigned long *cook, *raw0;
 105         unsigned long dough[32];
 106         register int i;
 107
 108         cook = dough;
 109         for( i = 0; i < 16; i++, raw1++ ) {
 110                 raw0 = raw1++;
 111                 *cook    = (*raw0 & 0x00fc0000L) << 6;
 112                 *cook   |= (*raw0 & 0x00000fc0L) << 10;
 113                 *cook   |= (*raw1 & 0x00fc0000L) >> 10;
 114                 *cook++ |= (*raw1 & 0x00000fc0L) >> 6;
 115                 *cook    = (*raw0 & 0x0003f000L) << 12;
 116                 *cook   |= (*raw0 & 0x0000003fL) << 16;
 117                 *cook   |= (*raw1 & 0x0003f000L) >> 4;
 118                 *cook++ |= (*raw1 & 0x0000003fL);
 119                 }
 120         usekey(dough);
 121         return;
 122         }
 123
 124 void cpkey(register unsigned long *into)
 125 {
 126         register unsigned long *from, *endp;
 127
 128         from = KnL, endp = &KnL[32];
 129         while( from < endp ) *into++ = *from++;
 130         return;
 131         }
 132
 133 void usekey(register unsigned long *from)
 134 {
 135         register unsigned long *to, *endp;
 136
 137         to = KnL, endp = &KnL[32];
 138         while( to < endp ) *to++ = *from++;
 139         return;
 140         }
 141
 142 void des(unsigned char *inblock, unsigned char *outblock)
 143 {
 144         unsigned long work[2];
 145
 146         scrunch(inblock, work);
 147         desfunc(work, KnL);
 148         unscrun(work, outblock);
 149         return;
 150         }
 151
 152 static void scrunch(register unsigned char *outof, register unsigned long *into)
 153 {
 154         *into    = (*outof++ & 0xffL) << 24;
 155         *into   |= (*outof++ & 0xffL) << 16;
 156         *into   |= (*outof++ & 0xffL) << 8;
 157         *into++ |= (*outof++ & 0xffL);
 158         *into    = (*outof++ & 0xffL) << 24;
 159         *into   |= (*outof++ & 0xffL) << 16;
 160         *into   |= (*outof++ & 0xffL) << 8;
 161         *into   |= (*outof   & 0xffL);
 162         return;
 163         }
 164
 165 static void unscrun(register unsigned long *outof, register unsigned char *into)
 166 {
 167         *into++ = (unsigned char)((*outof >> 24) & 0xffL);
 168         *into++ = (unsigned char)((*outof >> 16) & 0xffL);
 169         *into++ = (unsigned char)((*outof >>  8) & 0xffL);
 170         *into++ = (unsigned char)(*outof++       & 0xffL);
 171         *into++ = (unsigned char)((*outof >> 24) & 0xffL);
 172         *into++ = (unsigned char)((*outof >> 16) & 0xffL);
 173         *into++ = (unsigned char)((*outof >>  8) & 0xffL);
 174         *into   =  (unsigned char)(*outof        & 0xffL);
 175         return;
 176         }
 177
 178 static const unsigned long SP1[64] = {
 179         0x01010400L, 0x00000000L, 0x00010000L, 0x01010404L,
 180         0x01010004L, 0x00010404L, 0x00000004L, 0x00010000L,
 181         0x00000400L, 0x01010400L, 0x01010404L, 0x00000400L,
 182         0x01000404L, 0x01010004L, 0x01000000L, 0x00000004L,
 183         0x00000404L, 0x01000400L, 0x01000400L, 0x00010400L,
 184         0x00010400L, 0x01010000L, 0x01010000L, 0x01000404L,
 185         0x00010004L, 0x01000004L, 0x01000004L, 0x00010004L,
 186         0x00000000L, 0x00000404L, 0x00010404L, 0x01000000L,
 187         0x00010000L, 0x01010404L, 0x00000004L, 0x01010000L,
 188         0x01010400L, 0x01000000L, 0x01000000L, 0x00000400L,
 189         0x01010004L, 0x00010000L, 0x00010400L, 0x01000004L,
 190         0x00000400L, 0x00000004L, 0x01000404L, 0x00010404L,
 191         0x01010404L, 0x00010004L, 0x01010000L, 0x01000404L,
 192         0x01000004L, 0x00000404L, 0x00010404L, 0x01010400L,
 193         0x00000404L, 0x01000400L, 0x01000400L, 0x00000000L,
 194         0x00010004L, 0x00010400L, 0x00000000L, 0x01010004L };
 195
 196 static const unsigned long SP2[64] = {
 197         0x80108020L, 0x80008000L, 0x00008000L, 0x00108020L,
 198         0x00100000L, 0x00000020L, 0x80100020L, 0x80008020L,
 199         0x80000020L, 0x80108020L, 0x80108000L, 0x80000000L,
 200         0x80008000L, 0x00100000L, 0x00000020L, 0x80100020L,
 201         0x00108000L, 0x00100020L, 0x80008020L, 0x00000000L,
 202         0x80000000L, 0x00008000L, 0x00108020L, 0x80100000L,
 203         0x00100020L, 0x80000020L, 0x00000000L, 0x00108000L,
 204         0x00008020L, 0x80108000L, 0x80100000L, 0x00008020L,
 205         0x00000000L, 0x00108020L, 0x80100020L, 0x00100000L,
 206         0x80008020L, 0x80100000L, 0x80108000L, 0x00008000L,
 207         0x80100000L, 0x80008000L, 0x00000020L, 0x80108020L,
 208         0x00108020L, 0x00000020L, 0x00008000L, 0x80000000L,
 209         0x00008020L, 0x80108000L, 0x00100000L, 0x80000020L,
 210         0x00100020L, 0x80008020L, 0x80000020L, 0x00100020L,
 211         0x00108000L, 0x00000000L, 0x80008000L, 0x00008020L,
 212         0x80000000L, 0x80100020L, 0x80108020L, 0x00108000L };
 213
 214 static const unsigned long SP3[64] = {
 215         0x00000208L, 0x08020200L, 0x00000000L, 0x08020008L,
 216         0x08000200L, 0x00000000L, 0x00020208L, 0x08000200L,
 217         0x00020008L, 0x08000008L, 0x08000008L, 0x00020000L,
 218         0x08020208L, 0x00020008L, 0x08020000L, 0x00000208L,
 219         0x08000000L, 0x00000008L, 0x08020200L, 0x00000200L,
 220         0x00020200L, 0x08020000L, 0x08020008L, 0x00020208L,
 221         0x08000208L, 0x00020200L, 0x00020000L, 0x08000208L,
 222         0x00000008L, 0x08020208L, 0x00000200L, 0x08000000L,
 223         0x08020200L, 0x08000000L, 0x00020008L, 0x00000208L,
 224         0x00020000L, 0x08020200L, 0x08000200L, 0x00000000L,
 225         0x00000200L, 0x00020008L, 0x08020208L, 0x08000200L,
 226         0x08000008L, 0x00000200L, 0x00000000L, 0x08020008L,
 227         0x08000208L, 0x00020000L, 0x08000000L, 0x08020208L,
 228         0x00000008L, 0x00020208L, 0x00020200L, 0x08000008L,
 229         0x08020000L, 0x08000208L, 0x00000208L, 0x08020000L,
 230         0x00020208L, 0x00000008L, 0x08020008L, 0x00020200L };
 231
 232 static const unsigned long SP4[64] = {
 233         0x00802001L, 0x00002081L, 0x00002081L, 0x00000080L,
 234         0x00802080L, 0x00800081L, 0x00800001L, 0x00002001L,
 235         0x00000000L, 0x00802000L, 0x00802000L, 0x00802081L,
 236         0x00000081L, 0x00000000L, 0x00800080L, 0x00800001L,
 237         0x00000001L, 0x00002000L, 0x00800000L, 0x00802001L,
 238         0x00000080L, 0x00800000L, 0x00002001L, 0x00002080L,
 239         0x00800081L, 0x00000001L, 0x00002080L, 0x00800080L,
 240         0x00002000L, 0x00802080L, 0x00802081L, 0x00000081L,
 241         0x00800080L, 0x00800001L, 0x00802000L, 0x00802081L,
 242         0x00000081L, 0x00000000L, 0x00000000L, 0x00802000L,
 243         0x00002080L, 0x00800080L, 0x00800081L, 0x00000001L,
 244         0x00802001L, 0x00002081L, 0x00002081L, 0x00000080L,
 245         0x00802081L, 0x00000081L, 0x00000001L, 0x00002000L,
 246         0x00800001L, 0x00002001L, 0x00802080L, 0x00800081L,
 247         0x00002001L, 0x00002080L, 0x00800000L, 0x00802001L,
 248         0x00000080L, 0x00800000L, 0x00002000L, 0x00802080L };
 249
 250 static const unsigned long SP5[64] = {
 251         0x00000100L, 0x02080100L, 0x02080000L, 0x42000100L,
 252         0x00080000L, 0x00000100L, 0x40000000L, 0x02080000L,
 253         0x40080100L, 0x00080000L, 0x02000100L, 0x40080100L,
 254         0x42000100L, 0x42080000L, 0x00080100L, 0x40000000L,
 255         0x02000000L, 0x40080000L, 0x40080000L, 0x00000000L,
 256         0x40000100L, 0x42080100L, 0x42080100L, 0x02000100L,
 257         0x42080000L, 0x40000100L, 0x00000000L, 0x42000000L,
 258         0x02080100L, 0x02000000L, 0x42000000L, 0x00080100L,
 259         0x00080000L, 0x42000100L, 0x00000100L, 0x02000000L,
 260         0x40000000L, 0x02080000L, 0x42000100L, 0x40080100L,
 261         0x02000100L, 0x40000000L, 0x42080000L, 0x02080100L,
 262         0x40080100L, 0x00000100L, 0x02000000L, 0x42080000L,
 263         0x42080100L, 0x00080100L, 0x42000000L, 0x42080100L,
 264         0x02080000L, 0x00000000L, 0x40080000L, 0x42000000L,
 265         0x00080100L, 0x02000100L, 0x40000100L, 0x00080000L,
 266         0x00000000L, 0x40080000L, 0x02080100L, 0x40000100L };
 267
 268 static const unsigned long SP6[64] = {
 269         0x20000010L, 0x20400000L, 0x00004000L, 0x20404010L,
 270         0x20400000L, 0x00000010L, 0x20404010L, 0x00400000L,
 271         0x20004000L, 0x00404010L, 0x00400000L, 0x20000010L,
 272         0x00400010L, 0x20004000L, 0x20000000L, 0x00004010L,
 273         0x00000000L, 0x00400010L, 0x20004010L, 0x00004000L,
 274         0x00404000L, 0x20004010L, 0x00000010L, 0x20400010L,
 275         0x20400010L, 0x00000000L, 0x00404010L, 0x20404000L,
 276         0x00004010L, 0x00404000L, 0x20404000L, 0x20000000L,
 277         0x20004000L, 0x00000010L, 0x20400010L, 0x00404000L,
 278         0x20404010L, 0x00400000L, 0x00004010L, 0x20000010L,
 279         0x00400000L, 0x20004000L, 0x20000000L, 0x00004010L,
 280         0x20000010L, 0x20404010L, 0x00404000L, 0x20400000L,
 281         0x00404010L, 0x20404000L, 0x00000000L, 0x20400010L,
 282         0x00000010L, 0x00004000L, 0x20400000L, 0x00404010L,
 283         0x00004000L, 0x00400010L, 0x20004010L, 0x00000000L,
 284         0x20404000L, 0x20000000L, 0x00400010L, 0x20004010L };
 285
 286 static const unsigned long SP7[64] = {
 287         0x00200000L, 0x04200002L, 0x04000802L, 0x00000000L,
 288         0x00000800L, 0x04000802L, 0x00200802L, 0x04200800L,
 289         0x04200802L, 0x00200000L, 0x00000000L, 0x04000002L,
 290         0x00000002L, 0x04000000L, 0x04200002L, 0x00000802L,
 291         0x04000800L, 0x00200802L, 0x00200002L, 0x04000800L,
 292         0x04000002L, 0x04200000L, 0x04200800L, 0x00200002L,
 293         0x04200000L, 0x00000800L, 0x00000802L, 0x04200802L,
 294         0x00200800L, 0x00000002L, 0x04000000L, 0x00200800L,
 295         0x04000000L, 0x00200800L, 0x00200000L, 0x04000802L,
 296         0x04000802L, 0x04200002L, 0x04200002L, 0x00000002L,
 297         0x00200002L, 0x04000000L, 0x04000800L, 0x00200000L,
 298         0x04200800L, 0x00000802L, 0x00200802L, 0x04200800L,
 299         0x00000802L, 0x04000002L, 0x04200802L, 0x04200000L,
 300         0x00200800L, 0x00000000L, 0x00000002L, 0x04200802L,
 301         0x00000000L, 0x00200802L, 0x04200000L, 0x00000800L,
 302         0x04000002L, 0x04000800L, 0x00000800L, 0x00200002L };
 303
 304 static const unsigned long SP8[64] = {
 305         0x10001040L, 0x00001000L, 0x00040000L, 0x10041040L,
 306         0x10000000L, 0x10001040L, 0x00000040L, 0x10000000L,
 307         0x00040040L, 0x10040000L, 0x10041040L, 0x00041000L,
 308         0x10041000L, 0x00041040L, 0x00001000L, 0x00000040L,
 309         0x10040000L, 0x10000040L, 0x10001000L, 0x00001040L,
 310         0x00041000L, 0x00040040L, 0x10040040L, 0x10041000L,
 311         0x00001040L, 0x00000000L, 0x00000000L, 0x10040040L,
 312         0x10000040L, 0x10001000L, 0x00041040L, 0x00040000L,
 313         0x00041040L, 0x00040000L, 0x10041000L, 0x00001000L,
 314         0x00000040L, 0x10040040L, 0x00001000L, 0x00041040L,
 315         0x10001000L, 0x00000040L, 0x10000040L, 0x10040000L,
 316         0x10040040L, 0x10000000L, 0x00040000L, 0x10001040L,
 317         0x00000000L, 0x10041040L, 0x00040040L, 0x10000040L,
 318         0x10040000L, 0x10001000L, 0x10001040L, 0x00000000L,
 319         0x10041040L, 0x00041000L, 0x00041000L, 0x00001040L,
 320         0x00001040L, 0x00040040L, 0x10000000L, 0x10041000L };
 321
 322 static void desfunc(register unsigned long *block, register unsigned long *keys)
 323 {
 324         register unsigned long fval, work, right, leftt;
 325         register int round;
 326
 327         leftt = block[0];
 328         right = block[1];
 329         work = ((leftt >> 4) ^ right) & 0x0f0f0f0fL;
 330         right ^= work;
 331         leftt ^= (work << 4);
 332         work = ((leftt >> 16) ^ right) & 0x0000ffffL;
 333         right ^= work;
 334         leftt ^= (work << 16);
 335         work = ((right >> 2) ^ leftt) & 0x33333333L;
 336         leftt ^= work;
 337         right ^= (work << 2);
 338         work = ((right >> 8) ^ leftt) & 0x00ff00ffL;
 339         leftt ^= work;
 340         right ^= (work << 8);
 341         right = ((right << 1) | ((right >> 31) & 1L)) & 0xffffffffL;
 342         work = (leftt ^ right) & 0xaaaaaaaaL;
 343         leftt ^= work;
 344         right ^= work;
 345         leftt = ((leftt << 1) | ((leftt >> 31) & 1L)) & 0xffffffffL;
 346
 347         for( round = 0; round < 8; round++ ) {
 348                 work  = (right << 28) | (right >> 4);
 349                 work ^= *keys++;
 350                 fval  = SP7[ work                & 0x3fL];
 351                 fval |= SP5[(work >>  8) & 0x3fL];
 352                 fval |= SP3[(work >> 16) & 0x3fL];
 353                 fval |= SP1[(work >> 24) & 0x3fL];
 354                 work  = right ^ *keys++;
 355                 fval |= SP8[ work                & 0x3fL];
 356                 fval |= SP6[(work >>  8) & 0x3fL];
 357                 fval |= SP4[(work >> 16) & 0x3fL];
 358                 fval |= SP2[(work >> 24) & 0x3fL];
 359                 leftt ^= fval;
 360                 work  = (leftt << 28) | (leftt >> 4);
 361                 work ^= *keys++;
 362                 fval  = SP7[ work                & 0x3fL];
 363                 fval |= SP5[(work >>  8) & 0x3fL];
 364                 fval |= SP3[(work >> 16) & 0x3fL];
 365                 fval |= SP1[(work >> 24) & 0x3fL];
 366                 work  = leftt ^ *keys++;
 367                 fval |= SP8[ work                & 0x3fL];
 368                 fval |= SP6[(work >>  8) & 0x3fL];
 369                 fval |= SP4[(work >> 16) & 0x3fL];
 370                 fval |= SP2[(work >> 24) & 0x3fL];
 371                 right ^= fval;
 372                 }
 373
 374         right = (right << 31) | (right >> 1);
 375         work = (leftt ^ right) & 0xaaaaaaaaL;
 376         leftt ^= work;
 377         right ^= work;
 378         leftt = (leftt << 31) | (leftt >> 1);
 379         work = ((leftt >> 8) ^ right) & 0x00ff00ffL;
 380         right ^= work;
 381         leftt ^= (work << 8);
 382         work = ((leftt >> 2) ^ right) & 0x33333333L;
 383         right ^= work;
 384         leftt ^= (work << 2);
 385         work = ((right >> 16) ^ leftt) & 0x0000ffffL;
 386         leftt ^= work;
 387         right ^= (work << 16);
 388         work = ((right >> 4) ^ leftt) & 0x0f0f0f0fL;
 389         leftt ^= work;
 390         right ^= (work << 4);
 391         *block++ = right;
 392         *block = leftt;
 393         return;
 394         }
 395
 396 /* Validation sets:
 397  *
 398  * Single-length key, single-length plaintext -
 399  * Key    : 0123 4567 89ab cdef
 400  * Plain  : 0123 4567 89ab cde7
 401  * Cipher : c957 4425 6a5e d31d
 402  *
 403  * Double-length key, single-length plaintext -
 404  * Key    : 0123 4567 89ab cdef fedc ba98 7654 3210
 405  * Plain  : 0123 4567 89ab cde7
 406  * Cipher : 7f1d 0a77 826b 8aff
 407  *
 408  * Double-length key, double-length plaintext -
 409  * Key    : 0123 4567 89ab cdef fedc ba98 7654 3210
 410  * Plain  : 0123 4567 89ab cdef 0123 4567 89ab cdff
 411  * Cipher : 27a0 8440 406a df60 278f 47cf 42d6 15d7
 412  *
 413  * Triple-length key, single-length plaintext -
 414  * Key    : 0123 4567 89ab cdef fedc ba98 7654 3210 89ab cdef 0123 4567
 415  * Plain  : 0123 4567 89ab cde7
 416  * Cipher : de0b 7c06 ae5e 0ed5
 417  *
 418  * Triple-length key, double-length plaintext -
 419  * Key    : 0123 4567 89ab cdef fedc ba98 7654 3210 89ab cdef 0123 4567
 420  * Plain  : 0123 4567 89ab cdef 0123 4567 89ab cdff
 421  * Cipher : ad0d 1b30 ac17 cf07 0ed1 1c63 81e4 4de5
 422  *
 423  * d3des V5.0a rwo 9208.07 18:44 Graven Imagery
 424  **********************************************************************/