Assignment 3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "bec7f4f1-e6d9-45f5-9951-5808ab3f4574",
   "metadata": {},
   "source": [
    "# CSI4108 (Fundamentals of) Cryptography - Assignment 3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d64344b8-fe73-4143-bb37-ec3e744211d1",
   "metadata": {},
   "source": [
    "## Student Infomation\n",
    "Name: Jake Wang\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "03394619-7303-4acd-8b11-d7245dcea929",
   "metadata": {},
   "source": [
    "## Import Required Libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "7811f98a-dec1-4d67-98ba-a7344648c48e",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import requests\n",
    "import time\n",
    "import operator\n",
    "from functools import reduce\n",
    "from Cryptodome.Util.number import getPrime as get_prime\n",
    "from Cryptodome.Util.number import getStrongPrime as get_strong_prime\n",
    "from Cryptodome.Util.number import isPrime as is_prime"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c22a746d-2bec-4bca-ac5c-3253d8ee40d1",
   "metadata": {},
   "source": [
    "## Question 1: Elgamal Public Key Encryption Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4804fdf-eb65-4d76-ba92-4b433c59c858",
   "metadata": {},
   "source": [
    "### Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "e1fe8e38-0cda-44b8-acf9-30af8f61b1bb",
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [],
   "source": [
    "def generate_keypair(q, alpha):\n",
    "    # Generate a private key within (1, q - 1).\n",
    "    private_key = random.randint(2, q - 2)\n",
    "    public_key = pow(alpha, private_key, q)\n",
    "\n",
    "    return private_key, public_key\n",
    "\n",
    "\n",
    "def encrypt(message, q, alpha, public_key, k=None):\n",
    "    if k is None:\n",
    "        k = random.randint(1, q - 1)\n",
    "\n",
    "    # Generate ephemeral key s\n",
    "    s = pow(public_key, k, q)\n",
    "\n",
    "    c1 = pow(alpha, k, q)\n",
    "    c2 = (s * message) % q\n",
    "\n",
    "    return c1, c2\n",
    "\n",
    "\n",
    "def decrypt(c1, c2, private_key, q):\n",
    "    # Recover ephemeral key s\n",
    "    s = pow(c1, private_key, q)\n",
    "    # Calculate the inverse of s\n",
    "    s_inverse = pow(s, -1, q)\n",
    "\n",
    "    decrypted_message = (c2 * s_inverse) % q\n",
    "    return decrypted_message"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a613b6b-7cb3-4329-88bc-8f5dd0d771fd",
   "metadata": {},
   "source": [
    "### Verification"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "b1660750-5d53-478d-b3cf-ecfb612ceac8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Plaintext: 42\n",
      "Generated keypair: (4, 81)\n",
      "Ciphertext: (25, 79)\n",
      "Decrypted plaintext: 42\n"
     ]
    }
   ],
   "source": [
    "q = 89\n",
    "alpha = 13\n",
    "\n",
    "# Message should be in [0, q - 1]\n",
    "message = 42\n",
    "\n",
    "private_key, public_key = generate_keypair(q, alpha)\n",
    "c1, c2 = encrypt(message, q, alpha, public_key)\n",
    "decrypted_message = decrypt(c1, c2, private_key, q)\n",
    "\n",
    "print(\"Plaintext:\", message)\n",
    "print(\"Generated keypair:\", (private_key, public_key))\n",
    "print(\"Ciphertext:\", (c1, c2))\n",
    "print(\"Decrypted plaintext:\", decrypted_message)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f931d6d-ba62-4e99-82a3-af8244bc10b8",
   "metadata": {},
   "source": [
    "### Decrypt ciphertext\n",
    "* $m_1$ is given to be 62\n",
    "* Choose $m_2 = 10$\n",
    "* Compute ciphertext of $m_1$ and $m_2$ with $k = 43$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "500ae145-ff96-425f-82cb-5912eb8a3397",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(41, 69) (41, 14)\n"
     ]
    }
   ],
   "source": [
    "# System parameters\n",
    "q = 89\n",
    "alpha = 13\n",
    "k = 43\n",
    "private_key, public_key = (55, 12)\n",
    "\n",
    "# Encrypt messages\n",
    "m_1 = 62\n",
    "e_1 = encrypt(m_1, q, alpha, public_key, k=k)\n",
    "m_2 = 10\n",
    "e_2 = encrypt(m_2, q, alpha, public_key, k=k)\n",
    "\n",
    "print(e_1, e_2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "80423cc8-bf4a-4968-9d2d-056e38051cea",
   "metadata": {},
   "source": [
    "Trying to compute $m_2$, given $e_1$, $e_2$:\n",
    "\n",
    "1. From the algorithm and the known value, we know\n",
    "    * $s_1 = s_2 = s = K_e ^ k$, where $K_e$ is the public key.\n",
    "    * $c_{2, 1} = sm_1 = 69, c_{2, 2} = sm_2 = 14$\n",
    "2. We can compute:\n",
    "    $$\n",
    "    \\begin{aligned}\n",
    "        (sm_1) ^ {-1} \\cdot (sm_2) &\\equiv c_{2, 1} ^ {-1} \\cdot c_{2, 2} \\pmod q \\\\\n",
    "        m_1 ^ {-1} \\cdot m_2 &\\equiv c_{2, 1} ^ {-1} \\cdot c_{2, 2} \\pmod q \\\\\n",
    "    \\end{aligned}\n",
    "    $$\n",
    "3. Multiple $m_1$ on both sides of the equation:\n",
    "    $$\n",
    "    \\begin{aligned}\n",
    "        m_2 &\\equiv c_{2, 1} ^ {-1} \\cdot c_{2, 2} \\cdot m_1 \\pmod q \\\\\n",
    "    \\end{aligned}\n",
    "    $$\n",
    "4. Then we can compute $m_2$ trivially:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "c7703afb-80c6-4702-a160-62de6b32e2ab",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "m_2 = 10\n"
     ]
    }
   ],
   "source": [
    "print(f\"m_2 = {(pow(e_1[1], -1, q) * e_2[1] * m_1) % q}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67dcf5cc-0b8d-4bc3-b5c7-0586cf3ed699",
   "metadata": {},
   "source": [
    "## Question 2: Miller-Rabin Primality Testing Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f5b42346-e66e-4b4d-93b7-aba491d9b4ed",
   "metadata": {},
   "source": [
    "### Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "fcd86f9f-5bd1-4aec-bd21-d6ee40a870bb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def miller_rabin(n, t):\n",
    "    if n <= 4:\n",
    "        return n == 2 or n == 3\n",
    "    if n & 1 == 0:\n",
    "        return False\n",
    "\n",
    "    # Compute d and k such that n - 1 = q * 2 ^ k.\n",
    "    q = n - 1\n",
    "    k = 0\n",
    "    while q & 1 == 0:\n",
    "        q >>= 1\n",
    "        k += 1\n",
    "\n",
    "    tested = set()\n",
    "    for _ in range(t):\n",
    "        # Select random integer a in (1, n - 1)\n",
    "        a = random.randint(2, n - 2)\n",
    "        while a in tested:\n",
    "            a = random.randint(2, n - 2)\n",
    "        tested.add(a)\n",
    "\n",
    "        x = pow(a, q, n)\n",
    "        # if a ^ q === 1 (mod n)\n",
    "        if x == 1:\n",
    "            # Inconclusive, continue to another round\n",
    "            continue\n",
    "\n",
    "        # for j in [0, k - 1]\n",
    "        for _ in range(k - 1):\n",
    "            x = pow(x, 2, n)\n",
    "            # if a ^ (2 ^ j * q) === n - 1 (mod n)\n",
    "            if x == n - 1:\n",
    "                # Inconclusive, continue to another round\n",
    "                break\n",
    "        else:\n",
    "            # Didn't encounter a break: composite number\n",
    "            return False\n",
    "\n",
    "    # Probably prime\n",
    "    return True\n",
    "\n",
    "\n",
    "def find_probable_prime(bits, confidence):\n",
    "    while True:\n",
    "        candidate = random.getrandbits(bits)\n",
    "        if miller_rabin(candidate, confidence):\n",
    "            return candidate"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "449597cc-b8fe-4152-9cb9-2e94b4bf65a3",
   "metadata": {},
   "source": [
    "### Verification"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "ffa8ae2a-2ae3-4821-9bbd-d7ec4e9684cd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A probable prime: 8221\n",
      "Found in the table\n"
     ]
    }
   ],
   "source": [
    "prime_set = {\n",
    "    prime\n",
    "    for list in (\n",
    "        line.strip().split()\n",
    "        for line in requests.get(\"https://t5k.org/lists/small/10000.txt\").text.splitlines()\n",
    "        if len(line) == 71\n",
    "    )\n",
    "    for prime in list\n",
    "}\n",
    "\n",
    "bits = 15\n",
    "confidence = 6\n",
    "\n",
    "probable_prime = find_probable_prime(bits, confidence)\n",
    "print(f\"A probable prime: {probable_prime}\")\n",
    "\n",
    "if str(probable_prime) in prime_set:\n",
    "    print(\"Found in the table\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "17872587-6f7f-4e83-bd0d-b6a95417d088",
   "metadata": {},
   "source": [
    "## Question 3: RSA and ECDH Exploration"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "37bda6e2-7ad6-4c87-966f-2e2fb19675f3",
   "metadata": {},
   "source": [
    "### RSA"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d79846e1-fe66-4b63-bcd6-11cc0a4554b6",
   "metadata": {},
   "source": [
    "#### Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "53d4e226-7d3e-446b-a8b1-d6e75afa0566",
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [],
   "source": [
    "def generate_keypair(bits):\n",
    "    p = get_prime(bits)\n",
    "    q = get_prime(bits)\n",
    "    n = p * q\n",
    "    phi = (p - 1) * (q - 1)\n",
    "    e = 65537\n",
    "    d = pow(e, -1, phi)\n",
    "    return (n, e), (n, d, p, q)\n",
    "\n",
    "\n",
    "def rsa_encrypt(message, public_key, mod_exp=pow):\n",
    "    n, e = public_key\n",
    "    return mod_exp(message, e, n)\n",
    "\n",
    "\n",
    "def rsa_decrypt(ciphertext, private_key, mod_exp=pow):\n",
    "    n, d, _, _ = private_key\n",
    "    return mod_exp(ciphertext, d, n)\n",
    "\n",
    "\n",
    "def rsa_decrypt_crt(ciphertext, private_key):\n",
    "    n, d, p, q = private_key\n",
    "\n",
    "    # CRT precalculations\n",
    "    m_list = [p, q]\n",
    "    totient_list = [m - 1 for m in m_list]\n",
    "\n",
    "    M = reduce(operator.mul, m_list)\n",
    "    M_list = [M // m for m in m_list]\n",
    "\n",
    "    d_list = [M % m for M, m in zip(M_list, m_list)]\n",
    "    d_reverse_list = [pow(d, -1, m) for d, m in zip(d_list, m_list)]\n",
    "\n",
    "    c_list = [d_reverse * M for d_reverse, M in zip(d_reverse_list, M_list)]\n",
    "\n",
    "    n = ciphertext\n",
    "    exponent = d\n",
    "\n",
    "    # CRT fast exponentiation\n",
    "    n_tuple = (n % m for m in m_list)\n",
    "    exponent_tuple = (exponent % totient for totient in totient_list)\n",
    "\n",
    "    result_tuple = (\n",
    "        pow(n_component, exponent_component, m)\n",
    "        for n_component, exponent_component, m\n",
    "        in zip(n_tuple, exponent_tuple, m_list)\n",
    "    )\n",
    "    result = sum(\n",
    "        result_component * c\n",
    "        for result_component, c in zip(result_tuple, c_list)\n",
    "    ) % M\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "191cbd46-d7ef-484b-9d65-c815234a636c",
   "metadata": {},
   "source": [
    "#### Benchmarking (decrypt with or without CRT)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "4b92a828-c706-4192-8fae-740be8287079",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original Message: 476921883457909\n",
      "Ciphertext: 11566844198355385838477940479021552757576863519650336099629353454437660844502692443071529641281925204084117133791999528949189657176491383314868478568282264316769098455107758487009952012379924441642232876888602979139272468524974705408398870449919457077619029487362402099454177236674492198816532972501481344874383336217509892416211632470311744913305334675117496760149890148123721810310834490543336764425504017416821812541888501323420570921140079305106840146159104595668848523098145612103730503192398462742527929075471138632796019382682938692017553750576279390960535704879050867617043137749741788463731778304503063209373\n",
      "Encryption Time: 0.00021886825561523438\n",
      "Decrypted Message (Without CRT): 476921883457909\n",
      "Decryption Time (Without CRT): 0.03512072563171387\n",
      "Decrypted Message (With CRT): 476921883457909\n",
      "Decryption Time (With CRT): 0.011171102523803711\n"
     ]
    }
   ],
   "source": [
    "# Generate key pair\n",
    "bits = 1024\n",
    "public_key, private_key = generate_keypair(bits)\n",
    "\n",
    "# Message to be encrypted\n",
    "message = 476921883457909\n",
    "\n",
    "# Encryption\n",
    "start_time = time.time()\n",
    "ciphertext = rsa_encrypt(message, public_key)\n",
    "encryption_time = time.time() - start_time\n",
    "\n",
    "# Decryption\n",
    "start_time = time.time()\n",
    "decrypted_message = rsa_decrypt(ciphertext, private_key)\n",
    "decryption_time_without_crt = time.time() - start_time\n",
    "\n",
    "# Decryption with CRT\n",
    "start_time = time.time()\n",
    "decrypted_message_crt = rsa_decrypt_crt(ciphertext, private_key)\n",
    "decryption_time_with_crt = time.time() - start_time\n",
    "\n",
    "print(\"Original Message:\", message)\n",
    "print(\"Ciphertext:\", ciphertext)\n",
    "print(\"Encryption Time:\", encryption_time)\n",
    "print(\"Decrypted Message (Without CRT):\", decrypted_message)\n",
    "print(\"Decryption Time (Without CRT):\", decryption_time_without_crt)\n",
    "print(\"Decrypted Message (With CRT):\", decrypted_message_crt)\n",
    "print(\"Decryption Time (With CRT):\", decryption_time_with_crt)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1743e5b1-9028-4f8a-9dbf-4e9d23ddf7bf",
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "source": [
    "#### Observation\n",
    "* Decryption with CRT is faster than normal decryption."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4dc3aa8b-1927-4b56-aaf5-a20f08d12b59",
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "source": [
    "### ECDH"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00210502-a35f-46b3-a261-32cd20a3c521",
   "metadata": {},
   "source": [
    "#### ECDH Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "1121e6d0-d718-44ee-93e0-16e78daf7f88",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Point:\n",
    "    def __init__(self, x: int, y: int):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        return self.x == other.x and self.y == other.y\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"Point({self.x}, {self.y})\"\n",
    "\n",
    "    def __str__(self):\n",
    "        return repr(self)\n",
    "\n",
    "\n",
    "class ECGroup:\n",
    "    def __init__(self, p: int, a: int, b: int):\n",
    "        self.p = p\n",
    "        self.a = a\n",
    "        self.b = b\n",
    "\n",
    "    def add(self, p: Point, q: Point):\n",
    "        if p == Point(0, 0):\n",
    "            return q\n",
    "        if q == Point(0, 0):\n",
    "            return p\n",
    "\n",
    "        if p != q:\n",
    "            slope = (q.y - p.y) * pow(q.x - p.x, -1, self.p) % self.p\n",
    "        else:\n",
    "            slope = (3 * p.x * p.x + self.a) * pow(2 * p.y, -1, self.p) % self.p\n",
    "\n",
    "        x = (slope * slope - p.x - q.x) % self.p\n",
    "        y = (slope * (p.x - x) - p.y) % self.p\n",
    "\n",
    "        return Point(x, y)\n",
    "\n",
    "    def multiply(self, k: int, p: Point):\n",
    "        result = Point(0, 0)\n",
    "        addend = p\n",
    "\n",
    "        while k:\n",
    "            if k & 1:\n",
    "                result = self.add(result, addend)\n",
    "            addend = self.add(addend, addend)\n",
    "            k >>= 1\n",
    "\n",
    "        return result\n",
    "\n",
    "    def y_squared(self, x: int):\n",
    "        return (x ** 3 + self.a * x + self.b) % self.p\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"ECGroup({self.p}, {self.a}, {self.b})\"\n",
    "\n",
    "    def __str__(self):\n",
    "        return repr(self)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e98b0cd-e33b-4f8d-9019-7ec57e72924a",
   "metadata": {},
   "source": [
    "#### ECDH Verification"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "71381862-6ec8-48f6-98e1-7ee2e2961c21",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "G is on curve: True\n",
      "Alice has key: Point(1290523551237518590156283625125266111764555020684, 887800925528475370478952271981502477580143452726)\n",
      "Bob has key: Point(1290523551237518590156283625125266111764555020684, 887800925528475370478952271981502477580143452726)\n",
      "Two keys are equal: True\n",
      "Ellpased time: 0.03154325485229492\n"
     ]
    }
   ],
   "source": [
    "# brainpoolP160r1\n",
    "# Reference: https://datatracker.ietf.org/doc/html/rfc5639#section-3.1\n",
    "E = ECGroup(\n",
    "    0xe95e4a5f737059dc60dfc7ad95b3d8139515620f,\n",
    "    0x340e7be2a280eb74e2be61bada745d97e8f7c300,\n",
    "    0x1e589a8595423412134faa2dbdec95c8d8675e58\n",
    ")\n",
    "G = Point(\n",
    "    0xbed5af16ea3f6a4f62938c4631eb5af7bdbcdbc3,\n",
    "    0x1667cb477a1a8ec338f94741669c976316da6321\n",
    ")\n",
    "\n",
    "# Verify that G is on the curve\n",
    "print(f\"G is on curve: {E.y_squared(G.x) == pow(G.y, 2, E.p)}\")\n",
    "\n",
    "start_time = time.time()\n",
    "\n",
    "# Alice side\n",
    "n_a = random.getrandbits(160)\n",
    "P_a = E.multiply(n_a, G)\n",
    "\n",
    "# Bob side\n",
    "n_b = random.getrandbits(160)\n",
    "P_b = E.multiply(n_b, G)\n",
    "\n",
    "# Alice and Bob exchange P_a and P_b\n",
    "\n",
    "# Alice side\n",
    "k_a = E.multiply(n_a, P_b)\n",
    "\n",
    "# Bob side\n",
    "k_b = E.multiply(n_b, P_a)\n",
    "\n",
    "end_time = time.time()\n",
    "\n",
    "print(f\"Alice has key: {k_a}\")\n",
    "print(f\"Bob has key: {k_b}\")\n",
    "# Two keys should be equal\n",
    "print(f\"Two keys are equal: {k_a == k_b}\")\n",
    "\n",
    "print(f\"Ellpased time: {end_time - start_time}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "680b1e48-5ee7-46fa-ae0b-67486c558936",
   "metadata": {},
   "source": [
    "#### DH Verification"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "5d97652c-aef4-4e45-8896-2e98ce9358be",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Alice has key: 1183355598691882188483629711617224954819096246507720799341269615982173437104994254197494264856397346563392022081924361694355093065657624286365815466844196697440931532766378865245112698870856222246808909858607337538491920939307630952766356292268040815517699806962037040720053113767873656258783986866473485912332241258155031931440419283945498102392923401459439868677334845\n",
      "Bob has key: 1183355598691882188483629711617224954819096246507720799341269615982173437104994254197494264856397346563392022081924361694355093065657624286365815466844196697440931532766378865245112698870856222246808909858607337538491920939307630952766356292268040815517699806962037040720053113767873656258783986866473485912332241258155031931440419283945498102392923401459439868677334845\n",
      "Two key are equal: True\n",
      "Ellpased time: 0.0041790008544921875\n"
     ]
    }
   ],
   "source": [
    "# 160-bit elliptive curve has 80-bit security.\n",
    "# To achieve 80-bit security, we need 1228-bit modulus size.\n",
    "# Reference: https://datatracker.ietf.org/doc/html/rfc3766#section-5\n",
    "\n",
    "# Generated with `openssl dhparam 1228`\n",
    "# PEM output:\n",
    "# -----BEGIN DH PARAMETERS-----\n",
    "# MIGkAoGaCg9o40rrQWqaxxCdFgwwnvPqJlvLt0M+iS5aOTMnKP6pe4/ogMX5iBCA\n",
    "# lpsf1veK5u91kKjMtqy1AoRmJm+oQRzVOQRBbRHVNgQNYjdTH0Buop4kv/A18v2B\n",
    "# aDZmijvPWCfkPmYx49d4pIpsKCIT17igBn+NI6QAGq3TE+cURNtU11yLPKC9Urmd\n",
    "# QtA+1TL4O6Vy1oTHT97dRwIBAgICAMg=\n",
    "# -----END DH PARAMETERS-----\n",
    "# View with `openssl dhparam -inform PEM -in ./dh.pem -check -text -noout`\n",
    "# DH Parameters: (1228 bit)\n",
    "# P:\n",
    "#     0a:0f:68:e3:4a:eb:41:6a:9a:c7:10:9d:16:0c:30:\n",
    "#     9e:f3:ea:26:5b:cb:b7:43:3e:89:2e:5a:39:33:27:\n",
    "#     28:fe:a9:7b:8f:e8:80:c5:f9:88:10:80:96:9b:1f:\n",
    "#     d6:f7:8a:e6:ef:75:90:a8:cc:b6:ac:b5:02:84:66:\n",
    "#     26:6f:a8:41:1c:d5:39:04:41:6d:11:d5:36:04:0d:\n",
    "#     62:37:53:1f:40:6e:a2:9e:24:bf:f0:35:f2:fd:81:\n",
    "#     68:36:66:8a:3b:cf:58:27:e4:3e:66:31:e3:d7:78:\n",
    "#     a4:8a:6c:28:22:13:d7:b8:a0:06:7f:8d:23:a4:00:\n",
    "#     1a:ad:d3:13:e7:14:44:db:54:d7:5c:8b:3c:a0:bd:\n",
    "#     52:b9:9d:42:d0:3e:d5:32:f8:3b:a5:72:d6:84:c7:\n",
    "#     4f:de:dd:47\n",
    "# G:    2 (0x2)\n",
    "# recommended-private-length: 200 bits\n",
    "# DH parameters appear to be ok.\n",
    "p = \"0a0f68e34aeb416a9ac7109d160c309e\" \\\n",
    "    \"f3ea265bcbb7433e892e5a39332728fe\" \\\n",
    "    \"a97b8fe880c5f9881080969b1fd6f78a\" \\\n",
    "    \"e6ef7590a8ccb6acb5028466266fa841\" \\\n",
    "    \"1cd53904416d11d536040d6237531f40\" \\\n",
    "    \"6ea29e24bff035f2fd816836668a3bcf\" \\\n",
    "    \"5827e43e6631e3d778a48a6c282213d7\" \\\n",
    "    \"b8a0067f8d23a4001aadd313e71444db\" \\\n",
    "    \"54d75c8b3ca0bd52b99d42d03ed532f8\" \\\n",
    "    \"3ba572d684c74fdedd47\"\n",
    "p = int(p, 16)\n",
    "g = 0x2\n",
    "\n",
    "start_time = time.time()\n",
    "\n",
    "# Alice side\n",
    "n_a = random.getrandbits(160)\n",
    "P_a = pow(g, n_a, p)\n",
    "\n",
    "# Bob side\n",
    "n_b = random.getrandbits(160)\n",
    "P_b = pow(g, n_b, p)\n",
    "\n",
    "# Alice and Bob exchange P_a and P_b\n",
    "\n",
    "# Alice side\n",
    "k_a = pow(P_b, n_a, p)\n",
    "\n",
    "# Bob side\n",
    "k_b = pow(P_a, n_b, p)\n",
    "\n",
    "end_time = time.time()\n",
    "\n",
    "print(f\"Alice has key: {k_a}\")\n",
    "print(f\"Bob has key: {k_b}\")\n",
    "# Two keys should be equal\n",
    "print(f\"Two key are equal: {k_a == k_b}\")\n",
    "\n",
    "print(f\"Ellpased time: {end_time - start_time}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e8e1548-c34c-4f56-88ec-fa4ee25c21b1",
   "metadata": {},
   "source": [
    "#### Observation\n",
    "* Under the security level of 80 bits, we can see DH is faster than ECDH algorithm."
   ]
  }
 ],
 "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.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}