Chapter 124. Cryptography

Cryptography studies methods for protecting information.

Its basic tasks are confidentiality, integrity, authentication, and key exchange. A cryptographic system may hide a message, verify that data were not changed, prove identity, or allow two parties to agree on a secret over an insecure channel.

Linear algebra appears in cryptography through finite fields, vector spaces over modular arithmetic, matrix transformations, error-correcting codes, lattices, and systems of equations. Classical ciphers such as the Hill cipher use matrix multiplication modulo an integer. Modern cryptographic constructions use deeper algebraic structures, but many of their computations still reduce to vectors, matrices, rings, and finite-field linear algebra. MIT’s linear algebra notes introduce cryptography through finite fields and modular matrix operations, including the Hill cipher.

124.1 Plaintext, Ciphertext, and Keys

A plaintext is the original message.

A ciphertext is the encrypted message.

A key is auxiliary information that determines how encryption and decryption are performed.

The general pattern is

\text{plaintext} + \text{key} \longmapsto \text{ciphertext}.

Decryption reverses this process:

\text{ciphertext} + \text{key} \longmapsto \text{plaintext}.

A cryptographic scheme is secure only if an adversary cannot recover useful information without the required key.

124.2 Modular Arithmetic

Cryptography often uses arithmetic modulo an integer.

For an integer $m$ , two integers $a$ and $b$ are congruent modulo $m$ if

a \equiv b \pmod m.

This means that $m$ divides $a-b$ .

For example,

29 \equiv 3 \pmod {26}.

Modular arithmetic turns numbers into residue classes. In the alphabet cipher setting, letters may be represented by numbers modulo $26$ :

Letter	Number
A	0
B	1
C	2
$\cdots$	$\cdots$
Z	25

Then encryption can be expressed as arithmetic on numbers.

124.3 Finite Fields

A finite field is a field with finitely many elements.

The simplest finite fields are

\mathbb{F}_p

where $p$ is prime. Their elements are

0,1,2,\ldots,p-1,

with addition and multiplication performed modulo $p$ .

The prime condition is important. If $p$ is prime, every nonzero element has a multiplicative inverse.

For example, in $\mathbb{F}_5$ ,

2^{-1}=3

because

2\cdot 3 = 6 \equiv 1 \pmod 5.

Finite fields allow linear algebra to be performed in a finite setting. Vectors, matrices, bases, inverses, rank, and linear systems all make sense over $\mathbb{F}_p$ .

124.4 Vector Spaces over Finite Fields

The vector space

\mathbb{F}_p^n

consists of length- $n$ vectors whose entries are elements of $\mathbb{F}_p$ .

For example,

v = \begin{bmatrix} 2 \\ 0 \\ 4 \end{bmatrix} \in \mathbb{F}_5^3.

Vector addition and scalar multiplication are performed modulo $p$ .

u = \begin{bmatrix} 3 \\ 1 \\ 4 \end{bmatrix}, \qquad v = \begin{bmatrix} 2 \\ 0 \\ 4 \end{bmatrix},

then in $\mathbb{F}_5^3$ ,

u+v = \begin{bmatrix} 0 \\ 1 \\ 3 \end{bmatrix}.

The first coordinate is $3+2=5\equiv 0$ , and the third is $4+4=8\equiv 3$ .

124.5 Linear Ciphers

A linear cipher encrypts blocks of symbols using a linear transformation.

Let

x\in \mathbb{F}_p^n

be a plaintext block. Let $A$ be an invertible $n\times n$ matrix over $\mathbb{F}_p$ .

Encryption is

y=Ax.

Decryption is

x=A^{-1}y.

The matrix $A$ is the key.

The requirement that $A$ be invertible is essential. Without invertibility, different plaintext blocks may produce the same ciphertext block, and decryption would be ambiguous.

124.6 The Hill Cipher

The Hill cipher is a classical matrix cipher.

