Implement DES key expansion

I wanted to make a challenge to do the full DES encryption algorithm, but that may be a bit too involved to get a ton of participation. This challenge is to simply generate the 16 48-bit subkeys used to encrypt data:

key schedule

The algorithm is described well enough on wikipedia, and all relevant shift tables and such data are on this page.

Your task is to write a program or function that accepts 64 bits of input, and outputs the 16 48-bit keys. I am not picky about input or output formats, but hex coded is fairly standard.

You can check your results against the examples on this page, or this page

Shortest code wins.

captncraig

Posted 2012-11-14T21:05:16.757

Reputation: 4 373

you're wanting the 16 48-bit keys generated before running through the S-Box phase? or do we need to implement those lookup tables too (and which tables should we use)? – ardnew – 2012-11-14T22:03:58.207

sorry, i ignored your clearly labeled link to the table data – ardnew – 2012-11-14T22:10:05.617

I just want the subkeys (the outputs on the left side of the diagram). Also labelled KS[1] to KS[16] when you run the first example link. – captncraig – 2012-11-15T04:23:12.547

7Random story: One of my most embarrassing programming stories from college (Computer Science) was with a DES implementation for a crypto class. As usual I procrastinated, and when I had trouble getting bit-shifting working correctly the night before it was due, I changed tack and wrote a fully-functional DES implementation using String variables/operations. Yes, I mean literally strings like, "01011100" - ASCII strings of "0" and "1". Instructor never commented on it. As long as it ran, he was happy. I have been ashamed of this for 5 years now; never told anybody before today. – loneboat – 2012-11-15T14:57:01.337

That's funny, but probably significantly easier to work with as strings than the bitwise arithmetic required to keep it all in binary. – captncraig – 2012-11-15T17:14:08.933

1@loneboat Redeem yourself! :D – jdstankosky – 2012-11-15T20:38:34.550

The test cases have gone missing. – Peter Taylor – 2013-06-10T15:13:37.217

Answers

Perl - 384 314 chars

input is in decimal (from STDIN), output in binary. includes all necessary tables. feel free to improve anything

use Math'BaseConvert b10;
@_=sprintf("%064b",<>)=~/./g;
$s=b10 cG4xqQ8GMvUpZSqYtTAVVCZyBjrZs7FkNdowNTFBipcmG28UIKQKyfLYHWWjdq;
$s=~s/../$_[$&-1]/g;
map{
  $n=28-$_;
  $s=~s/(.{$_})(.{$n})(.{$_})(.+)/$2$1$4$3/;
  $_=b10"G._NqruyC5whI_KjAHzrS3ZgLTX7BzGp0.zML.AaubJCuwPtzPomq";
  s|..|($s=~/./g)[$&-1]|eg;
  say$_
}b10("3_AUuKOqD")=~/./g

ardnew

Posted 2012-11-14T21:05:16.757

Reputation: 2 177

1Do those strings not benefit from a higher base (e.g. base64)? – Peter Taylor – 2012-11-16T08:01:04.103

yep, thanks @PeterTaylor. i had to find a library that would treat the the strings as large integers transparently – ardnew – 2012-11-16T18:48:07.313

GolfScript (175 chars)

I assume input and output in MSB-first upper-case hex.

For want of good test cases, I don't guarantee that this implementation is correct. I've worked to a test case which I derived from Rivest's simple test for implementations of DES: given his test input of 9474B8E8C73BCA7D I think that the expected output is

BE23F4265E76
63FD57CA5952
6DEDC3C5E33C
73E5BBF11EC8
FD8593D8923F
778A9F177EAC
3FB0963839F1
3E0CFEA3E837
41FFD1A34BCB
55FDE796B313
F3E5C3F70764
79C7A758ABCA
F1919F74F41D
3582F76B34EA
B758B6ACF92B
44FF4B3F4D29

To that caveat I must add another, which is that I use a lot of base conversion including some of strings with non-printable characters. As usual, I'll give the program in a couple of ASCII-safe formats. xxd output:

0000000: 312f 7b31 302c 2727 2a37 312c 3635 3e2b  1/{10,''*71,65>+
0000010: 3a5e 5c3f 3136 2b32 7b62 6173 657d 3a42  :^\?16+2{base}:B
0000020: 7e28 3b7e 7d25 607b 3d7d 2b5b 3536 5b5b  ~(;~}%`{=}+[56[[
0000030: 2d38 5d32 342a 372f 2e2b 2739 3939 1b37  -8]24*7/.+'999.7
0000040: 3717 275d 7a69 705b 5d2a 5b5d 2a7b 3124  7.']zip[]*[]*{1$
0000050: 2b7d 2f5d 2534 3932 3831 2032 427b 2129  +}/]%49281 2B{!)
0000060: 7b32 382f 7b28 2b7d 257e 2b7d 2a27 1d3c  {28/{(+}%~+}*'.<
0000070: f9df 2a9b 7079 2030 dea2 83df 3bca a82f  ..*.py 0....;../
0000080: 50ec 11f8 e55c 74d2 f104 b2ae 130e ac5c  P....\t........\
0000090: d627 27ff 3827 7b42 7d2f 7b31 243d 7d25  .''.8'{B}/{1$=}%
00000a0: 342f 7b32 425e 3d7d 256e 2b5c 7d2f 3b    4/{2B^=}%n+\}/;

Base-64 encoded:

MS97MTAsJycqNzEsNjU+KzpeXD8xNisye2Jhc2V9OkJ+KDt+fSVgez19K1s1NltbLThdMjQqNy8u
Kyc5OTkbNzcXJ116aXBbXSpbXSp7MSQrfS9dJTQ5MjgxIDJCeyEpezI4L3soK30lfit9KicdPPnf
KptweSAw3qKD3zvKqC9Q7BH45Vx00vEEsq4TDqxc1icn/zgne0J9L3sxJD19JTQvezJCXj19JW4r
XH0vOw==

And with the magic strings substituted with a printable (but longer) version using escape characters and some unnecessary line-breaks:

1/{10,''*71,65>+:^\?16+2{base}:B~(;~}%`{=}+
[56[[-8]24*7/.+'999\e77\027']zip[]*[]*{1$+}/]
%49281 2B{!){28/{(+}%~+}*
'\035<\371\337*\233py 0\336\242\203\337;\312\250/P\354\021\370\345\\t\322\361\004\262\256\023\016\254\\\326'
'\3778'{B}/{1$=}%4/{2B^=}%n+\}/;

This is a pretty literal translation. The vaguely interesting bits are:

Permutation PC1 turns out to have a lot of structure. If you take first differences, all but 6 of them are -8. The second line of the reformatted version reconstructs it from these differences in 39 characters. For comparison, representing it by base conversion would require 44 characters for the string literal; and representing a generic permutation of numbers 1 to 63 requires 36 base-256 digits (i.e. a 38-character string literal plus code to convert it).
49281 2B{!) ... } encodes the shift lengths. This is the most obvious place to attempt further optimisation.
Permutation PC2 doesn't seem to have any usable structure, so that's a straight double base conversion. (Not to be confused with a double bass conversion).

Peter Taylor

Posted 2012-11-14T21:05:16.757

Reputation: 41 901