Cryptography Question

By Deane Barker on July 21, 2003

I have a question about cryptography. I’m posting it here in the hopes that someone will know the answer. This isn’t a technical question, just a general theory, “I wonder how that works”-type question.

How does a cryptologist know that he has decoded something? If he’s trying to brute force an encrypted message, he has to try umpteen different keys. So how does he know when he’s got the right key and the message is decrypted?

For example, a terrorist has encoded a message about when a bomb is going to go off. Fred the intrepid cryptologist has to decode the message. So he starts brute-forcing it. Now, correct me if I’m wrong, but every key Fred tries will produce something — the wrong key will result in gibberish, the correct key will result in a coherent message. But if Fred is trying keys at the rate of several million a second (which he would have to do to brute force even mild encryption), he obviously can’t review the results of every attempt.

So how does Fred know when he’s found the right key and can stop trying? Does he have to review every result of an encryption attempt to see if it makes sense? If you know the answer, post it here. Thanks.

Gadgetopia

Comments

  1. I don’t know for sure, but perhaps it reviews the results on the fly and flags coherent patterns in those results, based on comparisons to known words. Just a guess.

  2. Dave, you got it right. Bruce Schneier, author of the seminal book “Applied Cryptography” and principal at CounterPane Secruity sent me an email refering me to this:

    http://www.counterpane.com/crypto-gram-9812.html#plaintext

    A quote:

    “For example, RC4 encrypts data in bytes. Imagine a single ASCII letter as plaintext. There are 26 possible plaintexts out of 256 possible decryptions. Any random key, when used to decrypt the ciphertext, has a 26/256 chance of producing a valid plaintext. The analyst has no way to tell the wrong plaintext from the correct plaintext.

    Now imagine a 1K e-mail message. The analyst tries random keys, and eventually a plaintext emerges that looks like an e-mail message: words, phrases, sentences, grammar. The odds are infinitesimal that this is not the correct plaintext.”

Comments are closed. If you have something you really want to say, email editors@gadgetopia.com and we‘ll get it added for you.