Linear Algebra Application: Ciphers

Cryptography: Hill Ciphers

Imron Rosyadi

Cryptography: Hill Ciphers

The Art of Secrecy: Cryptography

Cryptography is the study of secure communication techniques that allow only the sender and intended recipient of a message to view its contents.

Key Terminology:

• Plaintext: The original, unencrypted message.
• Ciphertext: The encrypted message.
• Cipher: The algorithm used for encryption/decryption.
• Enciphering (Encryption): Converting plaintext to ciphertext.
• Deciphering (Decryption): Converting ciphertext to plaintext.

ECE Relevance:

• Secure Communications: Protecting data in transit (e.g., wireless, internet).
• Data Integrity: Ensuring messages haven’t been tampered with.
• Authentication: Verifying identities.
• Privacy: Securing personal and sensitive information.

Cryptography is crucial in modern ECE, from securing network traffic and IoT devices to protecting embedded systems. Linear algebra provides powerful tools for building and analyzing cryptographic systems.

Basic Ciphers: Substitution Ciphers

Substitution ciphers replace each letter of the alphabet with a different letter or symbol.

Example: Caesar Cipher (Shift Cipher)

• Each letter is shifted a fixed number of positions down the alphabet.
• Plain A becomes D, B becomes E, etc. (shift by 3).

Plaintext: ROME WAS NOT BUILT IN A DAY

Ciphertext: U RPH ZDV QRW EXLOW LQ D GDB

Weaknesses:

• Frequency Analysis: They preserve the frequencies of individual letters.
• Common letters like ‘E’, ‘T’, ‘A’ will still appear frequently, even if substituted.
• This makes them relatively easy to break using statistical methods.

Caution

Substitution ciphers are generally not secure for modern applications!

Hill Ciphers: A Linear Algebra Approach

To overcome the weaknesses of substitution ciphers, polygraphic systems encipher groups of letters instead of single ones.

• Polygraphic System: Divides plaintext into sets of \(n\) letters, which are then replaced by \(n\) cipher letters.
• Hill Ciphers: A class of polygraphic systems using matrix transformations.
  • Introduced by Lester S. Hill in the 1920s.
  • Uses a square matrix (the encoding matrix) to transform numerical representations of plaintext letters into ciphertext.
• Advantage: Conceals individual letter frequencies by mixing them within groups.

graph TD
    A[Plaintext Message] --> B{Group into N-tuples}
    B --> C[Convert Letters to Numbers]
    C --> D[Plaintext Vector $\mathbf{p}$]
    D -- Linear Transformation --> E[Multiply by Encoding Matrix A]
    E --> F[Ciphertext Vector $\mathbf{c} = A\mathbf{p} \pmod{26}$]
    F --> G[Convert Numbers to Letters]
    G --> H[Ciphertext Message]

    style A fill:#f9f,stroke:#333,stroke-width:2px
    style H fill:#bbf,stroke:#333,stroke-width:2px
    style E fill:#ccf,stroke:#333,stroke-width:2px

The core idea is to treat groups of letters as vectors and apply a linear transformation (matrix multiplication). This “scrambles” the letters in a way that simple frequency analysis no longer works.

Encoding Scheme: Letters to Numbers

For Hill Ciphers, each letter of the alphabet is assigned a numerical value. We use a 0-indexed system for ‘Z’ to simplify modular arithmetic later.

Note

Convention: A=1, B=2, …, Y=25, Z=0.

Table 1: Alphabet to Numerical Values

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
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	0

This mapping is crucial. The choice of Z=0 is specific to Hill Ciphers, allowing for direct use of modulo 26 arithmetic where 0 is a valid residue.

Hill Cipher Encoding Steps

Let’s formalize the encoding process for a Hill 2-cipher (using \(2 \times 2\) matrices).

1. Choose an Encoding Matrix \(A\): \[ A = \left[ \begin{array}{l l}{a_{11}} & {a_{12}}\\ {a_{21}} & {a_{22}} \end{array} \right] \]
   • \(A\) must have integer entries.
   • Certain conditions on \(A\) are required for decipherment (we’ll see this later).
