/*----- Main code ---------------------------------------------------------*/
-/* --- @permute@ --- *
- *
- * Arguments: @const char *p@ = pointer to permutation table
- * @uint32 a, b@ = source value to permute
- * @uint32 *d@ = destination for value
- *
- * Returns: ---
- *
- * Use: Performs a 64-bit permutation. The table is given in the
- * normal (but bizarre) DES bit numbering system. That's not to
- * say that the tables in this source file are like the normal
- * DES tables, because they're not.
- */
-
-static void permute(const char *p, uint32 a, uint32 b, uint32 *d)
-{
- uint32 x = 0, y = 0;
- int i;
-
- for (i = 0; i < 32; i++) {
- int q = p[i];
- uint32 t;
- if (!q)
- continue;
- else if (q <= 32)
- t = a;
- else {
- t = b;
- q -= 32;
- }
- if (t & (1 << (32 - q)))
- x |= (1 << (31 - i));
- }
-
- p += 32;
-
- for (i = 0; i < 32; i++) {
- int q = p[i];
- uint32 t;
- if (!q)
- continue;
- else if (q <= 32)
- t = a;
- else {
- t = b;
- q -= 32;
- }
- if (t & (1 << (32 - q)))
- y |= (1 << (31 - i));
- }
-
- d[0] = x;
- d[1] = y;
-}
-
/* --- @des_expand@ --- *
*
* Arguments: @const octet *k@ = pointer to key material
void des_init(des_ctx *k, const void *buf, size_t sz)
{
- uint32 x, y;
+#define REGWD 32
+ typedef uint32 regty;
+
+ uint32 x, y, u, v;
uint32 *kp = k->k;
- uint32 ka[2];
int i;
- /* --- @pc1@ --- *
- *
- * This cryptographically useless permutation is used to mangle the key
- * before it's subjected to the key schedule proper. I've not actually
- * messed it about much except for inserting padding at the beginning of
- * the two halves of the key.
- */
-
- static const char pc1[] = {
- 0, 0, 0, 0,
- 57, 49, 41, 33, 25, 17, 9,
- 1, 58, 50, 42, 34, 26, 18,
- 10, 2, 59, 51, 43, 35, 27,
- 19, 11, 3, 60, 52, 44, 36,
- 0, 0, 0, 0,
- 63, 55, 47, 39, 31, 23, 15,
- 7, 62, 54, 46, 38, 30, 22,
- 14, 6, 61, 53, 45, 37, 29,
- 21, 13, 5, 28, 20, 12, 4
- };
-
- /* --- @pc2@ --- *
- *
- * This irritating but necessary permutation mangles the key between the
- * simple rotation-based schedule and the actual XOR with which it modifies
- * the behaviour of the cipher.
- *
- * This version of the table doesn't look much like the original. This is
- * because some parts of the world have been permuted in order to make
- * things simpler for the round function. In particular, everything is
- * rotated left one place to avoid problems with the wraparound of the
- * expansion permutation, and the key is split between odd and even S-boxes
- * rather than high and low ones. That's without the complication of the
- * padding bits in the representation of the 56-bit proto-key.
- */
-
- static const char pc2[] = {
- 0, 0, 3 + 4, 28 + 4, 15 + 4, 6 + 4, 21 + 4, 10 + 4, /* S-box 2 */
- 0, 0, 16 + 4, 7 + 4, 27 + 4, 20 + 4, 13 + 4, 2 + 4, /* S-box 4 */
- 0, 0, 30 + 8, 40 + 8, 51 + 8, 45 + 8, 33 + 8, 48 + 8, /* S-box 6 */
- 0, 0, 46 + 8, 42 + 8, 50 + 8, 36 + 8, 29 + 8, 32 + 8, /* S-box 8 */
- 0, 0, 14 + 4, 17 + 4, 11 + 4, 24 + 4, 1 + 4, 5 + 4, /* S-box 1 */
- 0, 0, 23 + 4, 19 + 4, 12 + 4, 4 + 4, 26 + 4, 8 + 4, /* S-box 3 */
- 0, 0, 41 + 8, 52 + 8, 31 + 8, 37 + 8, 47 + 8, 55 + 8, /* S-box 5 */
- 0, 0, 44 + 8, 49 + 8, 39 + 8, 56 + 8, 34 + 8, 53 + 8 /* S-box 7 */
- };
-
- /* --- @v@ --- *
+ /* --- @r@ --- *
*
* Contains the rotation amounts for the key halves.
*/
- static const char v[] = {
+ static const char r[] = {
1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
};
KSZ_ASSERT(des, sz);
des_expand(buf, sz, &x, &y);
- /* --- Permute using the pointless PC1 --- */
+ /* --- Permute using the pointless PC1 --- *
+ *
+ * For reference, the original PC1 permutation is
+ *
+ * Left half 57 49 41 33 25 17 9
+ * 1 58 50 42 34 26 18
+ * 10 2 59 51 43 35 27
+ * 19 11 3 60 52 44 36
+ *
+ * Right half 63 55 47 39 31 23 15
+ * 7 62 54 46 38 30 22
+ * 14 6 61 53 45 37 29
+ * 21 13 5 28 20 12 4
+ *
+ * The network below implements this pretty directly; the two 28-bit halves
+ * end up in the least significant bits of the two output words; the parity
+ * bits, which are formally discarded, end up in the top 4 bits of each
+ * half in some random order, and are finally masked off so that they don't
+ * interfere with the rotation below. (I did an exhaustive search, and
+ * there are no better Beneš networks.)
+ */
- permute(pc1, x, y, ka);
- x = ka[0]; y = ka[1];
+ SWIZZLE_2(x, y, 1, 0x55005401, 0x55005500);
+ SWIZZLE_2(x, y, 2, 0x32320101, 0x33330000);
+ TWIZZLE_0(x, y, 0xf0e1f0f1);
+ SWIZZLE_2(x, y, 4, 0x0f0e0f0f, 0x08050201);
+ SWIZZLE_2(x, y, 8, 0x005a003a, 0x005a005a);
+ SWIZZLE_2(x, y, 16, 0x00007c6c, 0x000023cc);
+ TWIZZLE_0(x, y, 0x20f1e0f0);
+ SWIZZLE_2(x, y, 2, 0x10000333, 0x33201013);
+ SWIZZLE_2(x, y, 1, 0x10055005, 0x10455005);
+ x &= 0x0fffffff; y &= 0x0fffffff;
/* --- Now for the key schedule proper --- */
for (i = 0; i < 16; i++) {
- if (v[i] == 1) {
+ if (r[i] == 1) {
x = ((x << 1) | (x >> 27)) & 0x0fffffff;
y = ((y << 1) | (y >> 27)) & 0x0fffffff;
} else {
x = ((x << 2) | (x >> 26)) & 0x0fffffff;
y = ((y << 2) | (y >> 26)) & 0x0fffffff;
}
- permute(pc2, x, y, kp);
- kp += 2;
+
+ /* --- Apply PC2, which is another Beneš network --- *
+ *
+ * The original permutation is described as follows.
+ *
+ * S-box 1: 14 17 11 24 1 5
+ * S-box 2: 3 28 15 6 21 10
+ * S-box 3: 23 19 12 4 26 8
+ * S-box 4: 16 7 27 20 13 2
+ * S-box 5: 41 52 31 37 47 55
+ * S-box 6: 30 40 51 45 33 48
+ * S-box 7: 44 49 39 56 34 53
+ * S-box 8: 46 42 50 36 29 32
+ *
+ * Firstly, note the way that the key bits are arranged in the words @x@
+ * and @y@: viewed from the way DES numbers bits from the most-
+ * significant end down, there are four padding bits in positions 1--4,
+ * and another four in positions 33--36. Because the bits in the left-
+ * hand half of the key all feed into the first four S-boxes, we must
+ * adjust the bit positions by 4; and we must adjust the positions of the
+ * bits in the right-hand half by 8.
+ *
+ * Secondly, this isn't how we want to apply the key. The formal
+ * description of DES includes an `expansion' %$E$%: essentially, we take
+ * each chunk of four bits in the 32-bit half block, and glue on the
+ * nearest bits from the preceding and following chunk to make a six-bit
+ * chunk, which we then XOR with six bits of key and feed into the S-box
+ * to collapse back down to four bits. We avoid having to do this in
+ * practice by doing the S-boxes in two steps: first, the even-numbered
+ * ones and then the odd-numbered ones. Because these two collections of
+ * S-boxes don't involve overlapping input bits, we can just XOR in the
+ * correct key bits and apply the substitution. There's one more little
+ * problem, which is that the input to the final S-box needs the topmost
+ * bit of the input half-block, which we handle by having previously
+ * rotated the message block left by one position. And that's the
+ * permutation that we implement here.
+ *
+ * There are too many blank spaces to search exhaustively for an optimal
+ * network. Based on my experience with PC1, I don't expect the optimal
+ * network to be significantly better than this one.
+ */
+
+ u = x; v = y;
+ SWIZZLE_2(u, v, 1, 0x10551050, 0x05500504);
+ SWIZZLE_2(u, v, 2, 0x12131230, 0x33102201);
+ SWIZZLE_2(u, v, 8, 0x00a200ec, 0x009100ba);
+ SWIZZLE_2(u, v, 16, 0x000012ab, 0x000028e0);
+ SWIZZLE_2(u, v, 4, 0x0a090805, 0x0b040002);
+ TWIZZLE_0(u, v, 0x33856c2a);
+ SWIZZLE_2(u, v, 16, 0x00003385, 0x00004c6a);
+ SWIZZLE_2(u, v, 8, 0x001500c8, 0x004700e8);
+ SWIZZLE_2(u, v, 2, 0x20130212, 0x00310022);
+ SWIZZLE_2(u, v, 1, 0x05404145, 0x54510510);
+ kp[0] = u; kp[1] = v; kp += 2;
}
+
+#undef REGWD
}
/* --- @des_eblk@, @des_dblk@ --- *
~mdw / catacomb / blobdiff