We keep secrets for a LOT of reasons

And for the most part, people and computers are really good at keeping them! Hooray!

But what good is knowledge I can't share? Like what's the point of even having a secret if I can't tell it to anyone?

Can

I

Tell

You

A

Secret?

Hill Cipher Demo goes here

So... what was that?

A Hill Cipher!

What's a cipher?

It's a process that turns one piece of text (plaintext) into a jumbled up piece of text (ciphertext) that is difficult* to undo.

The simplest cipher is a Caesar Cipher. How 2 Caesar?

Choose your plaintext, e.g. , and any number k from 0 to 25
For each letter in the plaintext, output the letter k after it in the alphabet, wrapping around after 26
Write down your ciphertext and key (k)
To turn it back into the original, plug in ciphertext and -k

Try it out!

k =

What's a Hill Cipher?

Just like any cipher, it turns plaintext into ciphertext and back again.

However, Hill Ciphers are much harder to crack than Caesar ciphers. Why is that?

Caesar ciphers have very few (26) possible keys. Hill Ciphers have many (∞), so you can't just check every key
Caesar enciphers one letter at a time, so are prone to frequency attacks; Hill Ciphers encipher groups of n, so are much less vunerable

How do they work?

In the simplest way possible, it's just a matrix to encipher and its inverse* to decipher.

Turn a chunk of text of length n into vector of numbers
Pass the vector through an n×n transformation matrix
Mod the result and turn it back into numbers

Let's go through each of the 4 basic steps

1. Make a key

We start with a text key:

For a Hill 2-cipher, we need to turn this into a 2x2 matrix. Take the first 4 letters and convert them to letters based on their position in the alphabet using this table

a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

So [placeholder] becomes [placeholder]. Notice:

We exclude all non-alphabetical characters. [why?]
We repeat the password if we're under length 4. [why?]

Then we can place those values into a matrix in row-major order

A =

-> Loading...

Note that unlike a Caesar Cipher, not all possible keys are valid. We'll get to why in step 3.

2. Encipher

This is the easiest step!

Remember, A =

Start with the plaintext:

Remember, we're using a Hill 2-cipher, so our matrix is 2x2: that means each input vector ("chunk") must be of length 2*.

So our chunks are Loading.... Like earlier, we omit all non-alphabetic characters to simplify the vectors*

Now convert our chunks into vectors of length 2: Loading...

And multiply each vector by the A-matrix to get enciphered vectors: Loading...

You might notice this outputting numbers WAY higher than 26 (which we can't turn into letters). That's because we're missing...

2.5. MODULUS!

TL;DR: we want to guarantee our numbers are back in range, so mod them by 26 to get in-range vectors. The longer explanation...

Straight linear transformations are relatively easy to undo (they're just multiplication and addition); outputting the full result gives a LOT of info to an attacker (can just look for linear combinations that add to, say, 1000 = not actually that many in the grand scheme of things)
We can't really fix this (and to some extent don't want to, since we want to be able to decrypt!) BUT can reduce the certainty of the information
Modulus does just that: it's the remainder, which can be attained from ∞ transformation outputs*.

In any case, mod-ing and translating back to text should finally turn into .

3. Make Decipher Key

All we've really done so far is:

Create a transformation matrix A from our key string
Create a list of vectors (a matrix!) P from our plaintext

... and encode AP mod 26 into text as ciphertext

If it weren't for the mod, step 3 would be obvious: find A^-1 and multiply AP by it.

Turns out, number theory is actually really nice here: via some fancy math*, we can find our decryption matrix, B.

This is where the key restrictions come in: we calculate B as B = (A^-1 * modinv(det A) * det(A)) mod 26, which requires A to be invertible AND its determinant to have a modular inverse. Your key is valid, so:

B =

4. Decipher

All the hard work is done! B in mod 26 behaves exactly like you'd expect A^-1 to behave regularly, so we can just:

Chunk up and vectorize Loading... into Loading...
Pass each chunk through B and mod them to get Loading...
Turn the chunks back into letters, to get Loading... (our original text was Loading...)

4 steps.

And two of them (enciphering and deciphering) are practically the same. Somehow, that's all we need to package up a secret for sharing.

How well does Hill protect our secrets though?

It's kinda bad

The Hill Cipher was developed mainly as an educational tool and a proof-of-concept for linear algebra-based block ciphers.

And it's really good at that! The key ideas are the same as encryption algorithms that computers actually use (e.g. aes, rsa), and it's a great intro to cryptography.

BUT we don't use it irl because:

It's perfectly linear, so if cracked on one block, whole transmission is cracked
More limited key space than other encryption methods (see requirements from step 3)
Padding (the "a"s we added to the end) gives repeated characters -> can hint at matrix
Patterns remain (can allow predictable documents to be cracked)

That leaves a LOT of space for improvement! One easy change is to increase matrix size from 2x2. This lets us "jumble" more letters at once, so get a more secure* message.

Play around with it on the next page!

Full Playground Goes here

Thanks for Reading!

ngl took WAY too long to do this but I think it's pretty nice :)

Before continuing, please enter a valid matrix A to do the enciphering! Go back to step 1, fix your matrix, then come back.

a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25