THE HILL CIPHER, RINGS, AND SOME LINEAR ALGEBRA

MATH 195

Usually, in linear algebra we take matrices with entries in the real numbers or some other field, but this is not strictly required. As can be seen, this extension has some interesting consequences for cryptography.

Hill Cipher

We take P = C = (ℤ/nℤ)^{k}, n > 1, k ≥ 1, e.g. n = 26, k = 3. We let K = GL(k, ℤ/nℤ) be the general linear group, the set of (k × k)-matrices K with entries from ℤ/nℤ that are invertible, i.e. for which there exists a k × k-matrix L over ℤ/nℤ such that KL = LK = I, the k × k identity matrix:

I = (\begin{matrix}1 & 0 & … & 0 \\ 0 & 1 & … & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & … & 1 \end{matrix})

We say that L is the inverse of K, or L = K^{−1}.

For example, GL(1, ℤ/nℤ) = (ℤ/nℤ)^{∗}.

The encryption is then E_{K}(α) = Kα, where α ∈ P is viewed as a column vector. To decrypt, we apply the inverse:

D_{K}(E_{K}(α)) = D_{K}(Kα) = K^{−1}(Kα) = (K^{−1}K)α = Iα = α.

Elementary Matrices

How can such an invertible matrix K be obtained? For a ∈ ℤ/nℤ, we have elementary matrices:

E_{ij}(a) = (\begin{matrix}1 & 0 & … & 0 & … & 0 \\ 0 & 1 & … & a & … & 0 \\ ⋮ & ⋮ & ... & ⋮ & & ⋮ \\ 0 & 0 & … & 1 & … & 0 \\ ⋮ & ⋮ & & ⋮ & ... & ⋮ \\ 0 & 0 & … & 0 & … & 1 \end{matrix})

where we take ones down the diagonal and a in the ith row and jth column.

Note that E_{ij}(a)^{−1} = E_{ij}(−a), so this matrix is invertible. To obtain a key, we pick i_{1}, j_{1}, a_{1}, …, i_{t}, j_{t}, a_{t} and take

K = E_{i_{1}j_{1}}(a_{1})E_{i_{2}j_{2}}(a_{2}) … E_{i_{t}j_{t}}(a_{t})

This is some of the material covered February 5–7, in Math 195: Cryptography, taught by Hendrik Lenstra, prepared by John Voight jvoight@math.berkeley.edu.

and the inverse is

K^{−1} = E_{i_{t}j_{t}}(−a_{t}) … E_{i_{1}j_{1}}(−a_{1})

since (gh)^{−1} = h^{−1}g^{−1}.

Rings

Let us develop this theory a bit further. We can do linear algebra not just over the real numbers or ℤ/nℤ, but over any ring. [See §5.1 in Fraleigh for a review of rings.]

Definition. A ring is a set R together with two operations

+ : R × R → R
(a, b) ↦ a + b

and

· : R × R → R
(a, b) ↦ a · b = ab

such that • R is an abelian group with respect to + (with neutral element 0);

• · is associative a(bc) = (ab)c and bilinear:

a(b + c) = ab + ac
(a + b)c = ac + bc

• There is an element 1 ∈ R such that for all a ∈ R, 1a = a1 = a.

Example. ℤ/nℤ, ℝ, ℤ are rings. M(k, ℤ/nℤ) is a ring (matrix multiplication is associative, for example, and the identity element is the identity matrix). In fact for any ring R, M(k, R), the set of (k × k)-matrices with entries in the ring R, is itself a ring.

In general, a ring is not a group under multiplication (because of a lack of inverses); we define

R^{∗} = {a ∈ R : ∃b ∈ R : ab = ba = 1},

and this is the group of units (or invertible elements) of R.

Example. We have for the ring ℤ/nℤ the group (ℤ/nℤ)^{∗}; for ℝ we have ℝ^{∗} = ℝ\{0}; ℤ^{∗} = {1, −1}, and M(k, ℤ/nℤ)^{∗} = GL(k, ℤ/nℤ).

Why do we need algebra for cryptography? We would like to endow our finite sets with some bit of structure to aid us in encrypting and decrypting. This structure helps us to solve problems, such as if we remove the opposite corners of a checkerboard and try to fill it with dominoes, if we color the squares in the ordinary way we see that it cannot be done (as we have more dark squares than light squares). In this case, we have solved a problem by putting a ℤ/2ℤ structure on the bland set of squares of the checkerboard.

Note that R^{∗} = R if and only if R = {0}. If R = {0}, then certainly R^{∗} = R, and conversely, if R^{∗} = R then 0 ∈ R^{∗} so 0 = 0b = 1 so a = 1a = 0a = 0, so R = {0}.

Not all rings are commutative, i.e. ab = ba for all a, b ∈ R: for example, for matrices,

(\begin{matrix}1 & 1 \\ 0 & 1 \end{matrix}) (\begin{matrix}1 & 0 \\ 1 & 1 \end{matrix}) = (\begin{matrix}2 & 1 \\ 1 & 1 \end{matrix})

whereas

