7
$\begingroup$

The first go-to weakness when talking about substitution ciphers is frequency analysis. It assumes that there's a simple 1 to 1 character mapping between the plain text and the cipher text.

Could a frequency analysis be thwarted if this were a 1 to Many mapping?

For example, what if the input text contained say 30 characters: 26 letters, space, period, question mark, and exclamation mark. Enough for most communication needs between two people. The output could be quite a bit larger, like the 95 printable characters. E could be mapped to multiple output characters that appear at unusual frequencies in the cipher text that don't look like E on a frequency analysis. This mapping could also map space to 1 or more characters so you can't analyze word length or word frequency.

Every character could map to at least 3 output characters and knowing that some characters are already pretty rare they may not even need to be mapped to that many. Perhaps just 2 or even 1 that way other more frequently used characters could map to 5 or 6 cipher text characters.

Is there a different kind of analysis that could target a cipher like this?

$\endgroup$
0

1 Answer 1

5
$\begingroup$

This is called homophonic encryption, and has been around for a long time.

In terms of cryptanalysis of such ciphers, there is a nice thesis from SJSU on this topic which is available here. The attacks tested in that cipher were based on hill climbing and local optimization techniques. The conclusion states:

We designed and implemented an efficient attack on the homophonic substitution ciphers. The attack is based on the hill-climbing heuristic technique. The proposed algorithm has a multi-layered architecture with three nested loops to solve the challenges imposed by the homophonic substitution ciphers and the hill-climbing technique. The algorithm was successfully tested on simple substitution ciphers and many instances of homophonic substitution ciphers with variable ciphertext sizes and cipher symbol sizes. [..] For the ciphertexts having minimum 3000 characters and maximum 75 cipher symbols, the algorithm was able to break at least 85% of cipher symbols.

So, homophonic substitution increases the required ciphertext length, as expected, for a high rate of success of correctly decrypting plaintext characters. If 55 ciphertext symbols are used (to flatten the frequency distribution) the success rate increases from about 10% for a ciphertext length of 300 characters to about 80% for a ciphertext length of 4000 characters.

If 95 ciphertext characters are used, at 4000 character ciphertext length, the success rate is around 50%.

$\endgroup$
1
  • 1
    $\begingroup$ It’s not clear to me how this answers the question Is there a different kind of analysis that could target a cipher like this? It would be cool if you could expand your answer accordingly… after all – Corey is asking about “analysis” (read: other options of cryptanalysis besides frequency analysis to target such ciphers). He did not ask “can you identify what kind of encryption this is”. $\endgroup$
    – e-sushi
    May 28, 2016 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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