1
$\begingroup$

I am trying to write a program to break transposition cipher using dictionary search. But I cannot understand the finishing condition of the search. Is there any theory that the maximum number of valid word can only be generated by decripting the cipher text using the valid key only? If not what can be a good finishing condition?

$\endgroup$
  • $\begingroup$ Could you explain a bit more what you understand by dictionary search ? Like are you using your dictionary to find the key, or are you trying to find the key by trying to have words from your dictionary appearing in your decrypted cipher text ? $\endgroup$ – Biv Jul 21 '16 at 9:59
  • $\begingroup$ You mean how to know the decryption is correct? Are you assuming a ciphertext-only attack, so no known plaintext? $\endgroup$ – otus Jul 21 '16 at 10:23
  • $\begingroup$ I am trying to find the key by trying to have words from the dictionary appearing in the decrypted cipher text. $\endgroup$ – Mostafizur Rahman Jul 27 '16 at 0:23
  • $\begingroup$ Yes, I am trying a ciphertext-only attack. $\endgroup$ – Mostafizur Rahman Jul 27 '16 at 0:25
1
$\begingroup$

In a chosen plaintext attack, the expected ciphertext length required to conclude that a decryption is correct was derived by Claude Shannon and is called the unicity distance. It depends on the distributions of the plaintext and the key and is infinite for the one time pad.

So if $K$ is the random variable describing the key with a known distribution, and the message has $N$ symbols, say $(M_1,\ldots,M_N)$ with the message distribution known, let the encryption map be $$(C_1,\ldots,C_N)=E(M_1,\ldots,M_N;K).$$

Then the unicity distance is defined as $$D:=\min\{ N: H(K|(C_1,\ldots,C_N))=0\},$$ where $H(\cdot|\cdot)$ is the conditional Shannon entropy.

See, e.g., wikipedia or van der Lubbe's Information Theory text.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.