“Hill ciphers 2x2, 3x3 and 4x4 solved straight from the crib blocks, with and without an added vector”
New root in family 8. The matrix is solved from the known blocks by linear algebra mod 26 rather than searched; every numbering, block alignment and direction is covered, and the affine form Bauer left untested.
revertedstatus
a new rootparents
3 mintime, all phases
2candidates
16/24known letters
1
The experiment method
What the method does with the 24 known letters.
A Hill ciphera Hill cipher A cipher that turns letters into numbers, takes them two, three or four at a time, and mixes each group with a fixed table of numbers. turns letters into numbers, takes them two, three or four at a time, and mixes each group with a fixed table of numbers. The sculpture's grid has an extra L that spells HILL down one column, which some take as a hint. We know enough letters in a row that we can work the mixing table out directly, like solving simultaneous equations, instead of guessing it. If the tablethe table The right-hand half of the sculpture, 26 rows of the alphabet each shifted one place further, starting from the word KRYPTOS. we work out from EASTNORTHEAST also turns the carved lettersthe carved letters The 97 letters cut into the copper at the CIA, shown at the top of every experiment page. at 64 to 74 into BERLINCLOCK, it is real; if it does not, that kind of Hill cipher is out.
Words in the margin are defined on the glossary page.
1.1
The method at work
The carved letters go in at the top; the reading comes out at the bottom.
the blocks
A Hill cipher mixes blocks of letters with a table of numbers. Whole blocks inside the known letters give equations that pin the table; the known letters in partial blocks are left over to test it.
the test
Drawn for blocks of 4: four whole blocks, sixteen letters, exactly enough to pin the table. For blocks of 2 and 3 the whole blocks outnumber the unknowns, and the extra blocks are the test.
the bound
Block sizes 2 to 4, plain or with an added vector, four numberings, every alignment, both directions: 144 settings, 12 consistent with the whole blocks, and every one fails the remaining known letters.
2
Best candidate against the known letters
Laid out as the copper carries K4: OBKR ends the line that finishes K3, then three lines of 31. Left, as carved, the 24 known places in accent. Right, the candidate: a known place it gets right is an accent cell, one it misses is outlined. This is the candidate with most known letters right; none passed every gate.
in: the copper, always the same
as carved, 97 letters; the 24 known places in accent
ECDMRIPFEIMEHNLSSTTRTVDOHW?OBKR
UOXOGHULBSOLIFBBWFLRVQQPRNGKSSO
TWTQSJQSSEKZZWATJKLUDIAWINFBNYP
VTTMZFPKWGDKZXTJCDIGKUHUAUEKCAR
OBKR ends the line that finishes K3, then three lines of 31
out: the candidate
every place read; known places in accent, misses outlined
ECDMRIPFEIMEHNLSSTTRTVDOHW?MQMH
CZPDGGADDVUBAZRSIBRGTNORTHEAOPU
WKBKRXSSHCYHFEOBNKMMRQUYCLTBFER
LINCLOBMSPJGHQNWCECYUQHOGBUWEWR
checked: the known letters in place, and the reading turns back into the copper
3
How the score is made
The loss of the best candidate, part by part. Zero is solved.
Known letters missed
8 of 24, ten points each
80.00
English
the 73 free letters score -8.51; English text scores -3.6
4.91
Key
114 bits to write it down (key words are cheap, arbitrary letters 4.7 bits each); each 60 beyond 60 costs a point
0.90
Loss
of 240, the worst possible
85.80 35.8%
4
Walkthrough, by hand
Redo the method on a few letters with pencil and paper.
Number the letters A=0 to Z=25.
Take blocks of two starting at position 1, so 23-24 and 25-26 are whole blocks inside EASTNORTHEAST: AS and TN, which are (0,18) and (19,13).
The carved letters there are LR and VQ: (11,17) and (21,16).
We want a 2x2 table M with M times (0,18) = (11,17) and M times (19,13) = (21,16), all mod 26.
Put the plaintext pairs side by side as a 2x2 matrix, invert it mod 26 if its determinant is coprime to 26, and multiply: that is M.
Now test M on the next block, 27-28, OR, which must come out as the carved QP.
If it does not, this setting is dead.
Repeat for every numbering, every alignment and the other direction.
the worksheet: the first steps by hand, on squared paper
5
Worked example, generated
The same steps run by the code on the real letters.
2x2, standard numbering A=0, blocks from position 1, matrix encrypts: solve from blocks 23-24 and 25-26
plain blocks AS=[0, 18] TN=[19, 13]; cipher blocks LR=[11, 17] VQ=[21, 16]
plaintext matrix [[0, 19], [18, 13]] has determinant 22, not invertible mod 26: use another pair of blocks
6
Hypothesis, for a cryptanalyst
Family, key space, the constraint under test, and the clues it reads.
The HILL column and Bauer's conjecture (knowledge/sources/bauer-2017-unsolved-chapter-notes.md, C21 reading a): K4 is a Hill cipher. Bauer and Edkins exhausted 2x2 and 3x3 under six numberings by search; 4x4, the affine form C = MP + v, and shifted numberings are open. A crib run of 13 letters contains, for block size n and alignment o, several whole blocks; with n of them whose plaintext matrix is invertible mod 26, M = C P^-1 is determined, and any further block is a check with chance 26^-n. For the affine form, block differences remove v and one more block is needed. Numberings: standard and KRYPTOS order, each 0-based and 1-based; both directions (the matrix encrypts or decrypts); alignments 0 to n-1. For every determined matrix the remaining crib blocks are checked, the text decrypted (the odd last letter left as is) and submitted if the cribs hold. 4x4 has four whole crib blocks at best, so it is determined with no check and must stand on the English of the rest; 4x4 affine needs five and is not determined here. Bounds: complete for the stated forms.
7
Prediction
Written before the run; the result decides it.
For 2x2 and 3x3, every numbering, alignment and direction gives a matrix from the first crib blocks that fails the remaining blocks, as Bauer found. The affine 2x2 and 3x3 forms fail the same way. For 4x4 a matrix exists for some settings with nothing left to check; its decryption of the other 73 letters is not English. Zero candidates pass.
8
Method
For each numbering map letters to 0-25.
For each block size n, alignment o and direction, list the whole crib blocks and their ciphertext blocks.
Plain form: pick n blocks with an invertible plaintext matrix, solve M, check the rest. Affine form: use differences between blocks to solve M, then v from one block, check the rest.
Decrypt the text with the inverse map; submit if all 24 cribs hold.
Record, per setting, how many blocks were available and how many checks passed.
9
Result and bounds
The harness's record: candidates, gates, loss, and the negative result this experiment leaves behind.