Encrypt and Decrypt with Hill Cipher

Encrypt and Decrypt with Hill Cipher.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# https://www.cs.uri.edu/cryptography/classicalhill.htm\n",
    "# https://en.wikipedia.org/wiki/Hill_cipher\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def normalize_text(text):\n",
    "  return list(map(lambda t: ord(t) - ord('A'), text)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[12, 8, 18, 18]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "normalize_text(\"MISS\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def filled_text(text, n, ch):\n",
    "  return text + ''.join([ch for i in range((n - len(text) % n) % n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'MISSISSIPPIK'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "filled_text(\"MISSISSIPPI\", 2, 'K')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'MISS'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "filled_text(\"MISS\", 2, 'K')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def encrypt(key, plain_text):\n",
    "    T = filled_text(plain_text, 2, 'K')\n",
    "    K = np.array(key).reshape(2, 2)\n",
    "    P = np.array(normalize_text(T)).reshape(int(len(T) / 2), 2) \n",
    "    M = np.matmul(K, P.transpose()) % 26\n",
    "    C = (M + ord('A')).transpose().reshape(len(T))\n",
    "    return ''.join([chr(c) for c in C])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'CIKKGEUWEROY'"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "encrypt([3,25,24,17], \"MISSISSIPPI\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decrypt(key, cipher_text):\n",
    "    T = filled_text(cipher_text, 2, 'K') # len(cipher_text) % 2 should be 0\n",
    "    K = np.array(key).reshape(2, 2)\n",
    "    C = np.array(normalize_text(T)).reshape(int(len(T) / 2), 2)\n",
    "    M = np.matmul(K, C.transpose()) % 26\n",
    "    P = (M + ord('A')).transpose().reshape(len(T))\n",
    "    return ''.join([chr(p) for p in P])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'MISSISSIPPIK'"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "decrypt([3,17,8,25], \"CIKKGEUWEROY\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'MISSISSIPPEY'"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "decrypt([3,17,8,25], \"CIKKGEUWERO\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sympy.solvers.diophantine import diop_linear\n",
    "from sympy.abc import x, y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def det(A):\n",
    "    A = np.array(A).reshape(2, 2)\n",
    "    return A[0, 0] * A[1, 1] - A[1, 0] * A[0, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-549"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "det([3, 25, 24, 17])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def detInvMod(A, n):\n",
    "    d = det(A)\n",
    "    left, right = diop_linear(d * x - n * y - 1)\n",
    "    if (left == None or right == None):\n",
    "        raise ValueError(\"I don't know how to solve the linear equation... :-(\")\n",
    "    else:\n",
    "        a, b = left.as_coeff_add()\n",
    "        b = b[0].as_coeff_Mul()[0]\n",
    "        return int(a + b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "17"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "detInvMod([3, 25, 24, 17], 26)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def invMod(A, n):\n",
    "    dInv = detInvMod(A, n)\n",
    "    AInv = np.array([A[3], -A[1], -A[2], A[0]]).reshape(2, 2)\n",
    "    return ((dInv * AInv) % n).reshape(4).tolist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 17, 8, 25]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "invMod([3, 25, 24, 17], 26)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'HIAT'"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "K = [3, 3, 2, 5]\n",
    "invMod(K, 26)\n",
    "encrypt(K, \"HELP\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'HELP'"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "KInv = invMod(K, 26)\n",
    "decrypt(KInv, \"HIAT\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'KLDBYCRYXF'"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "K = [1, 1, 2, 3]\n",
    "KInv = invMod([1, 1, 2, 3], 26)\n",
    "L = [8, 3, 1, 19]\n",
    "LInv = invMod([8, 3, 1, 19], 26)\n",
    "encrypt(L, encrypt(K, \"HELLOWORLD\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'HELLOWORLD'"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "decrypt(KInv, decrypt(LInv, \"KLDBYCRYXF\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'SNUJCI'"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "encrypt(L, encrypt(K, \"FABIO\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'FABIOK'"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "decrypt(KInv, decrypt(LInv, \"SNUJCI\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "D = {(i, j, k, l): decrypt([i, j, k, l], \"HIAT\") for i in range(26) for j in range(26) for k in range(26) for l in range(26)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'PPTT'"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D[1, 1, 1, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'HELP'"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D[15, 17, 20, 9]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'HIRE'"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D[25, 5, 14, 18]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'HERO'"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D[25, 5, 14, 24]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'HARD'"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D[25, 5, 18, 7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 0, 18, 1)]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[k for (k, v) in D.items() if v.startswith(\"HEAT\")]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[((1, 0, 18, 1), 'HEAT'),\n",
       " ((7, 1, 24, 18), 'FATE'),\n",
       " ((9, 22, 10, 1), 'FACT'),\n",
       " ((21, 2, 0, 18), 'HOME'),\n",
       " ((25, 5, 6, 18), 'HERE'),\n",
       " ((25, 5, 14, 11), 'HERB'),\n",
       " ((25, 5, 14, 18), 'HIRE'),\n",
       " ((25, 5, 14, 24), 'HERO'),\n",
       " ((25, 5, 18, 7), 'HARD')]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[(k, v) for (k, v) in D.items() if v in (\"HEAT\", \"HERE\", \"HERB\", \"HIRE\", \"HERO\", \"HARD\", \"HOME\", \"FATE\", \"FACT\")]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}