Skip to main content
Cryptography

Return to Answer

added 38 characters in body
Source Link
hobbs
hobbs
  • 285
  • 1
  • 8

Assuming that the key is chosen at random, that the key and the message are the same length, and that keys are not reused between messages, then possession of the ciphertext gives you exactly 0 information about the plaintext.

For every bit of ciphertext, there are two possibilities: either the corresponding key bit is 0 and the corresponding plaintext bit is the same as the ciphertext bit; or the key bit is 1 and the plaintext bit is the opposite of the ciphertext bit. By the assumption that the key is unknown and random, both possibilities are equally likely — and by symmetry this is true whether the ciphertext bit was 0 or 1. Therefore our knowledge of the ciphertext cannot do anything to increase our knowledge of the plaintext unless we also have knowledge of the key. The definition of perfection in cryptography is that all security lies in the key, so by this standard OTP is perfect.

This means that if XORing BS1 with cyphertex BS4 results in a compressible BS5, then BS1 is at least part of BS2 or contains part of BS2.

This statement isn't generally valid. You're doing two things implicitly here. First, you're assuming a compression algorithm (hopefully it's a fixed one, otherwise we will never agree what "compressible" means). Then, you're assuming that the correct plaintext is compressible using this algorithm. Perhaps this is true, perhaps it's not. If you assume that it is, then you're assuming prior knowledge about the plaintext. An attempt at "breaking" OTP by decrypting the ciphertext with various keys and seeing which one gives you the best compressibility doesn't give you any additional information, because the OTP decryption is equally likely to produce any given string as input to the compressor, so you might as well simply give the compressor random inputs and see which ones compress well. This will work exactly as well. And if an algorithm that doesn't require the ciphertext as input performs exactly as well as the one you proposed, you can't actually be decrypting anything, can you? You're simply selecting random plausible messages from the prior distribution implied by the compression algorithm itself.

Assuming that the key is chosen at random, that the key and the message are the same length, and that keys are not reused between messages, then possession of the ciphertext gives you exactly 0 information about the plaintext.

For every bit of ciphertext, there are two possibilities: either the corresponding key bit is 0 and the corresponding plaintext bit is the same as the ciphertext bit; or the key bit is 1 and the plaintext bit is the opposite of the ciphertext bit. By the assumption that the key is unknown and random, both possibilities are equally likely — and by symmetry this is true whether the ciphertext bit was 0 or 1. Therefore our knowledge of the ciphertext cannot do anything to increase our knowledge of the plaintext unless we also have knowledge of the key. The definition of perfection in cryptography is that all security lies in the key, so by this standard OTP is perfect.

This means that if XORing BS1 with cyphertex BS4 results in a compressible BS5, then BS1 is at least part of BS2 or contains part of BS2.

You're doing two things implicitly here. First, you're assuming a compression algorithm (hopefully it's a fixed one, otherwise we will never agree what "compressible" means). Then, you're assuming that the correct plaintext is compressible using this algorithm. Perhaps this is true, perhaps it's not. If you assume that it is, then you're assuming prior knowledge about the plaintext. An attempt at "breaking" OTP by decrypting the ciphertext with various keys and seeing which one gives you the best compressibility doesn't give you any additional information, because the OTP decryption is equally likely to produce any given string as input to the compressor, so you might as well simply give the compressor random inputs and see which ones compress well. This will work exactly as well. And if an algorithm that doesn't require the ciphertext as input performs exactly as well as the one you proposed, you can't actually be decrypting anything, can you? You're simply selecting random plausible messages from the prior distribution implied by the compression algorithm itself.

Assuming that the key is chosen at random, that the key and the message are the same length, and that keys are not reused between messages, then possession of the ciphertext gives you exactly 0 information about the plaintext.

For every bit of ciphertext, there are two possibilities: either the corresponding key bit is 0 and the corresponding plaintext bit is the same as the ciphertext bit; or the key bit is 1 and the plaintext bit is the opposite of the ciphertext bit. By the assumption that the key is unknown and random, both possibilities are equally likely — and by symmetry this is true whether the ciphertext bit was 0 or 1. Therefore our knowledge of the ciphertext cannot do anything to increase our knowledge of the plaintext unless we also have knowledge of the key. The definition of perfection in cryptography is that all security lies in the key, so by this standard OTP is perfect.

This means that if XORing BS1 with cyphertex BS4 results in a compressible BS5, then BS1 is at least part of BS2 or contains part of BS2.

This statement isn't generally valid. You're doing two things implicitly here. First, you're assuming a compression algorithm (hopefully it's a fixed one, otherwise we will never agree what "compressible" means). Then, you're assuming that the correct plaintext is compressible using this algorithm. Perhaps this is true, perhaps it's not. If you assume that it is, then you're assuming prior knowledge about the plaintext. An attempt at "breaking" OTP by decrypting the ciphertext with various keys and seeing which one gives you the best compressibility doesn't give you any additional information, because the OTP decryption is equally likely to produce any given string as input to the compressor, so you might as well simply give the compressor random inputs and see which ones compress well. This will work exactly as well. And if an algorithm that doesn't require the ciphertext as input performs exactly as well as the one you proposed, you can't actually be decrypting anything, can you? You're simply selecting random plausible messages from the prior distribution implied by the compression algorithm itself.

Source Link
hobbs
hobbs
  • 285
  • 1
  • 8

Assuming that the key is chosen at random, that the key and the message are the same length, and that keys are not reused between messages, then possession of the ciphertext gives you exactly 0 information about the plaintext.

For every bit of ciphertext, there are two possibilities: either the corresponding key bit is 0 and the corresponding plaintext bit is the same as the ciphertext bit; or the key bit is 1 and the plaintext bit is the opposite of the ciphertext bit. By the assumption that the key is unknown and random, both possibilities are equally likely — and by symmetry this is true whether the ciphertext bit was 0 or 1. Therefore our knowledge of the ciphertext cannot do anything to increase our knowledge of the plaintext unless we also have knowledge of the key. The definition of perfection in cryptography is that all security lies in the key, so by this standard OTP is perfect.

This means that if XORing BS1 with cyphertex BS4 results in a compressible BS5, then BS1 is at least part of BS2 or contains part of BS2.

You're doing two things implicitly here. First, you're assuming a compression algorithm (hopefully it's a fixed one, otherwise we will never agree what "compressible" means). Then, you're assuming that the correct plaintext is compressible using this algorithm. Perhaps this is true, perhaps it's not. If you assume that it is, then you're assuming prior knowledge about the plaintext. An attempt at "breaking" OTP by decrypting the ciphertext with various keys and seeing which one gives you the best compressibility doesn't give you any additional information, because the OTP decryption is equally likely to produce any given string as input to the compressor, so you might as well simply give the compressor random inputs and see which ones compress well. This will work exactly as well. And if an algorithm that doesn't require the ciphertext as input performs exactly as well as the one you proposed, you can't actually be decrypting anything, can you? You're simply selecting random plausible messages from the prior distribution implied by the compression algorithm itself.