Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I was reading on a site about the Zodiac Killer and how he used a basic substitution cipher, but instead of substituting english letters and characters he substituted symbols.

I was wondering, if you had a large enough subset of symbols to use for commonly repeating letters like E,T,S ... then by what means could someone decipher the cipher. This is also referring to the fact that no one has yet to decipher his last message. Obviously this type of system of cryptography would not withstand in modern computing.

I am more interested in other techniques that could be used, I also found this site '340 Cipher', which includes frequency counts.

share|improve this question
    
I found this article a couple of days ago. fostercity.patch.com/groups/editors-picks/p/… Does it make sense to you? –  user10781 Dec 8 '13 at 9:28
    
"Obviously this type of system of cryptography would not withstand in modern computing" and "This is also referring to the fact that no one has yet to decipher his last message." seem rather contradictory? If there isn't enough data then it's quite possible even a theoretically weak cipher could be strong enough to remain unbroken since one cannot know which is the correct decryption –  figlesquidge Dec 8 '13 at 10:24
add comment

3 Answers

up vote 4 down vote accepted

If I understand your cipher idea right, you would have a larger ciphertext alphabet than the plaintext alphabet, where each plaintext symbol maps to multiple ciphertext symbols (and the number is dependent on the frequency of the plaintext symbol), one of which is used randomly.

This is known as a Homophonic substitution, and with it the single-symbol frequency analysis usable for simple substitution ciphers is thwarted, since all symbols now have similar frequencies.

But as soon as we start to look at frequencies of letter-pairs (and triplets), we will observe enough structures to break this, too. For example, q is almost always followed by u, and thus the ciphertexts of q will almost always be followed by one of the ciphertexts of u. (I don't know enough about the statistic properties of the English language to give more examples, but you can be sure that an attacker would know.)

Some examples from German:

  • As in English, q is almost always followed by u.
  • A c is almost always followed by either k or h.
  • ei has about same frequency as ie (and i is the only letter who has this property related to e).

Some more details are given in David's answer.

Of course, if the ciphertext is so short (or the translation table so large) that each symbol is only used once or twice (or not at all), cryptanalysis is more difficult (or even impossible).

share|improve this answer
    
So like the 'th' and other tuple letters will still be observable? That is interesting! –  Jim Sep 1 '11 at 17:28
1  
Jes - while the possible ciphertexts for both t and h will occur with similar frequency as all the others, the pairs of ciphertext symbols corresponding to th will occur more often than other pairs (like these for ht, for example). –  Paŭlo Ebermann Sep 1 '11 at 23:34
add comment

What you're describing sounds very similar to the Caesar Cipher which can be cracked by counting the frequency of commonly repeating letters.

As for other techniques, it depends what you mean by 'other'. I presume that you mean other techniques that use a one-to-one mapping (or a variant thereof). If so, have a look at the one-time-pad which, if used correctly is (almost) impossible to crack.

Essentially, each bit or character from the plaintext is encrypted by a modular addition with a bit or character from a secret random key (or pad) of the same length as the plaintext, resulting in a ciphertext. If the key is truly random, as large as or greater than the plaintext, never reused in whole or part, and kept secret, the ciphertext will be impossible to decrypt or break without knowing the key.

share|improve this answer
add comment

As Paŭlo Ebermann says, this is (apparently) a homophonic cipher.

Ciphers that obscure single-letter-frequencies, such as homophonic ciphers, the Alberti cipher, Vigenère cipher, the Playfair cipher, etc. are impossible to crack using single-letter frequency analysis, which is the only cryptanalysis technique published before 1863.

However, other cryptanalysis techniques that have been developed since then. Given enough ciphertext, you can discover other patterns and decrypt the message. Several of these techniques are mentioned in Stahl's proposal for a homophonic cipher that attempts to resist those techniques.

F. A. Stahl. "A homophonic cipher for computational cryptography" 1973

Ciphertext-only cryptanalysis techniques that can be applied to homophonic ciphers include:

  • Some words (and word fragments) are very common. If we find a near-repeat -- "aBcde" in one place, and "aXcde" in another -- we begin to suspect that B and X both refer to the same plaintext letter.
  • When encrypting a plaintext letter that could be represented by several ciphertext symbols, one way to guarantee that all those ciphertext symbols have exactly the same frequency is for the writer to cycle through them -- when encrypting the first plaintext "h", the writer writes "M", the next plaintext "h" becomes ")", the next "M", then ")", etc. Later when the cryptanalyst sees that 2 symbols that always occur in the order (neglecting all other symbols) "M)M)M)M)" in the ciphertext, or 3 symbols that always occur in order "tr\tr\tr\tr\", we begin to suspect that M and ) both refer to one plaintext letter, and that t, r, and \ all refer to one other plaintext letter.
  • many bigram frequencies in English are significantly different than what we might predict from the underlying single-letter frequencies alone. Some enciphered letters might have a next-cipher-letter frequency that is relatively flat (all other ciphertext letters follow it), so perhaps it is a vowel, while other enciphered letters have a very spiked next-letter frequency (the next letter is nearly always one of a small set of ciphertext letters), so perhaps it is a consonant -- if extremely spiked, perhaps it is the 'q'.
  • And other cryptanalysis techniques.

this type of system of cryptography would not withstand in modern computing.

Obviously it has withstood modern attempts at decoding.

With a homophonic cipher message where every symbol is unique (and we have no other messages that use the same ciphertext-to-plaintext mapping) -- imagine if we only had the first 2 rows of the 340 Cipher -- every possible message is a plausible message, much like every possible message is a plausible message with a one-time-pad, and such a "entirely unique" message is impossible to decrypt.

With messages that contain some repeats, we can rule out some possible messages, but if the message is short enough, there may be a huge number of plausible deciphered plaintexts (using different homophonic encryption alphabets), much like the one-time-pad gives a huge number of plausible deciphered plaintexts (using different keypads). One of them is the original message, but even an infinite amount of computer power won't help you figure out which one it is.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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