A little while back, I had a email from Marie about Alexander d’Agapeyeff’s (1939) book “Codes and Ciphers”, highlighting some interesting mistakes she had found in his section on double transposition cipher.
D’Agapeyeff described this as a cipher system that the Russian Nihilists had used, but said that they had used the same keyword for both halves of the transposition (i.e. for transposing both the columns and the rows), a technical flaw that made it easy to crack. (Oddly, the Nihilists are nowadays associated with an entirely different kind of encipherment.)
Let’s take a closer look…
D’Agapeyeff’s Double Transposition
What follows is d’Agapeyeff’s account, with comments along the way.
At the end of the nineteenth century the Russian Nihilists used a double cipher, which, having been transposed vertically, was then transposed horizontally; but they made the mistake of using the same keyword in both transpositions. As it is a common variation of double columnar cipher, we give it as an example:
The first thing that Marie picked up on was that the way that d’Agapeyeff converted the transposition keyword SCHUVALOF to an ordering was clearly incorrect: F is the sixth letter of the alphabet, so there is no obvious way that it would be counted as the highest ranked of the nine letters in the keyword. When I looked at this, I immediately guessed that it should instead have read SCHUVALOV – as it turned out, this was a good try, though still very slightly wrong. 😐
Regardless, it should already be clear that something a little non-obvious is going on here.
Now suppose we have to encipher the following: ‘Reunion to-morrow at three p.m. Bring arms as we shall attempt to bomb the railway station. Chief.’
The ‘abcd’ at the end are ‘nulls’ used to fill in the squares.
Now we transpose the message according to the letter sequence of the keyword:
So the message reads:
OMPBOETTMWORATMROTMREBRHEPIATHILBERWTYSIOATANOEUNTRNIOSGAASNRMWLSHATEALTAHIBCCEFD
In all languages where certain letters must follow or precede certain others, the deciphering of this script will never present difficulties. We first count the number of letters in the script (81), which will give us the size of the square (9×9), and once this is done all we have to do is remember that in nine cases out of ten ‘h’ follows either ‘t’ or ‘s’ or ‘c’, and that the bigrams such as AT, TO, WE and the very helpful (English) trigram ‘the’, and the doubles TT, LL, EE, etc., are the most common. In fact, the Russian police soon found out all about that conspiracy.
The second thing Marie noted here was that d’Agapeyeff was using the double transposition decryption direction here, rather than the encryption direction.
All in all, I’d agree with Marie that d’Agapeyeff didn’t seem to have fully understood how the system worked. Smartly, though, Marie now doggedly decided to look at d’Agapeyeff’s crypto sources, to see if he had copied this whole section blindly from somewhere. And, eventually, she found that d’Agapeyeff’s direct source for the above was none other than…
Auguste Kerckhoffs
…the Dutch cryptographer Auguste Kerckhoffs (1835-1903).
Kerckhoffs’ influential book (well, extended article, really) “La Cryptographie Militaire” is available online as a PDF, or as an HTMLized version here.
What follows is my usual free translation of Kerckhoffs’ description of double transposition, which we can immediately see beyond any reasonable doubt as being the source for d’Agapeyeff’s version:
On the occasion of the Nihilists’ last appearance in court, the Russian newspapers published the accused’s secret cipher. It is a system of double transposition, where the letters are first transposed by vertical columns, and are then further transposed by horizontal rows. The same word serves as a key for both transpositions: to do this, the keyword is transformed into a series of numbers, where each number matches the rank of the letter within the normal alphabetical sequence.
Here is the process applied to the word SCHUVALOW:
OK, though I was on this occasion very slightly wrong (SCHUVALOV rather than SCHUVALOW), I was at least wrong in the right kind of way. 🙂 Kerckhoffs continues:
Now, if we were to transpose a sentence such as this one – Vous êtes invité à vous trouver ce soir, à onze heures précises, au local habituel de nos réunions – we would proceed first as in the previously described [single transposition] case, and then carry out the same operation for the horizontal rows.
= s c i a u e s e l a v i v o n t e u v t r e r s o u c a c a b i o l h t n e l o s u d e r, etc.
However complicated this transposition may appear to us, deciphering a cryptogram written with this system, can never present insurmountable difficulties in languages where certain letters only present themselves in particular combinations, such as q or x in French. Here, the Russian decipherers seem to have carried out their decryption work in a relatively short time.
For any passing conlang fans, Auguste Kerckhoffs was also closely associated with the artificial language Volapük, which some people think is really koldälik. 🙂
d’Agapeyeff + Kerckhoffs = …?
It’s important to remember that d’Agapeyeff wasn’t himself a cryptographer, but rather someone who was trying to collect together interesting crypto stuff into a book that had originally been commissioned for someone else entirely to write. The project wasn’t something he was aiming to do, but rather something that fell in his lap.
As Marie points out, the big technical thing that d’Agapeyeff got wrong is that the numbers are the wrong way round, and so he is performing a double transposition decryption rather than a double transposition encryption: the two are not the same at all. That is, if you used SCHUVALOW as your single transposition keyword and then single transposition encrypted the text “SCHUVALOW”, you should get the ciphertext “ACHLOSUVW”: but both Kerckhoffs and d’Agapeyeff (copying Kerckhoffs) seem to have got this the wrong way round.
Having thought about this for a little while, I’ve come to suspect that d’Agapeyeff may well have faultily believed that double transposition was a self-inverse process, i.e. where the decryption and encryption transformations are identical.
All of which would dovetail very neatly indeed with the report that we have that he was unable to decrypt his own challenge cipher: for if he (wrongly) believed that double transposition was self-inverse, then he wouldn’t (if his challenge cipher had used double transposition) have been able to decrypt it at all. If this is correct, then his failure wasn’t anything as foolish as misremembering the keyword, but instead misunderstanding one of the component ciphers that made up the overall chain.
Might this insight help us decrypt his challenge cipher? Well… insofar as it now seems far more likely to me that he used double transposition as one of his stages, then the answer may very well be yes. Hopefully we shall see… 🙂
If I do a double transposition _en_coding on “Reunion tomorrow…” with the keyword SCHUVALOW used twice, I actually end up with “OMPBOETTMWORAT…” just like d’Agapeyeff does. What am I missing here? Good find on Kerckhoff being the source!
Narga: the point was that in the usual description of a single columnar transposition, the encryption direction would transpose the keyword (were it to be included in the plaintext properly aligned) into the ordered version, while the decryption direction would reassemble the ordered version of the keyword back to the keyword. Hence the numbers written about REUNIONTO should have been 623781459, rather than 123456789. And so the description given in d’Agapeyeff’s book (and, by implication, in Kerckhoffs’ monograph) is back to front.
However, I have a strong suspicion that d’Agapeyeff thought the transformation was symmetrical (i.e. where encryption is the same as decryption), which it isn’t: and that it might therefore have been the case that if d’Agapeyeff’s challenge cipher used that as one of its stages, he may – years later – have (incorrectly) concluded that his keyword was wrong, when in fact it was simply that he had misremembered how the cipher worked.