notebooks/2-mathematics-of-cryptography.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ch2: Mathematics of Cryptography"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.1 Euclid's Algorithm \n",
    "Find the gcd of any 2 given numbers `a` and `b`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gcd(a, b):\n",
    "    return gcd(b, a % b) if b != 0 else a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "# test using custom parameters\n",
    "print(gcd(10, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.2 Extended Euclid's Algorithm\n",
    "To find the solution to the equation $ax + by = gcd(a, b)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def extended_gcd(a, b):\n",
    "    s, old_s = 1, 0\n",
    "    t, old_t = 0, 1\n",
    "\n",
    "    while b != 0:\n",
    "        q = a // b\n",
    "        a, b = b, a % b\n",
    "        s, old_s = old_s, s - q * old_s\n",
    "        t, old_t = old_t, t - q * old_t\n",
    "    return a, s, t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7 7\n"
     ]
    }
   ],
   "source": [
    "# test using any custom pramters a and b\n",
    "a = 161\n",
    "b = 28\n",
    "hcf, s, t = extended_gcd(a, b)\n",
    "print(s * a + t * b, hcf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.3 Diophantine's Equation\n",
    "The diopahntine's equation $ax + by = c$ has a solution when $gcd(a, b) | c$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def diophantine_sol_exists(a, b, c):\n",
    "    hcf = gcd(a, b)\n",
    "    return c % hcf == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# returns solution of diophantine equation in form (x, y) if exists\n",
    "# returns the particular solution otherwise returns nothing\n",
    "def diophantine(a, b, c):\n",
    "    hcf = gcd(a, b)\n",
    "    # solution exits\n",
    "    if c % hcf == 0:\n",
    "        _, s, t = extended_gcd(a / hcf, b / hcf)\n",
    "        return int((c / hcf) * s), int((c / hcf) * t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# generator function to iterate over solutions\n",
    "def diophantine_general(a, b, c, iters=10):\n",
    "    if diophantine_sol_exists(a, b, c):\n",
    "        x, y = diophantine(a, b, c)\n",
    "        hcf = gcd(a, b)\n",
    "        for i in range(iters):\n",
    "            yield x + i * (b // hcf), y - i * (a // hcf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 20\n",
      "1 16\n",
      "2 12\n",
      "3 8\n",
      "4 4\n",
      "5 0\n"
     ]
    }
   ],
   "source": [
    "for x, y in diophantine_general(20, 5, 100, iters=6):\n",
    "    print(x, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.4 Additive Inverse\n",
    "Additive inverse of number $a$ in $Z_{n}$ always exists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def additive_inverse(a, n):\n",
    "    return (n - a) % n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "print(additive_inverse(0, 10))\n",
    "print(additive_inverse(4, 10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.5 Multiplicative Inverse\n",
    "Multiplicate inverse of $a$ in $Z_{n}$ exists only if $a$ and $n$ are relitively prime i.e. $gcd(a, n) = 1$. The multiplicative inverse if exists means that $(a * b) mod(n) = 1$ where $b$ is the multiplicative inverse. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def multiplicative_inverse_exists(a, n):\n",
    "    return gcd(a, n) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "print(multiplicative_inverse_exists(8, 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def multiplicative_inverse(a, n):\n",
    "    if multiplicative_inverse_exists(a, n):\n",
    "        for num in range(n):\n",
    "            if multiplicative_inverse_exists(num, n) and (a * num) % n == 1:\n",
    "                return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "print(multiplicative_inverse(1, 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n"
     ]
    }
   ],
   "source": [
    "print(multiplicative_inverse(3, 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "# finding all multiplcative inverse pairs in modulo n\n",
    "def multiplicative_inverses(n):\n",
    "    pairs = []\n",
    "    for num in range(n):\n",
    "        if multiplicative_inverse_exists(num, n):\n",
    "            pairs.append((num, multiplicative_inverse(num, n)))\n",
    "    return pairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(1, 1), (2, 6), (3, 4), (4, 3), (5, 9), (6, 2), (7, 8), (8, 7), (9, 5), (10, 10)]\n"
     ]
    }
   ],
   "source": [
    "print(multiplicative_inverses(11))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "if their exists a multiplicative inverse of $b$ in $Z_n$ then the multiplicative inverse of $b$ is the solution of the extended euclid's algorithm for $n$ and $b$ where the value of `t` will be the multiplicative inverse."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def multiplicative_inverse(b, n):\n",
    "    if multiplicative_inverse_exists(b, n):\n",
    "        return (extended_gcd(n, b)[2] + n) % n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n"
     ]
    }
   ],
   "source": [
    "print(multiplicative_inverse(3, 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "print(multiplicative_inverse(2, 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "19\n"
     ]
    }
   ],
   "source": [
    "print(multiplicative_inverse(11, 26))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "87\n"
     ]
    }
   ],
   "source": [
    "print(multiplicative_inverse(23, 100))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "print(multiplicative_inverse(12, 26))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(1, 1), (2, 6), (3, 4), (4, 3), (5, 9), (6, 2), (7, 8), (8, 7), (9, 5), (10, 10)]\n"
     ]
    }
   ],
   "source": [
    "print(multiplicative_inverses(11))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.5 Soltions to Sigle Variable Linear Equations \n",
    "The solution to the equatin of form $ax \\cong b \\% n$ for x exists if $gcd(a, n) | b$ and the number of solutions are $gcd(a, n)$ The particular solution $x_0 = (b * (a / gcd(a, n))^{-1}) \\% (n / gcd(a, n))$ and the general solutions are $x = x_0 + k(n / gcd(a, n))$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sol_single_var_le(a, b, n):\n",
    "    hcf = gcd(a, n)\n",
    "    sols = []\n",
    "    if b % hcf == 0:\n",
    "        a, b, n = a // hcf, b // hcf, n // hcf\n",
    "        x_0 = (b * multiplicative_inverse(a, n)) % n\n",
    "        for k in range(hcf):\n",
    "            sols.append(x_0 + k * n)\n",
    "    return sols"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[6, 15]\n"
     ]
    }
   ],
   "source": [
    "print(sol_single_var_le(14, 12, 18))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For equations of the form $ax + c \\cong b \\% n$ we first subtract $c$ from both sides to obtain $b = (b - c) \\% n$. Then we obtain an equation of form $ax \\cong b \\% n$ and we use previous method solve."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sol_single_var_le(a, b, n, c=0):\n",
    "    if c != 0:\n",
    "        b = (b - c) % n\n",
    "        \n",
    "    hcf = gcd(a, n)\n",
    "    sols = []\n",
    "    if b % hcf == 0:\n",
    "        a, b, n = a // hcf, b // hcf, n // hcf\n",
    "        x_0 = (b * multiplicative_inverse(a, n)) % n\n",
    "        for k in range(hcf):\n",
    "            sols.append(x_0 + k * n)\n",
    "    return sols"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5]\n"
     ]
    }
   ],
   "source": [
    "print(sol_single_var_le(a=3, b=6, n=13, c=4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[6, 15]\n"
     ]
    }
   ],
   "source": [
    "print(sol_single_var_le(14, 12, 18))"
   ]
  }
 ],
 "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}