# How large is the Playfair cipher keyspace? [duplicate]

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.

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.)

• I can't understand the limit limitations part. I even have this :Given any 5x5 configuration, any of the four row rotations is equivalent, for a total of five equivalent configurations. For each of these five configurations, any of the four column rotations is equivalent. So each configuration in fact represents 25 equivalent configurations. Any explanations for idiots out there? Oct 25, 2022 at 20:20
• @MoteZart: Maybe some practice would help? At the beginning of the linked older answer there are three Playfair key tables. Try encrypting some short message with each of them and compare the resulting ciphertexts. Or try encrypting the message with one of the tables and then decrypting it with the others. (Then try finding some more equivalent key tables like that. Can you come up with a systematic way to generate them? How many of them are there?) Oct 25, 2022 at 21:09