{ "cells": [ { "cell_type": "markdown", "id": "7e4ae260", "metadata": { "tags": [] }, "source": [ "# Public-Key Encryption (Optional)" ] }, { "cell_type": "markdown", "id": "d40e889b", "metadata": {}, "source": [ "**CS1302 Introduction to Computer Programming**\n", "___" ] }, { "cell_type": "markdown", "id": "5ee439d2", "metadata": {}, "source": [ "This notebook will introduce the idea of public-key (asymmetric key) cryptography called the [RSA algorithm](https://en.wikipedia.org/wiki/RSA_(cryptosystem))." ] }, { "cell_type": "markdown", "id": "aed6fc29", "metadata": { "tags": [] }, "source": [ "## Motivation" ] }, { "cell_type": "markdown", "id": "c276d99c", "metadata": {}, "source": [ "**What is public key encryption?**" ] }, { "cell_type": "markdown", "id": "69bf1e39", "metadata": {}, "source": [ "Suppose there is one receiver trying to receive private messsages from multiple senders." ] }, { "cell_type": "markdown", "id": "4df01f03", "metadata": {}, "source": [ "````{prf:definition} Asymmetric key cipher\n", "\n", "Every sender uses the same public key $k_e$ to encrypt a plaintext $x$ to a ciphertext $y$ as\n", "\n", "$$\n", "y = E(x, k_e).\n", "$$ (encrypt)\n", "\n", "The receiver with the private key $k_d$ decrypts the ciphertext back to the plaintext as\n", "\n", "$$\n", "x = D(y, k_d).\n", "$$ (decrypt)\n", "\n", "$k_e, k_d, E, D$ is chosen to ensure\n", "\n", "- Decryptability: The receiver can recover the plaintext.\n", "- Secrecy: Anyone with only the public key but not the private key cannot recover the plaintext.\n", "\n", "````" ] }, { "cell_type": "markdown", "id": "86f09f32", "metadata": {}, "source": [ "**Exercise** (Optional) What is the benefit of asymmetric key cipher over symmetric key cipher?" ] }, { "cell_type": "markdown", "id": "a9890417", "metadata": { "nbgrader": { "grade": false, "grade_id": "benefits", "locked": true, "points": 0, "schema_version": 3, "solution": false, "task": true }, "tags": [ "hide-input" ] }, "source": [ "- Easy to share keys: Encryption key can be shared to all senders publicly.\n", "- Easy to store keys: Only the receiver needs to know the private key." ] }, { "cell_type": "markdown", "id": "3c019090", "metadata": {}, "source": [ "**Is public key encryption possible?**" ] }, { "cell_type": "markdown", "id": "e396ca16", "metadata": {}, "source": [ "Unfortunately, public key encryption is an invertible function given a public key:" ] }, { "cell_type": "markdown", "id": "283313cb", "metadata": {}, "source": [ "````{prf:proposition} \n", "\n", "The plaintext can be recovered from the ciphertext using the public key, even without the private key. \n", " \n", "````" ] }, { "cell_type": "markdown", "id": "ab796b4f", "metadata": {}, "source": [ "**Exercise** (Optional) Prove the above proposition." ] }, { "cell_type": "markdown", "id": "9f3ca2da", "metadata": { "nbgrader": { "grade": true, "grade_id": "invertible", "locked": false, "points": 0, "schema_version": 3, "solution": true, "task": false }, "tags": [ "hide-input" ] }, "source": [ "````{prf:proof} \n", "\n", "It suffices to show that the encryption $E(\\cdot, k_e)$ is invertible for any public key $k_e$, i.e., two plaintext $x_1$ and $x_2$ are the same if and only if they encrypts to the same ciphertexts using the same key $k_e$.\n", "If two plaintexts are the same, then their ciphertexts must be the same by {eq}`encrypt`. It remains to prove the converse. \n", "\n", "If the ciphertexts are the same, i.e.,\n", "\n", "$$E(x_1, k_e)=E(x_2, k_e)=y,$$\n", "\n", "then, by {eq}`decrypt`, \n", "\n", "$$x_1 = D(y, k_d) = x_2,$$ \n", "\n", "i.e., the plaintexts are the same.\n", "\n", "The converse is trivial.\n", "\n", "````" ] }, { "cell_type": "markdown", "id": "15b53e63", "metadata": {}, "source": [ "**How to make public key encryption secure?**" ] }, { "cell_type": "markdown", "id": "ac03cf3e", "metadata": {}, "source": [ "We can make it computationally infeasible to invert $E(\\cdot, k_e)$ unless with the private key $k_d$ is available. Such a function is called the [trapdoor function](https://en.wikipedia.org/wiki/Trapdoor_function#:~:text=A%20trapdoor%20function%20is%20a,are%20widely%20used%20in%20cryptography.). An example of a trapdoor function is:" ] }, { "cell_type": "markdown", "id": "e684c352", "metadata": {}, "source": [ "````{prf:proposition} Integer factorization\n", "\n", "Computing the product of of two prime numbers $p$ and $q$, i.e.,\n", "\n", "$$\n", "(p,q)\\mapsto n,\n", "$$\n", "\n", "is a trapdoor function because integer factorization (computing $p$ and $q$ from $n$) is [co-NP](https://en.wikipedia.org/wiki/Integer_factorization) (difficult).\n", "\n", "````" ] }, { "cell_type": "markdown", "id": "1a9fe1bf", "metadata": {}, "source": [ "As the size of $p$ and $q$ increases, the time required to factor $n$ increases dramatically as illustrated [here](https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/pi/time-complexity-exploration)." ] }, { "cell_type": "markdown", "id": "16dad03d", "metadata": { "tags": [] }, "source": [ "## RSA Algorithm" ] }, { "cell_type": "markdown", "id": "a6653fc2", "metadata": {}, "source": [ "**How to encrypt/decrypt?**" ] }, { "cell_type": "markdown", "id": "f7f67b34", "metadata": {}, "source": [ "The encryption and decryption use modulo exponentiation instead of addition:\n", "\n", "$$\n", "\\begin{align}\n", "E(x, k_e) &:= x^e \\bmod n && \\text{where }k_e:=(e,n)\\\\\n", "D(c, k_d) &:= c^d \\bmod n && \\text{where }k_d:=(d,n),\n", "\\end{align}\n", "$$\n", " \n", "and $e$, $d$, and $n$ are positive integers." ] }, { "cell_type": "markdown", "id": "bf999c05", "metadata": {}, "source": [ "Computing exponentiation can be fast using [repeated squaring](https://en.wikipedia.org/wiki/Exponentiation_by_squaring). The built-in function `pow` already has an efficient implementation:" ] }, { "cell_type": "code", "execution_count": 1, "id": "5b226025", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "22.5 ms ± 61.8 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n" ] } ], "source": [ "%%timeit\n", "x, e, n = 3, 2 ** 1000000, 4\n", "pow(x, e, n)" ] }, { "cell_type": "markdown", "id": "acd7d311", "metadata": {}, "source": [ "**Exercise** (Optional) Implement you own `modulo_power` using a recusion." ] }, { "cell_type": "code", "execution_count": 2, "id": "b4307a92", "metadata": { "nbgrader": { "grade": false, "grade_id": "modulo_power", "locked": false, "schema_version": 3, "solution": true, "task": false }, "tags": [ "hide-input" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "22.4 ms ± 136 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n" ] } ], "source": [ "%%timeit\n", "def modulo_power(x, e, n):\n", " ### BEGIN SOLUTION\n", " if e == 0:\n", " return 1 % n\n", " if e == 1:\n", " return x % n\n", " return (\n", " x * modulo_power(x ** 2, e // 2, n)\n", " if e % 2\n", " else modulo_power(x ** 2, e // 2, n)\n", " )\n", " ### END SOLUTION\n", "\n", "\n", "x, e, n = 3, 2 ** 1000000, 4\n", "pow(x, e, n)" ] }, { "cell_type": "markdown", "id": "d8ac459c", "metadata": {}, "source": [ "**How to ensure decryptability?**" ] }, { "cell_type": "markdown", "id": "134d64c8", "metadata": {}, "source": [ "For $x = D(E(x, k_e), k_d) = x^{ed} \\bmod n$, we need $0\\leq x < n$ and\n", "\n", "$$\n", "x^{ed} \\equiv x \\mod n.\n", "$$ (decryptability)" ] }, { "cell_type": "markdown", "id": "1d04cfea", "metadata": {}, "source": [ "**Exercise** (Optional) Derive the above condition using $(a^c \\bmod b) = (a\\bmod b)^c \\bmod b$." ] }, { "cell_type": "markdown", "id": "8c352125", "metadata": { "nbgrader": { "grade": false, "grade_id": "decryptability", "locked": true, "points": 0, "schema_version": 3, "solution": false, "task": true }, "tags": [ "hide-input" ] }, "source": [ "$$\n", "\\begin{align}\n", "x &= D(E(x, k_e), k_d) \\\\\n", "&= (x^{e} \\bmod n)^{d} \\bmod n \\\\\n", "&= x^{ed} \\bmod n.\n", "\\end{align}\n", "$$" ] }, { "cell_type": "markdown", "id": "b5fa20b7", "metadata": {}, "source": [ "RSA makes use of the following result to choose $(e, d, n)$:" ] }, { "cell_type": "markdown", "id": "66a3006e", "metadata": {}, "source": [ "````{prf:theorem} Fermat's little Theorem\n", "\n", "If $p$ is prime, then\n", "\n", "$$\n", "x^{p-1}\\equiv 1 \\mod p\n", "$$ (fermat)\n", "\n", "for any integer $x$.\n", "\n", "````" ] }, { "cell_type": "markdown", "id": "22b780ac", "metadata": {}, "source": [ "There are elegant and elementary [combinatorial proofs](https://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_little_theorem#Combinatorial_proofs)." ] }, { "cell_type": "markdown", "id": "68907529", "metadata": {}, "source": [ "Since {eq}`fermat` implies $x^p = x \\bmod p$, can we choose \n", "- $n=p$ and \n", "- $ed=p$\n", "\n", "to satisfies {eq}`decryptability`?" ] }, { "cell_type": "markdown", "id": "6f3d0ec2", "metadata": {}, "source": [ "No because the private key can then be easily computed from the public key: $d = n/e$." ] }, { "cell_type": "markdown", "id": "40b7519e", "metadata": {}, "source": [ "Alternatively, by raising {eq}`fermat` to the power of any integer $m$,\n", "\n", "$$\n", "x^{m(p-1)} \\equiv 1 \\mod p.\n", "$$ (fermat-m)" ] }, { "cell_type": "markdown", "id": "4ded8844", "metadata": {}, "source": [ "Can we have $n=p$ and $ed \\equiv 1 \\bmod p-1$?" ] }, { "cell_type": "markdown", "id": "54f6ae4d", "metadata": {}, "source": [ "No because $d$ is the modular multiplicative inverse of $e$, which is [easy to compute](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Computation), e.g., using `pow` with an exponent of `-1`. In particular, for prime modulus here, the inverse is $d=e^{p-2}\\bmod p$:" ] }, { "cell_type": "code", "execution_count": 3, "id": "4ef062d4", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(5, True)" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "e, n = 3, 7\n", "d = pow(e, -1, n)\n", "d, e * d % n == 1 and d == e ** (n - 2) % n" ] }, { "cell_type": "markdown", "id": "999c6bed", "metadata": {}, "source": [ "**How to make it difficult to compute $d$?**" ] }, { "cell_type": "markdown", "id": "0985e166", "metadata": {}, "source": [ "RSA makes use of the hardness of factoring a product of large primes to create the desired trapdoor function." ] }, { "cell_type": "markdown", "id": "cb49ddf0", "metadata": {}, "source": [ "In particular, with $m(p-1)$ in {eq}`fermat-m` being the least common multiple $\\operatorname{lcm}(p-1,q-1)$ for another prime number $q$, we have\n", "\n", "$$\n", "\\begin{align}\n", "x^{\\operatorname{lcm}(p-1, q-1)} &\\equiv 1 \\mod p && \\text{and}\\\\\n", "x^{\\operatorname{lcm}(p-1, q-1)} &\\equiv 1 \\mod q && \\text{by symmetry.}\n", "\\end{align}\n", "$$" ] }, { "cell_type": "markdown", "id": "1f563e77", "metadata": {}, "source": [ "This implies $x^{\\operatorname{lcm}(p-1, q-1)} - 1$ is divisible by both $p$ and $q$, and so\n", "\n", "$$\n", "x^{\\operatorname{lcm}(p-1, q-1)} \\equiv 1 \\mod p q.\n", "$$\n", "\n", "Raising both sides to the power of any positive integer $m$ give:" ] }, { "cell_type": "markdown", "id": "aad78620", "metadata": {}, "source": [ "````{prf:proposition} RSA\n", "\n", "If $p$ and $q$ are prime, then\n", "\n", "$$\n", "x^{\\overbrace{m \\operatorname{lcm}(p-1, q-1)}^{ed - 1}} \\equiv 1 \\mod \\overbrace{p q}^n\n", "$$ (rsa)\n", "\n", "for any integer $x$. This implies {eq}`decryptability` with by choosing $n = pq$ and\n", "\n", "$$\n", "ed \\equiv 1 \\mod \\operatorname{lcm}(p-1, q-1).\n", "$$ (ed)\n", "\n", "````" ] }, { "cell_type": "markdown", "id": "2e665716", "metadata": {}, "source": [ "Although $d$ is still the modulo multiplicative inverse of $e$, it is with respect to $\\operatorname{lcm}(p-1, q-1)$, which is not easy to compute without knowing the factors of $n$, namely $p$ and $q$. It can be shown that computing $d$ is [as hard as](https://crypto.stackexchange.com/questions/16036/is-knowing-the-private-key-of-rsa-equivalent-to-the-factorization-of-n) computing $\\operatorname{lcm}(p-1, q-1)$ or factoring $n$." ] }, { "cell_type": "markdown", "id": "f8256a78", "metadata": {}, "source": [ "**How to generate the public key and private key?**" ] }, { "cell_type": "markdown", "id": "2a1e68ca", "metadata": {}, "source": [ "By {eq}`ed`, we can compute $d$ as the modulo multiplicative inverse of $e$. How to choose $e$ then?" ] }, { "cell_type": "markdown", "id": "80e917f8", "metadata": {}, "source": [ "We can choose any $e \\in \\{1, \\dots, \\operatorname{lcm}(p-1, q-1)\\}$ such that $e$ does not divide $\\operatorname{lcm}(p-1, q-1)$." ] }, { "cell_type": "markdown", "id": "5b2cfe7c", "metadata": {}, "source": [ "**Exercise** (Optional) For $e$ to have the modulo multiplicative inverse, it should not divide $\\operatorname{lcm}(p-1, q-1)$. Why?" ] }, { "cell_type": "markdown", "id": "4ce699b0", "metadata": { "nbgrader": { "grade": true, "grade_id": "inverse", "locked": false, "points": 0, "schema_version": 3, "solution": true, "task": false }, "tags": [ "hide-input" ] }, "source": [ "Otherise, $ed \\bmod \\operatorname{lcm}(p-1, q-1) = 0$, which violates {eq}`ed` for any integer $d$." ] }, { "cell_type": "markdown", "id": "aa1ef21a", "metadata": {}, "source": [ "The following function randomly generate the `e, d, n` for some given prime numbers `p` and `q`:" ] }, { "cell_type": "code", "execution_count": 4, "id": "282bc7b6", "metadata": {}, "outputs": [], "source": [ "from math import gcd\n", "from random import randint\n", "\n", "\n", "def get_rsa_keys(p, q):\n", " n = p * q\n", " lcm = (p - 1) * (q - 1) // gcd(p - 1, q - 1)\n", " while True:\n", " e = randint(1, lcm - 1)\n", " if gcd(e, lcm) == 1:\n", " break\n", " d = pow(e, -1, lcm)\n", " return e, d, n, lcm" ] }, { "cell_type": "markdown", "id": "83231080", "metadata": {}, "source": [ "Note that\n", "\n", "$$\n", "\\operatorname{lcm}(p-1, q-1) = \\frac{(p-1)(q-1)}{\\operatorname{gcd}(p-1, q-1)}.\n", "$$" ] }, { "cell_type": "markdown", "id": "69c6cf5f", "metadata": {}, "source": [ "As an example, if we choose two prime numbers $p=17094589121$ and $q=1062873761$:" ] }, { "cell_type": "code", "execution_count": 5, "id": "4cabc7d4", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(31327097961925559, 88499297323668999, 18169390231786954081, True)" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "e, d, n, lcm = get_rsa_keys(17094589121, 1062873761)\n", "e, d, n, e * d % lcm == 1" ] }, { "cell_type": "markdown", "id": "146871f5", "metadata": {}, "source": [ "The integer $1302$ can be encrypted as follows:" ] }, { "cell_type": "code", "execution_count": 6, "id": "4763bf64", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The plain text \"1302\" has been encrypted into \"6193348746418475734\".\n" ] } ], "source": [ "x = 1302\n", "c = pow(x, e, n)\n", "print(f'The plain text \"{x}\" has been encrypted into \"{c}\".')" ] }, { "cell_type": "markdown", "id": "6b95e49a", "metadata": {}, "source": [ "With the private key $k_d$, the ciphertext can be decrypted easily as" ] }, { "cell_type": "code", "execution_count": 7, "id": "f2908df3", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The cipher \"6193348746418475734\" has been decrypted into \"1302\".\n" ] } ], "source": [ "output = pow(c, d, n)\n", "print(f'The cipher \"{c}\" has been decrypted into \"{output}\".')" ] }, { "cell_type": "markdown", "id": "092f649f", "metadata": {}, "source": [ "**Exercise** (optional) Using the `rsa` module, [generate a RSA key pair](https://stuvel.eu/python-rsa-doc/usage.html#generating-keys) with suitable length and then use it to encrypt and decrypt your own message. You can install the module as follows:" ] }, { "cell_type": "code", "execution_count": 8, "id": "8fc74170", "metadata": { "tags": [ "remove-output" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Requirement already satisfied: rsa in /home/cs1302/my-conda-envs/jb/lib/python3.8/site-packages (4.7.2)\r\n", "Requirement already satisfied: pyasn1>=0.1.3 in /home/cs1302/my-conda-envs/jb/lib/python3.8/site-packages (from rsa) (0.4.8)\r\n" ] } ], "source": [ "!pip install rsa" ] } ], "metadata": { "jupytext": { "text_representation": { "extension": ".md", "format_name": "myst", "format_version": 0.13, "jupytext_version": "1.10.3" } }, "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.8.8" }, "source_map": [ 14, 18, 23, 27, 31, 35, 39, 62, 66, 71, 75, 79, 87, 91, 112, 116, 120, 134, 138, 142, 146, 159, 163, 167, 171, 199, 203, 211, 215, 225, 229, 243, 247, 255, 259, 267, 271, 275, 279, 283, 287, 298, 308, 326, 330, 334, 338, 342, 346, 350, 354, 368, 376, 380, 383, 387, 391, 395, 398, 402 ] }, "nbformat": 4, "nbformat_minor": 5 }