Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
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: More...
 
static matrix< int > generate_decryption_key (matrix< int > const &encrypt_key)
 Generate decryption matrix from an encryption matrix key. More...
 
static std::pair< matrix< int >, matrix< int > > generate_keys (size_t size, int limit1=0, int limit2=10)
 Generate encryption and decryption key pair. More...
 
static const std::string encrypt_text (const std::string &text, const matrix< int > &encrypt_key)
 Encrypt a given text using a given key. More...
 
static const std::string decrypt_text (const std::string &text, const matrix< int > &decrypt_key)
 Decrypt a given text using a given key. More...
 

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. More...
 
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. More...
 
template<typename T >
static const T gcd (T a, T b)
 Compute GCD of two integers using Euler's algorithm. More...
 
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 More...
 
static char get_idx_char (const uint8_t idx)
 Get the character at a given index in the STRKEY. More...
 
static uint8_t get_char_idx (const char ch)
 Get the index of a character in the STRKEY. More...
 
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. More...
 
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.

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
textinput text to encrypt or decrypt
keykey for encryption or decryption
Returns
encrypted/decrypted output
211  {
212  size_t text_len = text.length();
213  size_t key_len = key.size();
214 
215  // length of output string must be a multiple of key_len
216  // create output string and initialize with '\0' character
217  size_t L2 = text_len % key_len == 0
218  ? text_len
219  : text_len + key_len - (text_len % key_len);
220  std::string coded_text(L2, '\0');
221 
222  // temporary array for batch processing
223  int i;
224 #ifdef _OPENMP
225 #pragma parallel omp for private(i)
226 #endif
227  for (i = 0; i < L2 - key_len + 1; i += key_len) {
228  std::valarray<uint8_t> batch_int(key_len);
229  for (size_t j = 0; j < key_len; j++) {
230  batch_int[j] = get_char_idx(text[i + j]);
231  }
232 
233  batch_int = mat_mul(batch_int, key);
234 
235  for (size_t j = 0; j < key_len; j++) {
236  coded_text[i + j] =
237  STRKEY[batch_int[j]]; // get character at key
238  }
239  }
240 
241  return coded_text;
242  }
Here is the call graph for this function:

◆ 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
textstring to decrypt
decrypt_keykey for decryption
Returns
decrypted text
458  {
459  return codec(text, decrypt_key);
460  }
Here is the call graph for this function:

◆ 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
textstring to encrypt
encrypt_keykey for encryption
Returns
encrypted text
446  {
447  return codec(text, encrypt_key);
448  }
Here is the call graph for this function:

◆ gcd()

template<typename T >
static const T ciphers::HillCipher::gcd ( a,
b 
)
inlinestaticprivate

Compute GCD of two integers using Euler's algorithm.

Parameters
afirst number
bsecond number
Returns
GCD of \(a\) and \(b\)
138  {
139  if (b > a) // ensure always a < b
140  std::swap(a, b);
141 
142  while (b != 0) {
143  T tmp = b;
144  b = a % b;
145  a = tmp;
146  }
147 
148  return a;
149  }
Here is the call graph for this function:

◆ 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_keyencryption key for which to create a decrypt key
Returns
Decryption martix
371  {
372  size_t size = encrypt_key.size();
373  int L = std::strlen(STRKEY);
374 
375  matrix<int> decrypt_key(size, std::valarray<int>(size));
376  int det_encrypt = static_cast<int>(determinant_lu(encrypt_key));
377 
378  int mat_determinant = det_encrypt < 0 ? det_encrypt % L : det_encrypt;
379 
380  matrix<double> tmp_inverse = get_inverse(encrypt_key);
381  double d2 = determinant_lu(decrypt_key);
382 
383  // find co-prime factor for inversion
384  int det_inv = -1;
385  for (int i = 0; i < L; i++) {
386  if (modulo(mat_determinant * i, L) == 1) {
387  det_inv = i;
388  break;
389  }
390  }
391 
392  if (det_inv == -1) {
393  std::cerr << "Could not find a co-prime for inversion\n";
394  std::exit(EXIT_FAILURE);
395  }
396 
397  mat_determinant = det_inv * det_encrypt;
398 
399  // perform modular inverse of encryption matrix
400  int i;
401 #ifdef _OPENMP
402 #pragma parallel omp for private(i)
403 #endif
404  for (i = 0; i < size; i++) {
405  for (int j = 0; j < size; j++) {
406  int temp = std::round(tmp_inverse[i][j] * mat_determinant);
407  decrypt_key[i][j] = modulo(temp, L);
408  }
409  }
410  return decrypt_key;
411  }

