home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / crypt / 7160 < prev    next >
Encoding:
Text File  |  1993-01-27  |  1.8 KB  |  43 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!inmos!fulcrum!bham!warwick!pavo.csi.cam.ac.uk!rja14
  3. From: rja14@cl.cam.ac.uk (Ross Anderson)
  4. Subject: How to do filelength permutations
  5. Message-ID: <1993Jan27.120759.27430@infodev.cam.ac.uk>
  6. Sender: news@infodev.cam.ac.uk (USENET news)
  7. Nntp-Posting-Host: ely.cl.cam.ac.uk
  8. Organization: U of Cambridge Computer Lab, UK
  9. References: <1993Jan27.025903.27664@ole.cdac.com>
  10. Date: Wed, 27 Jan 1993 12:07:59 GMT
  11. Lines: 30
  12.  
  13. In article <1993Jan27.025903.27664@ole.cdac.com>, ray@ole.cdac.com (Ray Berry) 
  14. writes:
  15.  
  16. |>    It seems to me that permuting the order of characters [bytes] in an
  17. |> encrypted file would be valuable in hiding the structure, e.g. fixed
  18. |> headers, 'magic' characters, etc., which might otherwise facilitate a
  19. |> "chosen plain-text" decryption attack.
  20. |>
  21. |>    To that end, can anyone offer guidance on efficient algorithms which 
  22. |> can generate file-length permutations which could be seeded by a password?
  23.  
  24. Sorting and shuffling are in some sense inverse operations, so if you have a 
  25. good sorting routine, you can adapt it quite simply to shuffle a file.
  26.  
  27. For example, perform the algorithm `mergesort' with the modification that
  28. whenever the algorithm needs to make a decision, you just use the next bit
  29. of your key rather than checking whether a < b for some a and b.
  30.  
  31. If your file is n characters long, this uses nlogn key bits (exactly what you 
  32. need to specify an element of S_n) and O(nlogn) operations, so it's fairly
  33. efficient. It also lets you reuse existing code.
  34.  
  35. This idea occurred to Roger Needham and myself one day while waiting for the
  36. lift. It didn't seem a big enough idea to publish on its own, but it might be
  37. useful as part of some bigger system,
  38.  
  39. Ross
  40.  
  41. (PS: now you probably have to lie about any sorting software you take through 
  42. US customs, as well as about modular arithmetic routines!)
  43.