“F13.4e, Hill: 2x2 and 3x3, plain or affine, four letter numberings, every block alignment, solved from the ciphertext alone row by row; K4 against 100 shuffles, plants of both sizes”
F13.4e (issue #85), the Hill part. 0015 and 0105 killed every 2x2-4x4 Hill setting under the four standard numberings with the known letters; here they are not read. The classic ciphertext-only attack: each row of the decryption matrix (and its affine term) acts alone on every nth letter, so all 26^(n+1) rows are scored by the fit of their letters to English letter counts and the 2,000 best kept per row; rows are joined by a beam (bigram, then trigram fit inside blocks), the best invertible matrices scored by quadgrams and refined row by row, the best per setting rescored by MIX8m (F13.3). Changed before the run after dry runs: a sum of letter log-frequencies let rows that map every letter to E win, and 40 rows per row lost the true 3x3 rows (ranked 4-3,625 of 456,976). Settings: size 2 or 3, numbering standard or KRYPTOS order from 0 or from 1, block alignment 0..n-1: 20 cells. Statistic, copies and plants as 0234 (K4 against 100 shuffles; 8 plants per size, each against 10 own shuffles).
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. mixes letters in blocks of two or three using a small table of numbers. Without any known word it can still be broken one row of 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. at a time: each row decides every second (or third) letter, so we try every possible row and keep those whose letters look like English, then put the best rows together. We do it for K4the carved letters The 97 letters cut into the copper at the CIA, shown at the top of every experiment page., for shuffles of K4 and for hidden test messages.
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 idea
F13.4e, Hill: the matrix cipher solved from the carved letters alone, one row of the decoding table at a time.
the check
Every row scored by letter counts, rows joined by English pairs and triples, the best matrices refined; K4 against 100 shuffles.
the bound
2x2: plants read exactly 8/8 and K4 inside its shuffles (p 0.7327): closed. 3x3: plants found 4/8: blocked by power.
2
Experiment lineage
What this experiment was built on, from the lineage page: 12 experiments before it, back to the root of its line. Its number is in bold.
keptreverted, in its family's colour×error or timeoutreverted under today's rulesbuilt on a parent in the same familybuilt on a parent in another family
3
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?OYBU
LDAAMPCMIAABYLSKQSASIBTEDNCALPE
SDIANUNGDSFTORJAVOWSNATHOLFHAMY
KOULUTHRRDSSAOEACHFAHFOOSEBEFIW
checked: the known letters in place, and the reading turns back into the copper
4
How the score is made
The loss of the best candidate, part by part. Zero is solved.
Known letters missed
21 of 24, ten points each
210.00
English
the 73 free letters score -6.18; English text scores -3.6
2.58
Key
76 bits to write it down (key words are cheap, arbitrary letters 4.7 bits each); each 60 beyond 60 costs a point
0.27
Loss
of 240, the worst possible
212.85 88.7%
5
Walkthrough, by hand
Redo the method on a few letters with pencil and paper.
Number the letters, say A = 0 to Z = 25, and cut the carved text into blocks of three.
One row of the unknown decoding table turns each block into one message letter: try all 26 x 26 x 26 rows (and a shift) and keep the 40 whose letters look most like English.
Do the same for the other two rows.
Try every way of putting three kept rows together, read the whole text and keep the most English.
Compare K4's best with what shuffles of K4 reach.
the worksheet: the first steps by hand, on squared paper
6
Worked example, generated
The same steps run by the code on the real letters.
Row by row on a planted 2x2 Hill message (A = 0, matrix [[3, 3], [2, 5]]), no known letter:
carved VEEIFTMNEYMIAMQGBMLGFKJGPFAOFTPSKGHDBMPWTHFKEGOXQCDCWPDPAVKWVAAAUBLPAVBHXXHBAVRZAKTUUBNFNNZDKIZVW
rows found [[15, 17], [20, 9]], offsets [0, 0]; true inverse [[15, 17], [20, 9]]
reading TOOWILLTAKEAWEEKLYHOLIDAYHEWILLUSUALLYBEOBLIGEDTOABANDONTHEIDEAAFTERTHEFIRSTTHETOMBOFTUTANKHAMENW
7
Hypothesis, for a cryptanalyst
Family, key space, the constraint under test, and the clues it reads.
F8 (the HILL column, C21(a); Bauer's matrix conjecture) read without the known letters: the hedge for A2/A1 on a family the known letters killed exactly. F13.1 puts 3x3 Hill with an unknown numbering at 131 bits, under MIX8m's 189; with the four standard numberings it is 23-37 bits plus the alignment. The row-by-row attack is exact per row; with 32 letters per row the true row ranks in the hundreds or thousands of 456,976, so the beam keeps 2,000 per row, and the plants measure what is lost. Pre-registered: S = max z over the 20 cells against K4's 100 shuffles; K4 flags at p < 0.05; a size is decided when 6 of its 8 plants are above all 10 own shuffles.
8
Prediction
Written before the run; the result decides it.
Plants found 8/8 at 2x2 and most at 3x3 (32 letters per row is enough for letter counts to keep the true row among 40). K4 inside its shuffles (p above 0.05); readings at most 4-5 known letters. F8's Hill part closes ciphertext-only for the four numberings.
9
Method
Numberings: A=0 or A=1 on the standard or the KRYPTOS order. Alignments 0..n-1; letters outside whole blocks pass unchanged.
Per setting and row r: every (d_r1..d_rn, e_r) mod 26 scored by the English letter log-frequency of the letters it yields, plus the entropy of those letters (the fit of their counts to English, so a row that maps every letter to E does not win); the 2,000 best kept.
Rows joined by a beam: pairs of rows by English bigram fit inside each block (3,000 kept), the third row by trigram fit (3,000 kept), the 300 best invertible matrices scored by quadgrams on the whole text, the 20 best refined by swapping in any kept row while the score rises; the best rescored by MIX8m.
S = max z over 20 cells against K4's 100 shuffles; plants (random matrix, numbering, alignment, half affine) against 10 own shuffles each.
K4's best reading per cell submitted (key: size, numbering, alignment, matrix, offset).
10
Result and bounds
The harness's record: candidates, gates, loss, and the negative result this experiment leaves behind.
16candidates returned
0passed every gate
3/24known letters, best
88.7%lowest loss
nonechampion before
All 16 candidates, lowest loss first.
1failed at cribs3/24 known lettersloss 88.7%
ECDMRIPFEIMEHNLSSTTRTVDOHW?OYBU
LDAAMPCMIAABYLSKQSASIBTEDNCALPE
SDIANUNGDSFTORJAVOWSNATHOLFHAMY
KOULUTHRRDSSAOEACHFAHFOOSEBEFIW
2failed at cribs3/24 known lettersloss 88.7%
ECDMRIPFEIMEHNLSSTTRTVDOHW?OYBU
LDAAMPCMIAABYLSKQSASIBTEDNCALPE
SDIANUNGDSFTORJAVOWSNATHOLFHAMY
KOULUTHRRDSSAOEACHFAHFOOSEBEFIW
3failed at cribs2/24 known lettersloss 92.7%
ECDMRIPFEIMEHNLSSTTRTVDOHW?OBWQ
NCOZSWHOHAAARDBOTODATIPYPERDSKI
LHRLIESIEVESUNDEHEBBRESCLSPMLOF
REPRTENGBAILIBSHEIFTRACYEAGESAR
4failed at cribs2/24 known lettersloss 92.7%
ECDMRIPFEIMEHNLSSTTRTVDOHW?OBWQ
NCOZSWHOHAAARDBOTODATIPYPERDSKI
LHRLIESIEVESUNDEHEBBRESCLSPMLOF
REPRTENGBAILIBSHEIFTRACYEAGESAR
5failed at cribs2/24 known lettersloss 93.0%
ECDMRIPFEIMEHNLSSTTRTVDOHW?YWAQ
MPTFCKSEDPEYCWLWAKLETTSGHEWVITO
KYSMRRHITATTEKJLAMUISMVUVFONOCO
NEFLHARRYFPFXOLASAARUBNLORATYPR
6failed at cribs2/24 known lettersloss 93.0%
ECDMRIPFEIMEHNLSSTTRTVDOHW?YWAQ
MPTFCKSEDPEYCWLWAKLETTSGHEWVITO
KYSMRRHITATTEKJLAMUISMVUVFONOCO
NEFLHARRYFPFXOLASAARUBNLORATYPR
7failed at cribs1/24 known lettersloss 96.9%
ECDMRIPFEIMEHNLSSTTRTVDOHW?VIOE
NXENDACWALHAYEWDAMIHOPREERBYTHP
ENWEPSSFORNTVDREOGOHEENGLYOPEAG
IOPLRLCRDDEOMYLEACRITRISTOTJIRR
8failed at cribs1/24 known lettersloss 96.9%
ECDMRIPFEIMEHNLSSTTRTVDOHW?VIOE
NXENDACWALHAYEWDAMIHOPREERBYTHP
ENWEPSSFORNTVDREOGOHEENGLYOPEAG
IOPLRLCRDDEOMYLEACRITRISTOTJIRR
9failed at cribs1/24 known lettersloss 97.0%
ECDMRIPFEIMEHNLSSTTRTVDOHW?SFUO
MGRITLAHLBMBARRSDROYDLFESETHATH
STHRYGSATTREVYNNGSBELIPBESBEILO
SEKYTJNAIDHEYHUVTBHOURUPABOUCFR
10failed at cribs1/24 known lettersloss 97.0%
ECDMRIPFEIMEHNLSSTTRTVDOHW?SFUO
MGRITLAHLBMBARRSDROYDLFESETHATH
STHRYGSATTREVYNNGSBELIPBESBEILO
SEKYTJNAIDHEYHUVTBHOURUPABOUCFR
11failed at cribs0/24 known lettersloss 100.9%
ECDMRIPFEIMEHNLSSTTRTVDOHW?OOKI
RBERPOINGTPKODOCSYNEOLFOIEDEHZT
RNTITLITSTNUOFARATTDJURTHEVEWAF
IAUFNEUSTRISEVEALLLINNHOBETNHPE
12failed at cribs0/24 known lettersloss 100.9%
ECDMRIPFEIMEHNLSSTTRTVDOHW?OOKI
RBERPOINGTPKODOCSYNEOLFOIEDEHZT
RNTITLITSTNUOFARATTDJURTHEVEWAF
IAUFNEUSTRISEVEALLLINNHOBETNHPE
13failed at cribs0/24 known lettersloss 101.1%
ECDMRIPFEIMEHNLSSTTRTVDOHW?OBYT
BEMYITBHMADEDKOPPHTBMATBYGNWRAS
USCSULDENEQSTADDEZICRDUMWICUDAY
BURGSIVEOIROTECAMDBYAHIDETATTAR
14failed at cribs0/24 known lettersloss 101.1%
ECDMRIPFEIMEHNLSSTTRTVDOHW?OBYT
BEMYITBHMADEDKOPPHTBMATBYGNWRAS
USCSULDENEQSTADDEZICRDUMWICUDAY
BURGSIVEOIROTECAMDBYAHIDETATTAR
15failed at cribs0/24 known lettersloss 101.2%
ECDMRIPFEIMEHNLSSTTRTVDOHW?OGAS
WTNKTOUTWONMSBAUIRYROGHPEUYMVON
WWCSTBERYPFROSHLEMAAOGENLTBACKL
YZULHNSIPPFFRLAMYOGIBBHILEFCTJB
16failed at cribs0/24 known lettersloss 101.2%
ECDMRIPFEIMEHNLSSTTRTVDOHW?OGAS
WTNKTOUTWONMSBAUIRYROGHPEUYMVON
WWCSTBERYPFROSHLEMAAOGENLTBACKL
YZULHNSIPPFFRLAMYOGIBBHILEFCTJB
K4 statistic 0.90 at 2x2 kry0 align 0, p 0.733; plant power 2x2 8/8, 3x3 4/8; read exactly 8/8, 2/8