home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / crypt / 6457 < prev    next >
Encoding:
Text File  |  1993-01-06  |  2.0 KB  |  42 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!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: Encryption plus compression (Was: Another well-intentioned novice's quest)
  5. Sender: news@news.uiowa.edu (News)
  6. Message-ID: <1993Jan6.221731.23956@news.uiowa.edu>
  7. Date: Wed, 6 Jan 1993 22:17:31 GMT
  8. References: <1993Jan6.215140.18753@ee.eng.ohio-state.edu>
  9. Nntp-Posting-Host: pyrite.cs.uiowa.edu
  10. Organization: University of Iowa, Iowa City, IA, USA
  11. Lines: 29
  12.  
  13. From article <1993Jan6.215140.18753@ee.eng.ohio-state.edu>,
  14. by butzerd@blanc.eng.ohio-state.edu (Dane C. Butzer):
  15. > 
  16. > Sorry if this has been brought up, but don't many compression programs put
  17. > some type of table at the start of the compressed file (defining what
  18. > characters map to what uncompressed sequences, for example)?
  19.  
  20. Yes, and such programs shouldn't be used in the context of encryption, for
  21. the reasons you suppose.
  22.  
  23. LZW and other adaptive compression algorithms don't put such tables there
  24. because they start with an initial table that is fixed and then adapt this
  25. table to the statistics of the data being compressed.  (As an aside, to
  26. use such compresson algorithms to do encryption, make this initial table
  27. a function of the key instead of a constant).
  28.  
  29. In the case of LZW, the initial table is typically a mapping from single
  30. characters to themselves (but with a 9th bit tacked on to indicate that
  31. the characters are sequences of length 1).  This makes LZW somewhat
  32. vulnerable to analysis, but the simple expedient of prefixing the text to
  33. be compressed with a fixed length string of random bytes (prior to
  34. compression) and then discarding these when the string is uncompressed
  35. can eliminate this problem.
  36.  
  37. In the case of LZW, I believe this string has to be fairly long.  In the
  38. case of my splay-tree based compression algorithm, a fairly short string
  39. will suffice.
  40.                 Doug Jones
  41.                 jones@cs.uiowa.edu
  42.