python/homomorphic/Benaloh.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "9a16b73d",
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import gcd\n",
    "import random\n",
    "import sympy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "b21a6ab2",
   "metadata": {},
   "outputs": [],
   "source": [
    "p = 10007\n",
    "q = 191"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "402578d1",
   "metadata": {},
   "outputs": [],
   "source": [
    "assert sympy.isprime(p)\n",
    "assert sympy.isprime(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "7c705f51",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = p*q\n",
    "phi = (p-1)*(q-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "f02c9c98",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1911337, 1901140)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n, phi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "eb42e937",
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_block_size():\n",
    "    while True:\n",
    "        r = random.randint(2, n)\n",
    "\n",
    "        if (\n",
    "            # r should divide p-1 without remainder\n",
    "            (p-1) % r == 0 \n",
    "            # r and (p - 1) / r must be coprimes\n",
    "            and gcd(r, int((p - 1) / r)) == 1\n",
    "            # r and q-1 must be coprimes\n",
    "            and gcd(r, q - 1)\n",
    "        ) == 1:\n",
    "            break\n",
    "    return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "fe70d731",
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_keys():    \n",
    "    while True:\n",
    "        r = generate_block_size()\n",
    "        \n",
    "        y = random.randint(2, n)\n",
    "        if gcd(y, n) != 1:\n",
    "            continue\n",
    "        \n",
    "        # to guarantee correct decryption\n",
    "        prime_factors = sympy.factorint(r).keys()\n",
    "        \n",
    "        # If r is composite, it was pointed out by Fousse et al. in 2011\n",
    "        # that the above conditions are insufficient to guarantee correct decryption\n",
    "        decryption_guaranteed = True\n",
    "        for prime_factor in prime_factors:\n",
    "            # none of r's prime factor should satisfy the condition\n",
    "            if pow(y, int(phi/prime_factor), n) == 1:\n",
    "                decryption_guaranteed = False\n",
    "        if decryption_guaranteed is False:\n",
    "            # regenerate keys\n",
    "            continue\n",
    "        \n",
    "        x = pow(y, int(phi/r), n)        \n",
    "        if x != 1:\n",
    "            break\n",
    "            \n",
    "    return r, x, y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "d6f4c5ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "r, x, y = generate_keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "06ba9c1d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1361714, 5003, 1911337)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# public key\n",
    "y, r, n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "0158c2f4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10007, 191, 1901140, 1028154)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# private key\n",
    "p, q, phi, x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e826f76f",
   "metadata": {},
   "source": [
    "# encryption"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "1ac5446c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# message must be member of Zr\n",
    "m = 17\n",
    "\n",
    "if m >= r:\n",
    "    print(f\"Warning! plaintext {m} should be member of Z_{r} but it is greater.\")\n",
    "    m = m % r\n",
    "    print(f\"So, it is restored to {m}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "6b933cad",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "plaintext: 17\n"
     ]
    }
   ],
   "source": [
    "print(f\"plaintext: {m}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "50a1b0c7",
   "metadata": {},
   "outputs": [],
   "source": [
    "# random key for encryption\n",
    "while True:\n",
    "    u = random.randint(1, n)\n",
    "    if gcd(u, n) == 1:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "d1105c05",
   "metadata": {},
   "outputs": [],
   "source": [
    "def encrypt(m, u):\n",
    "    return (pow(y, m, n) * pow(u, r, n)) % n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "585b243a",
   "metadata": {},
   "outputs": [],
   "source": [
    "c = encrypt(m, u)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "0731c84f",
   "metadata": {},
   "outputs": [],
   "source": [
    "assert gcd(c, n) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "76278f75",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ciphertext is 1721828\n"
     ]
    }
   ],
   "source": [
    "print(f\"ciphertext is {c}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f5c1f3e7",
   "metadata": {},
   "source": [
    "# decryption"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "acaa90b9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def decrypt(c):\n",
    "    a = pow(c, int(phi/r), n)\n",
    "\n",
    "    md = 0\n",
    "    while True:\n",
    "        if pow(x, md, n) == a:\n",
    "            break\n",
    "        md = md + 1\n",
    "    \n",
    "    return md"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "38090160",
   "metadata": {},
   "outputs": [],
   "source": [
    "m_prime = decrypt(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "53bbc817",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "restored plaintext is 17\n"
     ]
    }
   ],
   "source": [
    "print(f\"restored plaintext is {m_prime}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "31ad1cf0",
   "metadata": {},
   "outputs": [],
   "source": [
    "assert m_prime == m"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa370291",
   "metadata": {},
   "source": [
    "# Homomorphic Features of Benaloh Cryptosystem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "96daf1c5",
   "metadata": {},
   "outputs": [],
   "source": [
    "m1 = 10 % r\n",
    "u1 = random.randint(0, n)\n",
    "\n",
    "c1 = encrypt(m1, u1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "4841707a",
   "metadata": {},
   "outputs": [],
   "source": [
    "m2 = 17 % r\n",
    "u2 = random.randint(0, n)\n",
    "\n",
    "c2 = encrypt(m2, u2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "3dd76a6b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# multiplication of ciphertexts must be equal to encryption \n",
    "# of addition of plaintexts\n",
    "assert (c1 * c2) % n == encrypt(m1+m2, u1*u2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "ff2f3730",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# or deryption of multiplication of ciphertexts must be equal \n",
    "# to the addition of plaintext as well\n",
    "decrypt((c1 * c2) % n) == (m1+m2) % r "
   ]
  }
 ],
 "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.8.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}