# Clarification on Hill Cipher crib dragging technique

--- this has been edited as I realised the question was silly. replaced with helpful information ---

I want to confirm the following:

Given ciphertext "AGHTDIX... [cont.]" (C)

and crib (a word which I know exists in the plaintext) "WITH" (P)

I am attempting to find the key (K) by shifting "WITH" one spot down the text each time like so:

A   G   H   T   D   I   X
W   I   T   H   .   .   .
.   .   .   .   .   .   .
.   .   W   I   T   H   .
.   .   .   .   .   .   .


And calculating it using the formula (multiply the ciphertext matrix by the modular inverse of the plaintext/crib - sorry, I don't know how to insert proper formulas here):

[K] = [C] x [P]-1 (mod 26)


My question -- was -- really silly as I forgot that the Hill cipher encrypts in pairs. Crib dragging should then adapt to include letters which could come before or after the known plaintext.

A   G   H   T   D   I   X
W   I   T   H   .   .   .
[?  W]  [I  T]  [H  ?]  .
.   .   W   I   T   H   .
.   .   .   .   .   .   .


Answer below explains in better detail. Thank you :)

I suppose (as you use a length $4$ crib) that your encryption matrix $C$ is of the form

$$\begin{bmatrix} k_{11} & k_{12}\\ k_{21} & k_{22}\\ \end{bmatrix}$$

and so assuming word $(w_1, w_2, w_3, w_4)$ at a certain position $m$ gives two systems of equations $$\begin{bmatrix} k_{11} & k_{12}\\ k_{21} & k_{22}\\ \end{bmatrix} \begin{bmatrix} w_1\\ w_2\\ \end{bmatrix} = \begin{bmatrix} c_m\\ c_{m+1}\\ \end{bmatrix}$$ and

$$\begin{bmatrix} k_{11} & k_{12}\\ k_{21} & k_{22}\\ \end{bmatrix} \begin{bmatrix} w_3\\ w_4\\ \end{bmatrix} = \begin{bmatrix} c_{m+2}\\ c_{m+3}\\ \end{bmatrix}$$

which gives $4$ equations in the four key entries, rewritten as, e.g. $$\begin{bmatrix}w_1 & w_2 \\ w_3 & w_4\\ \end{bmatrix} \begin{bmatrix} k_{11} \\ k_{12} \end{bmatrix} = \begin{bmatrix}c_m \\ c_{m+2}\end{bmatrix}$$ and

$$\begin{bmatrix}w_1 & w_2 \\ w_3 & w_4\\ \end{bmatrix} \begin{bmatrix} k_{21} \\ k_{22} \end{bmatrix} = \begin{bmatrix}c_{m+1} \\ c_{m+3}\end{bmatrix}$$

which allows us to compute the candidate key entries as $$\begin{bmatrix}k_{11}\\k_{12}\end{bmatrix} = {\begin{bmatrix}w_1 & w_2 \\ w_3 & w_4\\\end{bmatrix}}^{-1} \begin{bmatrix}c_m \\ c_{m+2}\end{bmatrix}$$

etc. where we only have to compute the inverse of the plaintext matrix once in advance.

Then test these candidates on another part of the ciphertext (after WITH say) and check for sensible text. If we find it we have the correct $m$. The above holds if the crib WITH starts at a position where it is encrypted as (W,I) (T,H) which you should try first so $m$ even.). If it is at another position, we get more equations (6 for 3 pairs of cipher text) in 2 more unknowns (the 2 two missing plaintext characters before and after the crib) and have to solve those (easy by computer).