🚀 go-pugleaf

In article <1993Jan27.025903.27664@ole.cdac.com>, ray@ole.cdac.com (Ray Berry) 
writes:

|>    It seems to me that permuting the order of characters [bytes] in an
|> encrypted file would be valuable in hiding the structure, e.g. fixed
|> headers, 'magic' characters, etc., which might otherwise facilitate a
|> "chosen plain-text" decryption attack.
|>
|>    To that end, can anyone offer guidance on efficient algorithms which 
|> can generate file-length permutations which could be seeded by a password?

Sorting and shuffling are in some sense inverse operations, so if you have a 
good sorting routine, you can adapt it quite simply to shuffle a file.

For example, perform the algorithm `mergesort' with the modification that
whenever the algorithm needs to make a decision, you just use the next bit
of your key rather than checking whether a < b for some a and b.

If your file is n characters long, this uses nlogn key bits (exactly what you 
need to specify an element of S_n) and O(nlogn) operations, so it's fairly
efficient. It also lets you reuse existing code.

This idea occurred to Roger Needham and myself one day while waiting for the
lift. It didn't seem a big enough idea to publish on its own, but it might be
useful as part of some bigger system,

Ross

(PS: now you probably have to lie about any sorting software you take through 
US customs, as well as about modular arithmetic routines!)