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