{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "fe0993a1",
   "metadata": {},
   "source": [
    "[Home](Home.ipynb) <br/>\n",
    "[Crypto](Crypto.ipynb)\n",
    "\n",
    "# RSA Algorithm\n",
    "\n",
    "RSA gets focus in this curriculum because of the number and group theory concepts it ties together, not only because it's still heavily used as a part of the Web's security layer (SSL/TLS).  \n",
    "\n",
    "A similar curriculum might swap out RSA for ECC (Elliptic Curve Cryptography), which plays the same role in web browsers, and adjust other curriculum segments accordingly.\n",
    "\n",
    "Even if RSA gradually gives way to ECC, understanding how and why it works remains a valuable source of insights into the inner workings of important algorithms.\n",
    "\n",
    "### RSA History\n",
    "\n",
    "The essentials of RSA were first discovered by cryptographers working for GHCQ, a UK institution.  \n",
    "\n",
    "The algorithm was kept secret at that point, for fear of aiding some generic enemy.  Unleashing it upon the world could have unforeseen consequences.  World War 2, in which cryptography had played a major role, was still close behind in the rear view mirror.\n",
    "\n",
    "The acronym RSA is made of the initial letters of the surnames of Ron Rivest (cryptographer and professor at MIT), Adi Shamir (Israeli Cryptographer), and Leonard Adleman (American computer scientist), who first publicly described the algorithm in 1978.\n",
    "\n",
    "The community which developed and promoted the RSA algorithm was not beholden to GHCQ and resisted the NSA's efforts to keep a lid on it.  \n",
    "\n",
    "Phil Zimmerman helped popularize and spread the whole idea of public key crypto, if not RSA in particular.\n",
    "\n",
    "The web was emerging and businesses needed to offer a secure way to encrypt transactions.  The commercial sector needed this technology.\n",
    "\n",
    "Pubic key cryptography had come of age."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea93f44c",
   "metadata": {},
   "source": [
    "RSA depends on components introduced elsewhere in this text, most notably:\n",
    "\n",
    "* [the concept of prime versus composite](Crypto.ipynb)\n",
    "* [the concepts of totatives and totients](Crypto.ipynb)\n",
    "* [Euler's Theorem involving the totient](Euler.ipynb)\n",
    "* [Euclid's Extended Algorithm (EEA)](EEA.ipynb)\n",
    "* [Review of RSA in context](https://nbviewer.jupyter.org/github/4dsolutions/School_of_Tomorrow/blob/master/NumberTheory.ipynb) (School of Tomorrow)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a030625e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.display import YouTubeVideo"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b879c66",
   "metadata": {},
   "source": [
    "Curate your own Youtubes?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "9a831c36",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Generating:  p,q\n",
      "Generating:  u\n",
      "Generating:  d\n",
      "<_RSAobj @0x7f92f1e09280 n(1024),e,d,p,q,u,private>\n"
     ]
    }
   ],
   "source": [
    "# %load ./primes/rsacrypto_test.py\n",
    "#!/usr/bin/env python3\n",
    "\"\"\"\n",
    "Created on Sat Dec  2 21:07:56 2017\n",
    "\n",
    "@author: Kirby Urner\n",
    "\n",
    "conda install pycrypto\n",
    "pip3 install pycrypto\n",
    "\n",
    "https://www.dlitz.net/software/pycrypto/\n",
    "\n",
    "Here's a bug that we hit:\n",
    "https://github.com/pycrypto/pycrypto/issues/308\n",
    "\n",
    "Note that OpenSSL is the more frequently used not-Python\n",
    "util, run from the OS command line.\n",
    "\"\"\"\n",
    "\n",
    "from primes import invmod\n",
    "\n",
    "import Crypto.PublicKey.RSA as rsa\n",
    "\n",
    "def generating(s):\n",
    "    print(\"Generating: \", s, end=\"\")\n",
    "    \n",
    "rsaobj = rsa.generate(1024, progress_func=generating, e=17)\n",
    "\n",
    "print(rsaobj)\n",
    "\n",
    "p = rsaobj.p  # prime1\n",
    "q = rsaobj.q  # prime2\n",
    "n = rsaobj.n  # public key (p * q)\n",
    "e = rsaobj.e  # public encrypt exponent\n",
    "d = rsaobj.d  # secret decrypt key\n",
    "\n",
    "def test_n():\n",
    "    return p*q == n\n",
    "\n",
    "def test_inverse():\n",
    "    return d == invmod(e, (p-1)*(q-1))\n",
    "    \n",
    "def test_euler():\n",
    "    totient_of_n = (p-1)*(q-1)\n",
    "    return (e*d) % totient_of_n == 1\n",
    "\n",
    "def test_decrypt():\n",
    "    plaintext = b\"able was i ere i saw elba\"  # famous palindrome\n",
    "    ciphertext = rsaobj.encrypt(plaintext, b\"K\")\n",
    "    return rsaobj.decrypt(ciphertext[0]) == plaintext"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "3fdf3a4e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_inverse()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "cab826b6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[0;31mSignature:\u001b[0m  \u001b[0mrsaobj\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mencrypt\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mplaintext\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mK\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
       "\u001b[0;31mSource:\u001b[0m   \n",
       "    \u001b[0;32mdef\u001b[0m \u001b[0mencrypt\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mplaintext\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mK\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;34m\"\"\"Encrypt a piece of data with RSA.\u001b[0m\n",
       "\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m        :Parameter plaintext: The piece of data to encrypt with RSA. It may not\u001b[0m\n",
       "\u001b[0;34m         be numerically larger than the RSA module (**n**).\u001b[0m\n",
       "\u001b[0;34m        :Type plaintext: byte string or long\u001b[0m\n",
       "\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m        :Parameter K: A random parameter (*for compatibility only. This\u001b[0m\n",
       "\u001b[0;34m         value will be ignored*)\u001b[0m\n",
       "\u001b[0;34m        :Type K: byte string or long\u001b[0m\n",
       "\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m        :attention: this function performs the plain, primitive RSA encryption\u001b[0m\n",
       "\u001b[0;34m         (*textbook*). In real applications, you always need to use proper\u001b[0m\n",
       "\u001b[0;34m         cryptographic padding, and you should not directly encrypt data with\u001b[0m\n",
       "\u001b[0;34m         this method. Failure to do so may lead to security vulnerabilities.\u001b[0m\n",
       "\u001b[0;34m         It is recommended to use modules\u001b[0m\n",
       "\u001b[0;34m         `Crypto.Cipher.PKCS1_OAEP` or `Crypto.Cipher.PKCS1_v1_5` instead.\u001b[0m\n",
       "\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m        :Return: A tuple with two items. The first item is the ciphertext\u001b[0m\n",
       "\u001b[0;34m         of the same type as the plaintext (string or long). The second item\u001b[0m\n",
       "\u001b[0;34m         is always None.\u001b[0m\n",
       "\u001b[0;34m        \"\"\"\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;32mreturn\u001b[0m \u001b[0mpubkey\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpubkey\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mencrypt\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mplaintext\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mK\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
       "\u001b[0;31mFile:\u001b[0m      ~/opt/anaconda3/lib/python3.9/site-packages/Crypto/PublicKey/RSA.py\n",
       "\u001b[0;31mType:\u001b[0m      method\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "?? rsaobj.encrypt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "4aac431d",
   "metadata": {},
   "outputs": [],
   "source": [
    "c = rsaobj.encrypt(b\"attack at dawn\", b\"K\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "f95e7348",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(b'+\\xe2?A\\x98\\xb7O\\x12\\xa7\\xb7\\x05\\xa9\\xff\\xfc\\xd9\\xde+\\x03\\xf8<\\xeb\\x944S\\x10\\x133\\xcas\\xa1#2\\xa9J\\xa4C\\xd8\\x1cX\\xa6\\xef\\xcd9\\xe7\\xe3O J\\x87\\x87\\x8cd@\\xebo\\x84\\x17m\\xf4F}B\\xaf\\x8a\\x10n5\\x7f\\xa0\\x8cc\\xa1\\x14l\\xd1u`g\\xe7e@\\xfc^\\xfb\\x02qb\\xbc\\x07\\rW\\xd1@\\x9a\\xea\\rz-\\xe5\\xa63\\xac\\x14\\x81B\\xd2sQe\\x962Z\\x8cM\\xd1\\xcb\\xba\\xe9\\xd5\\xe9X\\xf0\\xc4de\\x9e\\xde\\xff',)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "084d1806",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'attack at dawn'"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rsaobj.decrypt(c[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "a982a6dd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "119353861243195446712675417770765824146975929069972250977091366093077385007699140626386330849234727126824758974147300218181130989174493410358646750159312997463360803438555963304411631399770295820887714785985874918809627514592173675448803051682476954425774027952044754491664338823260108968934257096925158099009"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p * q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "b70ba6f5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pow(5, 3, 20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "9b33b751-65e7-450e-a50b-6c6f84547138",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "125"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "5**3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "92dd67b1-3132-40b3-8e38-ee960fd628d0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "125//20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "5ee7567d-73e6-42ee-9a9d-e31d45285554",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "119"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "125 - 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "1234cb16-c672-4092-96c0-f4b58174de46",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "5 * 5 * 5 % 20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "4263df89-7864-467c-a11f-39e5df859786",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12354891489645"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pow(88398934597, 17, 82038745020938)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "82cdc899-f1c0-427d-8d8c-327cca35afea",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}