home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / crypt / 6349 < prev    next >
Encoding:
Text File  |  1993-01-04  |  2.4 KB  |  51 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!spool.mu.edu!uwm.edu!zaphod.mps.ohio-state.edu!moe.ksu.ksu.edu!hobbes.physics.uiowa.edu!news.uiowa.edu!news
  3. From: jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879)
  4. Subject: Re: Another well-intentioned novice's question
  5. Sender: news@news.uiowa.edu (News)
  6. Message-ID: <1993Jan4.142817.8171@news.uiowa.edu>
  7. Date: Mon, 4 Jan 1993 14:28:17 GMT
  8. References: <1993Jan04.051300.26089@rat.csc.calpoly.edu>
  9. Nntp-Posting-Host: pyrite.cs.uiowa.edu
  10. Organization: University of Iowa, Iowa City, IA, USA
  11. Lines: 38
  12.  
  13. From article <1993Jan04.051300.26089@rat.csc.calpoly.edu>,
  14. by rteasdal@polyslo.csc.calpoly.edu (Rusty):
  15. >                                           ... cryptographic    
  16. > efficiency would be greatly enhanced by compressing a message
  17. > before encrypting it, the better to remove repetitive patterns
  18. > from the plaintext.
  19. > 
  20. >     I don't see, though, that standard (i.e. LZW) compression
  21. > algorithms actually do remove any of the redundancy from the text;
  22.  
  23. If you compress text with a good data compression program, the
  24. compressed text looks like a random bit pattern.  Encrypting one
  25. random looking bit pattern typically produces another, and
  26. cryptanalysis of such patterns is far harder than analysis of
  27. encrypted normal text because the compression process has removed
  28. (some of) the redundancy which cryptanalytical techniques rely on
  29. to break codes.
  30.  
  31. It's also worth noting that many compression algorithms can
  32. themselves be used for (private key) encryption.  The source model
  33. used by the algorithm is, in effect, the key.  For some compression
  34. algorithms, the resulting cryptosystems are pretty weak, but for
  35. others, little is known about their security.
  36.  
  37. For example, I proposed (in CACM, some years ago) an adaptive
  38. compression algorithm based on splay trees (or splay tries?) where
  39. the initial tree used for prefix code construction is the key.  I
  40. have heard nothing about the security of this algorithm since I
  41. published it, although I believe that it is vulnerable to a
  42. controlled text attack (that is, if you can select the text to be
  43. encrypted, you can infer the key that was used).
  44.  
  45. If anyone's curious, I have been distributing a UNIX based data
  46. compression utility based on my algorithm for a number of years.
  47. It's about half the speed of LZW and produces equally compact output
  48. (sometimes better, sometimes worse).
  49.                     Doug Jones
  50.                     jones@cs.uiowa.edu
  51.