How large is the Playfair cipher keyspace? [duplicate]

Question

In the Playfair cipher, is the key space 5 x 5 = 25 or 25 x 25 = 625? I'm trying to work out the size of the key space if each set of equivalent keys is counted as one key.

Answer 1

The Playfair key matrix contains a permutation of the 25-letter cipher alphabet. The total number of such permutations is

\begin{aligned} 25! &= 1 \times 2 \times 3 \times \dots \times 25 \\ &= 15{,}511{,}210{,}043{,}330{,}985{,}984{,}000{,}000. \end{aligned}

However, as I noted in a previous answer, the Playfair cipher has equivalent keys: moving a row or a column from one side of the matrix to the opposite makes no difference to the Playfair encryption process.

By repeatedly moving rows and/or columns around in this way, we can pick any of the 25 letters and move it to any desired position in the matrix. Doing so fixes the positions of the remaining letters, though, so in effect each key matrix belongs to a class of 25 equivalent matrices. The total number of such equivalence classes is therefore

\begin{aligned} \frac{25!}{25} = 24! &= 1 \times 2 \times 3 \times \dots \times 24 \\ &= 620{,}448{,}401{,}733{,}239{,}439{,}360{,}000. \end{aligned}

---

Ps. For what it's worth, $24! \approx 2^{79}$. That is to say, the number of distinct (equivalence classes of) Playfair key matrices approximately matches the number of distinct 79-bit bitstrings — comparable to, say, the 80-bit keys of the modern Skipjack cipher. Even so, in practice, Playfair encryption can be broken using just pencil and paper, whereas breaking Skipjack by brute force (though perhaps nowadays possible for large state actors) would require a massive and expensive computing cluster.

The difference is, in large part, due to the fact that a Playfair key can be attacked incrementally: the encryption of each letter pair is determined by only a small part of the key matrix, and does so in a relatively simple way, allowing that specific part of the matrix to be determined just by comparing individual pieces of the plaintext and the ciphertext. And since the parts overlap, it's possible to join them together piece by piece, like a jigsaw puzzle, until the whole key matrix (up to equivalence, anyway) has been reconstructed.

Modern ciphers, in contrast, are designed so that every bit of the key affects the encryption of every part of the plaintext, and changing even a single bit of the key changes the ciphertext completely in a seemingly random way. Thus, such incremental attacks are generally not feasible against modern ciphers, so that the fastest possible attack becomes brute force testing of all possible keys one by one.

(Or, at least, that's how it's supposed to be; every once in a while, modern ciphers do get broken by new cryptanalytic attacks — the fancy modern descendants of the kind of statistical and combinatorical attacks that cryptologists of old employed against ciphers like Playfair. Still, nowadays, the existence of any practical attack against a cipher that is faster than brute force is generally considered to mean that the cipher in question is broken.)