ciphers::HillCipher Class Reference

Implementation of Hill Cipher algorithm. More...

Static Public Member Functions
static matrix< int >	generate_encryption_key (size_t size, int limit1=0, int limit2=10)
	Generate encryption matrix of a given size. Larger size matrices are difficult to generate but provide more security. Important conditions are:
static matrix< int >	generate_decryption_key (matrix< int > const &encrypt_key)
	Generate decryption matrix from an encryption matrix key.
static std::pair< matrix< int >, matrix< int > >	generate_keys (size_t size, int limit1=0, int limit2=10)
	Generate encryption and decryption key pair.
static const std::string	encrypt_text (const std::string &text, const matrix< int > &encrypt_key)
	Encrypt a given text using a given key.
static const std::string	decrypt_text (const std::string &text, const matrix< int > &decrypt_key)
	Decrypt a given text using a given key.

Static Private Member Functions
template<typename T1 , typename T2 >
static const T2	rand_range (T1 a, T1 b)
	Function to generate a random integer in a given interval.
template<typename T1 , typename T2 >
static double	rand_range (matrix< T2 > *M, T1 a, T1 b)
	Function overload to fill a matrix with random integers in a given interval.
template<typename T >
static const T	gcd (T a, T b)
	Compute GCD of two integers using Euler's algorithm.
static const std::valarray< uint8_t >	mat_mul (const std::valarray< uint8_t > &vector, const matrix< int > &key)
	helper function to perform vector multiplication with encryption or decryption matrix
static char	get_idx_char (const uint8_t idx)
	Get the character at a given index in the STRKEY.
static uint8_t	get_char_idx (const char ch)
	Get the index of a character in the STRKEY.
static const std::string	codec (const std::string &text, const matrix< int > &key)
	Convenience function to perform block cipher operations. The operations are identical for both encryption and decryption.
template<typename T >
static matrix< double >	get_inverse (matrix< T > const &A)
static int	modulo (int a, int b)

Detailed Description

Implementation of Hill Cipher algorithm.

Definition at line 82 of file hill_cipher.cpp.

Member Function Documentation

codec()

static const std::string ciphers::HillCipher::codec ( const std::string & text, const matrix< int > & key )

inlinestaticprivate

Convenience function to perform block cipher operations. The operations are identical for both encryption and decryption.

Parameters

text	input text to encrypt or decrypt
key	key for encryption or decryption

Returns

encrypted/decrypted output

Definition at line 211 of file hill_cipher.cpp.

                                                           {
        size_t text_len = text.length();
        size_t key_len = key.size();
 
        // length of output string must be a multiple of key_len
        // create output string and initialize with '\0' character
        size_t L2 = text_len % key_len == 0
                        ? text_len
                        : text_len + key_len - (text_len % key_len);
        std::string coded_text(L2, '\0');
 
        // temporary array for batch processing
        int i;
#ifdef _OPENMP
#pragma parallel omp for private(i)
#endif
        for (i = 0; i < L2 - key_len + 1; i += key_len) {
            std::valarray<uint8_t> batch_int(key_len);
            for (size_t j = 0; j < key_len; j++) {
                batch_int[j] = get_char_idx(text[i + j]);
            }
 
            batch_int = mat_mul(batch_int, key);
 
            for (size_t j = 0; j < key_len; j++) {
                coded_text[i + j] =
                    STRKEY[batch_int[j]];  // get character at key
            }
        }
 
        return coded_text;
    }

decrypt_text()

static const std::string ciphers::HillCipher::decrypt_text ( const std::string & text, const matrix< int > & decrypt_key )

inlinestatic

Decrypt a given text using a given key.

Parameters

text	string to decrypt
decrypt_key	key for decryption

Returns

decrypted text

Definition at line 458 of file hill_cipher.cpp.

                                                                          {
        return codec(text, decrypt_key);
    }

encrypt_text()

