Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
While the Playfair cipher has an enormous key space, the effective key space is a lot smaller due to lots of equivalent keys. And the cipher itself can be broken with much less effort than guessing the key. –  Paŭlo Ebermann Jul 9 '13 at 18:28
    
Welcome to Cryptography Stack Exchange. I formatted your question using MathJax for formulas and quote markers for the quotes, please check that I understood everything right. –  Paŭlo Ebermann Jul 9 '13 at 18:37
    
Thanks the questions are much more readable! I was actually wondering if I had answered them correctly. Most of that text is what I responded with. –  user7538 Jul 9 '13 at 19:04
    
Ah, you can edit again (there is an edit button/link) to make this clearer. I supposed you quoted something there. –  Paŭlo Ebermann Jul 9 '13 at 19:51
    
In four-square, isn't there only two randomly organized boxes of 25 letters of the alphabet? To my understanding, the two that have keys are random, but the other two are in normal alphabetic order. Wouldn't this mean that the keyspace would only be be square of (25!)? –  user7585 Jul 12 '13 at 22:36

1 Answer 1

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 need some 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.

share|improve this answer
    
O wow thank you very much for the useful information! I understand where I went wrong and can't believe I mistook it to be *4 instead of ^4. Thank you for clarifying everything. –  user7538 Jul 9 '13 at 20:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.