Paillier_Crypto.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Define Functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {},
   "outputs": [],
   "source": [
    "def PaillierEncrypt(m, n, g):\n",
    "    if m > n:\n",
    "        raise Exception(\"m is greater than n\")\n",
    "    r = 0\n",
    "    while r == 0:\n",
    "        r = ZZ.random_element(n)\n",
    "    a = power_mod(g, m, n^2)\n",
    "    b = power_mod(r, n, n^2)\n",
    "    return (a * b) % n^2\n",
    "\n",
    "def PaillierDecrypt(c):\n",
    "    if c == 0 or c > n^2:\n",
    "        raise Exception(\"c not in Z*n^2\")\n",
    "    j = power_mod(c, l, n^2)\n",
    "    i = (j-1) // n\n",
    "    return i*mu % n\n",
    "\n",
    "def PaillierSetup(p, q):\n",
    "    n = p*q\n",
    "    l = LCM(p-1, q-1)\n",
    "    gcd_pq = gcd(n, (p-1)*(q-1))\n",
    "    \n",
    "    if gcd_pq != 1:\n",
    "        raise Exception(\"gcd(p*q, (p-1)*(q-1)) is not 1\")\n",
    "\n",
    "    g = 0\n",
    "    while g == 0:\n",
    "        g = ZZ.random_element(n^2)\n",
    "\n",
    "    x = power_mod(g, l, n^2)\n",
    "    Lx = (x - 1) // n\n",
    "    mu = inverse_mod(Lx, n)\n",
    "    return (n,g,l,mu)\n",
    "\n",
    "def Encode(m):\n",
    "    m = str(m)\n",
    "    return sum(ord(m[i])*256^i for i in range(len(m)))\n",
    "\n",
    "def Decode(c):\n",
    "    c = Integer(c)\n",
    "    v = []\n",
    "    while c != 0:\n",
    "        v.append(chr(c % 256))\n",
    "        c //= 256\n",
    "    return \"\".join(v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Setup"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Public key: (4951760154835678088235319297, 12157316380842332127815027658171313756329623433454065373)\n",
      "Private key: (2305843009213693950, 4097652128932043684913954609)\n"
     ]
    }
   ],
   "source": [
    "p = 2^31-1\n",
    "q = 2^61-1\n",
    "n,g,l,mu = PaillierSetup(p, q)\n",
    "\n",
    "print(\"Public key: {}\".format((n,g)) )\n",
    "print(\"Private key: {}\".format((l, mu)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test Encrypt/Decrypt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hello World\n",
      "100\n"
     ]
    }
   ],
   "source": [
    "m = \"Hello World\"\n",
    "e_m = Encode(m)\n",
    "c = PaillierEncrypt(e_m, n, g)\n",
    "d_m = PallierDecrypt(c)\n",
    "\n",
    "print(Decode(d_m))\n",
    "\n",
    "m = 100\n",
    "c = PaillierEncrypt(m, n, g)\n",
    "print(PallierDecrypt(c))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test Homomorphic Ciphertext Addition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "m1 + m2 = 121\n",
      "c1 * c2 = 6212392697620324995125347471003475142548028240582872325\n",
      "Decrypted c_add: 121\n"
     ]
    }
   ],
   "source": [
    "m1 = 55\n",
    "m2 = 66\n",
    "print(\"m1 + m2 = {}\".format(m1 + m2))\n",
    "\n",
    "c1 = PaillierEncrypt(m1, n, g)\n",
    "c2 = PaillierEncrypt(m2, n, g)\n",
    "c_add = c1 * c2 % n^2\n",
    "print(\"c1 * c2 = {}\".format(c_add))\n",
    "\n",
    "c_add_dec = PaillierDecrypt(c_add)\n",
    "print(\"Decrypted c_add: {}\".format(c_add_dec))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test Homomorphic Plaintext Addition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "m1 + k = 60\n",
      "c1 * g^k % n^2 = 9495466230409339542186781159076937276842891489858114966\n",
      "Decrypted c_add: 60\n"
     ]
    }
   ],
   "source": [
    "k = 5\n",
    "print(\"m1 + k = {}\".format(m1 + k))\n",
    "\n",
    "c_add_p = (c1 * g^k) % n^2\n",
    "print(\"c1 * g^k % n^2 = {}\".format(c_add_p))\n",
    "\n",
    "c_add_p_dec = PaillierDecrypt(c_add_p)\n",
    "print(\"Decrypted c_add: {}\".format(c_add_p_dec))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test Homomorphic Multiplication"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "m1 * k = 275\n",
      "c1^k = 12305277194923270200335317408940480904325548858536473920\n",
      "Decrypted c_mul: 275\n"
     ]
    }
   ],
   "source": [
    "print(\"m1 * k = {}\".format(m1 * k))\n",
    "\n",
    "c_mul = power_mod(c1, k, n^2)\n",
    "print(\"c1^k = {}\".format(c_mul))\n",
    "\n",
    "c_mul_dec = PaillierDecrypt(c_mul)\n",
    "print(\"Decrypted c_mul: {}\".format(c_mul_dec))"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Raw Cell Format",
  "kernelspec": {
   "display_name": "SageMath 8.1",
   "language": "",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}