static const std::string ciphers::HillCipher::encrypt_text ( const std::string & text, const matrix< int > & encrypt_key )

inlinestatic

Encrypt a given text using a given key.

Parameters

text	string to encrypt
encrypt_key	key for encryption

Returns

encrypted text

Definition at line 446 of file hill_cipher.cpp.

                                                                          {
        return codec(text, encrypt_key);
    }

gcd()

template<typename T >

static const T ciphers::HillCipher::gcd ( T a, T b )

inlinestaticprivate

Compute GCD of two integers using Euler's algorithm.

Parameters

a	first number
b	second number

Returns

GCD of \(a\) and \(b\)

Definition at line 139 of file hill_cipher.cpp.

                                 {
        if (b > a)  // ensure always a < b
            std::swap(a, b);
 
        while (b != 0) {
            T tmp = b;
            b = a % b;
            a = tmp;
        }
 
        return a;
    }

generate_decryption_key()

static matrix< int > ciphers::HillCipher::generate_decryption_key ( matrix< int > const & encrypt_key )

inlinestatic

Generate decryption matrix from an encryption matrix key.

Parameters

encrypt_key

encryption key for which to create a decrypt key

Returns

Decryption martix

Definition at line 372 of file hill_cipher.cpp.

                                                                               {
        size_t size = encrypt_key.size();
        int L = std::strlen(STRKEY);
 
        matrix<int> decrypt_key(size, std::valarray<int>(size));
        int det_encrypt = static_cast<int>(determinant_lu(encrypt_key));
 
        int mat_determinant = det_encrypt < 0 ? det_encrypt % L : det_encrypt;
 
        matrix<double> tmp_inverse = get_inverse(encrypt_key);
        double d2 = determinant_lu(decrypt_key);
 
        // find co-prime factor for inversion
        int det_inv = -1;
        for (int i = 0; i < L; i++) {
            if (modulo(mat_determinant * i, L) == 1) {
                det_inv = i;
                break;
            }
        }
 
        if (det_inv == -1) {
            std::cerr << "Could not find a co-prime for inversion\n";
            std::exit(EXIT_FAILURE);
        }
 
        mat_determinant = det_inv * det_encrypt;
 
        // perform modular inverse of encryption matrix
        int i;
#ifdef _OPENMP
#pragma parallel omp for private(i)
#endif
        for (i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                int temp = std::round(tmp_inverse[i][j] * mat_determinant);
                decrypt_key[i][j] = modulo(temp, L);
            }
        }
        return decrypt_key;
    }

generate_encryption_key()

static matrix< int > ciphers::HillCipher::generate_encryption_key ( size_t size, int limit1 = 0, int limit2 = 10 )

inlinestatic

Generate encryption matrix of a given size. Larger size matrices are difficult to generate but provide more security. Important conditions are:

1. matrix should be invertible
2. determinant must not have any common factors with the length of character key There is no head-fast way to generate hte matrix under the given numerical restrictions of the machine but the conditions added achieve the goals. Bigger the matrix, greater is the probability of the matrix being ill-defined.

Parameters

size	size of matrix (typically \(\text{size}\le10\))
limit1	lower limit of range of random elements (default=0)
limit2	upper limit of range of random elements (default=10)

Returns

Encryption martix

Definition at line 340 of file hill_cipher.cpp.

                                                                {
        matrix<int> encrypt_key(size, std::valarray<int>(size));
        matrix<int> min_mat = encrypt_key;
        int mat_determinant = -1;  // because matrix has only ints, the
                                   // determinant will also be an int
        int L = std::strlen(STRKEY);
 
        double dd;
        do {
            // keeping the random number range smaller generates better
            // defined matrices with more ease of cracking
            dd = rand_range(&encrypt_key, limit1, limit2);
            mat_determinant = static_cast<int>(dd);
 
            if (mat_determinant < 0)
                mat_determinant = (mat_determinant % L);
        } while (std::abs(dd) > 1e3 ||  // while ill-defined
                 dd < 0.1 ||  // while singular or negative determinant
                 !std::isfinite(dd) ||  // while determinant is not finite
                 gcd(mat_determinant, L) != 1);  // while no common factors
        // std::cout <<
 
        return encrypt_key;
    }