2. Group Plaintext Letters:
   • Divide the plaintext into successive pairs of letters.
   • If the plaintext has an odd number of letters, add a “dummy” letter (e.g., ‘Z’) to the last pair.
3. Convert to Vectors & Multiply:
   • Replace each plaintext letter by its numerical value (from Table 1).
   • Form a plaintext column vector \(\mathfrak{p} = \left[ \begin{smallmatrix} p_1 \\ p_2 \end{smallmatrix} \right]\).
   • Compute the ciphertext vector \(\mathfrak{c} = A\mathfrak{p}\).
4. Convert to Alphabetic Equivalent:
   • Transform the numerical entries of \(\mathfrak{c}\) back into letters using Table 1.

This structured approach ensures consistency. The “dummy” letter is important to maintain pair groupings for the \(2 \times 2\) matrix operation.

Example: Encoding “IAM HIDING”

Let’s use the encoding matrix \(A = \left[ \begin{smallmatrix} 1 & 2 \\ 0 & 3 \end{smallmatrix} \right]\) to encipher “IAM HIDING”.

1. Group Plaintext: IAM HIDING \(\rightarrow\) IA, MH, ID, IN, GG (added dummy ‘G’ for even pairs).

2. Numerical Equivalent:

   • I=9, A=1
   • M=13, H=8
   • I=9, D=4
   • I=9, N=14
   • G=7, G=7

3. Enciphering IA: \[ \left[ \begin{array}{l l}{1} & {2}\\ {0} & {3} \end{array} \right] \left[ \begin{array}{l}{9}\\ {1} \end{array} \right] = \left[ \begin{array}{l}{1 \cdot 9 + 2 \cdot 1}\\ {0 \cdot 9 + 3 \cdot 1} \end{array} \right] = \left[ \begin{array}{l}{11}\\ {3} \end{array} \right] \] From Table 1: \(11 \rightarrow K\), \(3 \rightarrow C\). So, KC.

4. Enciphering MH: \[ \left[ \begin{array}{l l}{1} & {2}\\ {0} & {3} \end{array} \right] \left[ \begin{array}{l}{13}\\ {8} \end{array} \right] = \left[ \begin{array}{l}{1 \cdot 13 + 2 \cdot 8}\\ {0 \cdot 13 + 3 \cdot 8} \end{array} \right] = \left[ \begin{array}{l}{13 + 16}\\ {24} \end{array} \right] = \left[ \begin{array}{l}{29}\\ {24} \end{array} \right] \] Problem: The number 29 has no alphabet equivalent (max is 25 for Y). Solution: We use modular arithmetic! Any number greater than 25 is replaced by its remainder after division by 26. \(29 \pmod{26} = 3\). So, \(\left[ \begin{smallmatrix} 3 \\ 24 \end{smallmatrix} \right]\). From Table 1: \(3 \rightarrow C\), \(24 \rightarrow X\). So, CX.

This example highlights the need for modular arithmetic. The output of matrix multiplication can easily exceed 25, requiring us to “wrap around” within our alphabet’s numerical range.

Modular Arithmetic: The Crypto Backbone

Modular arithmetic is fundamental to Hill Ciphers (and most modern cryptography).

Important

Definition: If \(m\) is a positive integer (the modulus), and \(a, b\) are any integers, then \(a\) is equivalent to \(b\) modulo \(m\), written \(a \equiv b \pmod{m}\), if \(a - b\) is an integer multiple of \(m\).

Examples of Equivalences:

• \(7 \equiv 2 \pmod{5}\) (because \(7 - 2 = 5\), which is \(1 \cdot 5\))
• \(19 \equiv 3 \pmod{2}\) (because \(19 - 3 = 16\), which is \(8 \cdot 2\))
• \(-1 \equiv 25 \pmod{26}\) (because \(-1 - 25 = -26\), which is \(-1 \cdot 26\))
• \(12 \equiv 0 \pmod{4}\) (because \(12 - 0 = 12\), which is \(3 \cdot 4\))

For any modulus \(m\), every integer \(a\) is equivalent to exactly one integer in the set \(Z_m = \{0, 1, 2, \ldots, m-1\}\). This integer is called the residue of \(a\) modulo \(m\).

