quantum_burglary.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.7.4"
    },
    "toc": {
      "base_numbering": 1,
      "nav_menu": {},
      "number_sections": false,
      "sideBar": false,
      "skip_h1_title": false,
      "title_cell": "Table of Contents",
      "title_sidebar": "Contents",
      "toc_cell": false,
      "toc_position": {},
      "toc_section_display": false,
      "toc_window_display": false
    },
    "colab": {
      "name": "quantum_burglary.ipynb",
      "provenance": [],
      "include_colab_link": true
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/smaranjitghose/quantum_burglary/blob/master/quantum_burglary.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XM4O4HS4DQxc",
        "colab_type": "text"
      },
      "source": [
        "# Getting our dependecies"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lHfSbv8TDXFn",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "42cb4caa-ead5-43f5-a54b-d4714d80aabb"
      },
      "source": [
        "!pip install qiskit"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Collecting qiskit\n",
            "  Downloading https://files.pythonhosted.org/packages/6e/fa/1bf49aace6a4284d4326d39f2420cfb55378c1121c670437bcfe2fde9831/qiskit-0.18.0.tar.gz\n",
            "Collecting qiskit-terra==0.13.0\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/f4/7b/3cca9feb422031c328f3f8ce592527f7373a2e0ad3a0ebf68826f792b730/qiskit_terra-0.13.0-cp36-cp36m-manylinux2010_x86_64.whl (3.0MB)\n",
            "\u001b[K     |████████████████████████████████| 3.0MB 2.8MB/s \n",
            "\u001b[?25hCollecting qiskit-aer==0.5.0\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/95/b6/012458a5e892d8e18ef4ec734194bac816ffe32d50ddc0100b565455f0d8/qiskit_aer-0.5.0-cp36-cp36m-manylinux2010_x86_64.whl (23.4MB)\n",
            "\u001b[K     |████████████████████████████████| 23.4MB 1.7MB/s \n",
            "\u001b[?25hCollecting qiskit-ibmq-provider==0.6.0\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/ff/7d/94c7fada92532f1133ecd65dc08b1b12a2eb34e3c73b1ca515ef439b0a0a/qiskit_ibmq_provider-0.6.0-py3-none-any.whl (149kB)\n",
            "\u001b[K     |████████████████████████████████| 153kB 43.5MB/s \n",
            "\u001b[?25hCollecting qiskit-ignis==0.3.0\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/b9/f5/25c92e7c816da820163d0e951b5f340a5f69a4088c42fb44df4a9ba6bf14/qiskit_ignis-0.3.0-py3-none-any.whl (172kB)\n",
            "\u001b[K     |████████████████████████████████| 174kB 50.4MB/s \n",
            "\u001b[?25hCollecting qiskit-aqua==0.6.5\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/25/2d/ef2b2672c544a85a799dccc0de3c8dab88bee1b92cc84c302e01808eecfb/qiskit_aqua-0.6.5-py3-none-any.whl (1.8MB)\n",
            "\u001b[K     |████████████████████████████████| 1.8MB 41.9MB/s \n",
            "\u001b[?25hCollecting python-constraint>=1.4\n",
            "  Downloading https://files.pythonhosted.org/packages/37/8b/5f1bc2734ca611943e1d6733ee244238679f6410a10cd45ede55a61a8402/python-constraint-1.4.0.tar.bz2\n",
            "Collecting ply>=3.10\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/a3/58/35da89ee790598a0700ea49b2a66594140f44dec458c07e8e3d4979137fc/ply-3.11-py2.py3-none-any.whl (49kB)\n",
            "\u001b[K     |████████████████████████████████| 51kB 5.7MB/s \n",
            "\u001b[?25hCollecting fastjsonschema>=2.10\n",
            "  Downloading https://files.pythonhosted.org/packages/3a/2b/5e93ebbdc92fe742bfc006f79336c2ddcb436747ef579bc05057c43ad876/fastjsonschema-2.14.4-py3-none-any.whl\n",
            "Requirement already satisfied: dill>=0.3 in /usr/local/lib/python3.6/dist-packages (from qiskit-terra==0.13.0->qiskit) (0.3.1.1)\n",
            "Collecting marshmallow-polyfield<6,>=5.7\n",
            "  Downloading https://files.pythonhosted.org/packages/0c/7e/ceb805d05cd03709b8de122b4ac1e736c4eb91d05281ad2a2bcb484accef/marshmallow-polyfield-5.9.tar.gz\n",
            "Collecting marshmallow<4,>=3\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/d8/0b/bb43d7610e71d87e8537025841c248471dbf938c676d32b8f94c82148c04/marshmallow-3.5.1-py2.py3-none-any.whl (45kB)\n",
            "\u001b[K     |████████████████████████████████| 51kB 6.0MB/s \n",
            "\u001b[?25hRequirement already satisfied: numpy>=1.13 in /usr/local/lib/python3.6/dist-packages (from qiskit-terra==0.13.0->qiskit) (1.18.2)\n",
            "Requirement already satisfied: psutil>=5 in /usr/local/lib/python3.6/dist-packages (from qiskit-terra==0.13.0->qiskit) (5.4.8)\n",
            "Requirement already satisfied: networkx>=2.2; python_version > \"3.5\" in /usr/local/lib/python3.6/dist-packages (from qiskit-terra==0.13.0->qiskit) (2.4)\n",
            "Requirement already satisfied: jsonschema>=2.6 in /usr/local/lib/python3.6/dist-packages (from qiskit-terra==0.13.0->qiskit) (2.6.0)\n",
            "Collecting retworkx>=0.3.2\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/71/25/012f14ce065d0b8a679781407491c69e716b2d53be406443a493bf6b7483/retworkx-0.3.3-cp36-cp36m-manylinux2010_x86_64.whl (783kB)\n",
            "\u001b[K     |████████████████████████████████| 788kB 49.2MB/s \n",
            "\u001b[?25hRequirement already satisfied: scipy>=1.0 in /usr/local/lib/python3.6/dist-packages (from qiskit-terra==0.13.0->qiskit) (1.4.1)\n",
            "Collecting sympy>=1.3\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/ce/5b/acc12e3c0d0be685601fc2b2d20ed18dc0bf461380e763afc9d0a548deb0/sympy-1.5.1-py2.py3-none-any.whl (5.6MB)\n",
            "\u001b[K     |████████████████████████████████| 5.6MB 36.6MB/s \n",
            "\u001b[?25hCollecting pybind11>=2.4\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/89/e3/d576f6f02bc75bacbc3d42494e8f1d063c95617d86648dba243c2cb3963e/pybind11-2.5.0-py2.py3-none-any.whl (296kB)\n",
            "\u001b[K     |████████████████████████████████| 296kB 46.0MB/s \n",
            "\u001b[?25hRequirement already satisfied: cython>=0.27.1 in /usr/local/lib/python3.6/dist-packages (from qiskit-aer==0.5.0->qiskit) (0.29.16)\n",
            "Requirement already satisfied: requests>=2.19 in /usr/local/lib/python3.6/dist-packages (from qiskit-ibmq-provider==0.6.0->qiskit) (2.21.0)\n",
            "Collecting nest-asyncio!=1.1.0,>=1.0.0\n",
            "  Downloading https://files.pythonhosted.org/packages/fb/98/f4add7297a8d586fe7ac756707673d03d97b9ed7c171291bb43889dbfbc5/nest_asyncio-1.3.2-py3-none-any.whl\n",
            "Collecting requests-ntlm>=1.1.0\n",
            "  Downloading https://files.pythonhosted.org/packages/03/4b/8b9a1afde8072c4d5710d9fa91433d504325821b038e00237dc8d6d833dc/requests_ntlm-1.1.0-py2.py3-none-any.whl\n",
            "Collecting websockets<8,>=7\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/43/71/8bfa882b9c502c36e5c9ef6732969533670d2b039cbf95a82ced8f762b80/websockets-7.0-cp36-cp36m-manylinux1_x86_64.whl (63kB)\n",
            "\u001b[K     |████████████████████████████████| 71kB 8.0MB/s \n",
            "\u001b[?25hCollecting arrow>=0.15.5\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/92/fa/f84896dede5decf284e6922134bf03fd26c90870bbf8015f4e8ee2a07bcc/arrow-0.15.5-py2.py3-none-any.whl (46kB)\n",
            "\u001b[K     |████████████████████████████████| 51kB 5.7MB/s \n",
            "\u001b[?25hRequirement already satisfied: setuptools>=40.1.0 in /usr/local/lib/python3.6/dist-packages (from qiskit-ignis==0.3.0->qiskit) (46.1.3)\n",
            "Collecting quandl\n",
            "  Downloading https://files.pythonhosted.org/packages/07/ab/8cd479fba8a9b197a43a0d55dd534b066fb8e5a0a04b5c0384cbc5d663aa/Quandl-3.5.0-py2.py3-none-any.whl\n",
            "Collecting dlx\n",
            "  Downloading https://files.pythonhosted.org/packages/54/c0/b8fb5bb727e983b6f5251433ef941b48f38c65bb0bd6ec509e9185bcd406/dlx-1.0.4.tar.gz\n",
            "Requirement already satisfied: fastdtw in /usr/local/lib/python3.6/dist-packages (from qiskit-aqua==0.6.5->qiskit) (0.3.4)\n",
            "Collecting pyscf; sys_platform == \"linux\" or (python_version < \"3.8\" and sys_platform != \"win32\")\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/7a/ea/8ebe88368935dcc9a1a309764846e0bf5d04352d44067741aab3626ceb7f/pyscf-1.7.1-cp36-cp36m-manylinux1_x86_64.whl (24.3MB)\n",
            "\u001b[K     |████████████████████████████████| 24.3MB 1.5MB/s \n",
            "\u001b[?25hRequirement already satisfied: h5py in /usr/local/lib/python3.6/dist-packages (from qiskit-aqua==0.6.5->qiskit) (2.10.0)\n",
            "Collecting docplex\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/03/a8/5dc675dbe179a2bd4d1d40522f009b4517ad32890d55ae49449709128d0a/docplex-2.13.184.tar.gz (571kB)\n",
            "\u001b[K     |████████████████████████████████| 573kB 41.6MB/s \n",
            "\u001b[?25hRequirement already satisfied: scikit-learn>=0.20.0 in /usr/local/lib/python3.6/dist-packages (from qiskit-aqua==0.6.5->qiskit) (0.22.2.post1)\n",
            "Requirement already satisfied: decorator>=4.3.0 in /usr/local/lib/python3.6/dist-packages (from networkx>=2.2; python_version > \"3.5\"->qiskit-terra==0.13.0->qiskit) (4.4.2)\n",
            "Requirement already satisfied: mpmath>=0.19 in /usr/local/lib/python3.6/dist-packages (from sympy>=1.3->qiskit-terra==0.13.0->qiskit) (1.1.0)\n",
            "Requirement already satisfied: urllib3<1.25,>=1.21.1 in /usr/local/lib/python3.6/dist-packages (from requests>=2.19->qiskit-ibmq-provider==0.6.0->qiskit) (1.24.3)\n",
            "Requirement already satisfied: idna<2.9,>=2.5 in /usr/local/lib/python3.6/dist-packages (from requests>=2.19->qiskit-ibmq-provider==0.6.0->qiskit) (2.8)\n",
            "Requirement already satisfied: certifi>=2017.4.17 in /usr/local/lib/python3.6/dist-packages (from requests>=2.19->qiskit-ibmq-provider==0.6.0->qiskit) (2020.4.5.1)\n",
            "Requirement already satisfied: chardet<3.1.0,>=3.0.2 in /usr/local/lib/python3.6/dist-packages (from requests>=2.19->qiskit-ibmq-provider==0.6.0->qiskit) (3.0.4)\n",
            "Collecting ntlm-auth>=1.0.2\n",
            "  Downloading https://files.pythonhosted.org/packages/50/09/5e397eb18685b14fd8b209e26cdb4fa6451c82c1bcc651fef05fa73e7b27/ntlm_auth-1.4.0-py2.py3-none-any.whl\n",
            "Collecting cryptography>=1.3\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/8f/2d/29d2638b8df016526182594166c220913dafba3da0019b0776ff1bbc8ede/cryptography-2.9-cp35-abi3-manylinux2010_x86_64.whl (2.7MB)\n",
            "\u001b[K     |████████████████████████████████| 2.7MB 44.0MB/s \n",
            "\u001b[?25hRequirement already satisfied: python-dateutil in /usr/local/lib/python3.6/dist-packages (from arrow>=0.15.5->qiskit-ibmq-provider==0.6.0->qiskit) (2.8.1)\n",
            "Collecting inflection>=0.3.1\n",
            "  Downloading https://files.pythonhosted.org/packages/52/c1/36be286d85dbd76527fb613527222a795d7c071da195fa916e7bf3cb03cb/inflection-0.4.0-py2.py3-none-any.whl\n",
            "Requirement already satisfied: more-itertools in /usr/local/lib/python3.6/dist-packages (from quandl->qiskit-aqua==0.6.5->qiskit) (8.2.0)\n",
            "Requirement already satisfied: six in /usr/local/lib/python3.6/dist-packages (from quandl->qiskit-aqua==0.6.5->qiskit) (1.12.0)\n",
            "Requirement already satisfied: pandas>=0.14 in /usr/local/lib/python3.6/dist-packages (from quandl->qiskit-aqua==0.6.5->qiskit) (1.0.3)\n",
            "Requirement already satisfied: joblib>=0.11 in /usr/local/lib/python3.6/dist-packages (from scikit-learn>=0.20.0->qiskit-aqua==0.6.5->qiskit) (0.14.1)\n",
            "Requirement already satisfied: cffi!=1.11.3,>=1.8 in /usr/local/lib/python3.6/dist-packages (from cryptography>=1.3->requests-ntlm>=1.1.0->qiskit-ibmq-provider==0.6.0->qiskit) (1.14.0)\n",
            "Requirement already satisfied: pytz>=2017.2 in /usr/local/lib/python3.6/dist-packages (from pandas>=0.14->quandl->qiskit-aqua==0.6.5->qiskit) (2018.9)\n",
            "Requirement already satisfied: pycparser in /usr/local/lib/python3.6/dist-packages (from cffi!=1.11.3,>=1.8->cryptography>=1.3->requests-ntlm>=1.1.0->qiskit-ibmq-provider==0.6.0->qiskit) (2.20)\n",
            "Building wheels for collected packages: qiskit, python-constraint, marshmallow-polyfield, dlx, docplex\n",
            "  Building wheel for qiskit (setup.py) ... \u001b[?25l\u001b[?25hdone\n",
            "  Created wheel for qiskit: filename=qiskit-0.18.0-cp36-none-any.whl size=2896 sha256=87460a9da377ccd0b12d4a84320c6c2bfdcd705cc20cff1a2eef662526129dfc\n",
            "  Stored in directory: /root/.cache/pip/wheels/8a/57/67/edc41f78f233b50d3c8f84ec46bac1ca550db46541c4743cdd\n",
            "  Building wheel for python-constraint (setup.py) ... \u001b[?25l\u001b[?25hdone\n",
            "  Created wheel for python-constraint: filename=python_constraint-1.4.0-py2.py3-none-any.whl size=24080 sha256=50356114b4895f43d12d36561972f77a82ddc375eabdb985f7739aec263b49d9\n",
            "  Stored in directory: /root/.cache/pip/wheels/34/31/15/7b070b25d0a549d20ce2e9fe6d727471c2c61ef904720fd40c\n",
            "  Building wheel for marshmallow-polyfield (setup.py) ... \u001b[?25l\u001b[?25hdone\n",
            "  Created wheel for marshmallow-polyfield: filename=marshmallow_polyfield-5.9-cp36-none-any.whl size=8537 sha256=a191e9b13e5a4babb96d0de8289558027dfe72068758c2b7ec605a9604473c5e\n",
            "  Stored in directory: /root/.cache/pip/wheels/69/27/3e/7472f75eab2db111aa387715fe009af15899459517fc1a1906\n",
            "  Building wheel for dlx (setup.py) ... \u001b[?25l\u001b[?25hdone\n",
            "  Created wheel for dlx: filename=dlx-1.0.4-cp36-none-any.whl size=5712 sha256=2d22c72763bc72be95183af5cda1c0e7afb22a42b9ac38669d0c5c6fcae12cf2\n",
            "  Stored in directory: /root/.cache/pip/wheels/bb/ba/15/fdd0deb104df3254912998150ba9245668db06b00af5912d1a\n",
            "  Building wheel for docplex (setup.py) ... \u001b[?25l\u001b[?25hdone\n",
            "  Created wheel for docplex: filename=docplex-2.13.184-cp36-none-any.whl size=633100 sha256=2e038c85fd8ca6720a81d23046063f071b8b99a67e89dd6d5497f5b607de71f7\n",
            "  Stored in directory: /root/.cache/pip/wheels/35/67/46/e9d3c1cb652addc314816a29396c1c427c2735e8f6c656aab3\n",
            "Successfully built qiskit python-constraint marshmallow-polyfield dlx docplex\n",
            "Installing collected packages: python-constraint, ply, fastjsonschema, marshmallow, marshmallow-polyfield, retworkx, sympy, qiskit-terra, pybind11, qiskit-aer, nest-asyncio, ntlm-auth, cryptography, requests-ntlm, websockets, arrow, qiskit-ibmq-provider, qiskit-ignis, inflection, quandl, dlx, pyscf, docplex, qiskit-aqua, qiskit\n",
            "  Found existing installation: sympy 1.1.1\n",
            "    Uninstalling sympy-1.1.1:\n",
            "      Successfully uninstalled sympy-1.1.1\n",
            "Successfully installed arrow-0.15.5 cryptography-2.9 dlx-1.0.4 docplex-2.13.184 fastjsonschema-2.14.4 inflection-0.4.0 marshmallow-3.5.1 marshmallow-polyfield-5.9 nest-asyncio-1.3.2 ntlm-auth-1.4.0 ply-3.11 pybind11-2.5.0 pyscf-1.7.1 python-constraint-1.4.0 qiskit-0.18.0 qiskit-aer-0.5.0 qiskit-aqua-0.6.5 qiskit-ibmq-provider-0.6.0 qiskit-ignis-0.3.0 qiskit-terra-0.13.0 quandl-3.5.0 requests-ntlm-1.1.0 retworkx-0.3.3 sympy-1.5.1 websockets-7.0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qhTH5zinDQxh",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import numpy as np\n",
        "from qiskit import *\n",
        "from math import sqrt,log,gcd\n",
        "import random\n",
        "from random import randint\n",
        "import rsa"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0muwWXfSDQxo",
        "colab_type": "text"
      },
      "source": [
        "# Lets make our RSA Algorithm\n",
        "\n",
        "![flow-chart](https://i.ytimg.com/vi/-jSX9fNJiN8/maxresdefault.jpg)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UqpvahZnDQxq",
        "colab_type": "text"
      },
      "source": [
        "#### Calculating Modular  Inverse"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zZ4FIDGgDQxr",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def mod_inverse(a, m):\n",
        "    for x in range(1, m):\n",
        "        if (a * x) % m == 1:\n",
        "            return x\n",
        "    return -1"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2sf25-WVDQxx",
        "colab_type": "text"
      },
      "source": [
        "#### Checking for primality"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Fqx1BFHZDQxy",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def isprime(n):\n",
        "    if n < 2:\n",
        "        return False\n",
        "    elif n == 2:\n",
        "        return True\n",
        "    else:\n",
        "        for i in range(1, int(sqrt(n)) + 1):\n",
        "            if n % i == 0:\n",
        "                return False\n",
        "    return True"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7-KQY7NIDQx1",
        "colab_type": "text"
      },
      "source": [
        "## Generating Key Value Pairs"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cJfaefmDDQx2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def generate_keypair(keysize):\n",
        "    p = randint(1, 1000)\n",
        "    q = randint(1, 1000)\n",
        "    nMin = 1 << (keysize - 1)\n",
        "    nMax = (1 << keysize) - 1\n",
        "    primes = [2]\n",
        "    start = 1 << (keysize // 2 - 1)\n",
        "    stop = 1 << (keysize // 2 + 1)\n",
        "    if start >= stop:\n",
        "        return []\n",
        "    for i in range(3, stop + 1, 2):\n",
        "        for p in primes:\n",
        "            if i % p == 0:\n",
        "                break\n",
        "        else:\n",
        "            primes.append(i)\n",
        "    while (primes and primes[0] < start):\n",
        "        del primes[0]\n",
        "    # Select two random prime numbers p and q\n",
        "    while primes:\n",
        "        p = random.choice(primes)\n",
        "        primes.remove(p)\n",
        "        q_values = [q for q in primes if nMin <= p * q <= nMax]\n",
        "        if q_values:\n",
        "            q = random.choice(q_values)\n",
        "            break\n",
        "    # Calculate n\n",
        "    n = p * q\n",
        "    # Calculate phi\n",
        "    phi = (p - 1) * (q - 1)\n",
        "    # Select e\n",
        "    e = random.randrange(1, phi)\n",
        "    g = gcd(e, phi)\n",
        "    # Calculate d\n",
        "    while True:\n",
        "        e = random.randrange(1, phi)\n",
        "        g = gcd(e, phi)\n",
        "        d = mod_inverse(e, phi)\n",
        "        if g == 1 and e != d:\n",
        "            break\n",
        "\n",
        "    return ((e, n), (d, n))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "g4frYTkJDQx6",
        "colab_type": "text"
      },
      "source": [
        "## Encryption Step"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "z2tcwc9EDQx7",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def encrypt(plaintext, package):\n",
        "    e, n = package\n",
        "    ciphertext = [pow(ord(c), e, n) for c in plaintext]\n",
        "    return ''.join(map(lambda x: str(x), ciphertext)), ciphertext"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ipCW0Sg6DQx-",
        "colab_type": "text"
      },
      "source": [
        "## Decryption Step"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BwUiLjF_DQx-",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def decrypt(ciphertext, package):\n",
        "    d, n = package\n",
        "    plaintext = [chr(pow(c, d, n)) for c in ciphertext]\n",
        "    return (''.join(plaintext))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VHS2O4DgDQyC",
        "colab_type": "text"
      },
      "source": [
        "# Now lets test with a sample message"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lO2ji54kDQyC",
        "colab_type": "text"
      },
      "source": [
        "#### Generate Keys"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7E1abRK8DQyD",
        "colab_type": "code",
        "colab": {},
        "outputId": "13fc2fb4-f874-4346-e949-f28ecf7affde"
      },
      "source": [
        "import RSA_module\n",
        "\n",
        "bit_length = int(input(\"Enter bit length: \"))\n",
        "\n",
        "public_k, private_k = generate_keypair(2**bit_length)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Enter bit length: 4\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_wP53v_cDQyG",
        "colab_type": "text"
      },
      "source": [
        "#### Encryption"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aL2Qsf8_DQyG",
        "colab_type": "code",
        "colab": {},
        "outputId": "668a338a-7858-43f9-ce75-7e60c3870b7b"
      },
      "source": [
        "plain_txt = input(\"Enter a message: \")\n",
        "cipher_txt, cipher_obj = encrypt(plain_txt, public_k)\n",
        "\n",
        "print(\"Encrypted message: {}\".format(cipher_txt))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Enter a message: Smaranjit Ghose\n",
            "Encrypted message: 52672272517641537481764151472391857141541735045186494582311425740119401\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3cVvdxFVDQyJ",
        "colab_type": "text"
      },
      "source": [
        "#### Decryption"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EAtM7i5EDQyK",
        "colab_type": "code",
        "colab": {},
        "outputId": "89d591d9-4400-439f-9352-9bcfd89c3977"
      },
      "source": [
        "print(\"Decrypted message: {}\".format(decrypt(cipher_obj, private_k)))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Decrypted message: Smaranjit Ghose\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aoEW_z2KDQyO",
        "colab_type": "text"
      },
      "source": [
        "## Now lets frame Shor's Algorithm"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fh77fgefDQyP",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "qasm_sim = qiskit.Aer.get_backend('qasm_simulator')\n",
        "def period(a,N):\n",
        "    \n",
        "    available_qubits = 16 \n",
        "    r=-1   \n",
        "    \n",
        "    if N >= 2**available_qubits:\n",
        "        print(str(N)+' is too big for IBMQX')\n",
        "    \n",
        "    qr = QuantumRegister(available_qubits)   \n",
        "    cr = ClassicalRegister(available_qubits)\n",
        "    qc = QuantumCircuit(qr,cr)\n",
        "    x0 = randint(1, N-1) \n",
        "    x_binary = np.zeros(available_qubits, dtype=bool)\n",
        "    \n",
        "    for i in range(1, available_qubits + 1):\n",
        "        bit_state = (N%(2**i)!=0)\n",
        "        if bit_state:\n",
        "            N -= 2**(i-1)\n",
        "        x_binary[available_qubits-i] = bit_state    \n",
        "    \n",
        "    for i in range(0,available_qubits):\n",
        "        if x_binary[available_qubits-i-1]:\n",
        "            qc.x(qr[i])\n",
        "    x = x0\n",
        "    \n",
        "    while np.logical_or(x != x0, r <= 0):\n",
        "        r+=1\n",
        "        qc.measure(qr, cr) \n",
        "        for i in range(0,3): \n",
        "            qc.x(qr[i])\n",
        "        qc.cx(qr[2],qr[1])\n",
        "        qc.cx(qr[1],qr[2])\n",
        "        qc.cx(qr[2],qr[1])\n",
        "        qc.cx(qr[1],qr[0])\n",
        "        qc.cx(qr[0],qr[1])\n",
        "        qc.cx(qr[1],qr[0])\n",
        "        qc.cx(qr[3],qr[0])\n",
        "        qc.cx(qr[0],qr[1])\n",
        "        qc.cx(qr[1],qr[0])\n",
        "        \n",
        "        result = execute(qc,backend = qasm_sim, shots=1024).result()\n",
        "        counts = result.get_counts()\n",
        "        \n",
        "        results = [[],[]]\n",
        "        for key,value in counts.items(): \n",
        "            results[0].append(key)\n",
        "            results[1].append(int(value))\n",
        "        s = results[0][np.argmax(np.array(results[1]))]\n",
        "    return r"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YuFDO045DQyS",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def shors_breaker(N):\n",
        "    N = int(N)\n",
        "    while True:\n",
        "        a=randint(0,N-1)\n",
        "        g=gcd(a,N)\n",
        "        if g!=1 or N==1:\n",
        "            return g,N//g\n",
        "        else:\n",
        "            r=period(a,N) \n",
        "            if r % 2 != 0:\n",
        "                continue\n",
        "            elif pow(a,r//2,N)==-1:\n",
        "                continue\n",
        "            else:\n",
        "                p=gcd(pow(a,r//2)+1,N)\n",
        "                q=gcd(pow(a,r//2)-1,N)\n",
        "                if p==N or q==N:\n",
        "                    continue\n",
        "                return p,q"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "oLfUdM17DQyV",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def modular_inverse(a,m): \n",
        "    a = a % m; \n",
        "    for x in range(1, m) : \n",
        "        if ((a * x) % m == 1) : \n",
        "            return x \n",
        "    return 1"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "IA-Qn2oBDQyY",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "N_shor = public_k[1]\n",
        "assert N_shor>0,\"Input must be positive\"\n",
        "p,q = shors_breaker(N_shor)\n",
        "phi = (p-1) * (q-1)  \n",
        "d_shor = modular_inverse(public_k[0], phi) "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gy56p-L-DQyb",
        "colab_type": "text"
      },
      "source": [
        "# Lets Crack our Cipher Text using Shor's Algorithm"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VOcCTXA5DQyc",
        "colab_type": "code",
        "colab": {},
        "outputId": "c2a36929-9726-49fc-f596-16d0ff2f1be5"
      },
      "source": [
        "print('Message Cracked using Shors Algorithm: {} '.format(decrypt(cipher_obj, (d_shor,N_shor))))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Message Cracked using Shors Algorithm: Smaranjit Ghose \n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}