4
$\begingroup$

How to attack polyalphabetic affine cipher with only the ciphertext?

A polyalphabetic affine cipher can be seen as the composition of an affine cipher ($p \mapsto c \equiv a \times p + b \pmod{26})$ and a Vigenère cipher.

Consider we have a key such as $(a_{n\ mod\ 3},b_{n\ mod\ 3}) \in [(3,1); (7,2); (11,8)]$.
For instance itwas$_{plaintext}$ $\longrightarrow$ zgpbd$_{ciphertext}$. enter image description here

$\endgroup$
  • $\begingroup$ If you know the values (a,b) that are used to encrypt the individual letters of a given sequence, why couldn't you do the corresponding decryption? $\endgroup$ – Mok-Kong Shen Apr 15 '16 at 9:51
  • $\begingroup$ @Mok-KongShen problem is we don't know numbers a and b. We only know ciphertext. I use 1 - 30 key length and find letter probabilites for every key length but i am not sure which number is correct. $\endgroup$ – Retikulum Apr 15 '16 at 13:50
  • $\begingroup$ @otus I added picture, i think it is clear in picture. $\endgroup$ – Retikulum Apr 15 '16 at 14:11
  • $\begingroup$ Each pair of (a,b) results in a mapping from the alphabet in the normal order to the alphabet in another (permuted) order. So if your alphabet is of size m and you have n unknown pairs of (a,b), this means that you have a poly-alphabetical substitution matrix of m*n with permuted columns that you don't know. But this is a general challenge for analysis certainly much more difficult than the classical Vigenere. It's unlikely IMHO that someone would be able to provide you a recipe to straightforwardly solve the problem. $\endgroup$ – Mok-Kong Shen Apr 15 '16 at 14:55
  • 1
    $\begingroup$ This cipher is, without any doubts, more difficult than the Vigenere cipher. However, I think you could break it simply finding the period and then breaking n different affine ciphers. Obviously, your effort will be greater but I think it would be reasonable. P.S. sorry for my English $\endgroup$ – ssh3ll Apr 15 '16 at 17:58
3
$\begingroup$

This is a simple variant of the Vigenère cipher, and can be broken in basically the same way:

First, you need to determine the key length. The standard methods for doing this for any Vigenère-like cipher, like Kasiski examination or calculating the index of coincidence, work just fine here.

Once you've determined that the key most likely consists of $k$ separate affine maps, you then split the plaintext into $k$ columns, each encrypted with a different affine map, and break each of them like you'd break a normal monoalphabetic affine cipher, using letter frequency analysis.


Note that crib dragging or $n$-gram frequency analysis generally won't work for solving the columns, since the letters in each column aren't consecutive in the plaintext. On the other hand, since you have multiple columns taken from the same plaintext, you can mostly solve the cipher without knowing the actual letter frequency distribution of the plaintext (as long as it's sufficiently non-uniform).

To do that, simply take the letter frequencies from one of the ciphertext columns (say, the first one) and use them instead of the expected plaintext letter frequencies to solve all the other columns. Assuming that you have enough ciphertext for the statistical analysis to yield robust results, and that the plaintext doesn't just happen to contain any repetitive elements with period equal to the key length, this should give you a "pseudo-key" that, when used to decrypt all the other columns, will convert them to the same cipher alphabet as the first one. Thus you can effectively reduce the polyalphabetic cipher into a monoalphabetic one, which you can then solve e.g. by brute force.

(For increased robusteness, you can do the same thing with each of the ciphertext columns as the reference column, and check that the resulting affine maps between the columns are consistent with each other. If you find any mismatches between the maps suggested as most likely by frequency analysis, that can be a sign that some columns don't have sufficiently similar plaintext letter frequency distributions. In that case, you may want to examine the other reasonably likely maps found by frequency analysis to see if they'll solve the mismatch.)

This works because affine maps form a group. In particular, the inverse of any affine map is an affine map, and so is the composition of any two affine maps. Thus, decrypting a ciphertext column with one affine key and re-encrypting it with another is always equivalent to encrypting (or decrypting) it with some third key. The same trick works for ordinary Vigenère ciphers too, and for any other repeating-key substitution cipher (like the XOR cipher) whose underlying monoalphabetic substitutions form a group.

|improve this answer|||||
$\endgroup$

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.