The modulus \(m\) for our alphabet is 26, as there are 26 letters. This ensures that all numerical results “fit” back into our alphabet mapping.

Finding Residues (Interactive)

The residue of a non-negative integer \(a\) modulo \(m\) is simply the remainder when \(a\) is divided by \(m\). For negative integers, a theorem helps:

Tip

Theorem 10.14.1: For any integer \(a\) and modulus \(m\), let \(R = \text{remainder of } \frac{|a|}{m}\). Then the residue \(r\) of \(a\) modulo \(m\) is: \[ r = \left\{ \begin{array}{l l}{R} & {i f a \geq 0}\\ {m - R} & {i f a < 0 \text{ and } R \neq 0}\\ 0 & {i f a < 0 \text{ and } R = 0} \end{array} \right. \]

Example 3: Residues mod 26

• 1. \(87 \pmod{26}\): \(|87|=87\), \(87 \div 26 = 3\) remainder \(9\). Since \(a \geq 0\), \(r=9\). Thus, \(87 \equiv 9 \pmod{26}\).
• 2. \(-38 \pmod{26}\): \(|-38|=38\), \(38 \div 26 = 1\) remainder \(12\). Since \(a < 0\) and \(R \neq 0\), \(r = 26 - 12 = 14\). Thus, \(-38 \equiv 14 \pmod{26}\).
• 3. \(-26 \pmod{26}\): \(|-26|=26\), \(26 \div 26 = 1\) remainder \(0\). Since \(a < 0\) and \(R = 0\), \(r=0\). Thus, \(-26 \equiv 0 \pmod{26}\).

Finding Residues (Interactive)

Play with the inputs to see how residues are calculated.

viewof num_input = Inputs.text({label: "Enter an integer (a)", value: "87"});
viewof mod_input = Inputs.text({label: "Enter a modulus (m)", value: "26"});

The Pyodide block directly computes the residue. This interactive tool helps students grasp the concept by testing various positive and negative inputs with different moduli.

Multiplicative Inverses Modulo m

In ordinary arithmetic, every non-zero number \(a\) has a reciprocal \(a^{-1}\) such that \(a \cdot a^{-1} = 1\). In modular arithmetic, we seek \(a^{-1} \in Z_m\) such that \(a \cdot a^{-1} \equiv 1 \pmod{m}\).

Tip

A number \(a\) has a unique reciprocal modulo \(m\) if and only if \(a\) and \(m\) have no common prime factors (i.e., \(\text{gcd}(a, m) = 1\)).

Example 4: Reciprocal of 3 mod 26

• \(\text{gcd}(3, 26) = 1\), so a reciprocal exists.
• We need \(3x \equiv 1 \pmod{26}\).
• By trying values from \(0\) to \(25\), we find \(x=9\), because \(3 \cdot 9 = 27 \equiv 1 \pmod{26}\).
• Thus, \(3^{-1} \equiv 9 \pmod{26}\).

Example 5: A Number with No Reciprocal mod 26

• The number \(4\) has no reciprocal modulo \(26\).
• Why? Because \(4\) and \(26\) share a common prime factor: \(2\). (\(\text{gcd}(4, 26) = 2 \neq 1\)).

Multiplicative Inverses Modulo m (Interactive)

Test if a number has a reciprocal modulo \(m\), and find it if it exists.

viewof a_val = Inputs.text({label: "Enter number (a)", value: "3"});
viewof m_val_inv = Inputs.text({label: "Enter modulus (m)", value: "26"});

This interactive block demonstrates the condition for existence of a modular inverse and provides a simple way to find it. This is critical for understanding Hill cipher decipherment.

Enciphering a Pair (Interactive)

Let’s use the encoding matrix \(A = \left[ \begin{smallmatrix} 1 & 2 \\ 0 & 3 \end{smallmatrix} \right]\) to encipher any plaintext pair.

Recall: A=1, …, Y=25, Z=0.

viewof a11_enc = Inputs.text({label: "A[0,0]", value: "1"});
viewof a12_enc = Inputs.text({label: "A[0,1]", value: "2"});
viewof a21_enc = Inputs.text({label: "A[1,0]", value: "0"});
viewof a22_enc = Inputs.text({label: "A[1,1]", value: "3"});
viewof p1_enc = Inputs.text({label: "Plaintext Char 1 (e.g., 9 for I)", value: "9"});
viewof p2_enc = Inputs.text({label: "Plaintext Char 2 (e.g., 1 for A)", value: "1"});

This interactive block allows students to perform the core Hill cipher encoding operation for a pair of letters. They can change the encoding matrix or the plaintext input and see the resulting ciphertext.

Deciphering Hill Ciphers: The Inverse Matrix

To decode a Hill cipher, we need the inverse of the encoding matrix \(A\), denoted \(A^{-1}\), modulo \(m\).

If \(\mathbf{c} = A\mathbf{p} \pmod{m}\) is the ciphertext, then \(\mathbf{p} = A^{-1}\mathbf{c} \pmod{m}\) is the plaintext.

Important

Theorem 10.14.2: A square matrix \(A\) with entries in \(Z_m\) is invertible modulo \(m\) if and only if the residue of \(\det(A)\) modulo \(m\) has a reciprocal modulo \(m\).

Corollary 10.14.4 (for \(m=26\)): \(A\) is invertible modulo 26 if and only if the residue of \(\det(A)\) modulo 26 is not divisible by 2 or 13.

Inverse for a \(2 \times 2\) matrix (mod 26):

If \(A = \left[ \begin{smallmatrix} a & b \\ c & d \end{smallmatrix} \right]\), then \(A^{-1} = (\det(A))^{-1} \left[ \begin{smallmatrix} d & -b \\ -c & a \end{smallmatrix} \right] \pmod{26}\).

Where \((\det(A))^{-1}\) is the reciprocal of \(\det(A) = ad-bc\) modulo 26.

The condition on the determinant is crucial. If \(\det(A)\) shares factors with 26 (2 or 13), the matrix is not invertible, and the message cannot be uniquely deciphered. This is a design constraint for encoding matrices.

Example: Inverse of \(A = \left[ \begin{smallmatrix} 5 & 6 \\ 2 & 3 \end{smallmatrix} \right] \pmod{26}\)

1. Calculate Determinant:

   \(\det(A) = (5 \cdot 3) - (6 \cdot 2) = 15 - 12 = 3\).

2. Find \((\det(A))^{-1} \pmod{26}\):

   We need \(3^{-1} \pmod{26}\). From our earlier example/interactive, \(3^{-1} \equiv 9 \pmod{26}\).

3. Apply Inverse Formula: \[ A^{-1} = 9 \left[ \begin{array}{rr} 3 & -6 \\ -2 & 5 \end{array} \right] \pmod{26} \]

   • Multiply each entry by 9: \[ \left[ \begin{array}{rr} 9 \cdot 3 & 9 \cdot (-6) \\ 9 \cdot (-2) & 9 \cdot 5 \end{array} \right] = \left[ \begin{array}{rr} 27 & -54 \\ -18 & 45 \end{array} \right] \]
   • Take each entry modulo 26:
     • \(27 \pmod{26} = 1\)
     • \(-54 \pmod{26} = -54 + 3 \cdot 26 = -54 + 78 = 24\)
     • \(-18 \pmod{26} = -18 + 1 \cdot 26 = 8\)
     • \(45 \pmod{26} = 45 - 1 \cdot 26 = 19\)

   So, \(A^{-1} = \left[ \begin{array}{rr} 1 & 24 \\ 8 & 19 \end{array} \right] \pmod{26}\).

This example demonstrates the full process of finding a modular inverse matrix. It combines determinant calculation, finding modular reciprocals, and modular arithmetic for each entry of the adjoint matrix.

Example: Decoding “GTNKGKDUSK”

Using \(A^{-1} = \left[ \begin{smallmatrix} 1 & 24 \\ 8 & 19 \end{smallmatrix} \right]\) (from previous example) to decode “GTNKGKDUSK”.

1. Ciphertext to Numerical Pairs:

   GT (7, 20), NK (14, 11), GK (7, 11), DU (4, 21), SK (19, 11)

2. Deciphering GT: \[ \left[ \begin{array}{rr} 1 & 24 \\ 8 & 19 \end{array} \right] \left[ \begin{array}{l}{7}\\ {20} \end{array} \right] = \left[ \begin{array}{l}{1 \cdot 7 + 24 \cdot 20}\\ {8 \cdot 7 + 19 \cdot 20} \end{array} \right] = \left[ \begin{array}{l}{7 + 480}\\ {56 + 380} \end{array} \right] = \left[ \begin{array}{l}{487}\\ {436} \end{array} \right] \]

   Take modulo 26:

   • \(487 \pmod{26} = 18 \pmod{26} = 19\) (\(487 = 18 \cdot 26 + 19\))
   • \(436 \pmod{26} = 20 \pmod{26} = 20\) (\(436 = 16 \cdot 26 + 20\))

   Resulting plaintext vector: \(\left[ \begin{smallmatrix} 19 \\ 20 \end{smallmatrix} \right]\).

   From Table 1: \(19 \rightarrow S\), \(20 \rightarrow T\). So, ST.

3. Deciphering NK: \[ \left[ \begin{array}{rr} 1 & 24 \\ 8 & 19 \end{array} \right] \left[ \begin{array}{l}{14}\\ {11} \end{array} \right] = \left[ \begin{array}{l}{1 \cdot 14 + 24 \cdot 11}\\ {8 \cdot 14 + 19 \cdot 11} \end{array} \right] = \left[ \begin{array}{l}{14 + 264}\\ {112 + 209} \end{array} \right] = \left[ \begin{array}{l}{278}\\ {321} \end{array} \right] \]

   Take modulo 26:

   • \(278 \pmod{26} = 18 \pmod{26} = 18\) (\(278 = 10 \cdot 26 + 18\))
   • \(321 \pmod{26} = 9 \pmod{26} = 9\) (\(321 = 12 \cdot 26 + 9\))

   Resulting plaintext vector: \(\left[ \begin{smallmatrix} 18 \\ 9 \end{smallmatrix} \right]\).

   From Table 1: \(18 \rightarrow R\), \(9 \rightarrow I\). So, RI.

Continuing this process for all pairs yields: STRIKE NOWW.

The decoding process is simply the reverse of encoding, using the inverse matrix. This confirms the mathematical elegance of Hill Ciphers.

Breaking the Code: Known Plaintext Attack

Cryptographers also study how to break ciphers (decipher without the key/matrix).

One method for Hill Ciphers is the Known Plaintext Attack.

Scenario: You intercept a ciphertext and have a guess about a small portion of the original plaintext (e.g., “DEAR”).

Tip

Theorem 10.14.5 (Determining the Deciphering Matrix):

For a Hill \(n\)-cipher, if you know \(n\) linearly independent plaintext vectors \(\mathbf{p}_1, \ldots, \mathbf{p}_n\) and their corresponding ciphertext vectors \(\mathbf{c}_1, \ldots, \mathbf{c}_n\), you can find the deciphering matrix \(A^{-1}\).

• Form matrices \(P = \left[ \begin{smallmatrix} \mathbf{p}_1^T \\ \vdots \\ \mathbf{p}_n^T \end{smallmatrix} \right]\) and \(C = \left[ \begin{smallmatrix} \mathbf{c}_1^T \\ \vdots \\ \mathbf{c}_n^T \end{smallmatrix} \right]\).
• Apply elementary row operations to reduce \([C \mid P]\) to \([I \mid (A^{-1})^T]\).
• The deciphering matrix \(A^{-1}\) is the transpose of the right side.

For a Hill 2-cipher, we need 2 known plaintext-ciphertext pairs.

This theorem shows the vulnerability of Hill ciphers. If an attacker can guess even a small part of the message, they might be able to derive the entire decryption key. This is why strong ciphers today are designed to be resistant to such attacks.

Example: Deciphering with Known Plaintext

Intercepted Ciphertext: IOSBTGXESPXHOPDE

Known Plaintext: The message starts with DEAR.

1. Known Plaintext/Ciphertext Pairs (Numerical):

   • DE \(\rightarrow\) IO \(\mathbf{p}_1 = \left[ \begin{smallmatrix} 4 \\ 5 \end{smallmatrix} \right]\) (D=4, E=5) \(\leftrightarrow\) \(\mathbf{c}_1 = \left[ \begin{smallmatrix} 9 \\ 15 \end{smallmatrix} \right]\) (I=9, O=15)
   • AR \(\rightarrow\) SB \(\mathbf{p}_2 = \left[ \begin{smallmatrix} 1 \\ 18 \end{smallmatrix} \right]\) (A=1, R=18) \(\leftrightarrow\) \(\mathbf{c}_2 = \left[ \begin{smallmatrix} 19 \\ 2 \end{smallmatrix} \right]\) (S=19, B=2)

2. Form Matrices \(C\) and \(P\): \(C = \left[ \begin{smallmatrix} 9 & 15 \\ 19 & 2 \end{smallmatrix} \right]\) and \(P = \left[ \begin{smallmatrix} 4 & 5 \\ 1 & 18 \end{smallmatrix} \right]\).

3. Augmented Matrix \([C \mid P]\) and Row Operations (mod 26):

   The goal is to transform \([C \mid P]\) into \([I \mid (A^{-1})^T]\). This is a tedious process of modular row operations.

   The text provides the detailed steps, which involve finding modular inverses for pivots and performing row additions/multiplications modulo 26.

   After performing the necessary row operations (as shown in the source text), we arrive at: \[ \left[ \begin{array}{cc|cc} 1 & 0 & 1 & 0 \\ 0 & 1 & 17 & 9 \end{array} \right] \pmod{26} \] Thus, \((A^{-1})^T = \left[ \begin{smallmatrix} 1 & 0 \\ 17 & 9 \end{smallmatrix} \right]\).

4. Deciphering Matrix \(A^{-1}\): \(A^{-1} = ((A^{-1})^T)^T = \left[ \begin{smallmatrix} 1 & 17 \\ 0 & 9 \end{smallmatrix} \right]\).

5. Decode the Full Message:

   Using this \(A^{-1}\) on the entire ciphertext IOSBTGXESPXHOPDE yields:

   DE AR IK ES EN DT AN KS \(\rightarrow\) DEAR IKE SEND TANKS

This example shows how linear algebra, specifically Gaussian elimination, can be used not just for encryption but also for cryptanalysis. It’s a powerful demonstration of the double-edged sword of mathematical tools in security.

Linear Algebra in ECE: Beyond Hill Ciphers

The principles seen in Hill Ciphers extend to many vital ECE applications.

1. Digital Signal Processing (DSP):

• Transformations: Fourier Transforms (DFT, FFT) are linear transformations, essential for signal analysis, filtering, and compression.
• Filtering: Convolution operations can be represented as matrix multiplications.

2. Error Correction Codes:

• Coding Theory: Linear block codes (e.g., Hamming codes, Reed-Solomon codes) use finite field linear algebra to detect and correct errors in data transmission.

3. Control Systems:

• State-Space Representation: Linear systems are modeled using matrices (A, B, C, D) to analyze stability, controllability, and observability.

4. Communications Systems:

• MIMO (Multiple-Input, Multiple-Output): Uses matrix algebra for spatial multiplexing and beamforming to increase data rates and reliability in wireless communication.
• Modulation/Demodulation: Can involve linear transformations of signals.

5. Computer Graphics and Vision:

• Transformations: 2D/3D rotations, scaling, translations are represented by matrices.
• Image Processing: Filters, edge detection, and feature extraction often involve matrix operations.

6. Machine Learning/AI:

• Neural Networks: Core operations are matrix multiplications and vector additions.
• Data Analysis: Principal Component Analysis (PCA) for dimensionality reduction relies on eigenvectors and eigenvalues.

This slide highlights the broad impact of linear algebra across various ECE disciplines. Cryptography is just one example of its fundamental role in modern engineering.

Conclusion

Key Takeaways

• Hill Ciphers leverage matrix multiplication and modular arithmetic for polygraphic encryption, improving security over simple substitution ciphers.
• Modular Arithmetic is essential for keeping numerical results within a defined range, crucial for alphabet mapping.
• Matrix Inverses Modulo m enable decipherment and require specific conditions on the determinant.
• Known Plaintext Attacks demonstrate vulnerabilities, where linear algebra can be used for cryptanalysis.