◆ 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
sizesize of matrix (typically \(\text{size}\le10\))
limit1lower limit of range of random elements (default=0)
limit2upper limit of range of random elements (default=10)
Returns
Encryption martix
340  {
341  matrix<int> encrypt_key(size, std::valarray<int>(size));
342  matrix<int> min_mat = encrypt_key;
343  int mat_determinant = -1; // because matrix has only ints, the
344  // determinant will also be an int
345  int L = std::strlen(STRKEY);
346 
347  double dd;
348  do {
349  // keeping the random number range smaller generates better
350  // defined matrices with more ease of cracking
351  dd = rand_range(&encrypt_key, limit1, limit2);
352  mat_determinant = static_cast<int>(dd);
353 
354  if (mat_determinant < 0)
355  mat_determinant = (mat_determinant % L);
356  } while (std::abs(dd) > 1e3 || // while ill-defined
357  dd < 0.1 || // while singular or negative determinant
358  !std::isfinite(dd) || // while determinant is not finite
359  gcd(mat_determinant, L) != 1); // while no common factors
360  // std::cout <<
361 
362  return encrypt_key;
363  }

◆ 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
sizesize of matrix key (typically \(\text{size}\le10\))
limit1lower limit of range of random elements (default=0)
limit2upper 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
426  {
427  matrix<int> encrypt_key = generate_encryption_key(size);
428  matrix<int> decrypt_key = generate_decryption_key(encrypt_key);
429  double det2 = determinant_lu(decrypt_key);
430  while (std::abs(det2) < 0.1 || std::abs(det2) > 1e3) {
431  encrypt_key = generate_encryption_key(size, limit1, limit2);
432  decrypt_key = generate_decryption_key(encrypt_key);
433  det2 = determinant_lu(decrypt_key);
434  }
435  return std::make_pair(encrypt_key, decrypt_key);
436  }

◆ 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
chcharacter to search
Returns
index of character
190  {
191  size_t L = std::strlen(STRKEY);
192 
193  for (size_t idx = 0; idx <= L; idx++)
194  if (STRKEY[idx] == ch)
195  return idx;
196 
197  std::cerr << __func__ << ":" << __LINE__ << ": (" << ch
198  << ") Should not reach here!\n";
199  return 0;
200  }
Here is the call graph for this function:

