Hill Cipher

Another interesting multi letter cipher is the Hill cipher, developed by the mathematician Lester Hill in 1929.

THE HILL ALGORITHM 

This encryption algorithm takes n successive plaintext letters and substitutes for them n ciphertext letters. The substitution is determined by linear equations in which each character is assigned a numerical value (a=0,b=1,…,z=25). 

C=KP, where  K is the key matrix and P is the plaintext vector

P=K−1C, where K−1 is the inverse of key matrix K in \pmod{26}

How the Hill Cipher Works

  1. Key Matrix:

    • Choose a key matrix K of size n×nn \times n (e.g., 2×22 \times 2, 3×33 \times 3).
    • The key matrix should be invertible modulo 26 (the number of letters in the English alphabet).

  2. Plaintext Preparation:

    • Convert the plaintext into vectors of size nn.
    • If the plaintext length is not a multiple of nn, pad it with extra letters (e.g., 'X').

  3. Encryption:

    • Multiply the key matrix KK by each plaintext vector, and take the result modulo 26 to get the ciphertext vector.
    • Convert the resulting numbers back into letters.

  4. Decryption:

    • Calculate the inverse of the key matrix K−1K^{-1} modulo 26.
    • Multiply the inverse matrix by each ciphertext vector, and take the result modulo 26 to get the plaintext vector.
    • Convert the resulting numbers back into letters.

Example

Let's encrypt the plaintext "HELP" using a 2×22 \times 2 key matrix.

Step 1: Key Matrix

Choose the key matrix: K=[3325]

Step 2: Plaintext Preparation

Convert "HELP" into numbers: H=7, E=4, L=11, P=15

Since our key matrix is 2×22 \times 2, divide the plaintext into pairs:

  • (H, E) -> (7, 4)
  • (L, P) -> (11, 15)

Step 3: Encryption

Encrypt each pair using matrix multiplication and take modulo 26.

For (H, E): [3325][74]=[3⋅7+3⋅42⋅7+5⋅4]=[21+1214+20]=[3334]\begin{bmatrix} 3 & 3 \\ 2 & 5 \end{bmatrix} \begin{bmatrix} 7 \\ 4 \end{bmatrix} = \begin{bmatrix} 3 \cdot 7 + 3 \cdot 4 \\ 2 \cdot 7 + 5 \cdot 4 \end{bmatrix} = \begin{bmatrix} 21 + 12 \\ 14 + 20 \end{bmatrix} = \begin{bmatrix} 33 \\ 34 \end{bmatrix}

Take modulo 26: [3334]≡[78](mod26)\begin{bmatrix} 33 \\ 34 \end{bmatrix} \equiv \begin{bmatrix} 7 \\ 8 \end{bmatrix} \pmod{26}

Convert back to letters: (7, 8) -> HI

For (L, P): [3325][1115]=[3⋅11+3⋅152⋅11+5⋅15]=[33+4522+75]=[7897]\begin{bmatrix} 3 & 3 \\ 2 & 5 \end{bmatrix} \begin{bmatrix} 11 \\ 15 \end{bmatrix} = \begin{bmatrix} 3 \cdot 11 + 3 \cdot 15 \\ 2 \cdot 11 + 5 \cdot 15 \end{bmatrix} = \begin{bmatrix} 33 + 45 \\ 22 + 75 \end{bmatrix} = \begin{bmatrix} 78 \\ 97 \end{bmatrix}

Take modulo 26: [7897]≡[019](mod26)\begin{bmatrix} 78 \\ 97 \end{bmatrix} \equiv \begin{bmatrix} 0 \\ 19 \end{bmatrix} \pmod{26}

Convert back to letters: (0, 19) -> AT

So, the ciphertext for "HELP" is "HIAT"

Step 4: Decryption

To decrypt, we need the inverse of the key matrix modulo 26.

Find the determinant of KK: det(K)=3⋅5−3⋅2=15−6=9\text{det}(K) = 3 \cdot 5 - 3 \cdot 2 = 15 - 6 = 9

