Re: "complementary pairs of keys"

Justin Dolske (dolske@cis.ohio-state.edu)
Sun, 4 May 1997 21:02:39 -0400 (EDT)


On Sun, 4 May 1997, Trent Piepho wrote:

> This sounds like each key has another which will produce identical results.
> So, given that a key K isn't the correct key, it follows that its complement
> K' is also not the correct key. Am I totally wrong here, or is this on
> track?

It doesn't quite work out that way... :-)

[I'll use a little funny notation now: P<-K=C This means when the
plaintext P is "modified" with the key K, the cyphertext C is the result.
And, since DES is a symmetric cypher, the reverse is (must be) true:
C<-K=P]

DES has the somewhat interesting property where if P<-K=C, P'<-K'=C'. That
is, the modifying the complement of P with the complement of K gives the
complement of C.

You can't really make use of this to directly speed up the keysearch,
though. That's because to find out anything about K', you need to modify
P', not P -- which means you've got to do the whole DES encryptino process
again. Ie, P<-K=C does not imply P<-K'=C'

Justin Dolske <URL:http://www.cis.ohio-state.edu/~dolske/>
(dolske@cis.ohio-state.edu)
Graduate Fellow / Research Associate at The Ohio State University, CIS Dept.
-=-=-=-=-=-=-=-=-=-=-=-=-=- Random Sig-o-Matic (tm) -=-=-=-=-=-=-=-=-=-=-=-=-
"In wildness is the preservation of the world."
-- Henry David Thoreau