Exercise3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Alisa Todorova"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import math\n",
    "import sympy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2. Fermat Test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.1. Implement the Fermat test of primality with small integers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This implementation is based on slide 54 of Lecture Slides \"Computing with large integers\"\n",
    "\n",
    "# Fermat primality test with security parameter t, where\n",
    "# n is the number to test,\n",
    "# t is the number of times to repeat the test in order to reduce the probability of failure\n",
    "def fermat_test(n, t):\n",
    "    if n < 1 or t < 1:\n",
    "        return \"Please choose different n and/or t\"\n",
    "\n",
    "    # Handle cases when n-2<=2 (so we can later choose random a ∈ [2, n − 2])\n",
    "    if n==1:\n",
    "        return \"1 is neither a prime number nor a composite number\"\n",
    "    if n==2 or n==3:\n",
    "        return f\"{n} is a prime number\"\n",
    "    if n==4: \n",
    "        return \"4 is a composite number.\"\n",
    "\n",
    "    for i in range(t):\n",
    "        # Choose a random a ∈ [2, n − 2]\n",
    "        a = random.randint(2, n-2)\n",
    "\n",
    "        # Compute r = a^(n−1) mod n\n",
    "        r = pow(a, n-1, n)\n",
    "\n",
    "        if r!=1:\n",
    "            return f\"{n} is a composite number.\"\n",
    "        else:\n",
    "            return f\"{n} is a prime number\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'17 is a prime number'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Test Fermat primality test with security parameter t\n",
    "n = 17\n",
    "t = 10\n",
    "fermat_test(n,t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.2. Write a function to generate random k-bit prime numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This implementation is based on slids 63 and 65 of Lecture Slides \"Computing with large integers\"\n",
    "\n",
    "# Miller-Rabin primality test with security parameter t, where\n",
    "# n is the number to test,\n",
    "# t is the number of times to repeat the test in order to reduce the probability of failure\n",
    "def miller_rabin(n, t):\n",
    "    if n < 1 or t < 1:\n",
    "        return \"Please choose different n and/or t\"\n",
    "\n",
    "    # Handle cases when n-2<=2 (so we can later choose random a ∈ [2, n − 2])\n",
    "    if n==2 or n==3:\n",
    "        return True\n",
    "    # n must be odd\n",
    "    if n==1 or n%2==0: \n",
    "        return False\n",
    "\n",
    "    # Write n − 1 = 2^h · m for odd m\n",
    "    h, m = 0, n - 1\n",
    "    while m % 2 == 0:\n",
    "        h += 1\n",
    "        m //= 2\n",
    "\n",
    "    for i in range(t):\n",
    "        # Generate a random α ∈ Zn\n",
    "        a = random.randint(2, n - 2)\n",
    "\n",
    "        beta = pow(a, m, n)\n",
    "\n",
    "        if (beta == 1) or (beta == n - 1):\n",
    "            continue\n",
    "\n",
    "        # Testing wheter a ∈ L'n\n",
    "        for i in range(h - 1):\n",
    "            beta = pow(beta, 2, n)\n",
    "            if beta == n - 1:\n",
    "                break\n",
    "        else:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "# Generates a random k-bit prime number\n",
    "def k_bit_prime(k, t):\n",
    "    while True:\n",
    "        n = random.getrandbits(k)\n",
    "\n",
    "        if miller_rabin(n, t):\n",
    "            return n\n",
    "        else:\n",
    "            continue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is 17 prime: True\n",
      "Random 32-bit prime number: 1393214429\n"
     ]
    }
   ],
   "source": [
    "# Test Miller-Rabin primality test\n",
    "n = 17\n",
    "t = 10\n",
    "k = 32\n",
    "prime_check = miller_rabin(n, t)\n",
    "print(f\"Is {n} prime: {prime_check}\")\n",
    "k_bit = k_bit_prime(k, t)\n",
    "print(f\"Random {k}-bit prime number: {k_bit}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3. RSA"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.1. Write the key-generation function function of RSA. The function should generate two random primes p and q of size k/2 bits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This implementation is based on slide 7 of Lecture Slides \"The RSA cryptosystem - Part 1: encryption and signature\"\n",
    "\n",
    "# Generates an RSA key, where input n is the bitsize n of the RSA modulus N.\n",
    "def keyGen(n=512):\n",
    "\n",
    "    # Generate two large distinct primes p and q of same bit-size k/2, where k is a parameter.\n",
    "    # p = sympy.randprime(2 ** (n - 1) + 1, 2**n - 1)\n",
    "    # q = sympy.randprime(2 ** (n - 1) + 1, 2**n - 1)\n",
    "    # Smaller numbers for testing:\n",
    "    p = 17\n",
    "    q = 11\n",
    "\n",
    "    Nn = p * q\n",
    "\n",
    "    phi = (p - 1) * (q - 1)\n",
    "\n",
    "    # Select a random integer e such that gcd(e, φ) = 1\n",
    "    # e = random.randint(2, phi - 1)\n",
    "    # while math.gcd(e, phi) != 1:\n",
    "    #     e = random.randint(2, phi - 1)\n",
    "    # Smaller number for testing\n",
    "    e = 3\n",
    "\n",
    "    # Compute the unique integer d such that e · d ≡ 1 (mod φ)\n",
    "    d = pow(e, phi - 1, phi)\n",
    "\n",
    "    return Nn, p, q, e, d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(187, 17, 11, 3, 107)\n"
     ]
    }
   ],
   "source": [
    "# Test RSA key generation\n",
    "key = keyGen()\n",
    "print(key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.2. Implement the RSA encryption function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This implementation is based on slide 8 of Lecture Slides \"The RSA cryptosystem - Part 1: encryption and signature\"\n",
    "def encrypt(m, Nn, e):\n",
    "    # Ciphertext c = m^e mod n\n",
    "    c = (m**e) % Nn  \n",
    "    return c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.3. Implement the RSA decryption function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This implementation is based on slide 8 of Lecture Slides \"The RSA cryptosystem - Part 1: encryption and signature\"\n",
    "def decrypt(c, Nn, d):\n",
    "    # Message m = c^d mod n\n",
    "    m = (c**d) % Nn  \n",
    "    return m"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.4. Check that decryption works"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original message:89\n",
      "Encrypted message:166\n",
      "Decrypted message:89\n"
     ]
    }
   ],
   "source": [
    "def checkDec():\n",
    "    Nn, p, q, e, d = keyGen()\n",
    "\n",
    "    m = 89\n",
    "    print(f\"Original message:{m}\")\n",
    "\n",
    "    c = encrypt(m, Nn, e)\n",
    "    print(f\"Encrypted message:{c}\")\n",
    "    \n",
    "    dec = decrypt(c, Nn, d)\n",
    "    print(f\"Decrypted message:{dec}\")\n",
    "\n",
    "# Test encryption and decryption \n",
    "# Note: the output you see is tested with the smaller numbers\n",
    "checkDec()"
   ]
  }
 ],
 "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.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}