1
$\begingroup$

I am working on one interesting question. There is a ciphertext that has 10,000 letters. We need to distingish whether this ciphertext was encrypted by a transposition cipher or a simple subsitution cipher.

I understand a transposition cipher will keep the identity of each letter and a substitution cipher will change the letter to something new. So, I think we could probably check the common English patterns in the ciphertext (like 'ing', 'th', etc). If those patterns exist, we could conclude that this is a subsitution cipher. Otherwise, it would be a transposition cipher. However, this answer is not convincing for me. I hope to get an answer from an expert.

$\endgroup$
4
$\begingroup$

Think about what properties of the plaintext are preserved by the candidate ciphers. You want to look for those patterns.

Transposition moves letters around but keeps their identity. Substituting keeps positioning but changes identity.

So, you can do a test for whether letter identity is preserved.

The easiest is to do a frequency analysis: if your common letters (e, t, etc) are still common, you probably have a transposition. Of course if not, you are half way to breaking the substitution!

A bonus test goes the other way: see whether position is preserved. A perfect transposition will shuffle the letters, so no pairs should come up more often than expected by chance. If there are any weirdly frequent letter pairs, those are evidence that you have a substitution cipher.

$\endgroup$
1
$\begingroup$

One method is to simply try and break it. If you get an answer by analyzing the ciphertext assuming it is from one method then you can disregard the other one, especially if you have a large ciphertext such as 10,000 letters. Trying both methods only doubles the cost to the adversary after all.

As breaking a classical/simple transposition or substitution cipher should be relatively simple once you get the right method - especially on a computer, the amount of extra work to try both methods should be minimal, and probably less work than trying to distinguish one from the other without trying to decrypt the ciphertext.

$\endgroup$
  • $\begingroup$ That said, if somebody comes with a specific algorithm to distinguish one from the other then I'll happily vote up. $\endgroup$ – Maarten Bodewes Sep 21 '19 at 13:06

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.