POSTS

Block Cipher

What is it?

Block Cipher is an algorithm that uses a symmetric key to encrypt fixed-length plaintext blocks of, say, n-bits to produce ciphertext blocks of n-bits each.
The encryption function (E) turns plaintext blocks (P) into ciphertext blocks (C) using a secret key (k).
The decryption function (D) turns ciphertext blocks (C) into plaintext blocks (P) using the same secret key (k) that was used to encrypt the block.
To understand Block Cipher concepts including “Padding” and “Mode of Encryption”, visit this link: https://github.com/ashutosh1206/Crypton/tree/master/Block-Cipher

Image Source: https://www.crypto101.io/Crypto101.pdf

Why should we care?

Block ciphers operate as important elementary components in the design of many cryptographic protocols, and are widely used to implement encryption of bulk data.

How does it work?

A Block Cipher having block size of n has 2^n possible different plaintext blocks to encrypt.

Let, block_size = 4 bits

Thus, No. of possible blocks = 2^4 = 16

Since, each block is a sequence of 4 bits, hence, each of the blocks could be represented by a hexadecimal digit.

Image Source: hex to binary chart - Beste.globalaffairs.co

Nonsingular Transformation

Nonsingular Transformation means the encryption algorithm must be reversible (Nonsingular) to decrypt the ciphertext into the original plaintext. The ciphertext must be unique for each plaintext block.

<—>

Image Source: https://www.cybrary.it/0p3n//block-cipher/

Example: Hill Cipher

Hill cipher is an example of block cipher.
In Hill cipher, each letter of English alphabet is represented by a number modulo 26. Often the simple scheme A = 0, B = 1, …, Z = 25 is used, but this is not an essential feature of the cipher.
To encrypt a message, each block of n letters (considered as an n-component vector) is multiplied by an invertible n × n matrix, against modulus 26.
To decrypt the message, each block is multiplied by the inverse of the matrix used for encryption.

Encryption:

Image Source: https://en.wikipedia.org/wiki/Hill_cipher

Decryption:

Image Source: https://en.wikipedia.org/wiki/Hill_cipher

Hands-On: 2 x 2 Key Matrix

Encryption

We shall encrypt the plaintext message “shortexample” using the keyword “hill” and a 2 x 2 matrix.

Algorithm:

Turn the keyword into a key matrix (a 2 x 2 matrix for working with digraphs, a 3 x 3 matrix for working with trigraphs, etc).
Turn the plaintext into digraphs (or trigraphs) and each of these into a column vector.
Perform matrix multiplication modulo the length of the alphabet (i.e. 26) on each vector.
Convert these vectors into letters to produce the ciphertext.

Python Code:

import numpy as np 
from sympy import Matrix

def alphabet_by_position():
    alphabet_map = {
        "A": 0,
        "B": 1,
        "C": 2,
        "D": 3,
        "E": 4,
        "F": 5,
        "G": 6,
        "H": 7,
        "I": 8,
        "J": 9,
        "K": 10,
        "L": 11,
        "M": 12,
        "N": 13,
        "O": 14,
        "P": 15,
        "Q": 16,
        "R": 17,
        "S": 18,
        "T": 19,
        "U": 20,
        "V": 21,
        "W": 22,
        "X": 23,
        "Y": 24,
        "Z": 25
    }

    return alphabet_map


def string2matrix(keyword, row, col):
    keyword_new = []
    for char in keyword:
        keyword_new.append(getValueFromMap(alphabet_by_position(), char.upper()))
        #print char, keyword_new

    matrix = np.mat(keyword_new)
    matrix.shape = (row, col) 
    return matrix


def matrix2string(matrix):
    matrix_new = matrix.T
    myarray = np.asarray(matrix_new)
    #print myarray, list(np.squeeze(myarray))
    output = []
    for row in myarray:
        #output.append(getKeyFromMap(alphabet_by_position(), int_val))
        #print (row)
        for col in np.asarray(row):
            #print col
            output.append(getKeyFromMap(alphabet_by_position(), col))
    
    return ''.join(output)


def getValueFromMap(map, key):
    return map.get(key, "")

def getKeyFromMap(map, value):
    return map.keys()[map.values().index(value)]
    

def encrypt(plaintext, keyword, n):
    # Turn the keyword and the plaintext into matrices
    k_row, k_col = (n,n)
    keyword_matrix = string2matrix(keyword, k_row, k_col)

    p_row = n
    p_col = len(plaintext) / n
    plaintext_matrix = string2matrix(plaintext, p_col, p_row).T

    #Multiply the key matrix by each column vector in turn.
    matrix_multiplication = keyword_matrix * plaintext_matrix
    matrix_multiplication_modulo26 = matrix_multiplication % 26

    ciphertext = matrix2string(matrix_multiplication_modulo26)

    return ciphertext


def find_multiplicative_inverse(determinant, modulo):
    #print determinant, modulo
    for i in range(1, modulo):
        if (i*determinant % 26) == 1:
            return i


def get_adjugate_matrix2by2(matrix):
    m = Matrix(matrix)
    adjugate_matrix = m.adjugate()
    return np.mat(adjugate_matrix)


def decrypt(ciphertext, keyword, n):
    # Turn tcipheryword and the ciphertext into matrices
    k_row, k_col = (n,n)
    keyword_matrix = string2matrix(keyword, k_row, k_col)

    #Step 1 - Find the Multiplicative Inverse of the Determinant
    i=0
    j=0
    left_val = 1
    right_val = 1
    for row in np.asarray(keyword_matrix):
        for col in np.asarray(row):
            if(i == j):
                left_val *= col
            else:
                right_val *= col
                
            j+=1
        i+=1
        j=0

    determinant = (left_val - right_val)
    determinant_mod26 = determinant % 26
    #print determinant_mod26

    #Find the multiplicative inverse of the determinant working modulo 26
    multiplicative_inverse = find_multiplicative_inverse(determinant_mod26, 26)
    #print multiplicative_inverse

    #Step 2 - Find the Adjugate Matrix
    keyword_adjugate_matrix = get_adjugate_matrix2by2(keyword_matrix)
    keyword_adjugate_matrix_modulo26 = keyword_adjugate_matrix % 26
    #print(keyword_adjugate_matrix_modulo26)

    #Step 3 - Multiply the Multiplicative Inverse of the Determinant by the Adjugate Matrix
    keyword_inverse_matrix = multiplicative_inverse * keyword_adjugate_matrix_modulo26
    keyword_inverse_matrix_modulo26 = keyword_inverse_matrix %26
    #print (keyword_matrix * inverse_by_adjugate_modulo26) %26

    #Convert the ciphertext into column vectors 
    p_row = n
    p_col = len(ciphertext) / n
    ciphertext_matrix = string2matrix(ciphertext, p_col, p_row).T

    #Multiply the inverse matrix by each column vector in turn.
    matrix_multiplication = keyword_inverse_matrix * ciphertext_matrix
    matrix_multiplication_modulo26 = matrix_multiplication % 26

    plaintext = matrix2string(matrix_multiplication_modulo26)

    return plaintext
    

def run_encrypt():
    #We shall encrypt the plaintext message "short example" using the keyword hill and a 2 x 2 matrix.
    keyword = "hill"
    plaintext = "shortexample"
    n = 2
    ciphertext = encrypt(plaintext, keyword, n)
    print("The ciphertext is:\n%s \n") % (ciphertext)


run_encrypt()

Decryption

We shall decrypt the ciphertext message “APADJTFTWLFJ” using the keyword “hill” and a 2 x 2 matrix.