public_key_crypto_2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Cryptography\n",
    "\n",
    "## Public key cryptography\n",
    "\n",
    "### Number theory - part 2"
   ]
  },
  {
   "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": 54,
   "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.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": 55,
   "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": 57,
   "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": 58,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 * -2 + 21 * 1 = 1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(a, \"*\", x, \"+\", b, \"*\", y, \"=\", math.gcd(a,b))\n",
    "a * x + b * y"
   ]
  },
  {
   "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": [
    "**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": 59,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "N = 37\n",
    "a = 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4  * -9  +  37  *  1  =  1\n"
     ]
    }
   ],
   "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": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-9 28\n"
     ]
    }
   ],
   "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$ such that $g \\oplus h = e$\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",
    "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": [
    "$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": [
    "$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": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "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": "markdown",
   "metadata": {
    "cell_style": "split",
    "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": 63,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "p =  71  m =  70\n",
      "11  **  702  =  11  ** ( 702  %  70 ) = \n",
      " 11  **  2  (mod  71 )\n",
      "50\n",
      "50\n"
     ]
    }
   ],
   "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": 64,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4  *  172  =  4  * ( 172  %  24 ) =  4  *  4  (mod  24 )\n",
      "16\n",
      "16\n"
     ]
    }
   ],
   "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": 81,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "41 79 1517 1440\n"
     ]
    }
   ],
   "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": 85,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "518 139\n"
     ]
    }
   ],
   "source": [
    "e = 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": 68,
   "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": 86,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1270 1 821 329\n"
     ]
    }
   ],
   "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": 88,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7029"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "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": 95,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(9594, 123, 78)"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "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": 96,
   "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": 97,
   "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": 102,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.74"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sec_param = 100\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": 107,
   "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": 111,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(7081, 97, 73)"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "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": 112,
   "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": 113,
   "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": 118,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 34.5 s, sys: 0 ns, total: 34.5 s\n",
      "Wall time: 34.5 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 118,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "sec_param = 60\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 // 2)\n",
    "\n",
    "num_of_succ/tries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "private key:  10925\n",
      "public key:  16129 65537\n",
      "124 15491 8550\n"
     ]
    }
   ],
   "source": [
    "def GenRSA(w):\n",
    "    n = len(w)\n",
    "    N, p, q = GenModulus(w)\n",
    "    m = (p-1) * (q-1)\n",
    "    e = 2 ** 16 + 1\n",
    "    gcd, d, y = egcd(e, m)\n",
    "    if d < 0:\n",
    "        d = m + d\n",
    "    return N, e, d\n",
    "\n",
    "N, e, d = GenRSA(\"111111\")\n",
    "print(\"private key: \", d)\n",
    "print(\"public key: \", N, e)\n",
    "\n",
    "x  = 124\n",
    "\n",
    "def enc(x, N, e):\n",
    "    return x ** e % N\n",
    "\n",
    "def dec(c, N, d):\n",
    "    return c ** d % N\n",
    "\n",
    "c = enc(x, N, e)\n",
    "pt = dec(c, N, d)\n",
    "\n",
    "print(x, pt, c)"
   ]
  },
  {
   "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": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Cyclic groups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Let $\\mathbf{G}$ be a finite group of order $m$.\n",
    "\n",
    "Let $g \\in \\mathbf{G}$, consider the set:\n",
    "$$\\langle g \\rangle = \\{g^0, g^1, \\ldots \\}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "From *Theorem 7.14* we have $g^m = 1$.\n",
    "\n",
    "Let $i \\leq m$ be the samallest positive integer for which $g^i = 1$.\n",
    "\n",
    "Then the sequence repeats after $i$ terms, so:\n",
    "$$\\langle g \\rangle = \\{g^0, \\ldots, g^{i-1}\\}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The set contains exactly $i$ elements since:\n",
    "\n",
    "if $g^j = g^k$ with $0 \\leq j < k < i$\n",
    "\n",
    "then $g^{k-j} = 1$ and $0 < k - j < i$ (contradicting choice of $i$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$\\langle g \\rangle$ is a subgroup of $\\mathbf{G}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 10)\n"
     ]
    }
   ],
   "source": [
    "def group(n):\n",
    "    G = []\n",
    "    m = 0\n",
    "    for i in range(n):\n",
    "        if math.gcd(i, n) == 1:\n",
    "            G.append(i)\n",
    "            m = m + 1\n",
    "    return G, m\n",
    "            \n",
    "p = 11\n",
    "print(group(p)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dict_keys([1, 2, 4, 8, 5, 10, 9, 7, 3, 6]) 10\n"
     ]
    }
   ],
   "source": [
    "def subgroup(g, n, m):\n",
    "    H = {}\n",
    "    for i in range(m):\n",
    "        H[(g ** i % n)] = 1\n",
    "    return H\n",
    "\n",
    "p = 11\n",
    "gs = subgroup(2, p, p-1)\n",
    "\n",
    "print(gs.keys(), len(gs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 7 35 24\n",
      "6 dict_keys([1, 4, 16, 29, 11, 9])\n"
     ]
    }
   ],
   "source": [
    "p, q = 5, 7\n",
    "n, m = p * q, (p-1)*(q-1)\n",
    "print(p, q, n, m)\n",
    "#group(n)\n",
    "w = subgroup(4, n, m)\n",
    "print(len(w), w.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "*Definition 7.48* Let $\\mathbf{G}$ be a finite group and $g \\in \\mathbf{G}$. The **order** of $g$ is the smallest positive integer $i$ with $g^i = 1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 157,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def order(g, n):\n",
    "    o = 1\n",
    "    while g ** o % n != 1:\n",
    "        o = o + 1\n",
    "    return o\n",
    "\n",
    "order(10, 11)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Definition 7.49 Let $\\mathbf{G}$ be a finite group, and $g \\in \\mathbf{G}$ an element of order $i$. Then for any integer $x$ we have $g^x = g^{x \\bmod i}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Proposition 7.50 Let $\\mathbf{G}$ be a finite group, and $g \\in \\mathbf{G}$\n",
    "an element of order $i$.\n",
    "\n",
    "Then $g^x = g^y$ if and only if $x = y \\bmod i$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$\\langle 1 \\rangle = \\{ 1\\}$ - order 1\n",
    "\n",
    "if there exists $g \\in \\mathbf{G}$ with order $m = | \\mathbf{G}|$ then $\\langle g \\rangle = \\mathbf{G}$ and we call $\\mathbf{G}$ **cyclic**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(group(21))\n",
    "print(order(8, 21))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Proposition 7.51 Let $\\mathbf{G}$ be a finite group of order $m$, and say $g \\in \\mathbf{G}$ has order $i$ then $i | m$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Corollary 7.52 If $\\mathbf{G}$ is a group of prime order $p$, then $\\mathbf{G}$ is cyclic.\n",
    "\n",
    "Furthermore, all elements of $\\mathbf{G}$ except the identity are generators of $\\mathbf{G}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Theorem 7.53 If $p$ is prime then $\\mathbf{Z}_p^*$ is cyclic."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "$Z_{15}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([1, 2, 4, 7, 8, 11, 13, 14], 8)"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "group(15)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$DLOG_{\\mathcal{A}, G}(n)$:\n",
    "1. Run $\\mathcal{G}(1^n)$ to obtain $(G, q, g)$:\n",
    "    * $\\mathcal{G}$ - cyclic group \n",
    "    * $m$ - group order\n",
    "    * $g$ - generator\n",
    "2. Choose $h \\leftarrow \\mathcal{G}$\n",
    "3. $x \\leftarrow \\mathcal{A}(\\mathcal{G}, q, g, h)$\n",
    "4. Output is $1$ if $g^x = h$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Definintion 7.59 We say that the **discrete logarithm problem is hard relative to $\\mathcal{G}$** if for all PPT algorithms $\\mathcal{A}$ there exists a negligible function $\\mathsf{negl}$ such that \n",
    "$$P[DLOG_{\\mathcal{A}, G}(n) = 1] \\leq \\mathsf{negl}.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Computational Diffie-Hellman (CDH)**\n",
    "\n",
    "Fix a cyclic group $\\mathbf{G}$ and a generator $g \\in \\mathbf{G}$. Given $h_1, h_2$, define\n",
    "$$DH_g(h_1, h_2) = g^{\\log_g h_1 \\cdot \\log_g h_2}$$\n",
    "\n",
    "If $h_1 = g^x$ and $h_2 = g^y$ then \n",
    "$$DH_g(h_1, h_2) = g^{x \\cdot y} = h_1^y = h_2^x.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Definition 7.60 We say that DDH problem is hard relative to $\\mathbf{G}$ if for all PPT algorithms $\\mathcal{A}$ there exists a negligible function $\\mathsf{negl}$ such that\n",
    "$$\\left|P\\left[\\mathcal{A}(\\mathbf{G}, q, g, g^x, g^y, g^z) = 1\\right] - P\\left[\\mathcal{A}(\\mathbf{G}, q, g, g^x, g^y, g^{xy}\\right) = 1\\right| \\leq \\mathsf{negl},$$\n",
    "where in each case the probabilities are taken over the experiment in which $\\mathcal{G}(1^n)$ outputs $(\\mathbf{G}, q, g)$, and then random $x, y, z \\in \\mathbf{Z}_q$ are chosen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11 23 True\n"
     ]
    }
   ],
   "source": [
    "p = randprime(2, 20)\n",
    "q = 2 * p  + 1\n",
    "a = isprime(q)\n",
    "\n",
    "print(p, q, a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 193,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22], 22)\n",
      "5\n",
      "2\n",
      "11\n",
      "dict_keys([1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12]) None\n"
     ]
    }
   ],
   "source": [
    "print(group(q))\n",
    "\n",
    "x = random.randint(1, 2 * p)\n",
    "print(x)\n",
    "g = x ** 2 % q\n",
    "print(g)\n",
    "\n",
    "S = subgroup(g, q, q -1)\n",
    "print(S.keys(), print(len(S)))"
   ]
  }
 ],
 "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
}