Hill Cipher Decryption in Number Theory: Step-by-Step with Example

Number Theory

1. Divisibility
- 1.1. Greatest Common Divisor
  - 1.1.1. Important Problems On Greatest Common Divisor
- 1.2. Expressing Cubes As Differences Of Squares
2. Prime Numbers
- 2.1. Important Problems On Prime Numbers
- 2.2. Prime Number Theorem
  - 2.2.1. The Prime Number Theorem Explained With Interpretation
3. Congruence
- 3.1. Linear Congruence
  - 3.1.1. Important Applications On Linear Congruence
4. Number Theoretic Functions
- 4.1. Greatest Integer Functions
  - 4.1.1. Divisibility Of Binomial Coefficients
5. Quadratic Reciprocity
- 5.1. Legendre Symbol
  - 5.1.1. Legendre Symbol And Its Properties
6. Fermats Last Theorem
- 6.1. Proof Of Fermats Last Theorem
- 6.2. Pythagorean Triples
  - 6.2.1. Important Problems On Pythagorean Triples
7. Integers As Sum Of Squares
- 7.1. Sum Of More Than Two Squares
  - 7.1.1. Representation Of Integers As Sums Of Five Nonzero Squares For All Values Greater Than Or Equal To 170
- 7.2. Sum Of Two Squares
  - 7.2.1. Perfect Squares In Pythagorean Triples
8. Encryption And Decryption
- 8.1. Linear Cipher
  - 8.1.1. Important Applications On Linear Cipher
- 8.2. Hill Cipher
  - 8.2.1. Hill Cipher Decryption In Number Theory Step By Step With Example

Tags

—No tags

Hill Cipher Decryption

This guide on Hill Cipher decryption in Number Theory provides a clear, step-by-step explanation of how to reverse the encryption process and recover the original message. Using basic concepts from linear algebra and modular arithmetic, it walks you through the method of finding the inverse key matrix and applying it to decode a ciphertext. With a detailed example and easy-to-follow instructions, this resource is perfect for students, educators, and anyone interested in classical ciphers and the mathematical principles behind secure communication.

Hill Cipher

The Hill cipher is a classical encryption technique based on linear algebra and modular arithmetic. It was introduced by Lester S. Hill in 1929 and encrypts plaintext by transforming it into vectors and applying a key matrix.

If \( P \) is a plaintext vector and \( K \) is an invertible \( n \times n \) matrix modulo 26, then the ciphertext \( C \) is given by:

C \equiv K \cdot P \pmod{26}

To decrypt the message, use the inverse of the key matrix:

P \equiv K^{-1} \cdot C \pmod{26}

2×2 Hill Cipher

Let the key matrix be:

K = \begin{pmatrix} 3 & 5 \\ 8 & 13 \end{pmatrix}

Convert plaintext (e.g., "HI") into numeric form: H = 7, I = 8, so:

P = \begin{pmatrix} 7 \\ 8 \end{pmatrix}

Then compute the ciphertext:

C = K \cdot P \pmod{26} = \begin{pmatrix} 3 & 5 \\ 8 & 13 \end{pmatrix} \begin{pmatrix} 7 \\ 8 \end{pmatrix} \equiv \begin{pmatrix} 3\cdot7 + 5\cdot8 \\ 8\cdot7 + 13\cdot8 \end{pmatrix} \equiv \begin{pmatrix} 21 + 40 \\ 56 + 104 \end{pmatrix} \equiv \begin{pmatrix} 61 \\ 160 \end{pmatrix} \equiv \begin{pmatrix} 9 \\ 4 \end{pmatrix} \pmod{26}

So the ciphertext is J (9), E (4) → "JE".

Example

The ciphertext B ZRVU GRNPEKSTWSQ has been enciphered with the cipher \(C_1\equiv 3P_1 +5P_2 \pmod{26}\), \(C_2\equiv 8P_1 +13P_2 \pmod{26}\). Derive the plaintext.

