[Cryptography] Unicity distance of Playfair

Jerry Leichter leichter at lrw.com
Mon Mar 28 15:59:40 EDT 2016


> To make my argument clear: Compare the general case of poly-alphabetical
> substitution (with a 26*26 matrix where the coulmns are fairly random
> permutations of the alphabet) and the special case (namely Vigenere,
> with a 26*26 matrix where the first column is the alphabet as such and
> each successive column is a rotation by one place of the preceeding
> column). Evidently the number of possible keys of the two cases are
> exactly the same.
> 
> ​I am confused here.  If each row of the matrix is a distinct permutation of the alphabet, then  I think there are (26!)^26 possible keys.  For the Vigenere there (26!) keys.  Big difference.  
None of this matters.

Unicity distance is a very simple measure:  It is simply the number of bits of ciphertext encrypted with a given key which uniquely determines the key.

Since this is a *guarantee*, not an average, it's necessarily an integer number of bits.  If the keys must be represented by larger units than bits - say, bytes - then the unicity distance is perhaps more naturally represented in bytes.

Similarly, it's independent of any probability distributions over the keys or the plaintexts:  It's a *worst case* measure, so the fact that 50 bits is enough for 2^128-5 cases but you need 55 bits for the remaining 5 cases means your unicity distance is still 55.

The unicity distance can be infinite for completely broken ciphers.  If the key is two bits long, and the encryption is "XOR all input bits with the bottom bit of the key", then no amount of ciphertext ever distinguishes the keys 01 and 11.  You can try to modify the definition of unicity distance so as to ask for the amount of input until you can uniquely find a key that produces the same outputs as the original key - but that actually doesn't help much:  Encrypt by XOR'ing with the bottom bit of the two bit key for 10^10 bits, and from there XOR with the top bit.  The unicity distance is now 10^10+1, but that tells you absolutely nothing about the quality (or lack thereof) of the encryption.

While the distribution over the inputs or keys don't matter, the actual input or key sets *do* matter.  The "XOR with bottom bit" encryption goes from a infinite unicity distance to a one-bit unicity distance if keys must be chosen from the set {00, 01} - or in the limit to 0 if the key must be chosen from the set {00}.  The silly 10^10 example goes from 10^10+1 to infinite if the input is chosen from bit streams of length no more than 10^10 bits.

Padding the output with irrelevant bits obviously increases the unicity distance, since those bits "increase the count" without actually reducing the equivocation about the key.

Unicity distance is an simplified way to present some information-theoretical ideas about the safety of encrypted text, but it's not really useful for much else.
                                                        -- Jerry

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160328/e22228da/attachment.html>


More information about the cryptography mailing list