It groups letters into blocks, converts each block into a vector, and multiplies by a key matrix modulo $26$ .

For a block of two letters, choose a $2\times 2$ matrix

K = \begin{bmatrix} a & b \\ c & d \end{bmatrix}.

Encryption is

y \equiv Kx \pmod {26}.

The matrix must be invertible modulo $26$ . This means

\gcd(\det K,26)=1.

If the determinant shares a factor with $26$ , then $K$ has no inverse modulo $26$ , and decryption fails.

The Hill cipher is historically important because it shows how matrix multiplication can be used directly for encryption.

124.7 Example of Hill Encryption

Use the key matrix

K= \begin{bmatrix} 3 & 3 \\ 2 & 5 \end{bmatrix}.

Its determinant is

\det K = 3\cdot 5 - 3\cdot 2 = 9.

Since

\gcd(9,26)=1,

the matrix is invertible modulo $26$ .

Encode the plaintext block HI as

H=7,\qquad I=8.

Thus

x= \begin{bmatrix} 7 \\ 8 \end{bmatrix}.

Then

y = \begin{bmatrix} 3 & 3 \\ 2 & 5 \end{bmatrix} \begin{bmatrix} 7 \\ 8 \end{bmatrix} = \begin{bmatrix} 45 \\ 54 \end{bmatrix}.

Reduce modulo $26$ :

45\equiv 19, \qquad 54\equiv 2.

Thus

y= \begin{bmatrix} 19 \\ 2 \end{bmatrix}.

The ciphertext block is TC.

124.8 Decryption Matrix

To decrypt, compute

K^{-1} \pmod {26}.

For a $2\times 2$ matrix,

K^{-1} \equiv (\det K)^{-1} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix} \pmod {26}.

Here

\det K=9.

The inverse of $9$ modulo $26$ is $3$ , because

9\cdot 3=27\equiv 1 \pmod {26}.

Therefore

K^{-1} \equiv 3 \begin{bmatrix} 5 & -3 \\ -2 & 3 \end{bmatrix} \equiv \begin{bmatrix} 15 & 17 \\ 20 & 9 \end{bmatrix} \pmod {26}.

Check decryption:

\begin{bmatrix} 15 & 17 \\ 20 & 9 \end{bmatrix} \begin{bmatrix} 19 \\ 2 \end{bmatrix} = \begin{bmatrix} 319 \\ 398 \end{bmatrix}.

Reducing modulo $26$ ,

319\equiv 7, \qquad 398\equiv 8.

This recovers HI.

124.9 Affine Ciphers

An affine cipher combines a linear transformation with a translation.

For a vector block $x$ , encryption has the form

y=Ax+b.

Here $A$ is an invertible matrix and $b$ is a fixed vector.

Decryption is

x=A^{-1}(y-b).

Affine transformations are familiar from geometry. In cryptography, they act on finite vector spaces.

Affine ciphers are more general than purely linear ciphers, but they remain vulnerable to known-plaintext attacks because linear structure is easy to recover from enough examples.

124.10 Known-Plaintext Attacks on Linear Ciphers

A known-plaintext attack assumes that an adversary knows some plaintext blocks and their corresponding ciphertext blocks.

For a linear cipher

y=Ax,

suppose the adversary knows pairs

(x_1,y_1),\ldots,(x_n,y_n).

Form matrices

X= \begin{bmatrix} | & | & & | \\ x_1 & x_2 & \cdots & x_n \\ | & | & & | \end{bmatrix}, \qquad Y= \begin{bmatrix} | & | & & | \\ y_1 & y_2 & \cdots & y_n \\ | & | & & | \end{bmatrix}.

Then

Y=AX.

If $X$ is invertible, then

A=YX^{-1}.

Thus the key matrix can be recovered.

This shows why simple linear ciphers are not secure by modern standards.

124.11 Confusion and Diffusion

Classical cryptographic design often uses two principles: confusion and diffusion.

Confusion hides the relationship between the key and the ciphertext.

