Playfair cipher - questions about inserting 'X' I'm implementing the Playfair cipher as part of a programming project. I realize there are different versions of the cipher - I've been asked to implement the version which treats the letters 'I' and 'J' as the same letter, and which inserts the letter 'X' into the plaintext to ensure that every resulting bigram has unique letters ("TREESTUMP" becomes "TR EX ES TU MP"). It is also meant to append the letter 'X' if the length of the intermediate plaintext is not even ("SMOOCH" becomes "SM OX OC HX").

My first two questions have to do with the encryption process, the third has to do with the decryption process:


How are messages resolved which already end with an 'X', and have an
odd number of characters? For example, "REX" becomes "RE XX" -
surely that can't be right.
The Playfair Wikipedia article explains that 'X' is a good candidate
for insertions because it is an uncommon letter. However, it seems
to me that a cipher should be able to encrypt any message
irrespective of content - what if my plaintext contains two adjacent
'X's? For example, "REX XENOS" becomes "RE XX EN OS" - we can't be
expected to keep naively inserting 'X's between the two 'X's, no?
Finally, the Wikipedia article ends it's description of the cipher
by saying "drop[...] any extra "X"s or "Q"s that do not make sense
in the final message when finished", but it is not explained how
this is done. How can we know if an 'X' doesn't make sense in the
final message?
As Maarten notes in the comments, you're indeed expecting rather too much from an old classical cipher designed to be used by hand.  Ciphers from that era were simply not designed to be able to mechanically and unambiguously encode all possible messages.

Basically, as you've noted, the Playfair cipher as you've described it cannot encrypt all messages; specifically, it cannot handle messages where two consecutive identical letters fall into the same group, nor messages of odd length.  (There are Playfair variants that can handle both of those in various ways, but you don't seem to be using any of those variants.)

It is thus the encryptor's responsibility to somehow ensure that their message is of a suitable form to be encrypted with the cipher, while still (hopefully) conveying the appropriate meaning to the recipient when decrypted.

One common convention for doing that is to break up unencryptable plaintext segments (or pad messages with an unsuitable length) by inserting a dummy letter that is obviously misplaced, and which the recipient can therefore safely ignore while reading the message.  X and Q are common choices for such dummy letters, being rare in normal English text, but really any letter can be used.  So, for example, if you needed to break up a rare double X, you could e.g. turn it into XQX or XZX or whatever; it just needs to be something that the recipient can spot as an obvious error, and which they can be expected to be able to reliably correct.

But note that you also have other options: for example, you could simply choose to rephrase your message using different words that don't contain the problematic double letter.  Or, for the specific case of the Playfair cipher, you could simply choose to insert an extra dummy letter somewhere earlier in the message (or just adjust your word choice to change the length of the message) so that the double letter now gets split between two encrypted letter pairs.

In any case, note that the Playfair cipher (like most ciphers of its era) has a much more significant limitation: it cannot encode spaces or punctuation.  Thus, it cannot distinguish "inverse" from "in verse" or "No retreat!" from "No, retreat!".  So you will in any case have to take care when composing your messages to avoid potential misunderstandings due to run-on words and sentences.

(Some of that ambiguity can also be reduced by conventions like, say, inserting an X between words and a Q between sentences.  But such conventions are also just imperfect patches on top of a fundamentally limited encoding scheme.)

Of course, the Playfair cipher has other limitations too, like the inability to express letters outside the English alphabet.  Indeed, it cannot even represent all the letters in the English alphabet, typically conflating I and J into a single symbol.  Again, this is just something that the receiver is expected to be able to disambiguate based on context.