generate_keys()

static std::pair< matrix< int >, matrix< int > > ciphers::HillCipher::generate_keys ( size_t size, int limit1 = 0, int limit2 = 10 )

inlinestatic

Generate encryption and decryption key pair.

Parameters

size	size of matrix key (typically \(\text{size}\le10\))
limit1	lower limit of range of random elements (default=0)
limit2	upper limit of range of random elements (default=10)

Returns

std::pair<matrix<int>, matrix<int>> encryption and decryption keys as a pair

See also

generate_encryption_key

Definition at line 425 of file hill_cipher.cpp.

                                                                              {
        matrix<int> encrypt_key = generate_encryption_key(size);
        matrix<int> decrypt_key = generate_decryption_key(encrypt_key);
        double det2 = determinant_lu(decrypt_key);
        while (std::abs(det2) < 0.1 || std::abs(det2) > 1e3) {
            encrypt_key = generate_encryption_key(size, limit1, limit2);
            decrypt_key = generate_decryption_key(encrypt_key);
            det2 = determinant_lu(decrypt_key);
        }
        return std::make_pair(encrypt_key, decrypt_key);
    }

get_char_idx()

static uint8_t ciphers::HillCipher::get_char_idx ( const char ch )

inlinestaticprivate

Get the index of a character in the STRKEY.

Parameters

ch	character to search

Returns

index of character

Definition at line 191 of file hill_cipher.cpp.

                                                      {
        size_t L = std::strlen(STRKEY);
 
        for (size_t idx = 0; idx <= L; idx++)
            if (STRKEY[idx] == ch)
                return idx;
 
        std::cerr << __func__ << ":" << __LINE__ << ": (" << ch
                  << ") Should not reach here!\n";
        return 0;
    }

get_idx_char()

static char ciphers::HillCipher::get_idx_char ( const uint8_t idx )

inlinestaticprivate

Get the character at a given index in the STRKEY.

Parameters

idx	index value

Returns

character at the index

Definition at line 183 of file hill_cipher.cpp.

{ return STRKEY[idx]; }

get_inverse()

template<typename T >

static matrix< double > ciphers::HillCipher::get_inverse ( matrix< T > const & A )

inlinestaticprivate

Get matrix inverse using Row-transformations. Given matrix must be a square and non-singular.

Returns

inverse matrix

Definition at line 251 of file hill_cipher.cpp.

                                                          {
        // Assuming A is square matrix
        size_t N = A.size();
 
        matrix<double> inverse(N, std::valarray<double>(N));
        for (size_t row = 0; row < N; row++) {
            for (size_t col = 0; col < N; col++) {
                // create identity matrix
                inverse[row][col] = (row == col) ? 1.f : 0.f;
            }
        }
 
        if (A.size() != A[0].size()) {
            std::cerr << "A must be a square matrix!" << std::endl;
            return inverse;
        }
 
        // preallocate a temporary matrix identical to A
        matrix<double> temp(N, std::valarray<double>(N));
        for (size_t row = 0; row < N; row++) {
            for (size_t col = 0; col < N; col++)
                temp[row][col] = static_cast<double>(A[row][col]);
        }
 
        // start transformations
        for (size_t row = 0; row < N; row++) {
            for (size_t row2 = row; row2 < N && temp[row][row] == 0; row2++) {
                // this to ensure diagonal elements are not 0
                temp[row] = temp[row] + temp[row2];
                inverse[row] = inverse[row] + inverse[row2];
            }
 
            for (size_t col2 = row; col2 < N && temp[row][row] == 0; col2++) {
                // this to further ensure diagonal elements are not 0
                for (size_t row2 = 0; row2 < N; row2++) {
                    temp[row2][row] = temp[row2][row] + temp[row2][col2];
                    inverse[row2][row] =
                        inverse[row2][row] + inverse[row2][col2];
                }
            }
 
            if (temp[row][row] == 0) {
                // Probably a low-rank matrix and hence singular
                std::cerr << "Low-rank matrix, no inverse!" << std::endl;
                return inverse;
            }
 
            // set diagonal to 1
            double divisor = temp[row][row];
            temp[row] = temp[row] / divisor;
            inverse[row] = inverse[row] / divisor;
            // Row transformations
            for (size_t row2 = 0; row2 < N; row2++) {
                if (row2 == row)
                    continue;
                double factor = temp[row2][row];
                temp[row2] = temp[row2] - factor * temp[row];
                inverse[row2] = inverse[row2] - factor * inverse[row];
            }
        }
 
        return inverse;
    }

