home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / crypt / 3822 < prev    next >
Encoding:
Text File  |  1992-10-16  |  2.1 KB  |  50 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!pipex!pavo.csi.cam.ac.uk!cam-cl!rja14
  3. From: rja14@cl.cam.ac.uk (Ross Anderson)
  4. Subject: Re: DES generates A_(2^64)?
  5. Message-ID: <1992Oct16.094217.6932@infodev.cam.ac.uk>
  6. Sender: news@infodev.cam.ac.uk (USENET news)
  7. Nntp-Posting-Host: ely.cl.cam.ac.uk
  8. Reply-To: rja14@cl.cam.ac.uk (Ross Anderson)
  9. Organization: U of Cambridge, England
  10. References: <1992Oct13.174505.24230@b11.b11.ingr.com> <1992Oct15.125830.25539@bnr.ca> <PHR.92Oct15174530@napa.telebit.com>
  11. Date: Fri, 16 Oct 1992 09:42:17 GMT
  12. Lines: 36
  13.  
  14. In <PHR.92Oct15174530@napa.telebit.com>,  phr@telebit.com (Paul Rubin) writes:
  15.  
  16.     Michael Wiener and I submitted a paper to Crypto '92 entitled "DES is not
  17.     a Group". The principal argument is as follows.
  18.  
  19.     Consider the closure of DES encryptions under composition.  Our claim is
  20.     that this group must include permutations which are not equivalent to DES
  21.     encryption with any key.  Each of the n_i collected above must divide
  22.     the order of the group.  Compute n = lcm( n_i, i=1..k ).  If n > 2^56 then
  23.     the group must be larger than the set of DES encryptions.
  24.  
  25.     ...
  26.  
  27.     I heard that someone in Eastern Germany recently proved a stronger
  28.     result, that DES generates the alternating group on 2^64 letters.
  29.     This had been conjectured a while ago, though I don't know what the
  30.     evidence for it was.  Anyone know more about this?
  31.  
  32. Here is an abstract of the relevant paper:
  33.  
  34.  {\bf \noindent R Wernsdorf,}{\em ~Eurocrypt 92\\}
  35.  {\bf `The One-round Functions of DES Generate the Alternating Group'}
  36.  
  37.  Each round of DES consists of $2^{48}$ permutations. The group which they
  38.  generate is shown to be 3-transitive, and if this were not equal to
  39.  $A_{2^{64}}$, then it would have a unique minimal normal subgroup which is
  40.  Abelian or simple. The former is excluded by displaying a permutation with
  41.  too many fixed points, and the latter by the classification theory of
  42.  simple groups.
  43.  
  44. With luck we'll have the first issue of `Computer and Communications Security
  45. Abstracts' out shortly: it will contain abstracts like this of current
  46. research papers.
  47.  
  48. Ross Anderson
  49.  
  50.