Encrypt and Decrypt using 2x2 Hill Cipher

• Download source code - 1.5 KB

Introduction

This is the C++ answer to a specific question in Q&A, namely this one.

Background

2x2 Hill is  a simple cipher based on linear algebra, see this link. 

This implementation follows the algorithm recipe at Crypto Corner here.

Using the Code

A single class, HillCipher,  is implemented.

It gets the cipher key string in the constructor and exposes the following methods:

• string encode( string plain )
• string decode( string encoded )

You may use it as shown in the main function below:

int main()
{
  string msg, key;
  string enc, dec;

  cout << "plaese enter the message " << endl;
  cin >> msg;

  cout << "plaese enter the key " <<  endl;
  cin >> key;

  try
  {
    HillCipher hc(key);
    if (msg.length() % 2) msg += 'a'; // pad the message string
    string enc = hc.encode(msg);
    string dec = hc.decode(enc);
    cout << "encoded: " << enc << endl;
    cout << "decoded: " << dec << endl;
  }
  catch ( runtime_error re)
  {
    cerr << re.what() << endl;
    return -1;
  }
}

The Complete Code

HillCipher Class Declaration

#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <stdexcept>
using namespace std;

typedef  array < array <int, 2>, 2> Matrix;

class HillCipher
{
  HillCipher(){}

  Matrix _km; // key matrix
  Matrix _ikm; // inverted key matrix

public:
  HillCipher(const string & key);

  string encode(const string & plain); // encodes a string, 
                                       // if string length is odd then a 'a' is appended (padding)
  string decode(const string & encoded); // decode a string

private:  
  Matrix _build_key_matrix( const string & key);   // creates the key matrix
  static bool _validate_string( const string & s); // makes sure all characters 
                                                   // are in the 'a'..'z' range
  static int _determinant( const Matrix & m);      // computes the (modulo 26) determinant 
                                                   // of a 2x2 matrix
  static vector <int> _apply_matrix( const Matrix & m, const vector <int> & v); // applies (modulo 26) 
                                                   // the 2x2 matrix to the vector
  static int _mod26(int n); // obtains anumber in the 0..25 range
  static vector<int> _string2vector(const string & s); // converts the input string into a vector of int
  static string _vector2string(const vector<int> & v); // converts the input vector of int into a string
};

HillCipher Implementation, Public Methods

HillCipher::HillCipher( const string & key)
{
  if ( key.length() != 4 || ! _validate_string ( key ) )  throw runtime_error ("invalid key string");

  _km = _build_key_matrix(key);
  
  int det = _determinant( _km );
  
  if ( det == 0 || ( det % 2 ) == 0 || ( det % 13 ) == 0 ) throw runtime_error("invalid key matrix");
  
  int d;
  for ( d = 1; d < 26; ++d)
    if ( (d * det) % 26 == 1) break;
  
  _ikm[0][0] = _mod26( d * _km[1][1]);
  _ikm[0][1] = _mod26( -d * _km[0][1]);
  _ikm[1][0] = _mod26( -d * _km[1][0]);
  _ikm[1][1] = _mod26( d * _km[0][0]);
 
}

string HillCipher::encode( const string & plain )
{
  if ( plain.length() % 2 ) throw runtime_error("invalid plain string length");
  auto vplain = _string2vector(plain);
  auto venc = _apply_matrix( _km, vplain );
  string enc = _vector2string( venc );
  return enc;
}

string HillCipher::decode( const string & encoded )
{
  if ( encoded.length() % 2 ) throw runtime_error("invalid encoded string length");
  auto venc = _string2vector(encoded);
  auto vdec = _apply_matrix( _ikm, venc);
  string dec = _vector2string( vdec);
  return dec;
}

HillCipher Implementation, Private Methods

vector <int> HillCipher::_string2vector(const string & s)
{
  vector <int> v;
  for ( const auto  c : s)
    v.push_back(c -'a');
  return v;
}

vector <int> HillCipher::_apply_matrix( const Matrix & m, const vector <int> & v)
{
  vector <int> w;

  for (auto it = v.begin(); it != v.end(); it += 2)
  {
    int x = m[0][0]  * (*it) + m[0][1] * (*(it+1));
    w.push_back( _mod26( x ) );
    int y = m[1][0]  * (*it) + m[1][1] * (*(it+1));
    w.push_back( _mod26( y ) );
  }
  return w;
}

string HillCipher::_vector2string(const vector<int> & v)
{
  string s;
  for ( const auto i : v)
    s += static_cast<char>(i + 'a');
  return s;
}

Matrix HillCipher::_build_key_matrix( const string & key)
{
  Matrix m;
  auto it = key.begin();
  for (int r = 0; r <2; ++r)
    for (int c = 0; c <2; ++c, ++it)
      m[r][c] = (*it - 'a');
  return m;
}

bool HillCipher:: _validate_string(const string & s)
{
  for (const auto & c : s)
    if ( c < 'a' || c >'z') return false;

  return true;
}

int HillCipher::_determinant( const Matrix & m)
{
  return _mod26( m[0][0] * m[1][1] - m[0][1] * m[1][0] );
}

int HillCipher::_mod26(int n)
{
  n %= 26;
  if (n < 0) n+= 26;
  return n;
}

Points of Interest

In order to use this code, you need a modern (C++11) compiler.

All public methods (constructor included) might throw.

History

• 1^st October, 2017 - First release