Diffusion spreads the influence of each plaintext symbol across many ciphertext symbols.

Linear transformations are useful for diffusion. A well-chosen matrix can spread one input difference across many output coordinates.

However, linear transformations alone are insufficient. If every operation is linear, the whole cipher can be reduced to one large linear map.

Modern block ciphers therefore combine nonlinear substitution layers with linear mixing layers.

124.12 Substitution-Permutation Networks

A substitution-permutation network is a common block cipher structure.

It alternates between nonlinear substitution and linear permutation or mixing.

A simplified round has the form:

x \mapsto L(S(x)) + k.

Here:

Symbol	Meaning
$S$	Nonlinear substitution layer
$L$	Linear mixing layer
$k$	Round key

The nonlinear layer creates confusion. The linear layer creates diffusion.

Repeated rounds make the relationship between plaintext, key, and ciphertext difficult to analyze.

124.13 Matrix Mixing Layers

A mixing layer may be represented by multiplication by a matrix over a finite field.

Let

x\in \mathbb{F}_{2^8}^4.

A mixing layer may compute

y=Mx,

where

M\in \mathbb{F}_{2^8}^{4\times 4}.

The goal is that a small change in $x$ affects many coordinates of $y$ .

This is linear algebra over a finite field, not over the real numbers.

Finite-field matrix multiplication is used because bytes can be treated as field elements.

124.14 Boolean Vector Spaces

Many cryptographic algorithms operate on bits.

A block of $n$ bits is a vector in

\mathbb{F}_2^n.

Bitwise exclusive-or is addition in $\mathbb{F}_2^n$ :

1+1=0.

A linear Boolean function has the form

f(x)=a^Tx

over $\mathbb{F}_2$ .

An affine Boolean function has the form

f(x)=a^Tx+b.

Nonlinear Boolean functions are essential in modern symmetric cryptography. They prevent the cipher from collapsing into a solvable linear system.

124.15 Stream Ciphers and Linear Recurrences

A stream cipher generates a keystream

z_0,z_1,z_2,\ldots

and encrypts by

c_i=m_i+z_i

over $\mathbb{F}_2$ .

Some stream cipher components use linear feedback shift registers.

A linear recurrence over $\mathbb{F}_2$ has the form

s_{k+n} = a_{n-1}s_{k+n-1} +\cdots+ a_1s_{k+1} +a_0s_k.

The state evolves linearly.

Such systems are efficient, but linearity makes them vulnerable if used alone. Secure stream ciphers combine linear state update with nonlinear filtering, irregular clocking, or nonlinear feedback.

124.16 Public-Key Cryptography

Public-key cryptography uses two keys.

The public key may be shared with everyone. The private key must be kept secret.

A public-key encryption scheme allows anyone to encrypt using the public key, but only the private-key holder can decrypt.

The mathematical design is based on a trapdoor function:

\text{easy with public information, hard to invert without secret information}.

Classical examples use number theory, such as integer factorization or discrete logarithms. Modern post-quantum candidates often use lattices, codes, multivariate polynomials, or hash functions.

Linear algebra appears in several of these families.

124.17 Linear Codes in Cryptography

Error-correcting codes can be used for cryptography.

A code-based cryptosystem may publish a matrix that looks like a general linear code, while the private key contains hidden structure that allows efficient decoding.

The McEliece cryptosystem is a classical example. It is based on the difficulty of decoding a general linear code, which can be written as solving noisy linear equations over a finite field. Lecture notes on lattice-based cryptography describe McEliece as relying on the problem of recovering $x$ from $y=Ax+e$ over a finite field when the error vector $e$ is small.

The public problem has the form

y=Ax+e.

Here:

Symbol	Meaning
$A$	Public matrix
$x$	Message or hidden vector
$e$	Small error vector
$y$	Received or encrypted vector

Without the secret code structure, decoding is computationally hard.

124.18 Lattices

