I am interested in the complexity of attacking affine ciphers under the following two scenarios

  • during a Ciphertext only attack
  • during a Chosen Plaintext attack

For an alphabet of size $m$, how many calls to the decryption function would it take to brute force the key under each attack scenario?


Well, the previous answers assumed that you could ask for a single plaintext that consisted of multiple characters (possibly including the entire alphabet); I'll view it from the aspect of a plaintext consists of a single symbol.

If the multiplication operation within the affine operation is integer multiplication (modulo the alphabet size), then it suffices to ask for 2 chosen plaintexts; for example, the plaintexts of 0 and 1 - all else can be deduced from that.

If the multiplication is a matrix operation (or an extension field), then it's slightly less trivial. In this case, if the size of the alphabet $M$ has a prime factorization $p_1^{e_1}p_2^{e_2}...p_n^{e_n}$, then the total number of chosen plaintexts required during a chosen plaintext attack is $1 + max(e_0, e_1, ..., e_n)$. (Of course, if it's an extension field, then $n=1$)

As for the known plaintext (you have it labeled as "ciphertext only", but if we are allowed to call the decryption function, we know what the plaintext is), well, it depends on how the plaintexts were chosen. If they are chosen randomly, then with nontrivial probability the minimum number of ciphertexts will suffice (for example, in the integer multiplication case, 2 plaintexts will suffice iff their difference is relatively prime to the alphabet size); and even if when that minimum number doesn't suffice, with good probability 1 or 2 more plaintexts will.

| improve this answer | |

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.