mpc_2_zkp.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Cryptography\n",
    "\n",
    "## Secure Multiparty Computation - part 1\n",
    "\n",
    "# Intro"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**A Pragmatic Introduction to Secure Multi-Party Computation** by David Evans, Vladimir Kolesnikov, Mike Rosulek"
   ]
  },
  {
   "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": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Agenda"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Motivation\n",
    "\n",
    "* Auctions\n",
    "* Procurement\n",
    "* Benchmarking\n",
    "* Data Mining\n",
    "* Voting\n",
    "* Any computable function/functionality"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Tools\n",
    "\n",
    "* (verifiable) secret sharing\n",
    "* oblivious transfer\n",
    "* (homomorphic) commitments\n",
    "* zero-knowledge proofs \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "![oblivious transfer](img/ot.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import math\n",
    "import random\n",
    "from sympy import randprime, isprime, Mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def egcd(a, b):\n",
    "    if a == 0:\n",
    "        return (b, 0, 1)\n",
    "    else:\n",
    "        g, y, x = egcd(b % a, a)\n",
    "        return (g, x - (b // a) * y, y)\n",
    "\n",
    "def modinv(a, m):\n",
    "    g, x, y = egcd(a, m)\n",
    "    if g != 1:\n",
    "        raise Exception('modular inverse does not exist')\n",
    "    else:\n",
    "        return x % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [],
   "source": [
    "from sympy import primefactors"
   ]
  },
  {
   "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$"
   ]
  },
  {
   "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": {
    "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": 14,
   "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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "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": 16,
   "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 = 52\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": 17,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "512893 65537 467343\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",
    "    d = modinv(e, m)\n",
    "    return N, e, d, p, q\n",
    "# N, e - public key\n",
    "# N, d - private key\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",
    "N, e, d, p, q = GenRSA(\"111111111\")\n",
    "#print(\"private key: \", d)\n",
    "#print(\"public key: \", N, e)\n",
    "\n",
    "xx  = 120 * p % N #random.randint(2, N)\n",
    "\n",
    "y = enc(xx, N, e)\n",
    "x = dec(y, N, d)\n",
    "print(N, e, y)"
   ]
  },
  {
   "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": 18,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def randomZnElement(N):\n",
    "    g = N\n",
    "    while math.gcd(g, N) != 1:\n",
    "        g = random.randint(2, N)\n",
    "    return g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [],
   "source": [
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Naive Identification Scheme"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "## Password Scheme\n",
    "\n",
    "Peggy $(x, f(x))$, Vic $f(x)$\n",
    "1. Peggy:\n",
    "    * sends $x$ to Vic\n",
    "2. Vic:\n",
    "    * checks if $f(x)$ is correct\n",
    "  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "## Identification based on Public-Key Encryption\n",
    "\n",
    "Peggys $(x, f(x))$, Vic: $f(x)$\n",
    "\n",
    "1. Vic:\n",
    "    * selects $m$\n",
    "    * encrypts $c = Enc(f(x), m)$\n",
    "    * sends $c$ to Peggy\n",
    "2. Peggy:\n",
    "    * decrypts $m' = Dec(x, c)$\n",
    "    * sends $m'$ to Vic\n",
    "3. Vic:\n",
    "    * accepts the identity of Peggy iff $m=m'$\n",
    "    \n",
    "Dishonest Vic :\n",
    "1. captures an encryption $c$ that was sent to Peggy and then Vic can sent $c$ as a challenge\n",
    "2. Peggy decrypts $m' = Dec(x, c)$\n",
    "3. Vic learns the value of $m' = m$\n",
    "\n",
    "Before the protocol:\n",
    "- f(x)\n",
    "- c\n",
    "\n",
    "After the protocol:\n",
    "- he knows that $$m = Dec(x, c)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "![Naive authentication scheme](img/auth-enc.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A (Peggy) has:\n",
    "    - secret key $x$\n",
    "    - public key $f(x)$, for one-way function $f$\n",
    "    \n",
    "B (Vic) has:\n",
    "    - public key $f(x)$\n",
    "    \n",
    "    \n",
    "A's input: x\n",
    "$$F_A = 0$$\n",
    "\n",
    "\n",
    "B's input: $f(x) = y$\n",
    "$$F_B(x, y) = (y = f(x)) ? 1:0$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Completenes**: If Peggy knows the prover's secret, then Vic will always accept Peggy's proof."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Soundness**: If Peggy can convince Vic with reasonable probability, then she know the prover's secret.\n",
    "\n",
    "If Peggy does not know the secret then with high probability Vic will detect that"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Zero-knowledge** (intuition): whatever the verifier can efficiently compute after interacting with the prover, can be efficiently simulated without interaction.\n",
    "\n",
    "Performing the protocol with the Prover (Peggy) should not give any new information to Verifier (Vic)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Simplified Fiat-Shamir Identification Scheme"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Signature scheme (12.1)** a signature scheme is a tuple of three probabilistic polynomial-time algorithms $(Gen, Sign, Vrfy)$ satisfying the following:\n",
    "\n",
    "\n",
    "1. $(pk, sk) \\leftarrow Gen(1^n)$\n",
    "2. $\\sigma \\leftarrow Sign_{sk}(m)$, $m \\in \\{0, 1\\}^*$ ($Sign$ is probabilistic)\n",
    "3. $$b  = Vrfy(pk, m, \\sigma)$$\n",
    "    * $b = 1$ valid \n",
    "    * $b = 0$ invalid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Signature experiment $SigForge_{\\mathcal{A}, \\Pi}(n)$:\n",
    "\n",
    "1. $(pk, sk) \\leftarrow Gen(1^n)$\n",
    "2. \n",
    "    * $\\mathcal{A}$ is given $pk$ and oracle access to $Sign_{sk}(\\cdot)$\n",
    "    * $\\mathcal{A}$ outputs $(m, \\sigma)$\n",
    "    * $Q$ - the set of messages whose signature were requested by $\\mathcal{A}$ during its execution\n",
    "3. The output of the experiment is defined to be $1$ if and only if:\n",
    "    1. $Vrfy_{pk}(m, \\sigma) = 1$\n",
    "    2. $m \\not \\in Q$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "**Definition 12.2** A signature scheme $\\Pi = (Gen, Sign, Vrfy)$ is **existentially unforgeable under an adaptive chosen-message attack** if for all probabilistic polynomial-time adversaries $\\mathcal{A}$, there exists a negligible function **negl** such that\n",
    "$$P\\left[SigForge_{\\mathcal{A}, \\Pi}(n) = 1\\right] \\leq \\textsf{negl}(n).$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Textbook RSA signature**\n",
    "\n",
    "**Gen** $(N, e, d) \\leftarrow GenRSA(1^n)$\n",
    "\n",
    "* the public key $(N, e)$\n",
    "* the private key $(N, d)$\n",
    "\n",
    "**Sign**$([N, d], m)$, $m \\in Z_N^*$:\n",
    "\n",
    "* return $\\sigma = [m^d \\bmod N]$\n",
    "\n",
    "**Vrfy**$([N, e], m, \\sigma)$, output 1 if and only if\n",
    "\n",
    "$$ m = [\\sigma^e \\bmod N]$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "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, p, q\n",
    "\n",
    "def sign(x, N, d):\n",
    "    return x ** d % N\n",
    "\n",
    "def vrfy(m, sigma, N, e):\n",
    "    return m == sigma ** e % N"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Example 1** A no-message attack\n",
    "\n",
    "Goal: forge a signature under a random message"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$\\mathcal{A}([N, e])$:\n",
    "1. select $\\sigma \\leftarrow Z_N^*$\n",
    "2. compute $m = \\sigma^e \\bmod N$\n",
    "3. return $(m, \\sigma)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "N, e, d, p, q = GenRSA(\"11111\")\n",
    "\n",
    "def A(N, e):\n",
    "    sigma = randomZnElement(N)\n",
    "    m = sigma ** e % N\n",
    "    return m, sigma"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "m, sigma = A(N, e)\n",
    "print(m, sigma)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "vrfy(m, sigma, N, e)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Signature experiment $SigForge_{\\mathcal{A}, \\Pi}(n)$:\n",
    "\n",
    "1. $(pk, sk) \\leftarrow Gen(1^n)$\n",
    "2. \n",
    "    * $\\mathcal{A}$ is given $pk$ and oracle access to $Sign_{sk}(\\cdot)$\n",
    "    * $\\mathcal{A}$ outputs $(m, \\sigma)$\n",
    "    * $Q$ - the set of messages whose signature were requested by $\\mathcal{A}$ during its execution\n",
    "3. The output of the experiment is defined to be $1$ if and only if:\n",
    "    1. $Vrfy_{pk}(m, \\sigma) = 1$\n",
    "    2. $m \\not \\in Q$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Textbook RSA signature\n",
    "\n",
    "**Gen** $(N, e, d) \\leftarrow GenRSA(1^n)$\n",
    "\n",
    "* the public key $(N, e)$\n",
    "* the private key $(N, d)$\n",
    "\n",
    "**Sign**$([N, d], m)$, $m \\in Z_N^*$:\n",
    "\n",
    "* return $\\sigma = [m^d \\bmod N]$\n",
    "\n",
    "**Vrfy**$([N, e], m, \\sigma)$, output 1 if and only if\n",
    "\n",
    "$$ m = [\\sigma^e \\bmod N]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Example 2** Forging a signature on an arbitrary message"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "![forge](img/forge.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "m = randomZnElement(N)\n",
    "m1 = randomZnElement(N)\n",
    "m2 = m * modinv(m1, N) % N\n",
    "\n",
    "s1 = sign(m1, N, d)\n",
    "s2 = sign(m2, N, d)\n",
    "\n",
    "print(m, m1, m2)\n",
    "\n",
    "print(s1, s2)\n",
    "\n",
    "\n",
    "vrfy(m, (s1 * s2) % N, N, e)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Factoring - Fermat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "p = randprime(2000, 10000)\n",
    "q = randprime(2000, 10000)\n",
    "\n",
    "n = p * q\n",
    "\n",
    "print(p, q, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [],
   "source": [
    "gcdPlus = 1\n",
    "gcdMinus = 1\n",
    "\n",
    "step = 1\n",
    "\n",
    "while gcdPlus == 1 and gcdMinus == 1:\n",
    "    x = random.randint(2, n)\n",
    "    y = random.randint(2, n)\n",
    "    gcdPlus = math.gcd((x+y) % n, n)\n",
    "    gcdMinus = math.gcd((x-y) % n, n)\n",
    "    print(step, gcdPlus, gcdMinus)\n",
    "    step = step + 1\n",
    "    \n",
    "if gcdPlus > 1:\n",
    "    print(gcdPlus,\"*\", n // gcdPlus, \"=\", n)\n",
    "else:\n",
    "    print(gcdMinus,\"*\", n // gcdMinus, \"=\", n)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def P_gen(w):\n",
    "    N, e, d, p, q = GenRSA(w)"
   ]
  }
 ],
 "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}