notebooks/4-mathematics-cryptography-algebraic-structures.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ch4: Mathematics of Cryptography: Algebraic Structures\n",
    "## 4.1 Permutation Group\n",
    "In the permutation group we have $n$ elements that have been permutated (can be permuatted) in $n!$ ways. e.g. we have \n",
    "\n",
    "$$\n",
    "P_1 = \n",
    "\\begin{pmatrix}\n",
    "1 & 2 & 3 \\\\\n",
    "3 & 1 & 2\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "We also have another permutation $P_2$ as:\n",
    "$$\n",
    "P_2 = \n",
    "\\begin{pmatrix}\n",
    "1 & 2 & 3 \\\\\n",
    "1 & 3 & 2\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "We can also compose permutations which will again give us a result in the Permutations group.\n",
    "\n",
    "$$\n",
    "P_3 = P_2 \\circ P_1 = \n",
    "\\begin{pmatrix}\n",
    "1 & 2 & 3 \\\\\n",
    "3 & 2 & 1\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "> Note: The permutation group is a non-abelian group as closure property isn't satisfied."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Permutation(object):\n",
    "    def __init__(self, permutation: list):\n",
    "        self.permutation = permutation\n",
    "        self.permutation_map = self.get_permutations_map(permutation)\n",
    "\n",
    "    def value(self, index: int) -> int:\n",
    "        return self.permutation[index]\n",
    "\n",
    "    def permutate(self, sequence: list) -> list:\n",
    "        result = [0] * len(sequence)\n",
    "        for index, value in enumerate(sequence):\n",
    "            result[self.permutation_map[index] - 1] = value\n",
    "        return result\n",
    "\n",
    "    def get_permutations_map(self, permutation: list) -> list:\n",
    "        result = [0] * len(permutation)\n",
    "        for index, value in enumerate(permutation):\n",
    "            result[value - 1] = index + 1\n",
    "        return result\n",
    "\n",
    "    def compose(self, p):\n",
    "        permutations = [0] * len(self.permutation)\n",
    "        for index, value in enumerate(self.permutation):\n",
    "            permutations[index] = p.permutation[value - 1]\n",
    "        return Permutation(permutations)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-4, 17, 89]\n"
     ]
    }
   ],
   "source": [
    "p1 = Permutation([3, 1, 2])\n",
    "p2 = Permutation([1, 3, 2])\n",
    "print(p2.permutate([-4, 89, 17]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Newly Created Permutation: [3, 2, 1]\n",
      "[17, 89, -4]\n"
     ]
    }
   ],
   "source": [
    "# We can also compose different permutation groups to get a new permutation group\n",
    "p3 = p2.compose(p1)\n",
    "print('Newly Created Permutation:', p3.permutation)\n",
    "print(p3.permutate([-4, 89, 17]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.2 The Finite Galois Field ($GF(2^n)$) \n",
    "we represent the Galois Feld over $2^n$ as a Polynomial and define normal polynomial operations such as addition, subtractionn, multiplication, division over these feilds. We also define XOR operation which is the normal additive action ovr the Galois Feild and multiplication with modulo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Polynomial:\n",
    "    def __init__(self, coefficients: dict):\n",
    "        self.coefficients = coefficients\n",
    "\n",
    "    def __repr__(self):\n",
    "        representation = 'Polynomial{'\n",
    "        for degree, coefficient in self.coefficients.items():\n",
    "            representation += str(coefficient if coefficient != 1 else '') + 'x^' + str(degree) + ' '\n",
    "        return representation + '}'\n",
    "\n",
    "    def __add__(self, other):\n",
    "        result = {}\n",
    "        self.update_coefficients(other, result)\n",
    "        self.update_coefficients(self, result)\n",
    "        result = Polynomial(result)\n",
    "        result.prune()\n",
    "        return result\n",
    "\n",
    "    def __sub__(self, other):\n",
    "        result = {}\n",
    "        self.update_coefficients(self, result)\n",
    "        self.update_coefficients(other, result, factor=-1)\n",
    "        result = Polynomial(result)\n",
    "        result.prune()\n",
    "        return result\n",
    "\n",
    "    def __mul__(self, other):\n",
    "        result = {}\n",
    "        for degree1, coefficient1 in self.coefficients.items():\n",
    "            for degree2, coefficient2 in other.coefficients.items():\n",
    "                result[degree1 + degree2] = result.get(degree1 + degree2, 0) + coefficient1 * coefficient2\n",
    "        result = Polynomial(result)\n",
    "        result.prune()\n",
    "        return result\n",
    "\n",
    "    def __truediv__(self, divisor):\n",
    "        dividend = Polynomial(self.coefficients.copy())\n",
    "        quotient = {}\n",
    "        while dividend.degree() >= divisor.degree():\n",
    "            quotient_pow = dividend.degree() - divisor.degree()\n",
    "            quotient_coefficient = dividend.coefficients[dividend.degree()] / divisor.coefficients[divisor.degree()]\n",
    "            quotient[quotient_pow] = quotient.get(quotient_pow, 0) + quotient_coefficient\n",
    "            dividend = dividend - (divisor * Polynomial({quotient_pow: quotient_coefficient}))\n",
    "        return Polynomial(quotient), dividend\n",
    "\n",
    "    def __mod__(self, divisor):\n",
    "        return (self / divisor)[1]\n",
    "\n",
    "    def __xor__(self, other):\n",
    "        result = {}\n",
    "        for degree, coefficient in self.coefficients.items():\n",
    "            result[degree] = coefficient ^ other.coefficients.get(degree, 0)\n",
    "        for degree, coefficient in other.coefficients.items():\n",
    "            result[degree] = coefficient ^ self.coefficients.get(degree, 0)\n",
    "        result = Polynomial(result)\n",
    "        result.prune()\n",
    "        return result\n",
    "\n",
    "    def __neg__(self):\n",
    "        result = Polynomial(self.coefficients.copy())\n",
    "        for degree, coefficient in result.coefficients.items():\n",
    "            result.coefficients[degree] = -coefficient\n",
    "        return result\n",
    "\n",
    "    def degree(self) -> int:\n",
    "        return max(degree for degree in self.coefficients)\n",
    "\n",
    "    def prune(self):\n",
    "        zero_coefficient_degrees = set()\n",
    "        for degree, coefficient in self.coefficients.items():\n",
    "            if coefficient == 0:\n",
    "                zero_coefficient_degrees.add(degree)\n",
    "        for degree in zero_coefficient_degrees:\n",
    "            del self.coefficients[degree]\n",
    "\n",
    "    def additive_inverse(self):\n",
    "        return -self\n",
    "\n",
    "    @staticmethod\n",
    "    def update_coefficients(polynomial, coefficients, factor=1):\n",
    "        for degree, coefficient in polynomial.coefficients.items():\n",
    "            coefficients[degree] = coefficients.get(degree, 0) + factor * coefficient\n",
    "\n",
    "    @staticmethod\n",
    "    def additive_identity():\n",
    "        return Polynomial({})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Polynomial{x^8 x^4 x^3 x^1 x^0 x^12 x^7 x^2 }\n"
     ]
    }
   ],
   "source": [
    "# the polynomial is defined as a map of degree and corresponding coefficients\n",
    "# Testing the adition operation\n",
    "p1 = Polynomial({12: 1, 7: 1, 2: 1})\n",
    "p2 = Polynomial({8: 1, 4: 1, 3: 1, 1: 1, 0: 1})\n",
    "print(p1 + p2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Polynomial{x^12 x^7 x^2 -1x^8 -1x^4 -1x^3 -1x^1 -1x^0 }\n"
     ]
    }
   ],
   "source": [
    "# testing subtraction\n",
    "print(p1 - p2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Polynomial{x^20 x^16 2x^15 x^13 x^12 x^11 2x^10 x^8 x^7 x^6 x^5 x^3 x^2 }\n"
     ]
    }
   ],
   "source": [
    "#testing multiplication\n",
    "print(p1 * p2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Polynomial{-1x^12 -1x^7 -1x^2 }\n"
     ]
    }
   ],
   "source": [
    "# testing negation\n",
    "print(-p1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Polynomial{x^2 x^12 x^7 }\n",
      "Polynomial{x^12 x^7 x^2 }\n"
     ]
    }
   ],
   "source": [
    "# testing division\n",
    "quotient, remainder = p1 / p2\n",
    "print(quotient * p2 + remainder)\n",
    "print(p1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Polynomial{x^5 x^1 x^3 x^0 }\n"
     ]
    }
   ],
   "source": [
    "# testing the XOR operator\n",
    "p3 = Polynomial({5: 1, 2: 1, 1: 1})\n",
    "p4 = Polynomial({3: 1, 2: 1, 0: 1})\n",
    "print(p3 ^ p4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The additve identity is the zero Polynomial of the Galois Feild and the additve inverse is the negative of the Polynomial. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Polynomial{}\n",
      "Polynomial{-1x^12 -1x^7 -1x^2 }\n",
      "Polynomial{}\n"
     ]
    }
   ],
   "source": [
    "print(p1.additive_identity())\n",
    "print(p1.additive_inverse())\n",
    "print(p1 + p1.additive_inverse())"
   ]
  }
 ],
 "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.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}