4. Asymmetric Encryption.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Asymmetric Encryption\n",
    "\n",
    "Reminder: In asymmetric encryption schemes, the parties use ***different*** keys, that are mathematically ***related*** to each other."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## *<font color=\" #6495ED\">Exercise</font>*\n",
    "\n",
    " - Why asymmetric encryption is useful?\n",
    " - Give a few examples where it can be used?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### RSA\n",
    "\n",
    "RSA is an asymmetric encryption algorithm by Ron Rivest, Adi Shamir, and Leonard Adleman. It was published in 1977. Its security is based on the hardness of factorization problem. However, now it has its own problem, called the RSA problem. RSA is slow, and is not used for encrypting large data, but it's mostly used to encrypt the symmetric key that is used for encryption.\n",
    "\n",
    "\n",
    " * p, q, two big prime numbers (private, chosen)\n",
    " * n = pq, φ(n) = (p-1)(q-1)   (public, calculated)\n",
    " * e, with gcd(φ(n), e) = 1,  1 < e < φ(n)\t(public, chosen)\n",
    " * d = e - 1 mod φ(n)\t(private, calculated)\n",
    " * $E(M) = M^e \\mod n$\n",
    " * $D(M) = M^d \\mod n$\n",
    " * $D(E(M)) = M^{ed} \\mod n = M$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## *<font color=\" #6495ED\">Exercise</font>*\n",
    "\n",
    " - How to test if a number is prime?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## RSA EXAMPLE\n",
    "\n",
    " - p = 5; q = 11 => n = 55\n",
    " - φ(n) = 40\n",
    " - e = 3 => d = 27\n",
    "  - Because ed = 1 mod φ(n)\n",
    " - Public key: (e, n)\n",
    " - Private key: (d, n)\n",
    " - Encryption\n",
    "  - M = 2\n",
    " - Encryption(M) = $ M^e\\mod n$  = $2^3\\mod n$ = 8\n",
    " - Decryption(8) = $ M^d\\mod n$  = $8^{27} \\mod n$ = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "2 ** 3 % 55"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "8 ** 27 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "8 ** 27 % 55"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## *<font color=\" #6495ED\">Exercise</font>*\n",
    "\n",
    " - Why can't we just use asymmetric encryption?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### OpenSSL\n",
    "\n",
    "To generate keys, use the following instructions:\n",
    "\n",
    "```bash\n",
    " openssl genrsa -out private_key.pem 2048\n",
    " openssl pkcs8 -topk8 -inform PEM -outform DER -in private_key.pem -out private_key.der -nocrypt\n",
    " openssl rsa -in private_key.pem -pubout -outform DER -out public_key.der\n",
    " ```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%%bash\n",
    "openssl genrsa -out private_key.pem 2048\n",
    "openssl pkcs8 -topk8 -inform PEM -outform DER -in private_key.pem -out private_key.der -nocrypt\n",
    "openssl rsa -in private_key.pem -pubout -outform DER -out public_key.der"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# import key from a file. E.g., previously generated by OpenSSL\n",
    "from cryptography.hazmat.backends import default_backend\n",
    "from cryptography.hazmat.primitives import serialization\n",
    "\n",
    "with open(\"private_key.pem\", \"rb\") as key_file:\n",
    "     private_key = serialization.load_pem_private_key(\n",
    "            key_file.read(),\n",
    "            password=None,\n",
    "            backend=default_backend())\n",
    "public_key = private_key.public_key()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Generate a 2048 bit private key\n",
    "from cryptography.hazmat.backends import default_backend\n",
    "from cryptography.hazmat.primitives.asymmetric import rsa\n",
    "\n",
    "private_key = rsa.generate_private_key(\n",
    "    public_exponent=65537,\n",
    "    key_size=2048,\n",
    "    backend=default_backend())\n",
    "# to get the public key\n",
    "public_key = private_key.public_key()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "2 ** 16 +1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print(bin(2**16 + 1))\n",
    "print(bin(2**1 + 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## *<font color=\" #6495ED\">Exercise</font>*\n",
    "\n",
    " - What's wrong with textbook RSA?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## It's all about padding\n",
    "\n",
    "Textbook RSA is not IND-CPA secure, therefore we use Optimal Asymmetric Encryption Padding (OAEP). There are also other attacks against RSA with improper padding\n",
    "\n",
    "<img src=\"include/RSA_OAEP.png\">\n",
    "\n",
    "image souce: wikipedia"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from cryptography.hazmat.backends import default_backend\n",
    "from cryptography.hazmat.primitives import hashes\n",
    "from cryptography.hazmat.primitives.asymmetric import padding\n",
    "\n",
    "message = b\"The SECRET KEY\"\n",
    "ciphertext = public_key.encrypt(\n",
    "    message,\n",
    "    padding.OAEP(\n",
    "        mgf=padding.MGF1(algorithm=hashes.SHA1()),\n",
    "        algorithm=hashes.SHA1(),\n",
    "        label=None))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(ciphertext)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from cryptography.hazmat.backends import default_backend\n",
    "from cryptography.hazmat.primitives import hashes\n",
    "from cryptography.hazmat.primitives.asymmetric import padding\n",
    "\n",
    "plaintext = private_key.decrypt(\n",
    "    ciphertext,\n",
    "    padding.OAEP(\n",
    "        mgf=padding.MGF1(algorithm=hashes.SHA1()),\n",
    "        algorithm=hashes.SHA1(),\n",
    "        label=None))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(plaintext)"
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}