A lattice is a discrete set of points generated by integer combinations of basis vectors.

Given linearly independent vectors

b_1,\ldots,b_n\in\mathbb{R}^m,

the lattice is

L= \{z_1b_1+\cdots+z_nb_n : z_i\in\mathbb{Z}\}.

In matrix form, if

B= \begin{bmatrix} | & | & & | \\ b_1 & b_2 & \cdots & b_n \\ | & | & & | \end{bmatrix},

then

L=\{Bz:z\in\mathbb{Z}^n\}.

Lattices are central in modern post-quantum cryptography. Their security is often based on the difficulty of finding short vectors, close vectors, or solving noisy linear equations.

124.19 Learning With Errors

The Learning With Errors problem, or LWE, is based on noisy linear equations.

A simplified form gives samples

(a_i,b_i)

where

b_i = a_i^Ts + e_i \pmod q.

Here $s$ is a secret vector, $a_i$ is public, and $e_i$ is a small error term.

In matrix form,

b=As+e \pmod q.

If there were no error, this would be an ordinary linear system over $\mathbb{Z}/q\mathbb{Z}$ . With the small error vector, recovering $s$ becomes hard for suitable parameters.

This is the same structural theme as code-based cryptography: linear equations become hard after controlled noise is added. Lattice cryptography lectures describe LWE as solving noisy linear equations of the form $y=Ax+e$ with small error.

124.20 Short Vector Problems

One central lattice problem is the shortest vector problem.

Given a lattice basis, find a nonzero lattice vector of minimum length.

Formally,

\text{find } v\in L,\; v\neq 0,\quad \text{minimizing } \|v\|.

Another problem is the closest vector problem:

\text{given } t,\; \text{find } v\in L \text{ minimizing } \|t-v\|.

These problems are geometric and algebraic. They depend on norms, bases, integer combinations, and changes of basis.

Cryptographic security often relies on the practical difficulty of solving such problems in high dimensions.

124.21 Basis Quality

The same lattice may have many bases.

A basis with short, nearly orthogonal vectors is easier to use.

A basis with long, highly skewed vectors may hide the structure of the lattice.

Two bases $B$ and $B'$ generate the same lattice if

B'=BU

where $U$ is an integer unimodular matrix, meaning

\det U=\pm 1.

This is a change of basis over the integers.

Many lattice cryptosystems use the distinction between a good private basis and a bad-looking public basis.

124.22 Hash Functions

A cryptographic hash function maps data of arbitrary length to a fixed-length digest.

H(m)=h.

A secure hash function should make it hard to find:

Property	Meaning
Preimage	Given $h$ , find $m$ with $H(m)=h$
Second preimage	Given $m$ , find $m'\neq m$ with same hash
Collision	Find any $m\neq m'$ with same hash

Hash functions are not usually simple linear maps. If they were linear, collisions and preimages would be easier to analyze.

However, their internal operations often include vector-like bit operations, finite word arithmetic, permutations, and mixing steps.

124.23 Message Authentication Codes

A message authentication code, or MAC, verifies integrity and authenticity using a shared secret key.

The sender computes

t=\operatorname{MAC}_k(m).

The receiver recomputes the tag and checks equality.

A secure MAC prevents an adversary from producing valid tags for new messages.

Some MAC constructions use finite-field arithmetic. Polynomial authentication, for example, evaluates data as coefficients of a polynomial over a finite field or ring.

This again connects cryptography with algebraic computation.

124.24 Digital Signatures

A digital signature scheme uses a private signing key and a public verification key.

The signer computes

\sigma=\operatorname{Sign}_{sk}(m).

Anyone can check

\operatorname{Verify}_{pk}(m,\sigma).

The goal is unforgeability: without the private key, an adversary should not be able to produce a valid signature on a new message.

Some modern signature schemes are lattice-based. Others are code-based, hash-based, or based on elliptic curves.

Linear algebra appears especially in lattice and code-based constructions.

