public_key_crypto_1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Cryptography\n",
    "\n",
    "## Public key cryptography\n",
    "\n",
    "### Number theory - part 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Formuation of propositions, lemmas, definitions comes from:\n",
    "**Introduction to modern cryptography** by *Jonathan Katz* and *Yehuda Lindell*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "To see the notebook as a slide-show, use [RISE](https://rise.readthedocs.io/en/stable/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import math\n",
    "import random\n",
    "from sympy import randprime, isprime, Mod"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Proposition 7.1** Let $a$ be an integer and $b$ a positive integer. Then there exists unique integers $q, r$ for which $a = q b  + r$ and $0 \\leq r < b$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "a = 44\n",
    "b = 13"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "r = a % b\n",
    "print(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "q = a // b\n",
    "print(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(q * b  + r)\n",
    "print(a, \"=\", q, \"*\", b, \"+\", r)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Proposition 7.2** Let $a, b$ be positive integers. Then there exists integers $X, Y$ such that $Xa + Yb = \\gcd(a, b)$. \n",
    "\n",
    "Furthermore, $\\gcd(a, b)$ is the smallest positive integer that can be expressed in this way."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def egcd(a, b):\n",
    "    x,y, u,v = 0,1, 1,0\n",
    "    while a != 0:\n",
    "        q, r = b//a, b%a\n",
    "        m, n = x-u*q, y-v*q\n",
    "        b,a, x,y, u,v = a,r, u,v, m,n\n",
    "    gcd = b\n",
    "    return gcd, x, y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "a = 10\n",
    "b = 21\n",
    "\n",
    "gcd, x, y = egcd(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(a, \"*\", x, \"+\", b, \"*\", y, \"=\", math.gcd(a,b))\n",
    "a * x + b * y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Proposition 7.3** If $c | ab$ and $\\gcd(a, c) = 1$, then $c | b$. In particular, if $p$ is prime and $p | ab$ then either $p | a$ or $p | b$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "a = 12\n",
    "b = 15\n",
    "a * b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "c = 5\n",
    "print(math.gcd(a, c))\n",
    "print(a*b % c)\n",
    "print(b % c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Proposition 7.4** If $p | N$, $q | N$, and $\\gcd(p, q) = 1$, then $pq | N$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "p1 = 69\n",
    "q1 = 10\n",
    "N1 = 690\n",
    "print(math.gcd(p1, q1))\n",
    "print(N1 % p1)\n",
    "print(N1 % q1)\n",
    "print(N1 % (p1 * q1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "p2 = 46\n",
    "q2 = 10\n",
    "N2 = 690\n",
    "print(math.gcd(p2, q2))\n",
    "print(N2 % p2)\n",
    "print(N2 % q2)\n",
    "print(N2 % (p2 * q2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(N1 / (p1 * q1))\n",
    "print(N1 % (p1 * q1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(N2 / (p2 * q2))\n",
    "print(N2 % (p2 * q2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Example 7.5** (multiplication)\n",
    "\n",
    "$1230123012301 \\cdot 567567567 \\bmod 100 = ?$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$1230123012301 \\bmod 100 = 1$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$567567567 \\bmod 100 = 67$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$1230123012301 \\cdot 567567567 \\bmod 100 =$ \n",
    "\n",
    "$[1230123012301 \\bmod 100] \\cdot [567567567 \\bmod 100] = 1 \\cdot 67 \\bmod 100 = 67 $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "If for $b$ there exists an integer $b^{-1}$ such that $b b^{-1} = 1 \\bmod N$ then we call:\n",
    "\n",
    "* $b$ invertible\n",
    "\n",
    "* $b^{-1}$ modular inverse of $b$ modulo $N$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$a \\cdot b = c \\cdot b \\bmod N$\n",
    "\n",
    "$(a b) \\cdot b^{-1} = (c b) \\cdot b^{-1} \\bmod N \\rightarrow a = c \\bmod N$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Example 7.6** (division)\n",
    "\n",
    "$N = 36$. Then $ 5 \\cdot 4 = 20 = 23 \\cdot 4 \\bmod 36$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "But $5 \\neq 23 \\bmod 36$.\n",
    "\n",
    "Problem: $4 | 36$. $4$ is not invertible"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for i in range(1,36):\n",
    "    print(str(i) + \" \" + str(Mod(4 * i, 36) ))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Proposition 7.7** Let $a, N$ be integers, with $N > 1$. Then $a$ is invertible modulo $N$ if and only if $\\gcd(a, N) = 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$a X + N Y = \\gcd(a, N) = 1$\n",
    "\n",
    "$a X = 1 \\bmod N$\n",
    "\n",
    "$X = a^{-1} \\bmod N$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "N = 37\n",
    "a = 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "gcd, x, y = egcd(a, N)\n",
    "print(a, \" *\", x, \" + \", N, \" * \", y, \" = \", gcd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "Mod(a * x, N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Mod(a * (N - 9), N)\n",
    "print(x, N+x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Definition 7.9** A group is a set $\\mathbf{G}$ along with a binary operation $\\oplus$ for which the following conditions hold:\n",
    "\n",
    "* (Closure:) For all $g, h \\in \\mathbf{G}$, $g \\oplus h \\in \\mathbf{G}$\n",
    "\n",
    "* (Existance of an Identity:) There exists an **identity** $e \\in \\mathbf{G}$ such that for all $g \\in \\mathcal{G}$, $e \\oplus g = g = g \\oplus e$.\n",
    "\n",
    "* (Existence of Inverses:) For all $g \\in \\mathbf{G}$ there exists an element $h \\in \\mathbf G$\n",
    "\n",
    "* (Associativity:) For all $g_1, g_2, g_3 \\in \\mathbf{G}$, $(g_1 \\oplus g_2) \\oplus g_3 = g_1 \\oplus (g_2 \\oplus g_3)$.\n",
    "\n",
    "If $\\mathbf{G}$ has finite number of elements $\\rightarrow \\mathbf{G}$ is a *finite group*\n",
    "\n",
    "$|\\mathbf{G}|$ - order of the group - number of elements in $\\mathbf{G}$\n",
    "\n",
    "$\\mathbf{G}$ is **abelian** if\n",
    "\n",
    "* for all $g, h \\in \\mathbf{G}, g \\oplus h = h \\oplus g$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$(\\mathbb{Z}, +)$ - abelian group\n",
    "\n",
    "* closure"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* identity 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* inverse to $g$ is $h = -g$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* associativity\n",
    "\n",
    "* abelian"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Definition 7.9** A group is a set $\\mathbf{G}$ along with a binary operation $\\oplus$ for which the following conditions hold:\n",
    "\n",
    "* (Closure:) For all $g, h \\in \\mathbf{G}$, $g \\oplus h \\in \\mathbf{G}$\n",
    "\n",
    "* (Existance of an Identity:) There exists an **identity** $e \\in \\mathbf{G}$ such that for all $g \\in \\mathcal{G}$, $e \\oplus g = g = g \\oplus e$.\n",
    "\n",
    "* (Existence of Inverses:) For all $g \\in \\mathbf{G}$ there exists an element $h \\in \\mathbf G$\n",
    "\n",
    "* (Associativity:) For all $g_1, g_2, g_3 \\in \\mathbf{G}$, $(g_1 \\oplus g_2) \\oplus g_3 = g_1 \\oplus (g_2 \\oplus g_3)$.\n",
    "\n",
    "If $\\mathbf{G}$ has finite number of elements $\\rightarrow \\mathbf{G}$ is a *finite group*\n",
    "\n",
    "$|\\mathbf{G}|$ - order of the group - number of elements in $\\mathbf{G}$\n",
    "\n",
    "$\\mathbf{G}$ is **abelian** if\n",
    "\n",
    "* for all $g, h \\in \\mathbf{G}, g \\oplus h = h \\oplus g$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$(\\mathbb{Z}\\setminus \\{0\\}, \\cdot)$ - abelian group?\n",
    "\n",
    "* closure"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* identity 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* inverse to $g$ is $h = 1/g$\n",
    "\n",
    "but $1/2 \\not\\in \\mathbb{Z} \\setminus \\{0\\}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$(\\mathbb{R} \\setminus \\{0\\}, \\cdot)$ is abelian group with identity $1$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Definition 7.9** A group is a set $\\mathbf{G}$ along with a binary operation $\\oplus$ for which the following conditions hold:\n",
    "\n",
    "* (Closure:) For all $g, h \\in \\mathbf{G}$, $g \\oplus h \\in \\mathbf{G}$\n",
    "\n",
    "* (Existance of an Identity:) There exists an **identity** $e \\in \\mathbf{G}$ such that for all $g \\in \\mathcal{G}$, $e \\oplus g = g = g \\oplus e$.\n",
    "\n",
    "* (Existence of Inverses:) For all $g \\in \\mathbf{G}$ there exists an element $h \\in \\mathbf G$\n",
    "\n",
    "* (Associativity:) For all $g_1, g_2, g_3 \\in \\mathbf{G}$, $(g_1 \\oplus g_2) \\oplus g_3 = g_1 \\oplus (g_2 \\oplus g_3)$.\n",
    "\n",
    "If $\\mathbf{G}$ has finite number of elements $\\rightarrow \\mathbf{G}$ is a *finite group*\n",
    "\n",
    "$|\\mathbf{G}|$ - order of the group - number of elements in $\\mathbf{G}$\n",
    "\n",
    "$\\mathbf{G}$ is **abelian** if\n",
    "\n",
    "* for all $g, h \\in \\mathbf{G}, g \\oplus h = h \\oplus g$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$G = \\left\\{A^n | n \\in \\mathbb{Z}\\right\\} = \\left\\{\\begin{pmatrix} 1 & 2 n \\\\ 0 & 1 \\end{pmatrix}: n \\in \\mathbb{Z} \\right\\}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from sympy.matrices import Matrix\n",
    "A = Matrix([[1,2], [0,1]]); A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "A.inv()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "A.inv() * A * A * A \n",
    "\n",
    "(Z, +) <-> G\n",
    "f(x) = Matrix([[1, 2x], [0, 1]])\n",
    "f(0) = Matrix([[1, 0], [0,1]])\n",
    "f(x + y) = f(x) * f(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Definition 7.9** A group is a set $\\mathbf{G}$ along with a binary operation $\\oplus$ for which the following conditions hold:\n",
    "\n",
    "* (Closure:) For all $g, h \\in \\mathbf{G}$, $g \\oplus h \\in \\mathbf{G}$\n",
    "\n",
    "* (Existance of an Identity:) There exists an **identity** $e \\in \\mathbf{G}$ such that for all $g \\in \\mathcal{G}$, $e \\oplus g = g = g \\oplus e$.\n",
    "\n",
    "* (Existence of Inverses:) For all $g \\in \\mathbf{G}$ there exists an element $h \\in \\mathbf G$\n",
    "\n",
    "* (Associativity:) For all $g_1, g_2, g_3 \\in \\mathbf{G}$, $(g_1 \\oplus g_2) \\oplus g_3 = g_1 \\oplus (g_2 \\oplus g_3)$.\n",
    "\n",
    "If $\\mathbf{G}$ has finite number of elements $\\rightarrow \\mathbf{G}$ is a *finite group*\n",
    "\n",
    "$|\\mathbf{G}|$ - order of the group - number of elements in $\\mathbf{G}$\n",
    "\n",
    "$\\mathbf{G}$ is **abelian** if\n",
    "\n",
    "* for all $g, h \\in \\mathbf{G}, g \\oplus h = h \\oplus g$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$Z^+_n = (Z_n, +) = (\\{0, 1, \\ldots, n-1\\}, +_{ \\bmod n})$ for $n \\geq 2$ is an abelian group of order $|Z_n^+| = n$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$a + b := [a + b \\bmod n]$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* closure\n",
    "\n",
    "* identity: 0\n",
    "\n",
    "* inverse of $a$: $a^{-1} = n - a$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [],
   "source": [
    "N = 7\n",
    "a = 3\n",
    "b = 4\n",
    "(a + b) % N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Definition 7.9** A group is a set $\\mathbf{G}$ along with a binary operation $\\oplus$ for which the following conditions hold:\n",
    "\n",
    "* (Closure:) For all $g, h \\in \\mathbf{G}$, $g \\oplus h \\in \\mathbf{G}$\n",
    "\n",
    "* (Existance of an Identity:) There exists an **identity** $e \\in \\mathbf{G}$ such that for all $g \\in \\mathcal{G}$, $e \\oplus g = g = g \\oplus e$.\n",
    "\n",
    "* (Existence of Inverses:) For all $g \\in \\mathbf{G}$ there exists an element $h \\in \\mathbf G$\n",
    "\n",
    "* (Associativity:) For all $g_1, g_2, g_3 \\in \\mathbf{G}$, $(g_1 \\oplus g_2) \\oplus g_3 = g_1 \\oplus (g_2 \\oplus g_3)$.\n",
    "\n",
    "If $\\mathbf{G}$ has finite number of elements $\\rightarrow \\mathbf{G}$ is a *finite group*\n",
    "\n",
    "$|\\mathbf{G}|$ - order of the group - number of elements in $\\mathbf{G}$\n",
    "\n",
    "$\\mathbf{G}$ is **abelian** if\n",
    "\n",
    "* for all $g, h \\in \\mathbf{G}, g \\oplus h = h \\oplus g$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$Z_n^* = (\\{a: \\gcd(a, n) = 1\\}, \\cdot_{ \\bmod n})$. If $n$ is prime:\n",
    "$Z_p^* = (Z_p, \\cdot) = (\\{1, \\ldots, p-1\\}, \\cdot_{ \\bmod p})$ for $p$ prime is an abelian group of order $|Z_p^*| = p - 1$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$a \\cdot b := [a \\cdot b \\bmod n]$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* closure\n",
    "\n",
    "* identity: 1\n",
    "\n",
    "* inverse of $a$?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "p = 17\n",
    "a = 8\n",
    "gcd, x, y = egcd(a, p)\n",
    "print(x)\n",
    "x = 17 + x\n",
    "print(x)\n",
    "print(Mod(x * a, p))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Definition 7.9** A group is a set $\\mathbf{G}$ along with a binary operation $\\oplus$ for which the following conditions hold:\n",
    "\n",
    "* (Closure:) For all $g, h \\in \\mathbf{G}$, $g \\oplus h \\in \\mathbf{G}$\n",
    "\n",
    "* (Existance of an Identity:) There exists an **identity** $e \\in \\mathbf{G}$ such that for all $g \\in \\mathcal{G}$, $e \\oplus g = g = g \\oplus e$.\n",
    "\n",
    "* (Existence of Inverses:) For all $g \\in \\mathbf{G}$ there exists an element $h \\in \\mathbf G$\n",
    "\n",
    "* (Associativity:) For all $g_1, g_2, g_3 \\in \\mathbf{G}$, $(g_1 \\oplus g_2) \\oplus g_3 = g_1 \\oplus (g_2 \\oplus g_3)$.\n",
    "\n",
    "If $\\mathbf{G}$ has finite number of elements $\\rightarrow \\mathbf{G}$ is a *finite group*\n",
    "\n",
    "$|\\mathbf{G}|$ - order of the group - number of elements in $\\mathbf{G}$\n",
    "\n",
    "$\\mathbf{G}$ is **abelian** if\n",
    "\n",
    "* for all $g, h \\in \\mathbf{G}, g \\oplus h = h \\oplus g$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$Z_n^* = (\\{a: \\gcd(a, n) = 1\\}, \\cdot_{ \\bmod n})$. \n",
    "\n",
    "Let $n = p \\cdot q$, $\\qquad p, q$ are primes -- an abelian group of order $|Z_{pq}^*| = (p - 1)(q-1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "p = randprime(1000, 2000)\n",
    "q = randprime(p+1, 2 * p)\n",
    "n = p * q\n",
    "print(p, q, n)\n",
    "order = 0\n",
    "for a in range(n):\n",
    "    if math.gcd(a, n) == 1:\n",
    "        #print(a)\n",
    "        order = order + 1\n",
    "print(\"Order\", order)\n",
    "print(p-1, q-1, (p-1)*(q-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Lemma 7.13** Let $\\mathbf{G}$ be a group and $a, b, c \\in \\mathbf{G}$. If $ac = bc$ then $a = b$.\n",
    "In particular , if $ac = c$ then $a$ is the identity in $\\mathbf{G}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Theorem 7.14** Let $\\mathbf{G}$ be finite group with $m = |\\mathbf{G}|$ with $m = |\\mathbf{G}|$, the order of the group. Then for any element $g \\in \\mathbf{G}$, $g^m = 1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n = 17\n",
    "m = n\n",
    "for g in range(n):\n",
    "    print(g * m % n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "p = randprime(10, 100)\n",
    "print(p)\n",
    "m = p - 1\n",
    "for g in range(1, p):\n",
    "    print(g ** m % p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Corollary 7.15** Let $\\mathbf{G}$ be a finite group with $m = |\\mathbf{G}| > 1$. Then for any $g \\in \\mathbf{G}$ and any integer $i$, we have $g^i = g^{[i \\bmod m]}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "p = randprime(2, 100)\n",
    "m = p - 1\n",
    "print(\"p = \",p, \" m = \", m)\n",
    "i = random.randint(p+1, 10 * p)\n",
    "a = random.randint(1, p-1)\n",
    "print(a,\" ** \", i, \" = \",\n",
    "      a, \" ** (\", i, \" % \", m, \") = \\n\",\n",
    "      a, \" ** \", i % m, \" (mod \",\n",
    "      p, \")\")\n",
    "print(a ** i % p)\n",
    "print(a ** (i % m) % p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "p = random.randint(2, 100)\n",
    "m = p\n",
    "i = random.randint(p, 10 * p)\n",
    "a = random.randint(0, p-1)\n",
    "print(a, \" * \", i, \" = \", \n",
    "      a, \" * (\", i, \" % \", m, \") = \",\n",
    "      a, \" * \", i % m, \" (mod \", p, \")\")\n",
    "print(a * i % p)\n",
    "print(a * (i % m) % p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Corollary 7.17** Let $\\mathbf{G}$ be a finite group with $m = |G| > 1$. Let $e > 0$ be an integer, and define the function $f_e: \\mathbf{G} \\rightarrow \\mathbf{G}$ by\n",
    "$$f_e(g) = g^e.$$\n",
    "\n",
    "If $\\gcd(e, m) = 1$, then $f_e$ is a permutation (i.e., a bijection). Moreover, if \n",
    "$$d = [e^{-1} \\bmod m]$$ then $f_d$ is the inverse of $f_e$.\n",
    "\n",
    "Proof: $f_d(f_e(g)) = f_d(g^e) = (g^e)^d = g^{e \\cdot d \\bmod m} = g^1 = g$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "p = randprime(10, 50)\n",
    "q, n, m = randprime(p+1, 2 * p), p * q, (p-1)*(q-1)\n",
    "print(p, q, n, m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "e = 3; #random.randint(3,m)\n",
    "gcd, d, y = egcd(e, m)\n",
    "if d < 0:\n",
    "    d = m + d\n",
    "print(e, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def f(x, g, n):\n",
    "    return g ** x % n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "g = random.randint(1, n)\n",
    "valid = math.gcd(g, n)\n",
    "ct = f(e, g, n)\n",
    "pt = f(d, ct, n)\n",
    "print(g, valid, ct, pt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Theorem 7.19** Let $N = \\prod_i p_i^{e_i}$, where  the $\\{p_i\\}$ are distinct primes and $e_i \\geq 1$. Then $\\phi(N) = \\prod_i p_i^{e_i - 1}(p_i - 1)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**The factoring experiment** $\\textsf{Factor}_{\\mathcal{A}, GenModulus}(n)$\n",
    "1. $(N, p, q) := GenModulus(1^n)$\n",
    "\n",
    "2. $(p', q') = \\mathcal{A}(N)$\n",
    "\n",
    "3. Output: 1 if $p' \\cdot q' = N$ and $p', q' > 1$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Definition 7.45** We say that factoring is hard relative to **GenModulus** if for all probabilistic polynomial-time algorithms $\\mathsf{A}$ there exists a negligible function **negl** such that \n",
    "$$P[\\textsf{Factor}_{\\mathcal{A}, GenModulus}(n) = 1] \\leq negl(n)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def GenModulus(w):\n",
    "    n = len(w)\n",
    "    p = random.randint(2 ** n, 2 ** (n+1))\n",
    "    q = random.randint(2 ** n, 2 ** (n+1))\n",
    "    N = p * q\n",
    "    return N\n",
    "\n",
    "GenModulus(\"111111\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**The factoring experiment** $\\textsf{Factor}_{\\mathcal{A}, GenModulus}(n)$\n",
    "1. $(N, p, q) := GenModulus(1^n)$\n",
    "\n",
    "2. $(p', q') = \\mathcal{A}(N)$\n",
    "\n",
    "3. Output: 1 if $p' \\cdot q' = N$ and $p', q' > 1$\n",
    "\n",
    "**Definition 7.45** We say that factoring is hard relative to **GenModulus** if for all probabilistic polynomial-time algorithms $\\mathsf{A}$ there exists a negligible function **negl** such that \n",
    "$$P[\\textsf{Factor}_{\\mathcal{A}, GenModulus}(n) = 1] \\leq negl(n)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def GenModulus(w):\n",
    "    n = len(w)\n",
    "    p = random.randint(2 ** n, 2 ** (n+1))\n",
    "    q = random.randint(2 ** n, 2 ** (n+1))\n",
    "    N = p * q\n",
    "    return N, p, q\n",
    "\n",
    "GenModulus(\"111111\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def Factor(n):\n",
    "    N, p, q = GenModulus(\"1\" * n)\n",
    "    pp, qq = A(N)\n",
    "    if pp > 1 and qq > 1 and pp * qq == N:\n",
    "        return 1\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def A(N):\n",
    "    if N % 2 == 0:\n",
    "        return 2, N // 2\n",
    "    else:\n",
    "        return 1, N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [],
   "source": [
    "sec_param = 30\n",
    "num_of_succ = 0\n",
    "tries = 100\n",
    "\n",
    "for i in range(tries):\n",
    "    num_of_succ = num_of_succ + Factor(sec_param)\n",
    "\n",
    "num_of_succ/tries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sympy import primefactors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**The factoring experiment** $\\textsf{Factor}_{\\mathcal{A}, GenModulus}(n)$\n",
    "1. $(N, p, q) := GenModulus(1^n)$\n",
    "\n",
    "2. $(p', q') = \\mathcal{A}(N)$\n",
    "\n",
    "3. Output: 1 if $p' \\cdot q' = N$ and $p', q' > 1$\n",
    "\n",
    "**Definition 7.45** We say that factoring is hard relative to **GenModulus** if for all probabilistic polynomial-time algorithms $\\mathsf{A}$ there exists a negligible function **negl** such that \n",
    "$$P[\\textsf{Factor}_{\\mathcal{A}, GenModulus}(n) = 1] \\leq negl(n)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def GenModulus(w):\n",
    "    n = len(w)\n",
    "    p = randprime(2 ** n, 2 ** (n+1))\n",
    "    q = randprime(2 ** n, 2 ** (n+1))\n",
    "    N = p * q\n",
    "    return N, p, q\n",
    "\n",
    "GenModulus(\"111111\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def Factor(n):\n",
    "    N, p, q = GenModulus(\"1\" * n)\n",
    "    pp, qq = A(N)\n",
    "    if pp > 1 and qq > 1 and pp * qq == N:\n",
    "        return 1\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def A(N):\n",
    "    factors = primefactors(N)\n",
    "    return factors[0], factors[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "%%time\n",
    "sec_param = 20\n",
    "num_of_succ = 0\n",
    "tries = 100\n",
    "\n",
    "for i in range(tries):\n",
    "    num_of_succ = num_of_succ + Factor(sec_param)\n",
    "\n",
    "num_of_succ/tries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def GenRSA(w):\n",
    "    n = len(w)\n",
    "    N, p, q = GenModulus(w)\n",
    "    m = (p-1) * (q-1)\n",
    "    e = 3\n",
    "    gcd, d, y = egcd(e, m)\n",
    "    if d < 0:\n",
    "        d = m + d\n",
    "    return N, e, d\n",
    "\n",
    "GenRSA(\"111111\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**The RSA experiment** $\\textsf{RSA-inv}_{\\mathcal{A}, GenRSA}(n)$\n",
    "1. $(N, e, d) := GenRSA(1^n)$\n",
    "\n",
    "2. choose $y \\leftarrow Z_N^*$\n",
    "\n",
    "2. $x = \\mathcal{A}(N, e, y)$\n",
    "\n",
    "3. Output: 1 if $x^e = y \\bmod N$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Definition 7.46** We say that RSA problem is hard relative to **GenRSA** if for all probabilistic polynomial-time algorithms $\\mathsf{A}$ there exists a negligible function **negl** such that \n",
    "$$P[\\textsf{RSA-inv}_{\\mathcal{A}, GenRSA}(n) = 1] \\leq negl(n)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}