Feige Fiat Shamir ZKP Scheme.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('p : ', 146715971)\n",
      "('q : ', 1420438457)\n",
      "n = 208401007464496747\n",
      "-------------------Iteration number 1------------------\n",
      "y^2 value to be checked = 140436635875085226\n",
      "One Iteration of the protocol ended.\n",
      "-------------------Iteration number 2------------------\n",
      "y^2 value to be checked = 58389631378839117\n",
      "One Iteration of the protocol ended.\n",
      "-------------------Iteration number 3------------------\n",
      "y^2 value to be checked = 100045907517066627\n",
      "One Iteration of the protocol ended.\n",
      "-------------------Iteration number 4------------------\n",
      "y^2 value to be checked = 152716804525263854\n",
      "One Iteration of the protocol ended.\n",
      "-------------------Iteration number 5------------------\n",
      "y^2 value to be checked = 51289082721150079\n",
      "One Iteration of the protocol ended.\n",
      "-------------------Iteration number 6------------------\n",
      "y^2 value to be checked = 107369114521425733\n",
      "One Iteration of the protocol ended.\n",
      "-------------------Iteration number 7------------------\n",
      "y^2 value to be checked = 190258694883471547\n",
      "One Iteration of the protocol ended.\n",
      "-------------------Iteration number 8------------------\n",
      "y^2 value to be checked = 198715157795777159\n",
      "One Iteration of the protocol ended.\n",
      "-------------------Iteration number 9------------------\n",
      "y^2 value to be checked = 93537618068837664\n",
      "One Iteration of the protocol ended.\n",
      "-------------------Iteration number 10------------------\n",
      "y^2 value to be checked = 97614567480700371\n",
      "One Iteration of the protocol ended.\n",
      "----------------------Ended------------------------\n",
      "Authentication Successful. Zero Knowledge Proof presented by Peggy was indeed correct.\n",
      "No information about the secret sk was leaked to Victor in this process.\n"
     ]
    }
   ],
   "source": [
    "# Sage Math Implementation of Feige Fiat Shamir Zero Knowledge Identification Scheme\n",
    "\n",
    "# To get a different random number everytime\n",
    "import time\n",
    "seed = int(round(time.time() * 10))\n",
    "\n",
    "\n",
    "# Generator for random number generation\n",
    "def gen_random_mod(k, modulus):\n",
    "    num = 0\n",
    "    while(num < k):\n",
    "        a = mod(gp.random(), modulus).lift()\n",
    "        while(gcd(a, modulus) != 1):\n",
    "            a = mod(gp.random(), modulus).lift()\n",
    "        yield a\n",
    "        num += 1\n",
    "\n",
    "class ZKP_Setup_TTP:\n",
    "    \n",
    "    def __init__(self, modbits, k, seed):\n",
    "        self.k = k\n",
    "        set_random_seed(seed)\n",
    "        current_randstate().set_seed_gp()\n",
    "        # use gp.random() to get prng random number\n",
    "        self.p = next_prime(2^modbits + gp.random())\n",
    "        print(\"p : \", self.p)\n",
    "        self.q = next_prime(2^modbits + gp.random())\n",
    "        print(\"q : \", self.q)\n",
    "        if self.p == self.q:\n",
    "            print(\"Primes are same, please run again\")\n",
    "        self.n = self.p*self.q\n",
    "        print(\"n = \"+str(self.n))\n",
    "        #a = [ i-1 for i in list(gen_random_mod(30, 3))]\n",
    "        self.a = list(gen_random_mod(k, self.n))\n",
    "        assert sum([gcd(i, self.n) for i in self.a]) == len(self.a)\n",
    "        #print(a)\n",
    "        self.asq = [i.powermod(2, self.n) for i in self.a]\n",
    "        #print(asq)\n",
    "        \n",
    "class ZKP_Peggy:\n",
    "    \n",
    "    def __init__(self, n, sk):\n",
    "        self.n = n\n",
    "        self.sk = sk\n",
    "        self.k = len(sk)\n",
    "        #print(self.sk)\n",
    "        \n",
    "    def x_compute(self):\n",
    "        sign = [ i-1 for i in list(gen_random_mod(1, 3))]\n",
    "        rlist = list(gen_random_mod(1, self.n))\n",
    "        self.r = rlist[0]\n",
    "        rsq = self.r.powermod(2, self.n)\n",
    "        if(sign[0] == 0):\n",
    "            return rsq\n",
    "        else:\n",
    "            return self.n-rsq\n",
    "        \n",
    "    def y_compute(self, alist):\n",
    "        y = mod(1, self.n)\n",
    "        y = y*self.r\n",
    "        for i in range(self.k):\n",
    "            y = y*self.sk[i].powermod(alist[i], self.n)\n",
    "        y = y.lift()\n",
    "        assert y < self.n\n",
    "        return y\n",
    "        \n",
    "\n",
    "class ZKP_Victor:\n",
    "    \n",
    "    def __init__(self, n, vk):\n",
    "        self.n = n\n",
    "        self.vk = vk\n",
    "        self.k = len(vk)\n",
    "        #print(self.vk)\n",
    "        \n",
    "    def choice_a(self, x):\n",
    "        self.abort = 0\n",
    "        if x == 0:\n",
    "            self.abort = 1\n",
    "            return []\n",
    "        self.x = x\n",
    "        self.a = [ i-1 for i in list(gen_random_mod(k, 3))]\n",
    "        #print(self.a)\n",
    "        return self.a\n",
    "    \n",
    "    def authenticate(self, y):\n",
    "        ysq = y.powermod(2, self.n)\n",
    "        print(\"y^2 value to be checked = \" + str(ysq))\n",
    "        yrhs = mod(1, self.n)\n",
    "        yrhs = yrhs*self.x\n",
    "        for i in range(self.k):\n",
    "            yrhs = yrhs*self.vk[i].powermod(self.a[i], self.n)\n",
    "        yrhs = yrhs.lift()\n",
    "        if yrhs == ysq or yrhs == self.n-ysq:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1\n",
    "\n",
    "class ZKP_Protocol:\n",
    "    \n",
    "    def __init__(self, modbits, k, seed, iterations):\n",
    "        zkp_gen = ZKP_Setup_TTP(modbits, k, seed)\n",
    "        peggy = ZKP_Peggy(zkp_gen.n, zkp_gen.a)\n",
    "        victor = ZKP_Victor(zkp_gen.n, zkp_gen.asq)\n",
    "        #Now protocol begins\n",
    "        cnt = 0\n",
    "        abort = 0\n",
    "        while (cnt < iterations and abort == 0):\n",
    "            print(\"-------------------Iteration number \" + str(cnt+1) + \"------------------\")\n",
    "            x = peggy.x_compute()\n",
    "            alist = victor.choice_a(x)\n",
    "            if not alist:\n",
    "                print(\"x was 0, so cannot proceed! Authentication Fails.\")\n",
    "                abort = 1\n",
    "            else:\n",
    "                y = peggy.y_compute(alist)\n",
    "                abort = victor.authenticate(y)\n",
    "            print(\"One Iteration of the protocol ended.\")\n",
    "            if(abort == 1):\n",
    "                print(\"Failed at iteration \" + str(cnt+1))\n",
    "            cnt += 1\n",
    "        print(\"----------------------Ended------------------------\")\n",
    "        if abort == 0:\n",
    "            print(\"Authentication Successful. Zero Knowledge Proof presented by Peggy was indeed correct.\")\n",
    "            print(\"No information about the secret sk was leaked to Victor in this process.\")\n",
    "        elif abort == 1:\n",
    "            print(\"Authentication UNSUCCESSFUL! Zero Knowledge Proof presented by Peggy was indeed INCORRECT.\")\n",
    "        \n",
    "modbits = 12\n",
    "k = 10\n",
    "iterations = 10\n",
    "zkp = ZKP_Protocol(modbits, k, seed, iterations)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "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.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}