From dawagner@tucson.princeton.edu Thu Jul 27 09:08:01 EDT 1995
Article: 37658 of sci.crypt
Path: cnn.Princeton.EDU!tucson.princeton.edu!dawagner
From: dawagner@tucson.princeton.edu (David A. Wagner)
Newsgroups: sci.crypt
Subject: Re: Null transformations in DES
Date: 27 Jul 1995 12:33:32 GMT
Organization: Princeton University
Lines: 45
Message-ID: <3v812s$c62@cnn.Princeton.EDU>
References: <3v00u6$ami@wombat.melbpc.org.au>
NNTP-Posting-Host: tucson.princeton.edu
In article <3v00u6$ami@wombat.melbpc.org.au>,
Steve Roberts wrote:
> Does anyone know of any null transforms using DES?
> That is, where encryption produces a result
> identical to the original text.
I've seen these called fixed points.
I think I remember that the weak keys have about 2^32 fixed points.
If I remember correctly, Don Coppersmith has a paper explaining this
(and various consequences of this); see below. If this correct, you
should be able to easily find an explicit example of this by trying
2^32 random plaintexts -- or maybe Coppersmith's paper shows an easier
way to find fixed points of weak keys, I forget.
If we assume that DES behaves like a random permutation for a fixed
unknown key (in other words, assume that DES is secure) then it's
possible to calculate the expected number of fixed points, etc.
In particular, a permutation with no fixed points is known (in math
circles) as a derangement, and it's a fun exercise to show that the
probability of getting a derangement is almost exactly 1/e.
Also, from the fact that about n!/e of the n! permutations are
derangements, it's fairly easy to calculate that about
C(n,m) (n-m)!/e = n! / (m! e) of the n! permutations have exactly
m fixed points, and the expected number of fixed points is 1.
Thus, we'd expect to get no fixed points for about 1/e of the keys,
and just 1 fixed point for about 1/e more of the keys, and 2 fixed
points for 1/2e of the keys, etc.
@inproceedings{weak-key-cycles,
author = {Don Coppersmith},
title = {The Real Reason for {Rivest's} Phenomenon},
booktitle = {Advances in Cryptology: {CRYPTO} '85},
pages = {535--536},
publisher = {Springer-Verlag},
year = {1986}
}
-------------------------------------------------------------------------------
David Wagner dawagner@princeton.edu