cryptosystems.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f55811b4",
   "metadata": {},
   "source": [
    "### Helpers and Imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "4c6b9373",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import math\n",
    "import sys\n",
    "from typing import Tuple\n",
    "sys.setrecursionlimit(1000000)\n",
    "\n",
    "def is_prime(n, k):\n",
    "    # Miller-Rabin primality test\n",
    "    # https://gist.github.com/Ayrx/5884790\n",
    "    \n",
    "    if n == 2:\n",
    "        return True\n",
    "    if n % 2 == 0:\n",
    "        return False\n",
    "\n",
    "    r, s = 0, n - 1\n",
    "    while s % 2 == 0:\n",
    "        r += 1\n",
    "        s //= 2\n",
    "    for _ in range(k):\n",
    "        a = random.randrange(2, n - 1)\n",
    "        x = pow(a, s, n)\n",
    "        if x == 1 or x == n - 1:\n",
    "            continue\n",
    "        for _ in range(r - 1):\n",
    "            x = pow(x, 2, n)\n",
    "            if x == n - 1:\n",
    "                break\n",
    "        else:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "\n",
    "def generate_big_prime(size):\n",
    "    k = 40\n",
    "    p = random.randrange(2 ** (size - 1), 2 ** size - 1)\n",
    "    if p % 2 == 0:\n",
    "        p += 1\n",
    "    while not is_prime(p, k):\n",
    "        p += 2\n",
    "    return p\n",
    "\n",
    "\n",
    "def egcd(a: int, b: int) -> Tuple[int, int, int]:\n",
    "    # https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm#Recursive_algorithm_2\n",
    "    \"\"\"return (g, x, y) such that a*x + b*y = g = gcd(a, b)\"\"\"\n",
    "    if a == 0:\n",
    "        return (b, 0, 1)\n",
    "    else:\n",
    "        b_div_a, b_mod_a = divmod(b, a)\n",
    "        g, x, y = egcd(b_mod_a, a)\n",
    "        return (g, y - b_div_a * x, x)\n",
    "\n",
    "\n",
    "def modinv(a: int, b: int) -> int:\n",
    "    # https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm#Modular_inverse\n",
    "    \"\"\"return x such that (x * a) % b == 1\"\"\"\n",
    "    g, x, _ = egcd(a, b)\n",
    "    if g != 1:\n",
    "        raise Exception('gcd(a, b) != 1')\n",
    "    return x % b\n",
    "\n",
    "\n",
    "def L(x, n):\n",
    "    # L function used in the Pallier cryptosystem\n",
    "    return (x - 1) // n\n",
    "\n",
    "\n",
    "def legendre(a, p):\n",
    "    \"\"\"return the Legendre symbol (a/p)\"\"\"\n",
    "    symbol = pow(a, int((p-1)/2), p)\n",
    "    if symbol == (p - 1):\n",
    "        return -1\n",
    "    else:\n",
    "        return symbol"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d3f383e1",
   "metadata": {},
   "source": [
    "# Pallier Cryptosystem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f6d93da",
   "metadata": {},
   "source": [
    "[Wikipedia page](https://en.wikipedia.org/wiki/Paillier_cryptosystem)\n",
    "\n",
    "[Original paper](https://doi.org/10.1007%2F3-540-48910-X_16)\n",
    "\n",
    "Security based on the [Decisional Composite Residuosity Assumption](https://en.wikipedia.org/wiki/Decisional_composite_residuosity_assumption).\n",
    "\n",
    "NOTE: Plaintext space is $\\mathbb{Z}_{n}$, ciphertext space is $\\mathbb{Z}_{(pq)^2}^*$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "ea62f4a8",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Pallier:\n",
    "    def __init__(self, security_param):\n",
    "        self.pk, self.__sk = self.gen(security_param)\n",
    "        \n",
    "        \n",
    "    def gen(self, security_param):\n",
    "        # 1. Choose two large prime numbers of equal length\n",
    "        length = security_param\n",
    "        p = generate_big_prime(length)\n",
    "        q = generate_big_prime(length)\n",
    "\n",
    "        # 2a. Compute n = pq and lambda = lcm(p-1, q-1)    OR\n",
    "        # 2b. Compute n = pq and lambda = phi(n) = (p - 1) * (q - 1)\n",
    "        n = p * q\n",
    "        lambda_ = (p - 1) * (q - 1)\n",
    "\n",
    "        # 3a. Select random integer g from Z_{n^2}^*    OR\n",
    "        # 3b. Compute g = n + 1\n",
    "        g = n + 1\n",
    "\n",
    "        # 4a. Ensure n divides the order of g and calculate mu = (L(g^lambda mod n^2))^{-1} mod n    OR\n",
    "        # 4b. Calculate mu = phi(n)^{-1} mod n = lambda^{-1} mod n\n",
    "        mu = modinv(lambda_, n)\n",
    "\n",
    "        # Set the public key and secret key\n",
    "        pk = (n, g)\n",
    "        sk = (lambda_, mu)\n",
    "\n",
    "        return pk, sk\n",
    "\n",
    "\n",
    "    def enc(self, m):\n",
    "        n, g = self.pk\n",
    "\n",
    "        # 1. Ensure 0 ≤ m < n\n",
    "        assert (0 <= m),\"Message value negative!\"\n",
    "        assert (m < n),\"Message value too large. Must be less than %i.\" %n\n",
    "\n",
    "        # 2. Select random r where 0 < r < n\n",
    "        r = random.randrange(1,n)\n",
    "\n",
    "        # 3. Compute ciphertext as: c = g^m * r^n mod n^2\n",
    "        n2 = n**2\n",
    "        c = pow(g, m, n2) * pow(r, n, n2) % n2\n",
    "\n",
    "        return c\n",
    "\n",
    "\n",
    "    def dec(self, c):\n",
    "        n, g = self.pk\n",
    "        lambda_, mu = self.__sk\n",
    "        m = (L(pow(c, lambda_, n**2), n) * mu) % n\n",
    "        return m"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eba5da97",
   "metadata": {},
   "source": [
    "Example of Pallier Cryptosystem in use:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "137280c3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input message = 761138187 \n",
      "\n",
      "Cyphertext = 109555124925612349841764861225426080 \n",
      "\n",
      "Decrypted message = 761138187\n"
     ]
    }
   ],
   "source": [
    "security_param = 30\n",
    "pallier = Pallier(security_param)\n",
    "\n",
    "m = random.randrange(0, 2**security_param)\n",
    "print('Input message =', m, '\\n')\n",
    "\n",
    "c = pallier.enc(m)\n",
    "print('Cyphertext =', c, '\\n')\n",
    "\n",
    "d = pallier.dec(c)\n",
    "print('Decrypted message =', d)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "55f2e0a3",
   "metadata": {},
   "source": [
    "# Goldwasser-Micali (GM) Cryptosystem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c2396377",
   "metadata": {},
   "source": [
    "[Wikipedia page](https://en.wikipedia.org/wiki/Goldwasser%E2%80%93Micali_cryptosystem)\n",
    "\n",
    "[Original paper](https://doi.org/10.1145%2F800070.802212)\n",
    "\n",
    "Security based on the [Quadratic Residuosity Assumption](https://en.wikipedia.org/wiki/Quadratic_residuosity_problem)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "4c5e370b",
   "metadata": {},
   "outputs": [],
   "source": [
    "class GoldwasserMicali:\n",
    "    def __init__(self, security_param):\n",
    "        self.pk, self.__sk = self.gen(security_param)\n",
    "\n",
    "        \n",
    "    def gen(self, security_param):\n",
    "        # 1. Choose two large prime numbers\n",
    "        length = security_param\n",
    "        p = generate_big_prime(length)\n",
    "        q = generate_big_prime(length)\n",
    "        while p == q:\n",
    "            q = generate_big_prime(length)\n",
    "\n",
    "        # 2. Calculate N = pq\n",
    "        N = p * q\n",
    "\n",
    "        # 3. Find some non-residue x such that the Legendre symbols satisfy (x/p) = (x/q) = -1\n",
    "        #    and hence the Jacobi symbol (x/N) = +1\n",
    "        #    (if N is a Blum integer, x = N - 1 satisfies this)\n",
    "        x = random.randrange(1, N)\n",
    "        while legendre(x, p) != -1 or legendre(x, q) != -1:\n",
    "            x = random.randrange(1, N)\n",
    "\n",
    "        # Set the public key and secret key\n",
    "        pk = (x, N)\n",
    "        sk = (p, q)\n",
    "        return pk, sk\n",
    "\n",
    "    \n",
    "    def enc(self, m):\n",
    "        x, N = self.pk\n",
    "\n",
    "        # 1. Encode m as a string of bits (m_1, ... , m_n)\n",
    "        m = bin(m)[2:]\n",
    "\n",
    "        # 2. For every bit m_i, generate a random y_i in Z_N^*.\n",
    "        #    c_i = (y_i)^2 * x^{m_i} mod N\n",
    "        c = []\n",
    "        for i in m:\n",
    "            m_i = int(i)\n",
    "            y_i = random.randrange(1,N)\n",
    "            while math.gcd(y_i, N) != 1:\n",
    "                y_i = random.randrange(1,N)\n",
    "            c_i = (pow(y_i, 2, N) * pow(x, m_i, N)) % N\n",
    "\n",
    "            # 3. Ciphertext c = (c_1, ... , c_n)\n",
    "            c.append(c_i)\n",
    "\n",
    "        return c\n",
    "\n",
    "    \n",
    "    def dec(self, c):\n",
    "        x, N = self.pk\n",
    "        p, q = self.__sk\n",
    "\n",
    "        # 1. For each i, using the prime factorization (p, q), determine whether the value c_i is a quadratic residue;\n",
    "        #    if so, m_i = 0, otherwise m_i = 1\n",
    "        #    c_i is a quadratic residue iff the c_i is a quadratic residue mod p and mod q\n",
    "        m = ''\n",
    "        for c_i in c:\n",
    "            if legendre(c_i, p) == 1 and legendre(c_i, q) == 1:\n",
    "                m += '0'\n",
    "            else:\n",
    "                m += '1'\n",
    "\n",
    "        return int(m, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56a73525",
   "metadata": {},
   "source": [
    "Example of Goldwasser-Micali Cryptosystem in use:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "5e4e4492",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input message = 941874103 \n",
      "\n",
      "Cyphertext = [382020139260115268, 57497093849027319, 280740274815503148, 86693635347503557, 447504030744685225, 85416634923437642, 19086356121398640, 434213616631917867, 234609333059313903, 136071047558476232, 59886604096816265, 194429624673525354, 72132123946678472, 44682346660034087, 50414680686547842, 188378195220825182, 207300300979643235, 229955957290367778, 90626161477678001, 112588761571657290, 265842209301465280, 414027469919845251, 233471137744709290, 454511551073634405, 352346127163188498, 341262052259981481, 404349022919723902, 343255642960993637, 8345928842247099, 318424249174729046] \n",
      "\n",
      "Decrypted message = 941874103\n"
     ]
    }
   ],
   "source": [
    "security_param = 30\n",
    "gm = GoldwasserMicali(security_param)\n",
    "\n",
    "m = random.randrange(0, 2**security_param)\n",
    "print('Input message =', m, '\\n')\n",
    "\n",
    "c = gm.enc(m)\n",
    "print('Cyphertext =', c, '\\n')\n",
    "\n",
    "d = gm.dec(c)\n",
    "print('Decrypted message =', d)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "94fbd7a6",
   "metadata": {},
   "source": [
    "# Schmidt-Samoa Cryptosystem\n",
    "\n",
    "[Wikipedia page](https://en.wikipedia.org/wiki/Schmidt-Samoa_cryptosystem)\n",
    "\n",
    "[Original paper](https://eprint.iacr.org/2005/278.pdf)\n",
    "\n",
    "Security based on the hardness of [Integer Factorization](https://en.wikipedia.org/wiki/Integer_factorization).\n",
    "\n",
    "NOTE: Plaintext space is $\\mathbb{Z}_{pq}$, ciphertext space is $\\mathbb{Z}_{p^2q}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "0c95faf5",
   "metadata": {},
   "outputs": [],
   "source": [
    "class SchmidtSamoa:\n",
    "    def __init__(self, security_param):\n",
    "        self.pk, self.__sk = self.gen(security_param)\n",
    "\n",
    "        \n",
    "    def gen(self, security_param):\n",
    "        # 1. Choose two large distinct prime numbers\n",
    "        length = security_param\n",
    "        p = generate_big_prime(length)\n",
    "        q = generate_big_prime(length)\n",
    "        while p == q:\n",
    "            q = generate_big_prime(length)\n",
    "\n",
    "        # 2. Calculate N = p^2 * q, n = p*q\n",
    "        N = pow(p, 2) * q\n",
    "        n = p * q\n",
    "\n",
    "        # 3. Compute d = N^{-1} mod lcm(p-1, q-1)\n",
    "        mod = math.lcm(p - 1, q - 1)\n",
    "        d = modinv(N, mod)\n",
    "        \n",
    "        # Set the public key and secret key\n",
    "        pk = N\n",
    "        sk = d, n\n",
    "        return pk, sk\n",
    "\n",
    "    \n",
    "    def enc(self, m):\n",
    "        N = self.pk\n",
    "\n",
    "        # Compute ciphertext c = m^N mod N\n",
    "        c = pow(m, N, N)\n",
    "\n",
    "        return c\n",
    "\n",
    "    \n",
    "    def dec(self, c):\n",
    "        N = self.pk\n",
    "        d, n = self.__sk\n",
    "\n",
    "        # Compute plaintext as m = c^d mod pq\n",
    "        m = pow(c, d, n)\n",
    "\n",
    "        return m"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49178b90",
   "metadata": {},
   "source": [
    "Example of Schmidt-Samoa Cryptosystem in use:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "257d6305",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input message = 199676316 \n",
      "\n",
      "Cyphertext = 430821789424431928636142144 \n",
      "\n",
      "Decrypted message = 199676316\n"
     ]
    }
   ],
   "source": [
    "security_param = 30\n",
    "ss = SchmidtSamoa(security_param)\n",
    "\n",
    "m = random.randrange(0, 2**security_param)\n",
    "print('Input message =', m, '\\n')\n",
    "\n",
    "c = ss.enc(m)\n",
    "print('Cyphertext =', c, '\\n')\n",
    "\n",
    "d = ss.dec(c)\n",
    "print('Decrypted message =', d)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "37fbe672",
   "metadata": {},
   "source": [
    "# Rabin Cryptosystem\n",
    "\n",
    "[Wikipedia page](https://en.wikipedia.org/wiki/Rabin_cryptosystem)\n",
    "\n",
    "[Original paper](http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-212.pdf)\n",
    "\n",
    "Security based on the hardness of [Integer Factorization](https://en.wikipedia.org/wiki/Integer_factorization).\n",
    "\n",
    "NOTE: Not CCA secure"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "id": "05d998e8",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Rabin:\n",
    "    def __init__(self, security_param):\n",
    "        self.pk, self.__sk = self.gen(security_param)\n",
    "\n",
    "        \n",
    "    def gen(self, security_param):\n",
    "        # 1. Choose two large distinct prime numbers that are equivalent to 3 mod 4\n",
    "        length = security_param\n",
    "        \n",
    "        p = generate_big_prime(length)\n",
    "        while p % 4 != 3:\n",
    "            p = generate_big_prime(length)\n",
    "            \n",
    "        q = generate_big_prime(length)\n",
    "        while p == q or q % 4 != 3:\n",
    "            q = generate_big_prime(length)\n",
    "\n",
    "        # 2. Calculate n = p*q\n",
    "        n = p * q\n",
    "        \n",
    "        # Set the public key and secret key\n",
    "        pk = n\n",
    "        sk = p, q\n",
    "        return pk, sk\n",
    "\n",
    "    \n",
    "    def enc(self, m):\n",
    "        # In reality, m should be converted to a number m' < n using a reversible mapping,\n",
    "        # but we can also just restrict our message space to be Z_n\n",
    "        \n",
    "        n = self.pk\n",
    "\n",
    "        # Compute ciphertext c = M^2 mod n\n",
    "        c = pow(m, 2, n)\n",
    "\n",
    "        return c\n",
    "\n",
    "    \n",
    "    def dec(self, c):\n",
    "        n = self.pk\n",
    "        p, q = self.__sk\n",
    "        \n",
    "        # 1. Compute the square root of c mod p and q\n",
    "        m_p = pow(c, (p + 1)//4, p)\n",
    "        m_q = pow(c, (q + 1)//4, q)\n",
    "        \n",
    "        # 2. Use the extended Euclidean algorithm to find y_p and y_q such that y_p * p + y_q * q = 1.\n",
    "        g, y_p, y_q = egcd(p, q) # where g = gcd(p, q) = 1\n",
    "        \n",
    "        # 3. Use the Chinese remainder theorem to find the four square roots of c mod n:\n",
    "        r_1 = (y_p * p * m_q + y_q * q * m_p) % n\n",
    "        r_2 = (n - r_1) % n\n",
    "        r_3 = (y_p * p * m_q - y_q * q * m_p) % n\n",
    "        r_4 = (n - r_3) %n\n",
    "\n",
    "        # The original plaintext m is one of these four values\n",
    "        return r_1, r_2, r_3, r_4"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "60b99cd0",
   "metadata": {},
   "source": [
    "Example of Rabin Cryptosystem in use:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "id": "b75dbf2b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input message = 869271000680915719 \n",
      "\n",
      "Cyphertext = 125750576587579010 \n",
      "\n",
      "Decrypted message is one of these: (522067691616414, 869271000680915719, 512825093095836574, 356967975276695559)\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "security_param = 30\n",
    "rabin = Rabin(security_param)\n",
    "n = rabin.pk\n",
    "\n",
    "m = random.randrange(0, n)\n",
    "print('Input message =', m, '\\n')\n",
    "\n",
    "c = rabin.enc(m)\n",
    "print('Cyphertext =', c, '\\n')\n",
    "\n",
    "d = rabin.dec(c)\n",
    "print('Decrypted message is one of these:', d)\n",
    "print(m in d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "13ee88e4",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.10.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}