124.25 Secret Sharing

Secret sharing splits a secret into pieces so that authorized groups can reconstruct it, while unauthorized groups learn nothing.

In Shamir secret sharing, choose a polynomial

f(x)=s+a_1x+\cdots+a_{t-1}x^{t-1}

over a finite field, where $s$ is the secret.

Each participant receives a point

(i,f(i)).

Any $t$ points determine the polynomial by interpolation, hence recover $s=f(0)$ .

Fewer than $t$ points do not determine the secret.

Polynomial interpolation is a linear algebra problem over a finite field. It can be written using a Vandermonde matrix.

124.26 Threshold Reconstruction

Suppose we have $t$ shares

(x_1,y_1),\ldots,(x_t,y_t).

The unknown polynomial coefficients satisfy

\begin{bmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^{t-1} \\ 1 & x_2 & x_2^2 & \cdots & x_2^{t-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_t & x_t^2 & \cdots & x_t^{t-1} \end{bmatrix} \begin{bmatrix} s \\ a_1 \\ \vdots \\ a_{t-1} \end{bmatrix} = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_t \end{bmatrix}.

The coefficient matrix is a Vandermonde matrix.

If the $x_i$ are distinct, the matrix is invertible over the field.

Thus reconstructing the secret is solving a linear system.

124.27 Multivariate Cryptography

Multivariate cryptography uses systems of polynomial equations over finite fields.

A public key may consist of quadratic polynomials

P_1(x_1,\ldots,x_n),\ldots,P_m(x_1,\ldots,x_n).

The private key gives hidden structure that makes inversion efficient.

The public problem is to solve

P(x)=y.

This is generally nonlinear, but linear algebra appears in attacks and algorithms through linearization, Macaulay matrices, Gröbner basis methods, rank conditions, and finite-field matrix reduction.

Thus even nonlinear cryptography often returns to large-scale linear algebra.

124.28 Side Note on Security

A mathematical construction being algebraically elegant does not imply security.

A secure cryptographic scheme needs precise threat models, parameter choices, reductions or strong evidence, implementation safety, side-channel resistance, and extensive public analysis.

Simple linear ciphers are useful for teaching but insecure in practice.

Modern cryptography uses linear algebra as one component inside carefully designed systems.

124.29 Cryptography and Linear Algebra

The dictionary is direct.

Cryptography concept	Linear algebra object
Bit string	Vector over $\mathbb{F}_2$
Block of symbols	Vector over a finite field
Linear cipher	Matrix multiplication
Decryption	Matrix inverse
Diffusion	Linear mixing map
Known-plaintext attack	Solving for an unknown matrix
Code-based cryptography	Linear codes and noisy equations
Lattice cryptography	Integer spans and basis reduction
LWE	Noisy modular linear system
Secret sharing	Vandermonde linear system
Boolean functions	Maps on $\mathbb{F}_2^n$
Multivariate attacks	Matrix linearization

Cryptography uses linear algebra both constructively and adversarially. Designers use matrices and vector spaces to build systems. Attackers use linear algebra to break weak structure.

124.30 Summary

Cryptography protects information by transforming it with secret structure.

Linear algebra appears first in classical matrix ciphers, where plaintext vectors are multiplied by invertible key matrices modulo an integer. It appears more deeply in finite-field vector spaces, Boolean functions, code-based cryptography, lattice cryptography, secret sharing, and multivariate systems.

The Hill cipher shows the simplest form:

y=Kx \pmod {26}.

Modern cryptography uses harder problems. Code-based systems hide structured error-correcting codes. Lattice-based systems use integer vector spaces and noisy modular equations such as

b=As+e \pmod q.

Secret sharing reconstructs information by solving finite-field linear systems.

The central principle is that cryptography often makes computation asymmetric. The intended user has secret structure that makes the problem easy. The adversary sees a matrix, vector, code, lattice, or polynomial system designed to make the inverse problem hard.