◆ 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
idxindex value
Returns
character at the index
182 { 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
250  {
251  // Assuming A is square matrix
252  size_t N = A.size();
253 
254  matrix<double> inverse(N, std::valarray<double>(N));
255  for (size_t row = 0; row < N; row++) {
256  for (size_t col = 0; col < N; col++) {
257  // create identity matrix
258  inverse[row][col] = (row == col) ? 1.f : 0.f;
259  }
260  }
261 
262  if (A.size() != A[0].size()) {
263  std::cerr << "A must be a square matrix!" << std::endl;
264  return inverse;
265  }
266 
267  // preallocate a temporary matrix identical to A
269  for (size_t row = 0; row < N; row++) {
270  for (size_t col = 0; col < N; col++)
271  temp[row][col] = static_cast<double>(A[row][col]);
272  }
273 
274  // start transformations
275  for (size_t row = 0; row < N; row++) {
276  for (size_t row2 = row; row2 < N && temp[row][row] == 0; row2++) {
277  // this to ensure diagonal elements are not 0
278  temp[row] = temp[row] + temp[row2];
279  inverse[row] = inverse[row] + inverse[row2];
280  }
281 
282  for (size_t col2 = row; col2 < N && temp[row][row] == 0; col2++) {
283  // this to further ensure diagonal elements are not 0
284  for (size_t row2 = 0; row2 < N; row2++) {
285  temp[row2][row] = temp[row2][row] + temp[row2][col2];
286  inverse[row2][row] =
287  inverse[row2][row] + inverse[row2][col2];
288  }
289  }
290 
291  if (temp[row][row] == 0) {
292  // Probably a low-rank matrix and hence singular
293  std::cerr << "Low-rank matrix, no inverse!" << std::endl;
294  return inverse;
295  }
296 
297  // set diagonal to 1
298  double divisor = temp[row][row];
299  temp[row] = temp[row] / divisor;
300  inverse[row] = inverse[row] / divisor;
301  // Row transformations
302  for (size_t row2 = 0; row2 < N; row2++) {
303  if (row2 == row)
304  continue;
305  double factor = temp[row2][row];
306  temp[row2] = temp[row2] - factor * temp[row];
307  inverse[row2] = inverse[row2] - factor * inverse[row];
308  }
309  }
310 
311  return inverse;
312  }
Here is the call graph for this function:

◆ 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
vectorvector to multiply
keyencryption or decryption key matrix
Returns
corresponding encrypted or decrypted text
160  {
161  std::valarray<uint8_t> out(vector); // make a copy
162 
163  size_t L = std::strlen(STRKEY);
164 
165  for (size_t i = 0; i < key.size(); i++) {
166  int tmp = 0;
167  for (size_t j = 0; j < vector.size(); j++) {
168  tmp += key[i][j] * vector[j];
169  }
170  out[i] = static_cast<uint8_t>(tmp % L);
171  }
172 
173  return out;
174  }
Here is the call graph for this function:

◆ 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
Mpointer to matrix to be filled with random numbers
alower limit of interval
bupper limit of interval
Template Parameters
T1type of input range
T2type 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]\)
118  {
119  for (size_t i = 0; i < M->size(); i++) {
120  for (size_t j = 0; j < M[0][0].size(); j++) {
121  M[0][i][j] = rand_range<T1, T2>(a, b);
122  }
123  }
124 
125  return determinant_lu(*M);
126  }
Here is the call graph for this function:

◆ 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
alower limit of interval
bupper limit of interval
Template Parameters
Ttype of output
Returns
random integer in the interval \([a,b)\)
92  {
93  // generate random number between 0 and 1
94  long double r = static_cast<long double>(std::rand()) / RAND_MAX;
95 
96  // scale and return random number as integer
97  return static_cast<T2>(r * (b - a) + a);
98  }
Here is the call graph for this function:

The documentation for this class was generated from the following file:
ciphers::HillCipher::codec
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 encryp...
Definition: hill_cipher.cpp:210
std::strlen
T strlen(T... args)
std::string
STL class.
ciphers::HillCipher::generate_encryption_key
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 provid...
Definition: hill_cipher.cpp:339
std::vector
STL class.
std::string::length
T length(T... args)
ciphers::STRKEY
static const char * STRKEY
Definition: hill_cipher.cpp:73
ciphers::HillCipher::gcd
static const T gcd(T a, T b)
Compute GCD of two integers using Euler's algorithm.
Definition: hill_cipher.cpp:138
std::isfinite
T isfinite(T... args)
ciphers::HillCipher::get_inverse
static matrix< double > get_inverse(matrix< T > const &A)
Definition: hill_cipher.cpp:250
ciphers::HillCipher::generate_decryption_key
static matrix< int > generate_decryption_key(matrix< int > const &encrypt_key)
Generate decryption matrix from an encryption matrix key.
Definition: hill_cipher.cpp:371
std::cerr
std::valarray
STL class.
ciphers::HillCipher::get_char_idx
static uint8_t get_char_idx(const char ch)
Get the index of a character in the STRKEY.
Definition: hill_cipher.cpp:190
std::rand
T rand(T... args)
std::swap
T swap(T... args)
std::round
T round(T... args)
std::endl
T endl(T... args)
determinant_lu
double determinant_lu(const matrix< T > &A)
Definition: lu_decomposition.h:90
ciphers::HillCipher::rand_range
static const T2 rand_range(T1 a, T1 b)
Function to generate a random integer in a given interval.
Definition: hill_cipher.cpp:92
std::make_pair
T make_pair(T... args)
ciphers::HillCipher::mat_mul
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
Definition: hill_cipher.cpp:159
std::exit
T exit(T... args)