python/homomorphic/Naccache–Stern.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import sympy\n",
    "from sympy.ntheory.modular import solve_congruence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# pick a family of small primes\n",
    "prime_set = [3,5,7,11,13,17]\n",
    "k = len(prime_set)\n",
    "\n",
    "assert all(sympy.isprime(prime) is True for prime in prime_set) is True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# divide the set in half and find products of primes\n",
    "u = 1; v = 1\n",
    "\n",
    "for i, prime in enumerate(prime_set):\n",
    "    if i < len(prime_set)/2:\n",
    "        u = u * prime\n",
    "    else:\n",
    "        v = v * prime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# product of all primes\n",
    "sigma = u*v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "while True:\n",
    "    # pick large prime numbers\n",
    "    a = sympy.randprime(100, 200)\n",
    "    b = sympy.randprime(100, 200)\n",
    "\n",
    "    assert sympy.isprime(a)\n",
    "    assert sympy.isprime(b)\n",
    "\n",
    "    # calculate two primes from chosen ones\n",
    "    p = (2*a*u)+1\n",
    "    q = (2*b*v)+1\n",
    "\n",
    "    if sympy.isprime(p) and sympy.isprime(q):\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n=30618288353, phi=30617326740\n"
     ]
    }
   ],
   "source": [
    "n = p*q\n",
    "phi = (p-1)*(q-1)\n",
    "print(f\"{n=}, {phi=}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# choose a generator. its order must be phi(n)/4?\n",
    "g = 131\n",
    "assert g < n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "public keys: 255255, 30618288353, 131\n",
      "private keys: 32971, 928643\n"
     ]
    }
   ],
   "source": [
    "print(f\"public keys: {sigma}, {n}, {g}\")\n",
    "print(f\"private keys: {p}, {q}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# encryption"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ciphertext is 11140580205\n"
     ]
    }
   ],
   "source": [
    "m = 202\n",
    "assert m < sigma\n",
    "\n",
    "def encrypt(m):\n",
    "    return pow(g, m, n)\n",
    "\n",
    "c = encrypt(m)\n",
    "print(f\"ciphertext is {c}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# decryption"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decrypt(c):\n",
    "    remainders = []\n",
    "    for i, prime in enumerate(prime_set):\n",
    "        ci = pow(c, int(phi/prime), n)\n",
    "\n",
    "        for j in range(0, prime):\n",
    "            if ci == pow(g, int((j*phi)/prime), n):\n",
    "                # print(f\"m_{i} = {j}\")\n",
    "                remainders.append(j)\n",
    "    \n",
    "    congruences = []\n",
    "    for i in range(0, k):\n",
    "        print(f\"m mod {prime_set[i]} = {remainders[i]}\")\n",
    "        congruences.append((remainders[i], prime_set[i]))\n",
    "    \n",
    "    # chinese remainder problem\n",
    "    ms = solve_congruence(*congruences)\n",
    "    ms = [i for i in ms if i < sigma]\n",
    "    m = ms[0]\n",
    "    print(f\"Then m = {m}\")\n",
    "    return m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "m mod 3 = 1\n",
      "m mod 5 = 2\n",
      "m mod 7 = 6\n",
      "m mod 11 = 4\n",
      "m mod 13 = 7\n",
      "m mod 17 = 15\n",
      "Then m = 202\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "202"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "decrypt(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# homomorphic features"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "m1 = 100\n",
    "m2 = 200\n",
    "\n",
    "c1 = encrypt(m1)\n",
    "c2 = encrypt(m2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(c1*c2) % n == encrypt(m1+m2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "m mod 3 = 0\n",
      "m mod 5 = 0\n",
      "m mod 7 = 6\n",
      "m mod 11 = 3\n",
      "m mod 13 = 1\n",
      "m mod 17 = 11\n",
      "Then m = 300\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "decrypt((c1*c2) % n) == m1+m2"
   ]
  }
 ],
 "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": 2
}