mat_mul()

static const std::valarray< uint8_t > ciphers::HillCipher::mat_mul ( const std::valarray< uint8_t > & vector, const matrix< int > & key )

inlinestaticprivate

helper function to perform vector multiplication with encryption or decryption matrix

Parameters

vector	vector to multiply
key	encryption or decryption key matrix

Returns

corresponding encrypted or decrypted text

Definition at line 160 of file hill_cipher.cpp.

                                                                    {
        std::valarray<uint8_t> out(vector);  // make a copy
 
        size_t L = std::strlen(STRKEY);
 
        for (size_t i = 0; i < key.size(); i++) {
            int tmp = 0;
            for (size_t j = 0; j < vector.size(); j++) {
                tmp += key[i][j] * vector[j];
            }
            out[i] = static_cast<uint8_t>(tmp % L);
        }
 
        return out;
    }

modulo()

static int ciphers::HillCipher::modulo ( int a, int b )

inlinestaticprivate

Definition at line 315 of file hill_cipher.cpp.

                                    {
        int ret = a % b;
        if (ret < 0)
            ret += b;
        return ret;
    }

rand_range() [1/2]

template<typename T1 , typename T2 >

static double ciphers::HillCipher::rand_range ( matrix< T2 > * M, T1 a, T1 b )

inlinestaticprivate

Function overload to fill a matrix with random integers in a given interval.

Parameters

M	pointer to matrix to be filled with random numbers
a	lower limit of interval
b	upper limit of interval

Template Parameters

T1	type of input range
T2	type of matrix

Returns

determinant of generated random matrix

Warning

There will need to be a balance between the matrix size and the range of random numbers. If the matrix is large, the range of random numbers must be small to have a well defined keys. Or if the matrix is smaller, the random numbers range can be larger. For an 8x8 matrix, range should be no more than \([0,10]\)

Definition at line 119 of file hill_cipher.cpp.

                                                        {
        for (size_t i = 0; i < M->size(); i++) {
            for (size_t j = 0; j < M[0][0].size(); j++) {
                M[0][i][j] = rand_range<T1, T2>(a, b);
            }
        }
 
        return determinant_lu(*M);
    }

rand_range() [2/2]

template<typename T1 , typename T2 >

static const T2 ciphers::HillCipher::rand_range ( T1 a, T1 b )

inlinestaticprivate

Function to generate a random integer in a given interval.

Parameters

a	lower limit of interval
b	upper limit of interval

Template Parameters

T	type of output

Returns

random integer in the interval \([a,b)\)

Definition at line 93 of file hill_cipher.cpp.

                                           {
        // generate random number between 0 and 1
        long double r = static_cast<long double>(std::rand()) / RAND_MAX;
 
        // scale and return random number as integer
        return static_cast<T2>(r * (b - a) + a);
    }

---

The documentation for this class was generated from the following file:

• ciphers/hill_cipher.cpp