Unicity distance

Unicity distance is a term used in cryptography referring to the length of an original cyphertext needed to break the cypher by reducing the number of possible spurious keys[?] to zero in a brute force attack (that is, trying every possible key).

Consider an attack on the cyphertext string "WNAIW". With a five letter key, this string could be deciphered into any other string, RIVER and WATER are both possibilities given the corresponding keys. This is a general rule of cryptography, with no additional information it is impossible, even in theory, to decode this message.

Of course even in this case only a certain number of five letter keys will result in English words. Using random keys we will not only get RIVER and WATER, but SXOOS and KHDOP as well. The number of "working" keys will likely be very much smaller than the set of all possible keys. The problem is knowing which of these "working" keys is the right one, the rest are spurious.

In general, given any particular assumptions about the size of the key and the number of possible messages, there is a cyphertext length where there is only one key that will generate a readable message. In the example above we see only uppercase english characters, so if we assume this is the input then there are 26 possible letters for each position in the string. Likewise if we assume five character uppercase keys, there are K=26^5 possible keys, of which the majority will not "work".

There are a tremendous number of possible messages, N, that can be generated using even this limited set of characters: N = 26^L, where L is the length of the message. However only a smaller set of them is readable plaintext due to the rules of language, perhaps M of them, where M is likely to be very much smaller than N. Moreover M has a one-to-one relationship with the number of keys that work, so given K possible keys, only K * (M/N) of them will "work". One of these is the correct key, the rest are spurious.

Since N is dependent on the length of the message L, whereas M is dependent on the number of keys, K, there is some L where the number of spurious keys is one. This L is the unicity distance.

see also cryptanalysis