_ Git - BoarSSL/blob - Crypto/DES.cs

   1 /*
   2  * Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining
   5  * a copy of this software and associated documentation files (the
   6  * "Software"), to deal in the Software without restriction, including
   7  * without limitation the rights to use, copy, modify, merge, publish,
   8  * distribute, sublicense, and/or sell copies of the Software, and to
   9  * permit persons to whom the Software is furnished to do so, subject to
  10  * the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be
  13  * included in all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  18  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  19  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  20  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  21  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  22  * SOFTWARE.
  23  */
  24
  25 using System;
  26
  27 namespace Crypto {
  28
  29 /*
  30  * Perfunctory implementation of the Triple-DES block cipher (also works
  31  * as "single DES" when used with an 8-byte DES key). It only processes
  32  * single blocks, and does it "in place" (the input block is replaced
  33  * with the output block in the same array). This code is a direct
  34  * translation of the specification and is not optimized for speed.
  35  *
  36  * Supported key sizes are 8, 16 and 24 bytes. When an 8-byte key is
  37  * used, this is the original DES (64-bit key, out of which 8 are
  38  * unused, so the "true key size" is 56 bits). When a 16-byte or 24-byte
  39  * key is used, this is Triple-DES (with a 16-byte key, the key is
  40  * expanded to 24 bytes by reusing bytes 0..7 as bytes 16..23 of the
  41  * key).
  42  *
  43  * Instances are not thread-safe; however, distinct threads may use
  44  * distinct instances concurrently.
  45  *
  46  * Since instances are pure managed code, there is no need for explicit
  47  * disposal after usage.
  48  */
  49
  50 public sealed class DES : BlockCipherCore {
  51
  52         ulong[] skey;
  53         int rounds;
  54
  55         /*
  56          * Initialize a new instance.
  57          */
  58         public DES()
  59         {
  60                 skey = new ulong[48];
  61         }
  62
  63         /* see IBlockCipher */
  64         public override IBlockCipher Dup()
  65         {
  66                 DES d = new DES();
  67                 Array.Copy(skey, 0, d.skey, 0, skey.Length);
  68                 d.rounds = rounds;
  69                 return d;
  70         }
  71
  72         /*
  73          * Get the block size in bytes (always 8).
  74          */
  75         public override int BlockSize {
  76                 get {
  77                         return 8;
  78                 }
  79         }
  80
  81         /*
  82          * Set the key (8, 16 or 24 bytes).
  83          */
  84         public override void SetKey(byte[] key, int off, int len)
  85         {
  86                 switch (len) {
  87                 case 8:
  88                         KeySchedule(key, off, 0);
  89                         rounds = 1;
  90                         break;
  91                 case 16:
  92                         KeySchedule(key, off, 0);
  93                         KeySchedule(key, off + 8, 16);
  94                         KeySchedule(key, off, 32);
  95                         rounds = 3;
  96                         break;
  97                 case 24:
  98                         KeySchedule(key, off, 0);
  99                         KeySchedule(key, off + 8, 16);
 100                         KeySchedule(key, off + 16, 32);
 101                         rounds = 3;
 102                         break;
 103                 default:
 104                         throw new ArgumentException(
 105                                 "bad DES/3DES key length: " + len);
 106                 }
 107
 108                 /*
 109                  * Inverse order of subkeys for the middle-DES (3DES
 110                  * uses the "EDE" configuration).
 111                  */
 112                 for (int j = 16; j < 24; j ++) {
 113                         ulong w = skey[j];
 114                         skey[j] = skey[47 - j];
 115                         skey[47 - j] = w;
 116                 }
 117         }
 118
 119         void KeySchedule(byte[] key, int off, int skeyOff)
 120         {
 121                 ulong k = Dec64be(key, off);
 122                 k = Perm(tabPC1, k);
 123                 ulong kl = k >> 28;
 124                 ulong kr = k & 0x0FFFFFFF;
 125                 for (int i = 0; i < 16; i ++) {
 126                         int r = rotK[i];
 127                         kl = ((kl << r) | (kl >> (28 - r))) & 0x0FFFFFFF;
 128                         kr = ((kr << r) | (kr >> (28 - r))) & 0x0FFFFFFF;
 129                         skey[skeyOff + i] = Perm(tabPC2, (kl << 28) | kr);
 130                 }
 131         }
 132
 133         /*
 134          * Encrypt one block; the block consists in the 8 bytes beginning
 135          * at offset 'off'. Other bytes in the array are unaltered.
 136          */
 137         public override void BlockEncrypt(byte[] buf, int off)
 138         {
 139                 if (rounds == 0) {
 140                         throw new Exception("no key provided");
 141                 }
 142                 ulong x = Dec64be(buf, off);
 143                 x = DoIP(x);
 144                 uint xl = (uint)(x >> 32);
 145                 uint xr = (uint)x;
 146                 for (int i = 0, k = 0; i < rounds; i ++) {
 147                         xl ^= FConf(xr, skey[k ++]);
 148                         xr ^= FConf(xl, skey[k ++]);
 149                         xl ^= FConf(xr, skey[k ++]);
 150                         xr ^= FConf(xl, skey[k ++]);
 151                         xl ^= FConf(xr, skey[k ++]);
 152                         xr ^= FConf(xl, skey[k ++]);
 153                         xl ^= FConf(xr, skey[k ++]);
 154                         xr ^= FConf(xl, skey[k ++]);
 155                         xl ^= FConf(xr, skey[k ++]);
 156                         xr ^= FConf(xl, skey[k ++]);
 157                         xl ^= FConf(xr, skey[k ++]);
 158                         xr ^= FConf(xl, skey[k ++]);
 159                         xl ^= FConf(xr, skey[k ++]);
 160                         xr ^= FConf(xl, skey[k ++]);
 161                         xl ^= FConf(xr, skey[k ++]);
 162                         uint tmp = xr ^ FConf(xl, skey[k ++]);
 163                         xr = xl;
 164                         xl = tmp;
 165                 }
 166                 x = ((ulong)xl << 32) | (ulong)xr;
 167                 x = DoIPInv(x);
 168                 Enc64be(x, buf, off);
 169         }
 170
 171         /*
 172          * Decrypt one block; the block consists in the 8 bytes beginning
 173          * at offset 'off'. Other bytes in the array are unaltered.
 174          */
 175         public override void BlockDecrypt(byte[] buf, int off)
 176         {
 177                 if (rounds == 0) {
 178                         throw new Exception("no key provided");
 179                 }
 180                 ulong x = Dec64be(buf, off);
 181                 x = DoIP(x);
 182                 uint xl = (uint)(x >> 32);
 183                 uint xr = (uint)x;
 184                 for (int i = 0, k = rounds << 4; i < rounds; i ++) {
 185                         xl ^= FConf(xr, skey[-- k]);
 186                         xr ^= FConf(xl, skey[-- k]);
 187                         xl ^= FConf(xr, skey[-- k]);
 188                         xr ^= FConf(xl, skey[-- k]);
 189                         xl ^= FConf(xr, skey[-- k]);
 190                         xr ^= FConf(xl, skey[-- k]);
 191                         xl ^= FConf(xr, skey[-- k]);
 192                         xr ^= FConf(xl, skey[-- k]);
 193                         xl ^= FConf(xr, skey[-- k]);
 194                         xr ^= FConf(xl, skey[-- k]);
 195                         xl ^= FConf(xr, skey[-- k]);
 196                         xr ^= FConf(xl, skey[-- k]);
 197                         xl ^= FConf(xr, skey[-- k]);
 198                         xr ^= FConf(xl, skey[-- k]);
 199                         xl ^= FConf(xr, skey[-- k]);
 200                         uint tmp = xr ^ FConf(xl, skey[-- k]);
 201                         xr = xl;
 202                         xl = tmp;
 203                 }
 204                 x = ((ulong)xl << 32) | (ulong)xr;
 205                 x = DoIPInv(x);
 206                 Enc64be(x, buf, off);
 207         }
 208
 209         /*
 210          * Arrays below are extracted exactly from FIPS 46-3. They use
 211          * the conventions defined in that document:
 212          *
 213          * -- Bits are numbered from 1, in the left-to-right order; in
 214          *    a 64-bit integer, the most significant (leftmost) bit is 1,
 215          *    while the least significant (rightmost) bit is 64.
 216          *
 217          * -- For each permutation (or extraction), the defined array
 218          *    lists the source index of each bit.
 219          *
 220          * -- For the S-boxes, bits 1 (leftmost) and 6 (rightmost) select
 221          *    the row, and bits 2 to 5 select the index within the row.
 222          */
 223
 224         static uint[,] Sdef = {
 225                 {
 226                         14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
 227                         0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
 228                         4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
 229                         15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13
 230                 }, {
 231                         15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
 232                         3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
 233                         0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
 234                         13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9
 235                 }, {
 236                         10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
 237                         13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
 238                         13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
 239                         1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12
 240                 }, {
 241                         7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
 242                         13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
 243                         10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
 244                         3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14
 245                 }, {
 246                         2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
 247                         14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
 248                         4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
 249                         11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3
 250                 }, {
 251                         12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
 252                         10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
 253                         9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
 254                         4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13
 255                 }, {
 256                         4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
 257                         13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
 258                         1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
 259                         6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12
 260                 }, {
 261                         13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
 262                         1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
 263                         7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
 264                         2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11
 265                 }
 266         };
 267
 268         static int[] defP = {
 269                 16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10,
 270                 2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25
 271         };
 272
 273         static int[] defPC1 = {
 274                 57, 49, 41, 33, 25, 17, 9,
 275                 1, 58, 50, 42, 34, 26, 18,
 276                 10, 2, 59, 51, 43, 35, 27,
 277                 19, 11, 3, 60, 52, 44, 36,
 278                 63, 55, 47, 39, 31, 23, 15,
 279                 7, 62, 54, 46, 38, 30, 22,
 280                 14, 6, 61, 53, 45, 37, 29,
 281                 21, 13, 5, 28, 20, 12, 4
 282         };
 283
 284         static int[] defPC2 = {
 285                 14, 17, 11, 24, 1, 5,
 286                 3, 28, 15, 6, 21, 10,
 287                 23, 19, 12, 4, 26, 8,
 288                 16, 7, 27, 20, 13, 2,
 289                 41, 52, 31, 37, 47, 55,
 290                 30, 40, 51, 45, 33, 48,
 291                 44, 49, 39, 56, 34, 53,
 292                 46, 42, 50, 36, 29, 32
 293         };
 294
 295         static int[] rotK = {
 296                 1, 1, 2, 2, 2, 2, 2, 2,
 297                 1, 2, 2, 2, 2, 2, 2, 1
 298         };
 299
 300         /*
 301          * Permutations (and extractions) are implemented with the
 302          * following tables, that are initialized from the class
 303          * initialization code. The representation of a permutation is
 304          * an array of words, where word at index k is a one-bit mask
 305          * that identifies the source bit that should go at position k
 306          * in the output. The "k" index here is in right-to-left
 307          * convention: least significant bit (rightmost) is numbered 0.
 308          *
 309          * The Perm() method applies a permutation, using one of the
 310          * tab*[] arrays.
 311          *
 312          * The S*[] arrays contain the S-boxes, with the permutation P
 313          * effect merged in, and expecting their 6-bit input "as is".
 314          */
 315         static ulong[] tabPC1;
 316         static ulong[] tabPC2;
 317
 318         static uint[] S1, S2, S3, S4, S5, S6, S7, S8;
 319
 320         static DES()
 321         {
 322                 tabPC1 = new ulong[defPC1.Length];
 323                 for (int i = 0; i < defPC1.Length; i ++) {
 324                         tabPC1[55 - i] = (ulong)1 << (64 - defPC1[i]);
 325                 }
 326                 tabPC2 = new ulong[defPC2.Length];
 327                 for (int i = 0; i < defPC2.Length; i ++) {
 328                         tabPC2[47 - i] = (ulong)1 << (56 - defPC2[i]);
 329                 }
 330
 331                 int[] PInv = new int[32];
 332                 for (int i = 0; i < defP.Length; i ++) {
 333                         PInv[32 - defP[i]] = 31 - i;
 334                 }
 335                 S1 = MakeSbox(PInv, 0);
 336                 S2 = MakeSbox(PInv, 1);
 337                 S3 = MakeSbox(PInv, 2);
 338                 S4 = MakeSbox(PInv, 3);
 339                 S5 = MakeSbox(PInv, 4);
 340                 S6 = MakeSbox(PInv, 5);
 341                 S7 = MakeSbox(PInv, 6);
 342                 S8 = MakeSbox(PInv, 7);
 343         }
 344
 345         static uint[] MakeSbox(int[] PInv, int i)
 346         {
 347                 uint[] S = new uint[64];
 348                 for (int j = 0; j < 64; j ++) {
 349                         int idx = ((j & 0x01) << 4) | (j & 0x20)
 350                                 | ((j & 0x1E) >> 1);
 351                         uint zb = Sdef[i, idx];
 352                         uint za = 0;
 353                         for (int k = 0; k < 4; k ++) {
 354                                 za |= ((zb >> k) & 1)
 355                                         << PInv[((7 - i) << 2) + k];
 356                         }
 357                         S[j] = za;
 358                 }
 359                 return S;
 360         }
 361
 362         static ulong IPStep(ulong x, int size, ulong mask)
 363         {
 364                 uint left = (uint)(x >> 32);
 365                 uint right = (uint)x;
 366                 uint tmp = ((left >> size) ^ right) & (uint)mask;
 367                 right ^= tmp;
 368                 left ^= tmp << size;
 369                 return ((ulong)left << 32) | (ulong)right;
 370         }
 371
 372         static ulong DoIP(ulong x)
 373         {
 374                 /*
 375                  * Permutation algorithm is initially from Richard
 376                  * Outerbridge; this implementation has been adapted
 377                  * from Crypto++ "des.cpp" file (which is in public
 378                  * domain).
 379                  */
 380                 uint l = (uint)(x >> 32);
 381                 uint r = (uint)x;
 382                 uint t;
 383                 t = ((l >>  4) ^ r) & 0x0F0F0F0F;
 384                 r ^= t;
 385                 l ^= t <<  4;
 386                 t = ((l >> 16) ^ r) & 0x0000FFFF;
 387                 r ^= t;
 388                 l ^= t << 16;
 389                 t = ((r >>  2) ^ l) & 0x33333333;
 390                 l ^= t;
 391                 r ^= t <<  2;
 392                 t = ((r >>  8) ^ l) & 0x00FF00FF;
 393                 l ^= t;
 394                 r ^= t <<  8;
 395                 t = ((l >>  1) ^ r) & 0x55555555;
 396                 r ^= t;
 397                 l ^= t <<  1;
 398                 x = ((ulong)l << 32) | (ulong)r;
 399                 return x;
 400         }
 401
 402         static ulong DoIPInv(ulong x)
 403         {
 404                 /*
 405                  * See DoIP().
 406                  */
 407                 uint l = (uint)(x >> 32);
 408                 uint r = (uint)x;
 409                 uint t;
 410                 t = ((l >>  1) ^ r) & 0x55555555;
 411                 r ^= t;
 412                 l ^= t <<  1;
 413                 t = ((r >>  8) ^ l) & 0x00FF00FF;
 414                 l ^= t;
 415                 r ^= t <<  8;
 416                 t = ((r >>  2) ^ l) & 0x33333333;
 417                 l ^= t;
 418                 r ^= t <<  2;
 419                 t = ((l >> 16) ^ r) & 0x0000FFFF;
 420                 r ^= t;
 421                 l ^= t << 16;
 422                 t = ((l >>  4) ^ r) & 0x0F0F0F0F;
 423                 r ^= t;
 424                 l ^= t <<  4;
 425                 x = ((ulong)l << 32) | (ulong)r;
 426                 return x;
 427         }
 428
 429         /*
 430          * Apply a permutation or extraction. For all k, bit k of the
 431          * output (right-to-left numbering) is set if and only if the
 432          * source bit in x defined by the tab[k] mask is set.
 433          */
 434         static ulong Perm(ulong[] tab, ulong x)
 435         {
 436                 ulong y = 0;
 437                 for (int i = 0; i < tab.Length; i ++) {
 438                         if ((x & tab[i]) != 0) {
 439                                 y |= (ulong)1 << i;
 440                         }
 441                 }
 442                 return y;
 443         }
 444
 445         static uint FConf(uint r0, ulong sk)
 446         {
 447                 uint skhi = (uint)(sk >> 24);
 448                 uint sklo = (uint)sk;
 449                 uint r1 = (r0 >> 16) | (r0 << 16);
 450                 return
 451                           S1[((r1 >> 11) ^ (skhi >> 18)) & 0x3F]
 452                         | S2[((r0 >> 23) ^ (skhi >> 12)) & 0x3F]
 453                         | S3[((r0 >> 19) ^ (skhi >>  6)) & 0x3F]
 454                         | S4[((r0 >> 15) ^ (skhi      )) & 0x3F]
 455                         | S5[((r0 >> 11) ^ (sklo >> 18)) & 0x3F]
 456                         | S6[((r0 >>  7) ^ (sklo >> 12)) & 0x3F]
 457                         | S7[((r0 >>  3) ^ (sklo >>  6)) & 0x3F]
 458                         | S8[((r1 >> 15) ^ (sklo      )) & 0x3F];
 459         }
 460
 461         /*
 462          * 64-bit big-endian decoding.
 463          */
 464         static ulong Dec64be(byte[] buf, int off)
 465         {
 466                 return ((ulong)buf[off] << 56)
 467                         | ((ulong)buf[off + 1] << 48)
 468                         | ((ulong)buf[off + 2] << 40)
 469                         | ((ulong)buf[off + 3] << 32)
 470                         | ((ulong)buf[off + 4] << 24)
 471                         | ((ulong)buf[off + 5] << 16)
 472                         | ((ulong)buf[off + 6] << 8)
 473                         | (ulong)buf[off + 7];
 474         }
 475
 476         /*
 477          * 64-bit big-endian encoding.
 478          */
 479         static void Enc64be(ulong v, byte[] buf, int off)
 480         {
 481                 buf[off + 0] = (byte)(v >> 56);
 482                 buf[off + 1] = (byte)(v >> 48);
 483                 buf[off + 2] = (byte)(v >> 40);
 484                 buf[off + 3] = (byte)(v >> 32);
 485                 buf[off + 4] = (byte)(v >> 24);
 486                 buf[off + 5] = (byte)(v >> 16);
 487                 buf[off + 6] = (byte)(v >> 8);
 488                 buf[off + 7] = (byte)v;
 489         }
 490 }
 491
 492 }