Find the modular inverse of the determinant modulo 26, which is 3 (since 9×3≡1(mod26)9 \times 3 \equiv 1 \pmod{26}

Compute the inverse matrix: K−1=19[5−3−23]≡3[5−3−23]≡[15−9−69]≡[1517209](mod26)K^{-1} = \frac{1}{9} \begin{bmatrix} 5 & -3 \\ -2 & 3 \end{bmatrix} \equiv 3 \begin{bmatrix} 5 & -3 \\ -2 & 3 \end{bmatrix} \equiv \begin{bmatrix} 15 & -9 \\ -6 & 9 \end{bmatrix} \equiv \begin{bmatrix} 15 & 17 \\ 20 & 9 \end{bmatrix} \pmod{26}

Decrypt the ciphertext "HIAT" using  K^{-1}

  • Convert "HIAT" to numbers: H=7, I=8, A=0, T=19

For (H, I): [1517209][78]=[15⋅7+17⋅820⋅7+9⋅8]=[105+136140+72]=[241212]

Take modulo 26: [241212]≡[74](mod26)

Convert back to letters: (7, 4) -> HE

For (A, T): [1517209][019]=[15⋅0+17⋅1920⋅0+9⋅19]=[0+3230+171]=[323171]\begin{bmatrix} 15 & 17 \\ 20 & 9 \end{bmatrix} \begin{bmatrix} 0 \\ 19 \end{bmatrix} = \begin{bmatrix} 15 \cdot 0 + 17 \cdot 19 \\ 20 \cdot 0 + 9 \cdot 19 \end{bmatrix} = \begin{bmatrix} 0 + 323 \\ 0 + 171 \end{bmatrix} = \begin{bmatrix} 323 \\ 171 \end{bmatrix}

Take modulo 26: [323171]≡[1115](mod26)

Convert back to letters: (11, 15) -> LP

The decrypted plaintext is "HELP".

Python Code Hill Cipher

import numpy as np

def mod_inverse(a, m):
    # Find modular inverse using extended Euclidean algorithm
    m0, x0, x1 = m, 0, 1
    if m == 1:
        return 0
    while a > 1:
        # q is quotient
        q = a // m
        m, a = a % m, m
        x0, x1 = x1 - q * x0, x0
    if x1 < 0:
        x1 += m0
    return x1

def matrix_mod_inverse(matrix, modulus):
    det = int(np.round(np.linalg.det(matrix)))
    det_inv = mod_inverse(det % modulus, modulus)
    matrix_mod_inv = det_inv * np.round(det * np.linalg.inv(matrix)).astype(int) % modulus
    return matrix_mod_inv

def encrypt(plaintext, key):
    key_matrix = np.array(key)
    plaintext_numbers = [ord(char) - ord('A') for char in plaintext.upper() if char.isalpha()]

    # Pad with 'X' if necessary
    if len(plaintext_numbers) % 2 != 0:
        plaintext_numbers.append(ord('X') - ord('A'))

    ciphertext = ''
    for i in range(0, len(plaintext_numbers), 2):
        vector = np.array(plaintext_numbers[i:i+2])
        encrypted_vector = np.dot(key_matrix, vector) % 26
        ciphertext += ''.join(chr(num + ord('A')) for num in encrypted_vector)
    
    return ciphertext

def decrypt(ciphertext, key):
    key_matrix = np.array(key)
    key_matrix_inv = matrix_mod_inverse(key_matrix, 26)
    ciphertext_numbers = [ord(char) - ord('A') for char in ciphertext.upper() if char.isalpha()]

    plaintext = ''
    for i in range(0, len(ciphertext_numbers), 2):
        vector = np.array(ciphertext_numbers[i:i+2])
        decrypted_vector = np.dot(key_matrix_inv, vector) % 26
        plaintext += ''.join(chr(int(num) + ord('A')) for num in decrypted_vector)

    return plaintext

# Example usage
key = [[3, 3], [2, 5]]
plaintext = "HELP"
ciphertext = encrypt(plaintext, key)
decrypted_text = decrypt(ciphertext, key)

print(f"Plaintext: {plaintext}")
print(f"Ciphertext: {ciphertext}")
print(f"Decrypted: {decrypted_text}")

Output:
Plaintext: HELP
Ciphertext: HIAT
Decrypted: HELP

Encrypt the text "cryptography" using HillCipher with key 
K=\begin{bmatrix}5 & 7 \\ 9 & 4 \\ \end{bmatrix} (University Question)
Plaintext: CRYPTOGRAPHY
Ciphertext: ZIRQLTTSBIVD

Comments

Post a Comment

Popular posts from this blog

Cryptographic Algorithms CST 393 KTU CS Honour Notes Semester V -Dr Binu V P

About Me About the Course and Scheme Syllabus Model Question Paper University Question Papers ******************************************************** Module-1 (Introduction to the Concepts of Security) Introduction CIA Triad OSI Security Architecture Security Attacks Security Services Security Mechanisms Model for Network Security Classical Encryption Techniques    Symmetric Cipher Model    Cryptography - Crypt Analysis Substitution Ciphers-Caesar Cipher Mono-alphabetic Ciphers Playfair Cipher Hill Cipher Poly Alphabetic Ciphers- Vigenere Cipher Vernam Cipher- One Time Pad Transposition Ciphers Module-2 (Symmetric Key Crypto Systems) Stream Cipher Vs Block Cipher Traditional Block Cipher Structure- Fiestel Structure Data Encryption Standard - DES Algorithm Differential and Linear Cryptanalysis Double DES and Triple DES International Data Encryption Algorithm ( IDEA) Advanced Encryption Standard ( AES) Block Cipher Modes of Operation Stream Cipher and RC4 Module...
Read more

OSI Security Architecture

To assess effectively the security needs of an organization and to evaluate and choose various security products and policies, the manager responsible for security needs some systematic way of defining the requirements for security and characterizing the approaches to satisfying those requirements. This is difficult enough in a centralized data processing environment; with the use of local and wide area networks, the problems are compounded. ITU-T Recommendation X.800, Security Architecture for OSI, defines such a systematic approach.The OSI security architecture is useful to managers as a way of organizing the task of providing security. Furthermore, because this architecture was developed as an international standard, computer and communications vendors have developed security features for their products and services that relate to this structured definition of services and mechanisms. The OSI security architecture focuses on security attacks, mechanisms, and services. These can be d...
Read more

Data Encryption Standard - DES Algorithm

Image
The Data Encryption Standard (DES) was the most widely used encryption scheme. DES was issued in 1977 by the National Bureau of Standards, now the National Institute of Standards and Technology (NIST), as Federal Information Processing Standard 46 (FIPS PUB 46). The algorithm itself is referred to as the Data Encryption Algorithm (DEA). For DEA, data are encrypted in 64-bit blocks using a 56-bit key. The algorithm transforms 64-bit input in a series of steps into a 64-bit output. The same steps, with the same key, are used to reverse the encryption. Key Concepts of DES Symmetric Key Algorithm : In DES, the same key is used for both encryption and decryption . This key must be shared between the sender and receiver securely. Block Cipher : DES operates on fixed-length groups of bits, called blocks . The block size for DES is 64 bits . The input data is divided into 64-bit blocks, which are encrypted one block at a time. Key Length : DES uses a 56-bit key (though 64 bits are sup...
Read more