(\begin{matrix}1 & 0 \\ 1 & 1 \end{matrix}) (\begin{matrix}1 & 1 \\ 0 & 1 \end{matrix}) = (\begin{matrix}1 & 1 \\ 1 & 2 \end{matrix})

If 0 ≠ 1, then 1 = 0 + 1 ≠ 1 + 1 = 2, so the matrix ring is not commutative, hence M(k, R) is not commutative if k ≥ 2, #R > 1.

Determinants

[For a review of determinants, you should consult any linear algebra text, for example, Hill, Elementary Linear Algebra with Applications. Elementary matrices are covered in §1.4, Determinants are covered in Chapter 2.]

Now we return to linear algebra over our ring ℤ/nℤ. The set of all (k × k)- matrices over ℤ/nℤ is denoted M(k, ℤ/nℤ) ⊃ GL(k, ℤ/nℤ). The determinant is the map

det : M(k, ℤ/nℤ) → ℤ/nℤ
det(A) = ∑_{σ∈Sym k} ϵ(σ) ∏_{i=1}^{k} a_{iσ(i)}

A = (a_{ij})_{1≤i,j≤k} where a_{ij} ∈ ℤ/nℤ, and the sum is taken over all permutations on the set of indices 1, …, k, where ϵ(σ) is the sign of the permutation (+1 if the permutation is even, i.e. composed of an even number of transpositions, −1 if σ is odd).

The determinant has the following properties:

• det A ∈ (ℤ/nℤ)^{∗} if and only if A is invertible.

• For all matrices A, B ∈ M(k, ℤ/nℤ), det(AB) = (det A)(det B) in ℤ/nℤ.

• Every K ∈ M(k, ℤ/nℤ) with det K = 1 is the product of finitely many

elementary matrices of the form E_{ij}(a). The first property (multiplicativity) is quite useful: If A is invertible, then there

is a matrix B such that AB = I, so det(A) det(B) = det(AB) = det(I) = 1, so det A is invertible in ℤ/nℤ, which proves one implication of the first property.

Or, more generally, let R be a commutative ring. We can define the determinant

det : M(k, R) → R.

E.g. for k = 2 given by

det (\begin{matrix}a & b \\ c & d \end{matrix}) = ad − bc

for any such matrix, a, b, c, d ∈ R. Notice that then intechanging rows, we get

det (\begin{matrix}c & d \\ a & b \end{matrix}) = cb − da = −(ad − bc)

since R is commutative.

Rule of thumb: All familiar rules about computing determinants that do not involve division are valid for square matrices over any commutative ring.

For k = 3, we have

det (\begin{matrix}a & b & c \\ d & e & f \\ g & h & i \end{matrix}) = aei − afh − bdi + bfg + cdh − ceg

where we take all permutations with the appropriate sign: we end up with k! terms, numbered by the permutations, in general,

det(a_{ij})_{1≤i,j≤k} = ∑_{σ∈Sym k} ϵ(σ) ∏_{i=1}^{k} a_{iσ(i)}

as before.

Determinants are multiplicative, but not additive: even though

det(AB) = det(A) det(B)

we do not necessarily have det(A + B) = det(A) + det(B).

There are a number of rules for computing determinants: in particular, we can row-reduce our matrix: take the matrix over ℤ/26ℤ:

K = (\begin{matrix}17 & 17 & 5 \\ 21 & 18 & 21 \\ 2 & 2 & 19 \end{matrix}) ≡ (\begin{matrix}−9 & −9 & 5 \\ −5 & −8 & −5 \\ 2 & 2 & −7 \end{matrix}) (mod 26).

We can subtract the second column from the first, and this will not change the determinant:

det K = det (\begin{matrix}0 & −9 & 5 \\ 3 & −8 & −5 \\ 0 & 2 & −7 \end{matrix}) = −3 det (\begin{matrix}−9 & 5 \\ 2 & −7 \end{matrix}) = −3(63 − 10) ≡ −3 (mod 26),

where we have used the property that given a zero, we can forget that row and column when expanding the determinant.

Using row-reduction to calculate determinants will save a great deal of time and is much more efficient than the general expansion (involving k! terms).

We may on occasion like to divide, so we revise our rule:

Rule: All familiar rules about computing determinants are valid for square matrices over any field.

Definition. A field is a commutative ring R with the property that R^{∗} = R \ {0}.

Example. ℝ is a field, but ℤ is not a field. ℤ/nℤ is a field if and only if n is prime.

Since 26 = 2 · 13, the ring ℤ/26ℤ is not a field. Instead, if you know about this, we can use the Chinese remainder theorem and reduce the task to a computation modulo 2

det K ≡ det (\begin{matrix}1 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \end{matrix}) ≡ 1 (mod 2)

and modulo 13

det K ≡ det (\begin{matrix}4 & 4 & 5 \\ −5 & 5 & −5 \\ 2 & 2 & 6 \end{matrix}) ≡ 10 (mod 13)

hence, det K ≡ 23 (mod 26).

THE HILL CIPHER, RINGS, AND SOME LINEAR ALGEBRA 5

Or, instead, we can change the size of the alphabet, replace 26 by a prime number, e.g. 29 or maybe 257.