Do you know where your variables are? PerlMonks

### Re^2: Compressing and Encrypting files on Windows

by jon_barber (Initiate)
 on Nov 02, 2004 at 11:23 UTC Need Help??

By definition a decent encryption algorithm will turn '0'x1000000 into random (and thus totally uncompressable noise).
...
This is a simple measure of the quality of the encryption - the compression algorithm can no longer see any patterns (and we know the plaintext has patterns).

I don't think this is true of one time pads. I can imagine a situation where a OTP could produce output that could then be highly compressed. Of course, this is a special case nitpick :).

• Comment on Re^2: Compressing and Encrypting files on Windows

Replies are listed 'Best First'.
Re^3: Compressing and Encrypting files on Windows
by tachyon (Chancellor) on Nov 02, 2004 at 22:34 UTC
What on earth makes you think data encrypted with a one time pad contains redundant data repeats and can thus be compressed? Please see Elgons note at Re^2: Compressing and Encrypting files on Windows and follow the link.

What makes you think that a OTP pad doesn't contain redundant repeats? As I understand it, a OTP operates by applying randomly generated data (the OTP) to the data that you wish to encrypt. To decrypt it you then reverse the transformation with the same OTP.

Given that the OTP is randomly generated, is it not possible to imagine that it might produce a cyphertext which did contain redundant data repeats and could therefore be highly compressable?

As I stated in my original comment, it was a nitpick over the definition that "a decent encryption algorithm would produce ... noise."

Given that the OTP is randomly generated, is it not possible to imagine that it might produce a cyphertext which did contain redundant data repeats and could therefore be highly compressable?

No, no and no. You are just plain wrong. Random data by definition contains no repeats. If it does it is not random. OTPs depend on that randomness. As you seem resistant to my suggestion to do some research.....

## What is a One-Time Pad?

A one-time pad is a very simple yet completely unbreakable symmetric cipher. "Symmetric" means it uses the same key for encryption as for decryption. As with all symmetric ciphers, the sender must transmit the key to the recipient via some secure and tamperproof channel, otherwise the recipient won't be able to decrypt the ciphertext.

The key for a one-time pad cipher is a string of random bits, usually generated by a cryptographically strong pseudo-random number generator (CSPRNG). It is better to generate the key using the natural randomness of quantum mechanical events (such as those detected by a Geiger counter), since quantum events are believed by many to be the only source of truly random information in the universe. One-time pads that use CSPRNGs are open to attacks which attempt to compute part or all of the key.

With a one-time pad, there are as many bits in the key as in the plaintext. This is the primary drawback of a one-time pad, but it is also the source of its perfect security (see below). It is essential that no portion of the key ever be reused for another encryption (hence the name "one-time pad"), otherwise cryptanalysis can break the cipher.

The cipher itself is exceedlingly simple. To encrypt plaintext, P, with a key, K, producing ciphertext, C, simply compute the bitwise exclusive-or of the key and the plaintext:

C = K^P
To decrypt ciphertext, C, the recipient computes
P = K^C
It's that simple, and it's perfectly secure, as long as the key is random and is not compromised.

## Why Are One-Time Pads Perfectly Secure?

If the key is truly random, an xor-based one-time pad is perfectly secure against ciphertext-only cryptanalysis. This means an attacker can't compute the plaintext from the ciphertext without knowlege of the key, even via a brute force search of the space of all keys! Trying all possible keys doesn't help you at all, because all possible plaintexts are equally likely decryptions of the ciphertext.

This result is true regardless of how few bits the key has or how much you know about the structure of the plaintext. To see this, suppose you intercept a very small, 8-bit, ciphertext. You know it is either the ASCII character 'S' or the ASCII character 'A' encrypted with a one-time pad. You also know that if it's 'S', the enemy will attack by sea, and if it's 'A', the enemy will attack by air. That's a lot to know. All you are missing is the key, a silly little 8-bit one-time pad.

You assign your crack staff of cryptanalysts to try all 256 8-bit one-time pads. This is a brute force search of the keyspace.

The results of the brute force search of the keyspace is that your staff finds one 8-bit key that decrypts the ciphertext to 'S' and one that decrypts it to 'A'. And you still don't know which one is the actual plaintext.

This argument is easilly generalized to keys (and plaintexts) of arbitrary length.

Text taken from here

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://404568]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others having a coffee break in the Monastery: (3)
As of 2024-02-24 23:39 GMT
Voting Booth?
My favourite way to spend a leap day ...

Results (23 votes). Check out past polls.