On the Subject of the Hill CM

Sometimes, you need to scale a mountain rather than a hill.

All letter-number conversions are to be done with respect to the scheme A1Y25Z0. All rows and columns of the matrices are numbered from 1 going down or right respectively.

Concatenate the letters on all numbered screens in order, and convert them into numbers. These numbers, in reading order, are entries in an N×N matrix, where N is the number of letters on a given numbered screen. This matrix will be labeled M.

If the Submit Button is white, use matrix M to decrypt the word. Otherwise, you will need to calculate the inverse matrix, I, to decrypt the word.

Concatenate the encrypted word with the letters on screen A (if any), then split this string into substrings of the same length as the width of the matrix. These will be the vectors to be used with the matrix.

Perform matrix-vector multiplication on each vector using correct matrix, M or I. To do this:

  1. For each row of the matrix, multiply the Xth entry of the row with the Xth entry of the vector.
  2. Take the sum of these numbers, this result will be the Xth entry of the resulting vector.
  3. Take each entry, modulo 26, and convert it to a letter. You should now have a decrypted set of letters

The instructions to calculate matrix I are written on the next pages.

Calculating matrix I:

The first number you will need to figure out is D, the multiplicative inverse of the determinant of matrix M.

To do this, calculate the determinant of matrix M:

  1. For each entry in the first row of matrix M, its position will be labeled P, multiply it by the determinant of the submatrix of matrix M, with entries not in the same row or column of this entry.
    • The determinant of a 1×1 matrix is the only entry in that matrix.
    • The determinant of a 0×0 matrix is 1.
  2. Multiply this number by -1 if P is even, and 1 otherwise.
  3. Sum the results calculated from each entry considered. This is the determinant of matrix M.
    • For convenience, take this number modulo 26. This number will be labeled E.

The multiplicative inverse of this determinant, D, is an integer that satisfies the following equation:

E × D ≡ 1 (mod 26)

A few methods to calculate D will be provided on page 6.

Next, the cofactor of matrix M must be calculated. To do this:

  1. For each entry, calculate the determinant of the submatrix of matrix M, with entries not in the same row or column of this entry.
  2. If the sum of the row and column indices of this entry is even, multiply this number by 1. Otherwise, multiply this number by -1.

Then, the transpose of this cofactor matrix is calculated by flipping the entries of the matrix over its main diagonal (the diagonal going from top-left to bottom-right).

Finally, multiply each entry of this transposed matrix by D, modulo 26. This is the inverse matrix, I.

Example 1

Encrypted Word: CAMCWSC
Screen 1: ZWVP
Screen 2: AGIL
Screen 3: BDUQ
Screen 4: CEKY
Screen A: P
Using matrix I

Matrix M:

00232216
01070912
02042117
03051125

Determinant:

+ M1,1 × Determinant([[07, 09, 12], [04, 21, 17], [05, 11, 25]])
- M1,2 × Determinant([[01, 09, 12], [02, 21, 17], [03, 11, 25]])
+ M1,3 × Determinant([[01, 07, 12], [02, 04, 17], [03, 05, 25]])
- M1,4 × Determinant([[01, 07, 09], [02, 04, 21], [03, 05, 11]])
= -37, mod 26 = 15

7 × 15 = 105, mod 26 = 1 => D = 7

Cofactor, after mod 26:

17152400
06160915
17142310
09202523

Adjugate (Cofactor after transposing):

17061709
15161420
24092325
00151023

Inverse matrix, I (Adjugate × D):

17×706×717×709×7
15×716×714×720×7
24×709×723×725×7
00×715×710×723×7
119042119063
105112098140
168063161175
000105070161
15161511
01082010
12110519
00011805

Encrypted numbers: [3, 1, 13, 3], [23, 19, 3, 16 (extra from screen A)]

Using vector 1: [3, 1, 13, 3]

Entry #1: 15×3 + 16×1 + 15×13 + 11×3 = 289, mod 26 = 03 => C
Entry #2: 01×3 + 08×1 + 20×13 + 10×3 = 301, mod 26 = 15 => O
Entry #3: 12×3 + 11×1 + 05×13 + 19×3 = 169, mod 26 = 13 => M
Entry #4: 00×3 + 01×1 + 18×13 + 05×3 = 250, mod 26 = 16 => P

Using vector 2: [23, 19, 3, 16]

Entry #1: 15×23 + 16×19 + 15×3 + 11×16 = 870, mod 26 = 12 => L
Entry #2: 01×23 + 08×19 + 20×3 + 10×16 = 395, mod 26 = 05 => E
Entry #3: 12×23 + 11×19 + 05×3 + 19×16 = 804, mod 26 = 24 => X
Entry #4: 00×23 + 01×19 + 18×3 + 05×16 = 153, mod 26 = 23 => W (extra)

Decrypted Word: COMPLEX

Example 2:

Encrypted Word: OKOOPL
Screen 1: AAP
Screen 2: FVY
Screen 3: QPE
Using matrix M

Matrix M:

010116
062225
171605

Encrypted numbers: [15, 11, 15], [15, 16, 12]

Using vector 1: [15, 11, 15]

01×15 + 01×11 + 16×15 = 266, mod 26 = 06 => F
06×15 + 22×11 + 25×15 = 707, mod 26 = 05 => E
17×15 + 16×11 + 05×15 = 506, mod 26 = 12 => L

Using vector 2: [15, 16, 12]

01×15 + 01×16 + 16×12 = 223, mod 26 = 15 => O
06×15 + 22×16 + 25×12 = 742, mod 26 = 14 => N
17×15 + 16×16 + 05×12 = 571, mod 26 = 25 => Y

Decrypted Word: FELONY

A few methods to calculate D

Determining D - Logic Way

  • 1. Set up 7 variables: M, N, Q, R, T1, T2, T3.
  • 2. Set M equal to 26.
  • 3. Set N equal to E.
  • 4. Q is equal to M / N, rounded down.
  • 5. R is equal to M mod N.
  • 6. Set T1 equal to 0.
  • 7. Set T2 equal to 1.
  • 8. T3 is equal to T1 - (T2 × Q).
  • 9. Set M equal to N.
  • 10. Set N equal to R.
  • 11. Q is equal to M / N, rounded down.
  • 12. R is equal to M mod N.
  • 13. Set T1 equal to T2.
  • 14. Set T2 equal to T3.
  • 15. T3 is equal to T1 - (T2 × Q).
  • 16. Repeat steps 9 - 15 until R is equal to 0, stopping at step 12.
  • 17. D is equal to T2 mod 26.

Determining D - Brute Force Way

  • 1. Find K in this equation: ((K × 26) + 1) mod E = 0
  • 2. D is equal to: ((K × 26) + 1) / E
    • This can be used as well: (D × E) mod 26 = 1

Determining D - Degenerate Way

There’s going to be a cheat sheet somewhere down the line. I might as well do it for them:

E1357911151719212325
D1921153197231151725