[cryptography] One Time Pad Cryptanalysis

Sandy Harris sandyinchina at gmail.com
Thu Oct 17 11:09:13 EDT 2013

Ben Laurie <ben at links.org> wrote:

>> |   Encryption is time-consuming; compressing a file before encryption
>> |   speeds up the process.
> I haven't benchmarked it, but I find it unlikely that compression is faster
> than encryption.

It can be if weak compression is acceptable. That may not be worth the
trouble, but it is certainly possible.

If the input is English text, then space is much the commonest
character, about one in seven.  If the encoding is ASCII, then the top
bit of every byte is zero. You can get >10% compression with a fast
dumb algorithm that just deletes spaces and sets the top bit of the
following character to indicate where to re-insert them. Any newline
not followed immediately by another can be removed the same way if
format is not an issue. A somewhat smarter method that replaces common
sequences like 'the' or 'ing' with single non-ASCII bytes can also be
fast and would probably give quite a bit better compression.

Where problems appear is if you try to be clever and adaptive; that is
clearly necessary for optimal compression, but perhaps not for useful
compression. It has higher overheads
and it requires some sort of header to tell the receiver about the
compression, which introduces a known plaintext risk.

More information about the cryptography mailing list