Cryptographic Primitives and Paillier Cryptosystem.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Working With Encrypted Data\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "## Simplified Symmetric Searchable Encryption\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Cryptographic Primitives\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Trapdoor for encrypted keyword: '7ac7c23a42bebb2d328d2869418c604b8a02dbd1e090717cfac8dfe431f658c3': 'a4b5c6'\n",
      "Trapdoor for encrypted keyword: '5404d16a19350e0f7f83dd6c0983dbb090aef12f5b6f74706d1bec85b7c7696d': 'd7e8f9'\n",
      "Trapdoor for encrypted keyword: 'c5c4e0fea918f6b7b8666c0871ec48d6fd52fb8e8ecc9b26a5a648d073cbf950': 'glh2i3'\n",
      "Trapdoor for encrypted keyword: 'dcfefe514bbf350ee6239984591e6c1dadc159febe791e0f12bc52c36935442b': 'j4k5l6'\n",
      "Trapdoor for encrypted keyword: '89542c7ec5bc0d758013cba83d5cca73cb7862dc1e2684710a9a67e91a684e8b': 'm7n8o9'\n",
      "'7ac7c23a42bebb2d328d2869418c604b8a02dbd1e090717cfac8dfe431f658c3': 'a4b5c6',\n",
      "'5404d16a19350e0f7f83dd6c0983dbb090aef12f5b6f74706d1bec85b7c7696d': 'd7e8f9',\n",
      "'c5c4e0fea918f6b7b8666c0871ec48d6fd52fb8e8ecc9b26a5a648d073cbf950': 'glh2i3',\n",
      "'dcfefe514bbf350ee6239984591e6c1dadc159febe791e0f12bc52c36935442b': 'j4k5l6',\n",
      "'89542c7ec5bc0d758013cba83d5cca73cb7862dc1e2684710a9a67e91a684e8b': 'm7n8o9',\n"
     ]
    }
   ],
   "source": [
    "import hashlib\n",
    "\n",
    "# List of already encrypted keywords\n",
    "encrypted_keywords = ['a4b5c6', 'd7e8f9', 'glh2i3', 'j4k5l6', 'm7n8o9']\n",
    "\n",
    "# Function to perform SHA-256 hashing\n",
    "def sha256_hash(text):\n",
    "    m = hashlib.sha256()\n",
    "    m.update(text.encode('utf-8'))\n",
    "    return m.hexdigest()\n",
    "\n",
    "# Generate trapdoors by hashing the encrypted keywords\n",
    "trapdoors = [sha256_hash(keyword) for keyword in encrypted_keywords]\n",
    "\n",
    "# Print the trapdoors\n",
    "for i, trapdoor in enumerate(trapdoors):\n",
    "    print(f\"Trapdoor for encrypted keyword: '{trapdoor}': '{encrypted_keywords[i]}'\")\n",
    "\n",
    "# Print the trapdoors\n",
    "for i, trapdoor in enumerate(trapdoors):\n",
    "    print(f\"'{trapdoor}': '{encrypted_keywords[i]}',\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Data Queries Over Encrypted Keywords\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original Keyword: Keyword not found\n"
     ]
    }
   ],
   "source": [
    "def query_hashed_value(hashed_value):\n",
    "    if hashed_value in hashed_values:\n",
    "        return hashed_values[hashed_value]\n",
    "    else:\n",
    "        return \"Keyword not found\"\n",
    "\n",
    "hashed_values = {\n",
    "    '3ff7519ab2b2435f4a4706ad91c13baeca1da4e229da4b54b0bc1e0d238edf37': 'a9b8c7',\n",
    "'22baf57cd41eadfee6e8bf55b16543678377d81c1aee62e7ccccc52aa1847479': 'd6e5f4',\n",
    "'dabb9c562b8d41b5523d29b128974173a8e04d2d6c47ed7cf5f249a7fcd5a85e': 'g2h1i0',\n",
    "'b178892ea3902c2cac8d6cd06dc3e9a07d338cdc2fed7eb62c858369b6ab0e49': 'j3k2l1',\n",
    "'7753c82ec4d5bbae9366540d77f4587c006f0f021ec6b6bb729c9c74bef17b8b': 'm4n5o6',\n",
    "'1f2a286e4438c3a6cfa08289a7e398995e8c7542fd00e7cd76237af6bee7453e': 'p7q8r9',\n",
    "'0984cd8e2e3955d7ae0cf15aa29e082b994b5ed4bb47d94e2616c82525d13e86': 's0t9u8',\n",
    "'9dfe6fdc1c22d94191e62fc5bf36c950475e77138aa0324d5541ba68e6fef8c7': 'v1w2x3',\n",
    "'9d33f52a4c79e267f57304cf4ec7f9052631a7bc8b905537b571b6df2d0229c0': 'y4z5a6',\n",
    "'b5021be1fb750b041260875c600f0c7816abcccab7ea6be0c9079502b72cf284': 'b9c8d7',\n",
    "'09a1985b4389c167b1dcd27361fa2f9fb4fb2e636ab3ccc5d11c73fb77e303bb': 'e2f3g4',\n",
    "'c3b5ef5ba3be457cbc0b9758a32d66efe2c093bdacdcb96e6e7c4dfa520c1db8': 'h5i6j7',\n",
    "'a862deec5346ba960eca70b7a2431b411475e015d6edfb3d4dcd8c8ebe39634f': 'k0l9m8',\n",
    "'8ff3b42d64e1c46691199f700c66d38c5035253897fe746fb19b6d949c49e917': 'n1o2p3',\n",
    "'a63c37d1d6531e72fbc4d838afe492124e14cd4ba20464fd39139ffc974f2f31': 'q4r5s6',\n",
    "'1638478bd91ff75133f5b20ac00fa274a5042ef239db5b04d99509760963e53b': 't7u8v9',\n",
    "'f09152f2b5c4e8e918b841379ad1fcb22da807f410e016e61968fd9307bd64d4': 'w0x9y8',\n",
    "'6f1f719bae613faed513669b32d967a8d8f65498700b95cfcd1ee574d60f1f9e': 'z7a6b5',\n",
    "'c2fa587c6298028e6da09dff4336f7b7619dcc6712ecc8b5ed2be4a8a414a899': 'c4d5e6',\n",
    "'01c1dcd2ba3677dac4f415cc98017c45e0d99faceb38eeb1944fa04e69e2e3bf': 'f7g8h9'\n",
    "}\n",
    "\n",
    "# Prompt participants with a hashed value\n",
    "hashed_query = \"2e9d85bf4d2a26efbfb1b21a6868baf4f1343b5b28b416232177826b3b6a47eb\"\n",
    "\n",
    "# Ask participants to run the query\n",
    "result = query_hashed_value(hashed_query)\n",
    "\n",
    "# Display the result\n",
    "print(\"Original Keyword:\", result)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "## Homomorphic Encryption\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### RSA Partially Homomorphic Multiplication\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Note: The below version is a simplified example for educational illustrative purposes\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "p: 31, q: 37, n: 1147, phi_n: 1080, e: 7, d: 463\n",
      "Encrypted m1: 326\n",
      "Encrypted m2: 1040\n",
      "Result of homomorphic multiplication: 675\n",
      "Decrypted result of multiplication: 12\n",
      "Result of plaintext multiplication: 12\n"
     ]
    }
   ],
   "source": [
    "# RSA Setup with explicit p and q\n",
    "p = 31  # a prime number\n",
    "q = 37  # another prime number\n",
    "\n",
    "# Check p and q are primes and distinct\n",
    "if not is_prime(p) or not is_prime(q) or p == q:\n",
    "    raise ValueError(\"Both p and q need to be distinct primes.\")\n",
    "\n",
    "n = p * q\n",
    "phi_n = (p-1) * (q-1)\n",
    "e = 2\n",
    "while gcd(e, phi_n) != 1:\n",
    "    e += 1\n",
    "\n",
    "d = mod(e, phi_n).inverse()  # Private exponent\n",
    "\n",
    "# Encryption function\n",
    "def encrypt_rsa(m, e, n):\n",
    "    return power_mod(m, e, n)\n",
    "\n",
    "# Decryption function\n",
    "def decrypt_rsa(c, d, n):\n",
    "    return power_mod(c, d, n)\n",
    "\n",
    "# Example usage\n",
    "m1 = 4\n",
    "m2 = 3\n",
    "\n",
    "# Encrypt\n",
    "c1 = encrypt_rsa(m1, e, n)\n",
    "c2 = encrypt_rsa(m2, e, n)\n",
    "\n",
    "# Homomorphic Multiplication\n",
    "c_mult = mod(c1 * c2, n)\n",
    "\n",
    "# Decrypt\n",
    "decrypted_mult = decrypt_rsa(c_mult, d, n)\n",
    "\n",
    "print(f\"p: {p}, q: {q}, n: {n}, phi_n: {phi_n}, e: {e}, d: {d}\")\n",
    "print(f\"Encrypted m1: {c1}\")\n",
    "print(f\"Encrypted m2: {c2}\")\n",
    "print(f\"Result of homomorphic multiplication: {c_mult}\")\n",
    "print(f\"Decrypted result of multiplication: {decrypted_mult}\")\n",
    "print(f\"Result of plaintext multiplication: {m1*m2}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "#### Paillier Cryptosystem Key Generation\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Valid lambda: 816\n",
      "Valid public key (n, g): (1751, 2789862)\n"
     ]
    }
   ],
   "source": [
    "from sage.all import gcd, IntegerModRing, lcm\n",
    "\n",
    "def generate_relatively_prime_g(n):\n",
    "    while True:\n",
    "        g = randint(2, n^2 - 1)  # Generate a random integer between 2 and n^2 - 1\n",
    "        if gcd(g, n^2) == 1:     # Check if 'g' is relatively prime to n^2\n",
    "            return g\n",
    "\n",
    "# Function to compute L(x)\n",
    "def L(x, n):\n",
    "    try:\n",
    "        return (x - 1) // n\n",
    "    except ZeroDivisionError:\n",
    "        return 0\n",
    "\n",
    "# Function to validate g\n",
    "def validate_g(g, lambda_, n, n_square):\n",
    "    L_value = L(power_mod(g, lambda_, n_square), n)\n",
    "    return L_value != 0 \n",
    "\n",
    "# Function to calculate lambda\n",
    "def calculate_lambda(p, q):\n",
    "    return lcm(p - 1, q - 1)\n",
    "\n",
    "# Function to find and validate g\n",
    "def find_valid_g_and_lambda(p, q, n):\n",
    "    lambda_ = calculate_lambda(p, q)\n",
    "    g = generate_relatively_prime_g(n) #g must be relatively prime to n*n\n",
    "    return lambda_, g\n",
    "\n",
    "# Define prime numbers for key generation\n",
    "p = 103  # First prime\n",
    "q = 17  # Second prime\n",
    "\n",
    "# Calculate n\n",
    "n = p * q\n",
    "\n",
    "# Find valid lambda and g\n",
    "lambda_, g = find_valid_g_and_lambda(p, q, n)\n",
    "\n",
    "print(f\"Valid lambda: {lambda_}\")\n",
    "print(f\"Valid public key (n, g): ({n}, {g})\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "#### Paillier Encryption of Data\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Encrypted plaintext c1: 91423\n",
      "Encrypted plaintext c2: 1923428\n",
      "Encrypted plaintext c3: 1481578\n"
     ]
    }
   ],
   "source": [
    "def paillier_encrypt(m, r, n, g):\n",
    "    n_squared = n^2\n",
    "    return (g^m * r^n) % n_squared  # Take the modulus n^2 here\n",
    "\n",
    "# Define public key parameters\n",
    "n = 1751  # Public modulus\n",
    "g = 49943352  # Public base\n",
    "\n",
    "# Define plaintexts and random numbers\n",
    "m1 = 5\n",
    "m2 = 10\n",
    "r1 = 7\n",
    "r2 = 11\n",
    "m3 = m1 + m2\n",
    "r3 = 5\n",
    "\n",
    "# Perform encryption\n",
    "c1 = paillier_encrypt(m1, r1, n, g)\n",
    "c2 = paillier_encrypt(m2, r2, n, g)\n",
    "c3 = paillier_encrypt(m3, r3, n, g)\n",
    "\n",
    "print(f\"Encrypted plaintext c1: {c1}\")\n",
    "print(f\"Encrypted plaintext c2: {c2}\")\n",
    "print(f\"Encrypted plaintext c3: {c3}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "#### Paillier Addition Over Encrypted Data\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Given encrypted value c1: 91423\n",
      "Given encrypted value c2: 1923428\n",
      "Result of Paillier addition (encrypted) ciphertext: 1202691\n"
     ]
    }
   ],
   "source": [
    "# Define Paillier addition function\n",
    "def paillier_addition(c1, c2, n):\n",
    "    c3 = (c1 * c2) % n^2\n",
    "    return c3\n",
    "\n",
    "# Given Paillier public key parameters\n",
    "n = 1751\n",
    "\n",
    "# Given encrypted values (ciphertexts)\n",
    "c1 = 91423 # Replace with the actual encrypted value for operand 1\n",
    "c2 = 1923428 # Replace with the actual encrypted value for operand 2\n",
    "\n",
    "# Perform Paillier addition\n",
    "ct = paillier_addition(c1, c2, n)\n",
    "\n",
    "print(f\"Given encrypted value c1: {c1}\")\n",
    "print(f\"Given encrypted value c2: {c2}\")\n",
    "print(f\"Result of Paillier addition (encrypted) ciphertext: {ct}\")\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "argv": [
    "sage-10.1",
    "--python",
    "-m",
    "sage.repl.ipython_kernel",
    "--matplotlib=inline",
    "-f",
    "{connection_file}"
   ],
   "display_name": "SageMath 10.1",
   "env": {
   },
   "language": "sagemath",
   "metadata": {
    "cocalc": {
     "description": "Open-source mathematical software system",
     "priority": 10,
     "url": "https://www.sagemath.org/"
    }
   },
   "name": "sage-10.1",
   "resource_dir": "/ext/jupyter/kernels/sage-10.1"
  },
  "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}