We have a Hill‐cipher on digraphs with key matrix

K \;=\; \begin{pmatrix} 3 & 5 \\[6pt] 8 & 13 \end{pmatrix},

The ciphertext is B Z R V U G R N P E K S T W S Q, which we group as:

\mathrm{BZ},\;\mathrm{RV},\;\mathrm{UG},\;\mathrm{RN},\;\mathrm{PE},\;\mathrm{KS},\;\mathrm{TW},\;\mathrm{SQ}.

We work modulo \(26\), with the mapping \(A \mapsto 0,\; B \mapsto 1,\dots,Z \mapsto 25\).

Step 1: Compute \(K^{-1} \bmod 26\)

\det(K) = 3\cdot13 - 5\cdot8 = 39 - 40 = -1 \equiv 25 \pmod{26},

So \((\det K)^{-1} \equiv 25\) since \(25 \cdot 25 = 625 \equiv 1 \pmod{26}\).

The adjugate of \(K\) is

\operatorname{adj}(K) = \begin{pmatrix} 13 & -5 \\[4pt] -8 & 3 \end{pmatrix} \equiv \begin{pmatrix} 13 & 21 \\[4pt] 18 & 3 \end{pmatrix} \pmod{26}.

Hence,

K^{-1} = 25\cdot\operatorname{adj}(K) \;\equiv\; \begin{pmatrix} 25\cdot13 & 25\cdot21 \\[6pt] 25\cdot18 & 25\cdot3 \end{pmatrix} \;\equiv\; \begin{pmatrix} 13 & 5 \\[4pt] 8 & 23 \end{pmatrix} \pmod{26}.

Step 2: Decrypt Each Digraph

For a ciphertext digraph \(C = (c_1, c_2)^T\),

P \;=\; K^{-1}C \;\pmod{26}.

Below we convert letters to numbers and back:

\begin{array}{|c|c|c|c|c|} \hline \text{Cipher} & (c_1,c_2) & K^{-1}C=(13c_1+5c_2,\;8c_1+23c_2)\!\!\!\!\!\pmod{26} & (p_1,p_2) & \text{Plain} \\ \hline \mathrm{BZ} & (1,25) & (13\cdot1+5\cdot25,\;8\cdot1+23\cdot25)\equiv(8,11) & (8,11) & I\,L \\ \mathrm{RV} & (17,21)& (13\cdot17+5\cdot21,\;8\cdot17+23\cdot21)\equiv(14,21)& (14,21)& O\,V \\ \mathrm{UG} & (20,6) & (13\cdot20+5\cdot6,\;8\cdot20+23\cdot6)\equiv(4,12) & (4,12) & E\,M \\ \mathrm{RN} & (17,13)& (13\cdot17+5\cdot13,\;8\cdot17+23\cdot13)\equiv(0,19) & (0,19) & A\,T \\ \mathrm{PE} & (15,4) & (13\cdot15+5\cdot4,\;8\cdot15+23\cdot4)\equiv(7,4) & (7,4) & H\,E \\ \mathrm{KS} & (10,18)& (13\cdot10+5\cdot18,\;8\cdot10+23\cdot18)\equiv(12,0) & (12,0) & M\,A \\ \mathrm{TW} & (19,22)& (13\cdot19+5\cdot22,\;8\cdot19+23\cdot22)\equiv(19,8) & (19,8) & T\,I \\ \mathrm{SQ} & (18,16)& (13\cdot18+5\cdot16,\;8\cdot18+23\cdot16)\equiv(2,18) & (2,18) & C\,S \\ \hline \end{array}

Step 3: Recover the Full Plaintext

Concatenating the plaintext digraphs yields:

\mathrm{IL}\;\mathrm{OV}\;\mathrm{EM}\;\mathrm{AT}\;\mathrm{HE}\;\mathrm{MA}\;\mathrm{TI}\;\mathrm{CS},

i.e.

\boxed{\text{I\,LOVE\,MATHEMATICS}.}