4
$\begingroup$

For a class 5 years ago I wrote a paper about "defeating character frequency analysis by using two cipher letters per plaintext letter" (jamesjava.blogspot.com/2009/08/defeating-character-frequency-analysis.html).

Quote:

Using two letters in the cipher text for each letter in the plaintext can be a good way to create a flat character distribution.

The algorithm is to partition the 676 2-letter combinations based on the standard character frequency. i.e. if the standard frequency for a letter is 5% then it will get 5% of the 2-letter combinations (randomly selected). This doubles the size of the data, could include spaces & punctuation, and makes a much larger key.

Note that some letters may get dropped because they occur less than 1/676 (0.15%) of the time. Both 1-gram and 2-gram frequency analysis produce a nearly uniform histogram (variation appears to only be caused by rounding). Two-gram results: P&P=5,117%; SH=5,013%.

Therefore this technique was extremely effective with no obvious weaknesses.

I didn't get much feedback from the professor so I wonder if anyone can comment on this and tell me if my conclusion is correct.

$\endgroup$
7
  • 6
    $\begingroup$ Sounds like a homophonic substitution cipher. $\endgroup$ Commented Jun 18, 2013 at 21:36
  • 2
    $\begingroup$ An extensive analysis of homophonic substitution ciphers can be found in this paper: Efficient Cryptanalysis of Homophonic Substitution Ciphers $\endgroup$
    – Reid
    Commented Jun 19, 2013 at 14:57
  • 1
    $\begingroup$ Could you copy the relevant paragraph from your paper into your question? This makes it easier to reference it in an answer. $\endgroup$ Commented Jun 20, 2013 at 18:33
  • $\begingroup$ Given sufficient ciphertext, you can still do frequency analysis. All you did was make the alphabet much larger. $\endgroup$
    – Antimony
    Commented Jul 3, 2013 at 6:36
  • 1
    $\begingroup$ @JamesA.N.Stauffer Given a large enough ciphertext, bigrams and trigrams may still be analyzed. English text consists of roughly 1.5% "th" bigrams, for instance. Based on character frequency, there would be about 2,680 pairs representing "th". You'd need a plaintext large enough to reliably detect quartets occurring 0.00055% of the time, which isn't really all that large. $\endgroup$ Commented Jul 17, 2013 at 22:47

1 Answer 1

3
$\begingroup$

It is probably impossible to remove language characteristics completely with a substitution cipher. Your algorithm flattens out single character frequencies, but that's it kinda.

Language bigrams (your cipher-quadruples) might not be uniform distributed. The reason for this is simple: Bigram probability is not just the product of the probabilities of both letters - they are not independent variables.

Let's make an example (frequencies from http://www.cryptograms.org/letter-frequencies.php):

  • Letter t with frequency 0.09056 => 61 cipher-bigrams for t
  • Letter h with frequency 0.06094 => 41 cipher bigrams for h
  • Bigram th with frequency 0.03882
  • Now there are $61*41=2501$ cipher quadruples for the original bigram th, and all of them have the same probability. However, $2501$ of $26^4 = 456976$ possible qudruples is just a fraction of 0.005473. So now the number of ciphertext quadruples for *th does not match required number to enforce a uniform distribution.

An other way to attack might work with those bigrams which are very unlikely or even impossible in English language.

$\endgroup$

Your Answer

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

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