Four-Square cipher and its keyspace Am I thinking about this correctly?


  Consider that the keyspace of the Playfair cipher is equivalent to all permutations of the alphabet, e.g. the number of distinct permutations of 25 objects, and is equal to $1.551 · 10^{25}$. (A lot!)
  
  1)    What is the keyspace of Four-Square, when considering both keys, as presented in this class?


Reading through the modules presented in this class, one may find:


  Like Playfair, the four-square cipher is a polygraphic substitution cipher. However, this cipher uses four 5 by 5 (four squares) boxes instead of one.


Using wolfram , you can see that $1.551 · 10^{25} =$ a very large #.
Since 4 square uses 4 boxes instead of one, we get: $1.551 · 10^{25} · 4 = 6.204·10^{25}$, which is our keyspace (another huge number).


  2)    If the alphabet for a Four-Square type cipher contained: uppercase, lowercase, the digits zero to nine, and the ligatures 'ae' and 'ce', in that ordering, (that is 64 codons); and the Four-Square tables were also extended in size to hold all of these characters, without omitting Q or combining I and J, what would the keyspace be? Would there be any problem working with this cipher?


Now there are 64 objects to deal with instead of 25.  Consider if this was a Playfair cipher: $1.551 · 10^{64}$ 
Again, since 4 square uses 4 boxes instead of one, we: $1.551 · 10^{64} · 4 = 6.204 · 10^{64}$.  Even though this is a lot more than our 25 codon keyspace, there shouldn’t be any problem working with this cipher (although you may need a super computer):


  The encryption procedure is simple; find the first character of the plaintext digraph in the box that is keyed with $k_1$, and the second character of the digraph in the box that is keyed with $k_2$. Then complete the square, giving the first character of the cipher text digraph is that is located in the upper-left box; and giving the second character that is located in the lower-right box.
Your math is off.

The key space of "four squares of random letters" is not four times as big as the one provided by one square, but the fourth power of that size.

To see this easier, consider the case of one $2×2$-square (or four ones), where you can still calculate everything by hand.

There are $4! = 24$ possible ways to fill a $2×2$-square. If you have four such squares, independently of each other, each has 24 ways to fill, so you get $24·24·24·24 = (4!)^4 = 331776$ ways to fill the four squares. This is a lot more than $4·(4!) = 96$. As an exercise, try to find more right groups of 4 such squares than 96 to see that this is actually true.

(An easier exercise would be to try this with 4 1×1 squares, though that is a bit less obvious to understand. There is only one $= 1! · 1! · 1! · 1! = 1!^4$ way of filling the four squares, instead of four $= 4 · 1!$ ways.)

A playfair cipher based on a 2×2 square would be trivial to break even by brute force, as the effective key space has a size of 6 (there are 4 equivalent squares each obtained by swapping rows and columns) ... and for each plain text pair, 4 of the six key pairs just act by swapping the plain text "letters" with each other. Also, you would have a plain text alphabet of size 4 (or better 3, so you have one letter left for inserting when you have double letters). You can try to break one by hand.

For our 25 square, this means that when one square gives 25! ways of filling it, four squares give $25!^4 \approx 5.7887 · 10^{100}$ different ways of filling them. That is your key space for the four-square cipher.

For the 8×8-square, you have $64!$ ways of filling them. But this is not $1.551⋅10^{64}$ (you can't simply convert factorials to powers this way), it is around $1.269·10^{89}$.

Four squares of that caliber give more than the google calculator can handle, i.e. $64!^4 = 2.592 · 10^{356}$.

To use this cipher, you don't need a computer at all (other maybe for generating your random squares), much less a super computer.



The strength of such a cipher is nevertheless much lower than a modern cipher with a similar (or even much lower) key space size would offer. Don't use such a cipher in real live.