cookbook.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## VSS based SSS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Secret: 1234\n",
      "Shares:\n",
      "   (1, 95469)\n",
      "   (2, 96555)\n",
      "   (3, 4492)\n",
      "   (4, 19286)\n",
      "   (5, 40934)\n",
      "   (6, 69436)\n",
      "Secret recovered from minimum subset of shares: 1234\n",
      "Secret recovered from a different minimum subset of shares:  1234\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "The following Python implementation of Shamir's Secret Sharing is\n",
    "released into the Public Domain under the terms of CC0 and OWFa:\n",
    "https://creativecommons.org/publicdomain/zero/1.0/\n",
    "http:https://www.openwebfoundation.org/legal/the-owf-1-0-agreements/owfa-1-0\n",
    "\n",
    "See the bottom few lines for usage. Tested on Python 2 and 3.\n",
    "\"\"\"\n",
    "\n",
    "from __future__ import division\n",
    "from __future__ import print_function\n",
    "\n",
    "import random\n",
    "import functools\n",
    "\n",
    "# 12th Mersenne Prime\n",
    "# (for this application we want a known prime number as close as\n",
    "# possible to our security level; e.g.  desired security level of 128\n",
    "# bits -- too large and all the ciphertext is large; too small and\n",
    "# security is compromised)\n",
    "_PRIME = 100003 #2 ** 127 - 1\n",
    "# 13th Mersenne Prime is 2**521 - 1\n",
    "\n",
    "_RINT = functools.partial(random.SystemRandom().randint, 0)\n",
    "\n",
    "def _eval_at(poly, x, prime):\n",
    "    \"\"\"Evaluates polynomial (coefficient tuple) at x, used to generate a\n",
    "    shamir pool in make_random_shares below.\n",
    "    \"\"\"\n",
    "    accum = 0\n",
    "    for coeff in reversed(poly):\n",
    "        accum *= x\n",
    "        accum += coeff\n",
    "        accum %= prime\n",
    "    return accum\n",
    "\n",
    "def make_random_shares(secret, minimum, shares, prime=_PRIME):\n",
    "    \"\"\"\n",
    "    Generates a random shamir pool for a given secret, returns share points.\n",
    "    \"\"\"\n",
    "    if minimum > shares:\n",
    "        raise ValueError(\"Pool secret would be irrecoverable.\")\n",
    "    poly = [secret] + [_RINT(prime - 1) for i in range(minimum - 1)]\n",
    "    points = [(i, _eval_at(poly, i, prime))\n",
    "              for i in range(1, shares + 1)]\n",
    "    return points\n",
    "\n",
    "def _extended_gcd(a, b):\n",
    "    \"\"\"\n",
    "    Division in integers modulus p means finding the inverse of the\n",
    "    denominator modulo p and then multiplying the numerator by this\n",
    "    inverse (Note: inverse of A is B such that A*B % p == 1) this can\n",
    "    be computed via extended Euclidean algorithm\n",
    "    http:https://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Computation\n",
    "    \"\"\"\n",
    "    x = 0\n",
    "    last_x = 1\n",
    "    y = 1\n",
    "    last_y = 0\n",
    "    while b != 0:\n",
    "        quot = a // b\n",
    "        a, b = b, a % b\n",
    "        x, last_x = last_x - quot * x, x\n",
    "        y, last_y = last_y - quot * y, y\n",
    "    return last_x, last_y\n",
    "\n",
    "def _divmod(num, den, p):\n",
    "    \"\"\"Compute num / den modulo prime p\n",
    "\n",
    "    To explain what this means, the return value will be such that\n",
    "    the following is true: den * _divmod(num, den, p) % p == num\n",
    "    \"\"\"\n",
    "    inv, _ = _extended_gcd(den, p)\n",
    "    return num * inv\n",
    "\n",
    "def _lagrange_interpolate(x, x_s, y_s, p):\n",
    "    \"\"\"\n",
    "    Find the y-value for the given x, given n (x, y) points;\n",
    "    k points will define a polynomial of up to kth order.\n",
    "    \"\"\"\n",
    "    k = len(x_s)\n",
    "    assert k == len(set(x_s)), \"points must be distinct\"\n",
    "    def PI(vals):  # upper-case PI -- product of inputs\n",
    "        accum = 1\n",
    "        for v in vals:\n",
    "            accum *= v\n",
    "        return accum\n",
    "    nums = []  # avoid inexact division\n",
    "    dens = []\n",
    "    for i in range(k):\n",
    "        others = list(x_s)\n",
    "        cur = others.pop(i)\n",
    "        nums.append(PI(x - o for o in others))\n",
    "        dens.append(PI(cur - o for o in others))\n",
    "    den = PI(dens)\n",
    "    num = sum([_divmod(nums[i] * den * y_s[i] % p, dens[i], p)\n",
    "               for i in range(k)])\n",
    "    return (_divmod(num, den, p) + p) % p\n",
    "\n",
    "def recover_secret(shares, prime=_PRIME):\n",
    "    \"\"\"\n",
    "    Recover the secret from share points\n",
    "    (x, y points on the polynomial).\n",
    "    \"\"\"\n",
    "    if len(shares) < 3:\n",
    "        raise ValueError(\"need at least three shares\")\n",
    "    x_s, y_s = zip(*shares)\n",
    "    return _lagrange_interpolate(0, x_s, y_s, prime)\n",
    "\n",
    "def main():\n",
    "    \"\"\"Main function\"\"\"\n",
    "    secret = 1234\n",
    "    shares = make_random_shares(secret, minimum=3, shares=6)\n",
    "\n",
    "    print('Secret:',secret)\n",
    "    print('Shares:')\n",
    "    if shares:\n",
    "        for share in shares:\n",
    "            print('  ', share)\n",
    "\n",
    "    print('Secret recovered from minimum subset of shares:',\n",
    "          recover_secret(shares[:3]))\n",
    "    print('Secret recovered from a different minimum subset of shares: ',\n",
    "          recover_secret(shares[-3:]))\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import math\n",
    "from decimal import Decimal\n",
    "import time\n",
    "\n",
    "def isprime(n):\n",
    "    if n == 2:\n",
    "        return True\n",
    "    if n == 1 or n % 2 == 0:\n",
    "        return False\n",
    "    i = 3\n",
    "    while i <= math.sqrt(n):\n",
    "        if n % i == 0:\n",
    "            return False\n",
    "        i = i + 2\n",
    "    return True\n",
    "\n",
    "\n",
    "def initial(Z_lower=100):\n",
    "    # generate q bigger than z_lower\n",
    "    q = Z_lower\n",
    "    while True:\n",
    "        if isprime(q):\n",
    "            break\n",
    "        else:\n",
    "            q = q + 1\n",
    "    print(\"q = \" + str(q))\n",
    "    print(\"\\nq is prime\\n\")\n",
    "\n",
    "    # Find p and r\n",
    "    r = 1\n",
    "    while True:\n",
    "        p = r * q + 1\n",
    "        if isprime(p):\n",
    "            print(\"r = \" + str(r))\n",
    "            print(\"p = \" + str(p))\n",
    "            print(\"\\np is prime\\n\")\n",
    "            break\n",
    "        r = r + 1\n",
    "\n",
    "    # Compute elements of Z_p*\n",
    "    Z_p_star = []\n",
    "    for i in range(0, p):\n",
    "        if (math.gcd(i, p) == 1):\n",
    "            Z_p_star.append(i)\n",
    "\n",
    "    # print(\"Z_p* = \")\n",
    "    # print(Z_p_star) # , len(Z_p_star) same length, i.e. range(p)\n",
    "\n",
    "    # Compute elements of G = {h^r mod p | h in Z_p*}\n",
    "    G = []\n",
    "    for i in Z_p_star:\n",
    "        G.append(i ** r % p)\n",
    "\n",
    "    G = list(set(G))\n",
    "    G.sort()\n",
    "    # print(\"\\nG = \")\n",
    "    # print(G)\n",
    "    # print(\"Order of G is \" + str(len(G)) + \". This must be equal to q.\")\n",
    "\n",
    "    # Since the order of G is prime, any element of G except 1 is a generator\n",
    "    g = random.choice(list(filter(lambda g: g != 1, G)))\n",
    "    print(\"\\ng = \" + str(g) + \"\\n\")\n",
    "\n",
    "    return p, q, r, g\n",
    "\n",
    "def generate_shares(n, t, secret, p, q, r, g, idxs):\n",
    "    if secret==0: secret=1 # one exception after quantization\n",
    "    assert secret >= 1 and secret <= q, \"secret not in range\"\n",
    "\n",
    "    FIELD_SIZE = q\n",
    "    coefficients = coeff(t, secret, FIELD_SIZE)\n",
    "    users = list(idxs) # users are to recieve the shares\n",
    "    assert n==len(users), \"these two number should be identical\"\n",
    "\n",
    "    shares = []\n",
    "    for i in users:\n",
    "        f_i = f(i, coefficients, q)\n",
    "        shares.append((i, f_i))\n",
    "\n",
    "    commitments = commitment(coefficients, g, p)\n",
    "    verifications = []\n",
    "    for i in users:\n",
    "        # check1 = g ** shares[i-1][1] % p\n",
    "        # check1 = g ** share_ith(shares, i) % p\n",
    "        check1 = quick_pow(g, share_ith(shares, i), p)\n",
    "        check2 = verification(g, commitments, i, p)\n",
    "        verifications.append(check2)\n",
    "        if check1 == check2:\n",
    "            pass\n",
    "        else:\n",
    "            print(\"checking fails with:\", check1, check2)\n",
    "\n",
    "    return shares, commitments, verifications\n",
    "\n",
    "def share_ith(shares, i):\n",
    "    for share in shares:\n",
    "        if share[0] == i:\n",
    "            return share[1]\n",
    "    return None\n",
    "\n",
    "def coeff(t, secret, FIELD_SIZE):\n",
    "    coeff = [random.randrange(0, FIELD_SIZE) for _ in range(t - 1)]\n",
    "    coeff.append(secret)  # a0 is secret\n",
    "    return coeff\n",
    "\n",
    "def f(x, coefficients, q):\n",
    "    y = Decimal('0')\n",
    "    for coefficient_index, coefficient_value in enumerate(coefficients[::-1]):\n",
    "        y += (Decimal(str(x)) ** Decimal(str(coefficient_index)) * Decimal(str(coefficient_value)))\n",
    "        y = Decimal(int(y)%q)\n",
    "    return int(y)\n",
    "\n",
    "\n",
    "def commitment(coefficients, g, p):\n",
    "    commitments = []\n",
    "    for coefficient_index, coefficient_value in enumerate(coefficients[::-1]):\n",
    "        c = g ** coefficient_value % p\n",
    "        # c = quick_pow(g,coefficient_value,p)\n",
    "        commitments.append(c)\n",
    "    return commitments\n",
    "\n",
    "\n",
    "def verification(g, commitments, i, p):\n",
    "    v = 1\n",
    "    for k, c in enumerate(commitments):\n",
    "        v = v * (c) ** (i ** k) % p\n",
    "        # v = v * quick_pow(c,i ** k,p) % p\n",
    "    return v\n",
    "\n",
    "\n",
    "def quick_pow(a, b, q):  # compute a^b mod q, in a faster way\n",
    "    temp = 1\n",
    "    for i in range(1, b + 1):\n",
    "        temp = temp * a % q\n",
    "    return temp % q\n",
    "\n",
    "\n",
    "def reconstruct_secret(pool, q):\n",
    "    x_s,y_s = [],[]\n",
    "    for share in pool:\n",
    "        x_s.append(share[0])\n",
    "        y_s.append(share[1])\n",
    "    out = _lagrange_interpolate(0, x_s, y_s, q)\n",
    "    return out\n",
    "\n",
    "def _lagrange_interpolate(x, x_s, y_s, p):\n",
    "    \"\"\"\n",
    "    Find the y-value for the given x, given n (x, y) points;\n",
    "    k points will define a polynomial of up to kth order.\n",
    "    \"\"\"\n",
    "    k = len(x_s)\n",
    "    assert k == len(set(x_s)), \"points must be distinct\"\n",
    "    def PI(vals):  # upper-case PI -- product of inputs\n",
    "        accum = 1\n",
    "        for v in vals:\n",
    "            accum *= v\n",
    "        return accum\n",
    "    nums = []  # avoid inexact division\n",
    "    dens = []\n",
    "    for i in range(k):\n",
    "        others = list(x_s)\n",
    "        cur = others.pop(i)\n",
    "        nums.append(PI(x - o for o in others))\n",
    "        dens.append(PI(cur - o for o in others))\n",
    "    den = PI(dens)\n",
    "    num = sum([_divmod(nums[i] * den * y_s[i] % p, dens[i], p)\n",
    "               for i in range(k)])\n",
    "    return (_divmod(num, den, p) + p) % p\n",
    "\n",
    "def _extended_gcd(a, b):\n",
    "    \"\"\"\n",
    "    Division in integers modulus p means finding the inverse of the\n",
    "    denominator modulo p and then multiplying the numerator by this\n",
    "    inverse (Note: inverse of A is B such that A*B % p == 1) this can\n",
    "    be computed via extended Euclidean algorithm\n",
    "    http:https://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Computation\n",
    "    \"\"\"\n",
    "    x = 0\n",
    "    last_x = 1\n",
    "    y = 1\n",
    "    last_y = 0\n",
    "    while b != 0:\n",
    "        quot = a // b\n",
    "        a, b = b, a % b\n",
    "        x, last_x = last_x - quot * x, x\n",
    "        y, last_y = last_y - quot * y, y\n",
    "    return last_x, last_y\n",
    "\n",
    "def _divmod(num, den, p):\n",
    "    \"\"\"Compute num / den modulo prime p\n",
    "\n",
    "    To explain what this means, the return value will be such that\n",
    "    the following is true: den * _divmod(num, den, p) % p == num\n",
    "    \"\"\"\n",
    "    inv, _ = _extended_gcd(den, p)\n",
    "    return num * inv\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "========Main VSS Starts==========\n",
      "q = 100003\n",
      "\n",
      "q is prime\n",
      "\n",
      "r = 42\n",
      "p = 4200127\n",
      "\n",
      "p is prime\n",
      "\n",
      "\n",
      "g = 2147431\n",
      "\n",
      "Original Secret: 1243\n",
      "10 5 1243 4200127 100003 42 2147431 [9, 3, 7, 8, 4, 6, 5, 2, 1, 10]\n",
      "Shares: (9, 18120), (3, 28819), (7, 93979), (8, 90164), (4, 54005), (6, 26763), (5, 62912), (2, 93326), (1, 30681), (10, 57847)\n",
      "Commitments: 1761168, 2124748, 1050745, 1380806, 832437\n",
      "verifications: 1190454, 4151512, 2634972, 1383553, 4013481, 3655039, 1539058, 521965, 3284121, 3424064\n",
      "Combining shares: (7, 93979), (5, 62912), (10, 57847), (9, 18120), (1, 30681)\n",
      "reconstruct_secret: 1243\n",
      "time cost in second: 5.674405813217163\n"
     ]
    }
   ],
   "source": [
    "# Driver code\n",
    "if __name__ == '__main__':\n",
    "    # initialization\n",
    "    time_start = time.time()\n",
    "    print(\"========Main VSS Starts==========\")\n",
    "    p,q,r,g = initial(10**5)\n",
    "\n",
    "    # Secret taken from the group Z_q* \n",
    "    t, n = 5, 10\n",
    "    secret = 1243\n",
    "    print(f'Original Secret: {secret}')\n",
    "\n",
    "    # Phase I: Generation of shares\n",
    "    users = [9, 3, 7, 8, 4, 6, 5, 2, 1, 10]\n",
    "    print(n, t, secret, p, q, r, g, users)\n",
    "    shares, commitments, verifications= generate_shares(n, t, secret, p, q, r, g, users)\n",
    "    print(f'Shares: {\", \".join(str(share) for share in shares)}')\n",
    "    print(f'Commitments: {\", \".join(str(commitment) for commitment in commitments)}')\n",
    "    print(f'verifications: {\", \".join(str(verification) for verification in verifications)}')\n",
    "\n",
    "    # Phase II: Secret Reconstruction\n",
    "    # Picking t shares randomly for reconstruction\n",
    "    pool = random.sample(shares, t)\n",
    "    print(f'Combining shares: {\", \".join(str(share) for share in pool)}')\n",
    "    secret_reconstructed = reconstruct_secret(pool, q)\n",
    "    print(\"reconstruct_secret:\",secret_reconstructed)\n",
    "\n",
    "    time_end = time.time()\n",
    "    print('time cost in second:', time_end-time_start)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## LCC"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isprime(n):\n",
    "    if n == 2:\n",
    "        return True\n",
    "    if n == 1 or n % 2 == 0:\n",
    "        return False\n",
    "    i = 3\n",
    "    while i <= math.sqrt(n):\n",
    "        if n % i == 0:\n",
    "            return False\n",
    "        i = i + 2\n",
    "    return True\n",
    "\n",
    "\n",
    "def initial(Z_lower=100):\n",
    "    # generate q bigger than z_lower\n",
    "    q = Z_lower\n",
    "    while True:\n",
    "        if isprime(q):\n",
    "            break\n",
    "        else:\n",
    "            q = q + 1\n",
    "    print(\"q = \" + str(q))\n",
    "    print(\"\\nq is prime\\n\")\n",
    "\n",
    "    # Find p and r\n",
    "    r = 1\n",
    "    while True:\n",
    "        p = r * q + 1\n",
    "        if isprime(p):\n",
    "            print(\"r = \" + str(r))\n",
    "            print(\"p = \" + str(p))\n",
    "            print(\"\\np is prime\\n\")\n",
    "            break\n",
    "        r = r + 1\n",
    "\n",
    "    # Compute elements of Z_p*\n",
    "    Z_p_star = []\n",
    "    for i in range(0, p):\n",
    "        if (math.gcd(i, p) == 1):\n",
    "            Z_p_star.append(i)\n",
    "\n",
    "    # print(\"Z_p* = \")\n",
    "    # print(Z_p_star) # , len(Z_p_star) same length, i.e. range(p)\n",
    "\n",
    "    # Compute elements of G = {h^r mod p | h in Z_p*}\n",
    "    G = []\n",
    "    for i in Z_p_star:\n",
    "        G.append(i ** r % p)\n",
    "\n",
    "    G = list(set(G))\n",
    "    G.sort()\n",
    "    # print(\"\\nG = \")\n",
    "    # print(G)\n",
    "    # print(\"Order of G is \" + str(len(G)) + \". This must be equal to q.\")\n",
    "\n",
    "    # Since the order of G is prime, any element of G except 1 is a generator\n",
    "    g = random.choice(list(filter(lambda g: g != 1, G)))\n",
    "    print(\"\\ng = \" + str(g) + \"\\n\")\n",
    "\n",
    "    return p, q, r, g\n",
    "\n",
    "\n",
    "def generate_shares(N, T, K, secrets, p, q, r, g, alphas, betas):\n",
    "    for secret in secrets:\n",
    "        assert secret >= 1 and secret <= q, \"secret not in range\"\n",
    "\n",
    "    FIELD_SIZE = q\n",
    "    noises = [random.randrange(0, FIELD_SIZE) for _ in range(T)]\n",
    "    \n",
    "    shares = []\n",
    "    for alpha in alphas:\n",
    "        # y = f(alpha, secrets, noises, betas, q)\n",
    "        y = _lagrange_interpolate(alpha, betas, secrets + noises, q)\n",
    "        shares.append((alpha, y))\n",
    "\n",
    "#     commitments = commitment(coefficients, g, p)\n",
    "#     verifications = []\n",
    "#     for i in users:\n",
    "#         # check1 = g ** shares[i-1][1] % p\n",
    "#         # check1 = g ** share_ith(shares, i) % p\n",
    "#         check1 = quick_pow(g, share_ith(shares, i), p)\n",
    "#         check2 = verification(g, commitments, i, p)\n",
    "#         verifications.append(check2)\n",
    "#         if check1 == check2:\n",
    "#             pass\n",
    "#         else:\n",
    "#             print(\"checking fails with:\", check1, check2)\n",
    "\n",
    "#     return shares, commitments, verifications\n",
    "    return shares,None,None\n",
    "\n",
    "\n",
    "def f(x, secrets, zs, betas, q):\n",
    "    y = Decimal('0')\n",
    "    for i, s in enumerate(secrets):\n",
    "        beta_i = Decimal(str(betas[i]))\n",
    "        prod = Decimal('1')\n",
    "        for beta in betas:\n",
    "            if beta != int(beta_i):\n",
    "                prod *= (Decimal(str(x))-Decimal(str(beta)))/(beta_i-Decimal(str(beta)))\n",
    "            else:pass\n",
    "        y += Decimal(str(s)) * prod\n",
    "        y = Decimal(round(y)%q)\n",
    "    k = len(secrets)\n",
    "    for j, z in enumerate(zs):\n",
    "        beta_j = Decimal(str(betas[k + j]))\n",
    "        prod = Decimal('1')\n",
    "        for beta in betas:\n",
    "            if beta != int(beta_j):\n",
    "                prod *= (Decimal(str(x)) - Decimal(str(beta))) / (beta_j - Decimal(str(beta)))\n",
    "            else:pass\n",
    "        y += Decimal(str(z)) * prod \n",
    "        y = Decimal(round(y)%q)\n",
    "    return int(y)\n",
    "\n",
    "def reconstruct_secret(pool, q, betas, K):\n",
    "    out = []\n",
    "    x_s,y_s = [],[]\n",
    "    for share in pool:\n",
    "        x_s.append(share[0])\n",
    "        y_s.append(share[1])\n",
    "    for k in range(K):\n",
    "        beta = betas[k]\n",
    "        # out.append(f_rec(beta,pool,q))\n",
    "        out.append(_lagrange_interpolate(beta, x_s, y_s, q))\n",
    "    return out\n",
    "\n",
    "def f_rec(x, pool, q):\n",
    "    y = Decimal('0')\n",
    "    for i, s in enumerate(pool):\n",
    "        alpha_i, share_i = pool[i]\n",
    "        prod = Decimal('1')\n",
    "        for share in pool:\n",
    "            if share_i != share[1]:\n",
    "                prod *= (Decimal(str(x))-Decimal(str(share[0]))) / (Decimal(str(alpha_i))-Decimal(str(share[0])))\n",
    "            else:pass\n",
    "        y += Decimal(str(share_i)) * prod\n",
    "        y = Decimal(int(y)%q)\n",
    "    return int(y)\n",
    "\n",
    "def _lagrange_interpolate(x, x_s, y_s, p):\n",
    "    \"\"\"\n",
    "    Find the y-value for the given x, given n (x, y) points;\n",
    "    k points will define a polynomial of up to kth order.\n",
    "    \"\"\"\n",
    "    k = len(x_s)\n",
    "    assert k == len(set(x_s)), \"points must be distinct\"\n",
    "    def PI(vals):  # upper-case PI -- product of inputs\n",
    "        accum = 1\n",
    "        for v in vals:\n",
    "            accum *= v\n",
    "        return accum\n",
    "    nums = []  # avoid inexact division\n",
    "    dens = []\n",
    "    for i in range(k):\n",
    "        others = list(x_s)\n",
    "        cur = others.pop(i)\n",
    "        nums.append(PI(x - o for o in others))\n",
    "        dens.append(PI(cur - o for o in others))\n",
    "    den = PI(dens)\n",
    "    num = sum([_divmod(nums[i] * den * y_s[i] % p, dens[i], p)\n",
    "               for i in range(k)])\n",
    "    return (_divmod(num, den, p) + p) % p\n",
    "\n",
    "def _extended_gcd(a, b):\n",
    "    \"\"\"\n",
    "    Division in integers modulus p means finding the inverse of the\n",
    "    denominator modulo p and then multiplying the numerator by this\n",
    "    inverse (Note: inverse of A is B such that A*B % p == 1) this can\n",
    "    be computed via extended Euclidean algorithm\n",
    "    http:https://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Computation\n",
    "    \"\"\"\n",
    "    x = 0\n",
    "    last_x = 1\n",
    "    y = 1\n",
    "    last_y = 0\n",
    "    while b != 0:\n",
    "        quot = a // b\n",
    "        a, b = b, a % b\n",
    "        x, last_x = last_x - quot * x, x\n",
    "        y, last_y = last_y - quot * y, y\n",
    "    return last_x, last_y\n",
    "\n",
    "def _divmod(num, den, p):\n",
    "    \"\"\"Compute num / den modulo prime p\n",
    "\n",
    "    To explain what this means, the return value will be such that\n",
    "    the following is true: den * _divmod(num, den, p) % p == num\n",
    "    \"\"\"\n",
    "    inv, _ = _extended_gcd(den, p)\n",
    "    return num * inv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "========Main LCC Starts==========\n",
      "q = 100003\n",
      "\n",
      "q is prime\n",
      "\n",
      "r = 42\n",
      "p = 4200127\n",
      "\n",
      "p is prime\n",
      "\n",
      "\n",
      "g = 2450215\n",
      "\n",
      "Original Secret: [422, 378, 1101]\n",
      "Shares: (1, 96927), (2, 39211), (3, 81959), (4, 93396), (5, 89295), (6, 16014), (7, 33548), (8, 98560), (9, 47427), (10, 79298), (11, 39116), (12, 679), (13, 49677), (14, 66729), (15, 10435)\n",
      "Combining shares: (12, 679), (13, 49677), (3, 81959), (8, 98560), (10, 79298), (1, 96927)\n",
      "reconstruct_secret: [422, 378, 1101]\n",
      "time cost in second: 5.603201150894165\n"
     ]
    }
   ],
   "source": [
    "\n",
    "# initialization\n",
    "time_start = time.time()\n",
    "print(\"========Main LCC Starts==========\")\n",
    "p,q,r,g = initial(10**5)\n",
    "\n",
    "# Secret taken from the group Z_q* \n",
    "T, N, K = 3, 15, 3\n",
    "secrets = [422,378,1101]\n",
    "print(f'Original Secret: {secrets}')\n",
    "\n",
    "# Phase I: Generation of shares\n",
    "alphas = list(range(1, 1+N))\n",
    "betas = list(range(1+N, N+K+T+1))\n",
    "shares, commitments, verifications= generate_shares(N, T, K, secrets, p, q, r, g, alphas, betas)\n",
    "print(f'Shares: {\", \".join(str(share) for share in shares)}')\n",
    "# print(f'Commitments: {\", \".join(str(commitment) for commitment in commitments)}')\n",
    "# print(f'verifications: {\", \".join(str(verification) for verification in verifications)}')\n",
    "\n",
    "# Phase II: Secret Reconstruction\n",
    "# Picking t shares randomly for reconstruction\n",
    "pool = random.sample(shares, T+K)\n",
    "print(f'Combining shares: {\", \".join(str(share) for share in pool)}')\n",
    "secret_reconstructed = reconstruct_secret(pool, q, betas, K)\n",
    "print(\"reconstruct_secret:\",secret_reconstructed)\n",
    "\n",
    "time_end = time.time()\n",
    "print('time cost in second:', time_end-time_start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(100, Decimal('100'))"
      ]
     },
     "execution_count": 117,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = 1009\n",
    "a % 101, Decimal(str(a)) % 101"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}