How do brute force decryption attacks know when they've found the right solution?

Question

How do brute-force attacks on encrypted data know when they've found the right key to decrypt the data? Is there a way to know that data's been decrypted, other than having a human looking at it? What if it's not human-friendly data?

Answer 1

It depends on the encryption method. For instance, with RSA encryption, if you are looking for the private key you know you have found it when the public key is a multiple of the number in question.

Answer 2

Cryptanalysts hope to have known ciphertext and plaintext. A key which decrypts that ciphertext to that plaintext is certainly the right key.

Without known plaintext, the data's format must be known. For example, plaintext HTML contains tags. A phone directory plaintext contains phone numbers. And so on.

Answer 3

It depends on the algorithm. With many algorithms there is only one correct decryption key. When you have the key you can easily verify it is the correct key in polynomial time.

With some algorithms though it is impossible to know when you have the right key. All plain texts (of the correct length) could give the output. An example of such a scheme is a one-time pad with XOR encryption. However if a one-time pad is reused ciphertexts can be XORed with each other to remove the key and then the two plaintext messages can be extracted by using techniques such as frequency analysis to determine what sort of data it is and what the most likely decryptions are.