# Non-exact substitution cyphers

Picture a simple substitution cypher of text with length $$N$$(spaces optional):

Plain    : ATTACK AT DAWN
Encrypted: ELLETI EL HEPG


Another way to represent the encrypted text is with an $$N \times N$$ matrix $$P$$ of $$0$$s and $$1$$s:

• $$P_{ij} = 1$$ if the $$i^{th}$$ character is the same as the $$j^{th}$$ character
• $$P_{ij} = 0$$ if the $$i^{th}$$ and $$j^{th}$$ characters are different
• $$P_{ij} = P_{ji}$$

So the encrypted text in the example above can be represented with the following matrix:

  E L L E T I _ E L _ H E P G
E 1 0 0 1 0 0 0 1 0 0 0 1 0 0
L 0 1 1 0 0 0 0 0 1 0 0 0 0 0
L 0 1 1 0 0 0 0 0 1 0 0 0 0 0
E 1 0 0 1 0 0 0 1 0 0 0 1 0 0
T 0 0 0 0 1 0 0 0 0 0 0 0 0 0
I 0 0 0 0 0 1 0 0 0 0 0 0 0 0
_ 0 0 0 0 0 0 1 0 0 1 0 0 0 0
E 1 0 0 1 0 0 0 1 0 0 0 1 0 0
L 0 1 1 0 0 0 0 0 1 0 0 0 0 0
_ 0 0 0 0 0 0 1 0 0 1 0 0 0 0
H 0 0 0 0 0 0 0 0 0 0 1 0 0 0
E 1 0 0 1 0 0 0 1 0 0 0 1 0 0
P 0 0 0 0 0 0 0 0 0 0 0 0 1 0
G 0 0 0 0 0 0 0 0 0 0 0 0 0 1


Now imagine there was noise during the transmission of the encrypted text and instead of having just $$0$$s and $$1$$s in the matrix above, we end up with real numbers $$P_{ij} \in [0, 1]$$ representing the probability of character $$i$$ being the same as character $$j$$ - higher $$P_{ij}$$ means more likely that $$i^{th}$$ and $$j^{th}$$ characters match.

Any ideas/references discussing attacks under the described conditions?

Edit: Consider $$N > 200$$ and the language of the plain text is known.

• How a ciphertext is encoded makes little difference. If it's not decodable, then it's useless. If it is decodable then it's just as broken as with any other encoding. So what is the question here? – Maeher Dec 21 '18 at 17:07
• @Maeher The substitution cypher is decodable and also breakable. My question is how to efficiently attack it if I don't have complete information which characters match with each other. – Georgi Gerganov Dec 21 '18 at 17:22
• As I said: If the scheme works at all, i.e., if the intended recipient can decrypt the message, then the encoding doesn't change anything. If the intended recipient is not able to decrypt, well then what's the point? – Maeher Dec 21 '18 at 17:40
• Once, you extract the tap voices, you need to group them with a threshold. Then perform the frequency analysis? – kelalaka Dec 21 '18 at 18:05
• @kelalaka This is my current approach - it does solve this particular task, but I am looking for something better than thresholding the probabilities. There are often groupings that cannot be obtained with thresholding (due to large noise), so I am looking for approach that allows such groupings, but of course only the most likely of them. It's a tradeoff between the probabilities $P_{ij}$ and the probability for encountering the obtained grouping in the English language. But not sure how to express it mathematically. – Georgi Gerganov Dec 21 '18 at 18:20