Reply To: Maths
Here’s some cryptographic maths for you:
Suppose we take the rows of a tableau from a polyalphabetic substitution cipher as a set,
and define a binary operation among them by finding the encryption of one using the other as
a key in a monoalphabetic substitution. Turns out it’s commutative and associative. Of course,
I only checked one or two examples, but that’s proof enough, right?
It should be no surprise that the rows of the Vigenere cipher with this binary operation is
isomorphic to Z mod 26 with addition. After all, each row is the key of a Caesar shift cipher.
The identity is the key in row A.
[An isomorphism is a map from one set to another such that map(x+y) = map(x)+map(y), where “+”
denotes the binary operator, which might not be addition. In other words, the structure of the
thing is the same after the mapping. Here, I’m saying that these substitution keys with the
binary operation defined as letting one act on the other in a substitution cipher has the same
structure as the set of integers {0,…,25} with addition modulo 26.]
What might be surprising is that it appears that the rows of a quagmire 3 tableau also form
a group isomorphic to Z26. However, they are not in the same order as with the Vigenere.
The identity is still ABCDEFGHIJKLMNOPQRSTUVWXYZ, but it appears in the row labeled by the
first letter of the keyword. Let’s try this example, generated from the keyword KEYWORD:
a JLMIBNPQSTAUVXGZKHEYWOFRCD b LMNJCPQSTUBVXZHKEIYWORGDFA c MNPLFQSTUVCXZKIEYJWORDHAGB d IJLHAMNPQSDTUVFXZGKEYWCOBR e BCFAYGHIJLEMNPRQSDTUVXOZWK f NPQMGSTUVXFZKEJYWLORDAIBHC g PQSNHTUVXZGKEYLWOMRDABJCIF h QSTPIUVXZKHEYWMORNDABCLFJG i STUQJVXZKEIYWONRDPABCFMGLH j TUVSLXZKEYJWORPDAQBCFGNHMI k ABCDEFGHIJKLMNOPQRSTUVWXYZ l UVXTMZKEYWLORDQABSCFGHPINJ m VXZUNKEYWOMRDASBCTFGHIQJPL n XZKVPEYWORNDABTCFUGHIJSLQM o GHIFRJLMNPOQSTBUVCXZKEAYDW p ZKEXQYWORDPABCUFGVHIJLTMSN q KEYZSWORDAQBCFVGHXIJLMUNTP r HIJGDLMNPQRSTUCVXFZKEYBWAO s EYWKTORDABSCFGXHIZJLMNVPUQ t YWOEURDABCTFGHZIJKLMNPXQVS u WORYVDABCFUGHIKJLEMNPQZSXT v ORDWXABCFGVHIJELMYNPQSKTZU w FGHCOIJLMNWPQSATUBVXZKDERY x RDAOZBCFGHXIJLYMNWPQSTEUKV y CFGBWHIJLMYNPQDSTAUVXZRKOE z DABRKCFGHIZJLMWNPOQSTUYVEX
The identity is k. The element that is its own inverse (maps to 13 in Z26 under the isomorphism) is i:
Sub(STUQJVXZKEIYWONRDPABCFMGLH,STUQJVXZKEIYWONRDPABCFMGLH) = ABCDEFGHIJKLMNOPQRSTUVWXYZ
The other elements have order 13 or 26, meaning that if you find x^13 or x^26 using the binary operation
defined above, then for some x^13 = identity, and for others x^26 = identity. And the inverse of each
key is also in the tableau.
This doesn’t work for quagmires 1, 2, and 4.
Can this help to identify a cipher from its key? Here is the key tableau from 2018 challenge 10B:
1 DCEOFGIAJKLMNPWQRTHUVXBYZS 2 TYZUSHARDOWBCEVFGIQJKLXMNP 3 WFGBIJKOLMNPQRCTUVDXYZESHA 4 GLMINPQFRTUVXYJZSHEADOKWBC 5 IMNJPQRGTUVXYZKSHAFDOWLBCE 6 YADZOWBXCEFGIJSKLMVNPQHRTU 7 CIJEKLMBNPQRTUFVXYWZSHGADO
If we let 1 operate on 4 we get 5: Sub(GLMINPQFRTUVXYJZSHEADOKWBC,GLMINPQFRTUVXYJZSHEADOKWBC) = IMNJPQRGTUVXYZKSHAFDOWLBCE.
Key 2 times key 4 gives the identity, so they are inverses of each other.
Key 2 times 5 is 1.
Key 3 times 7 is 4.
Key 5 times 6 is 7.
Key 6 times 7 is 1.
(key 1)^26 = ABCDEFGHIJKLMNOPQRSTUVWXYZ = identity
(key 2)^13 = identity
(key 3)^26 = identity
(key 4)^13 = identity
(key 5)^26 = identity
(key 6)^13 = identity
(key 7)^26 = identity
Looks like we have part of a quagmire 3 tableau. If we hadn’t already figured that out in 2018,
this analysis could have told us.
I think that the mapping from the tableau to Z26 might give some information about the keywords,
but so far all I can see is that we can get the first letter of one of them.
Ah, the nurse is coming with my meds. Time for me to log off.