[603] in cryptography@c2.net mail archive
Re: The unmentionable algorithm
daemon@ATHENA.MIT.EDU (Steven Bellovin)
Mon Apr 21 13:29:46 1997
To: jamesd@echeque.com, Adam Back <aba@dcs.ex.ac.uk>, coderpunks@toad.com,
cryptography@c2.net
Date: Sun, 20 Apr 1997 21:40:42 -0400
From: Steven Bellovin <smb@research.att.com>
I promised not to say anything more, but I couldn't resist.
DES really is easy to describe. The implementation problems arise
because we generally use languages that are too low-level. This is
it:
for i = 1 to 16
l[i] = r[i-1]
r[i] = l[i-1] XOR f(R[i-1], K[i])
where K is the key schedule array, and l[i] and r[i] are the left
and right halves of the operation after round i.
The f function isn't much more complex if your programming language
has the right primitives, to wit the ability to subscript an array
with an array, and get an array as a result. APL has that ability (and
did more than 30 years ago -- it's interesting to muse on the fact
that APL was very popular at IBM in the late 1960s and early 1970s,
when DES was being developed); in more modern terms, I could easily
write the necessary classes in C++. (It would look a bit messier
in Java, since one can't redefine the [] operator to work on user-defined
classes. But the semantics would be the same.)
f(R, K) = P[S(E[R] XOR K)]
P and E are expressed as arrays, per my description. S is expressed as
a function, because for sanity's sake it has to operate on 6-bit chunks.
But the operation on each chunk is simply subscripting an array.
What have I left out? Nothing complex. There are initial and final
permutations; those are array operations. And there's the key setup --
also a group of permutations, and hence easily represented as array
operations.
I didn't come up with this, of course; DES is *defined* that way, in
more or less that notation, in the FIPS. If you want, have a look at
http://www.itl.nist.gov/div897/pubs/fip46-2.htm.
