Computer decryption algorithms and knowing the solution

Question

This is a general question about using computers to decrypt information. It has puzzled me for a while.

The question is really two parts:

1. How does a computer check if a "guessed" key is the correct key? A human could do it because the result is readable - to humans. SO what does it mean to say the computer is checking a key?

2. How does the alogirthm know it has found the correct key? For example if the computer just brute force checks possible keys one-by-one (if it uses a better algorithm for this it isn't so relevent), at what point does it stop and say "this is the key and message!"?

Answer 1

Taking your two questions:

1. If the expected plaintext is ordinary text, then the computer will look at letter frequencies for the expected language. If the plaintext is some sort of file, say a spreadsheet, then the computer will look to match the format of such a file, usually the header. Again, frequency statistics may help; a bitmap file with lots of white space will contain many more 0x00 bytes than a random file would.

2. It doesn't. It finds a decryption that seems to fit the expected pattern, or one that deviates significantly from random. It would be up to a human to determine if this was correct, or just a false positive.

Answer 2

It depends on the cryptosystem and its implementation: there's no guarantee that the computer can tell a correct decryption from an incorrect one.

However, most systems designed for static data encryption (that is, for example, file or e-mail encryption, as opposed to just temporarily encrypting data to transfer it over an untrusted network) do include some way to detect when an incorrect key has been given. The exact mechanism varies, but some commonly used ones include:

• Check the key before attempting decryption, by including a cryptographic hash of it as part of the encrypted data. (For messages encrypted using public-key cryptography, one could simply include the public key, or a hash of it, in the encrypted message.)

• Check the key at the beginning of the decryption, by prepending a known header to the plaintext data — this could be as simple as a block of null bytes — and checking that it decrypts correctly.

• Check the key — and the integrity of the data — by including a message authentication code in the encrypted data (or using an authenticated encryption mode). The main purpose of a MAC is to protect the encrypted data against tampering, but as a side effect, it also serves to detect incorrect decryptions. However, the MAC cannot be verified without first reading and processing all the data, so for the sake of usability, it may still be useful to combine this with one of the other key verification methods described above.

In any case, a well designed encryption format will allow the user to be quickly notified, if they try to decrypt it with the wrong key — but not too quickly, as that would just make it easier to crack the key by brute force without doing anything to help legitimate users. The recommended way to achieve this, for symmetric encryption with a key derived from a passphrase, is to use a key derivation function (such as PBKDF2 or scrypt) with an adjustable parameter that controls how much work is needed to compute the key from the passphrase. This derived key (which should be long enough — say, 128 bits or more — to not inteslf be crackable by brute force) may then be verified with one of the methods described above.

Answer 3

you need a way to validate a key by a computer with an algorithm, you could make some heuristics to cut the tree, this is a pseudocode

foreach (keys as key) {

if (isPossibleKey(key)) {

result=tryBruteForce(key);
if (result) break; 

}

}

you could make any type of heuristics on the isPossibleKey method like "the key is present in online dictionary" or "is human readable" using some rules. more tune in isPossibleKey method less calls to the tryBrutoForce method you do.