AttackingRSA.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cracking RSA"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using this notebook:\n",
    "- Code blocks have dark backgrounds.\n",
    "- You can edit code blocks by clicking inside the block.\n",
    "- You can execute a code block by clicking the \"run\" button (see above), or by pressing Shift+Enter while editing the block.\n",
    "- The order in which code blocks are executed matters.  Normally we run from top to bottom.\n",
    "- The order in which code blocks have been run follows nubmers to the left. For example, the code block with `In [1]` was the first one to be run. \n",
    "\n",
    "Some tips:\n",
    "- To start over and execute all blocks, select Kernel -> Restart & Run All.\n",
    "\n",
    "SAVING YOUR WORK:\n",
    "- To save your work: click on the cloud icon with the downward pointing arrow.\n",
    "- To restore your work: click on the cloud icon with the upward pointing arrow.\n",
    "- If the system says \"connection lost\": save your work, open the URL again, and restore your work."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sympy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the notebook, we are going to try cracking RSA!  We are given a public key $e$ and $n$, and an encrypted message:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "e = 17\n",
    "n = 8633\n",
    "encrypted_message = 5711"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Can we find the private key $d$ and decrypt the message?  Recall that the private key $d$ was based on knowing the totient of $n$.  For very large $n$, computing the totient takes a long time; and this is where RSA derives it's strength.\n",
    "\n",
    "Previously we used the `sympy.totient` function to compute $phi$, but there is a shortcut.  Since $n$ is the product of the primes $p$ and $q$, then it's totient satisfies $phi(n) = (p-1)*(q-1)$.\n",
    "\n",
    "Try different primes $p$ and $q$ to see if you can crack the private key!\n",
    "\n",
    "Alternatively, can you compute $phi$ directly?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "check if n is divisible by p: False\n"
     ]
    }
   ],
   "source": [
    "p = 11\n",
    "print(f'check if n is divisible by p: {n%p==0}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once you find a $p$ that works, we can calculate $q$, $phi$, and $d$: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "q = n // p\n",
    "phi = (p-1) * (q-1)\n",
    "print(f'phi: {phi}')\n",
    "print(f'p:   {p}')\n",
    "print(f'q:   {q}')\n",
    "d = sympy.mod_inverse(e, phi)\n",
    "print(f'd: {d}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "decrypted_message = pow(encrypted_message, d, n)\n",
    "print(f'decrypted message: {decrypted_message}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now change the decrypted integer message back to a text message: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = decrypted_message\n",
    "ords = []\n",
    "while a:\n",
    "    ords.append(a % 100)\n",
    "    a //= 100\n",
    "recovered_message = ''.join(reversed([ chr(i) for i in ords ]))\n",
    "print(f'recovered message: {recovered_message}')"
   ]
  }
 ],
 "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.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}