# 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:

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.

Shortest code wins.

• 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 Nov 14 '12 at 22:03
• sorry, i ignored your clearly labeled link to the table data – ardnew Nov 14 '12 at 22:10
• 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 Nov 15 '12 at 4:23
• Random 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 Nov 15 '12 at 14:57
• @loneboat Redeem yourself! :D – jdstankosky Nov 15 '12 at 20:38

## 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

• Do those strings not benefit from a higher base (e.g. base64)? – Peter Taylor Nov 16 '12 at 8:01
• yep, thanks @PeterTaylor. i had to find a library that would treat the the strings as large integers transparently – ardnew Nov 16 '12 at 18:48

## 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:

1. 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).
2. 49281 2B{!) ... } encodes the shift lengths. This is the most obvious place to attempt further optimisation.
3. 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).