Isn't it difficult to recognize a successful decryption?

Question

When I hear about methods for breaking encryption algorithms, I notice there is often focused on how to decrypt very rapidly and how to reduce the search space. However, I always wonder how you can recognize a successful decryption, and why this doesn't form a bottleneck. Or is it often assumed that a encrypted/decrypted pair is known?

Answer 1

In assymetric cryptography you usually have access to the public key. Therefore, any decryption of an encrypted ciphertext can be re-encrypted using the public key and compared to the original ciphertext, thus revealing if the decryption was succesful.

The same is true for symmetric encryption. If you think you have decrypted a cipher, you must also think that you have found the key. Therefore, you can use that key to encrypt your, presumably correct, decrypted text and see if the encrypted result is identical to the original ciphertext.

Answer 2

From Cryptonomicon:

There is a compromise between the two extremes of, on the one hand, not knowing any of the plaintext at all, and, on the other, knowing all of it. In the Cryptonomicon that falls under the heading of cribs. A crib is an educated guess as to what words or phrases might be present in the message. For example if you were decrypting German messages from World War II, you might guess that the plaintext included the phrase "HElL HITLER" or "SIEG HElL." You might pick out a sequence of ten characters at random and say, "Let's assume that this represented HEIL HITLER. If that is the case, then what would it imply about the remainder of the message?"

...

Sitting down in his office with the fresh Arethusa intercepts, he went to work, using FUNERAL as a crib: if this group of seven letters decrypts to FUNERAL, then what does the rest of the message look like? Gibberish? Okay, how about this group of seven letters?

Answer 3

For symmetric encryption where the key length is shorter than the cipher-text length, you're guaranteed to not be able to produce every possible plain-text. You can probably guess what form your plain--text will take, to some degree -- you probably know whether it's an image, or XML, or if you don't even know that much then you can assume you'll be able to run file on it and not get 'data'. You have to hope that there are only a few keys which would give you even a vaguely sensible decryption and only one which matches the form you are looking for.

If you have a sample plain-text (or partial plain-text) then this gets a lot easier.

Answer 4

Generally, you have some idea of the format of the file you expect to result from the decryption, and most formats provide an easy way to identify them. For example, nearly all binary formats such as images, documents, zipfiles, etc, have easily identifiable headers, while text files will contain only ASCII, or only valid UTF-8 sequences.