blind_signatures.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [],
   "source": [
    "import math\n",
    "import random\n",
    "from sympy import randprime, isprime, Mod\n",
    "import hashlib\n",
    "\n",
    "def egcd(a, b):\n",
    "    if a == 0:\n",
    "        return (b, 0, 1)\n",
    "    else:\n",
    "        g, y, x = egcd(b % a, a)\n",
    "        return (g, x - (b // a) * y, y)\n",
    "\n",
    "def modinv(a, m):\n",
    "    g, x, y = egcd(a, m)\n",
    "    if g != 1:\n",
    "        raise Exception('modular inverse does not exist')\n",
    "    else:\n",
    "        return x % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [],
   "source": [
    "def GenModulus(w):\n",
    "    n = len(w) // 2\n",
    "    p = randprime(2 ** n, 2 ** (n+1))\n",
    "    q = randprime(2 ** n, 2 ** (n+1))\n",
    "    N = p * q\n",
    "    return N, p, q\n",
    "\n",
    "def randomZnElement(N):\n",
    "    g = N\n",
    "    while math.gcd(g, N) != 1:\n",
    "        g = random.randint(2, N)\n",
    "    return g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [],
   "source": [
    "def GenRSA(w):\n",
    "    n = len(w)\n",
    "    N, p, q = GenModulus(w)\n",
    "    m = (p-1) * (q-1)\n",
    "    e = 2 ** 16 + 1\n",
    "    d = modinv(e, m)\n",
    "    return N, e, d, p, q\n",
    "\n",
    "def enc(x, N, e):\n",
    "    return x ** e % N\n",
    "\n",
    "def dec(c, N, d):\n",
    "    return c ** d % N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [],
   "source": [
    "def sign(m, N, d):\n",
    "    sigma = m ** d % N\n",
    "    return sigma\n",
    "    \n",
    "def vrfy(m, s, N, e):\n",
    "    return s == (m ** e % N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [],
   "source": [
    "N, e, d, p, q = GenRSA(\"11111111\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [],
   "source": [
    "m = randomZnElement(N)\n",
    "\n",
    "def h(m, N):\n",
    "    return (3 * m + 1) % N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "327 520 667\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = sign(m, N, d)\n",
    "\n",
    "print(m, s, N)\n",
    "\n",
    "vrfy(m, s, N, e)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "cannot assign to function call (<ipython-input-32-899cfa78bcbd>, line 4)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-32-899cfa78bcbd>\"\u001b[0;36m, line \u001b[0;32m4\u001b[0m\n\u001b[0;31m    s = sign(m1 * m2, N, d) = s1 * s2\u001b[0m\n\u001b[0m        ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m cannot assign to function call\n"
     ]
    }
   ],
   "source": [
    "s1 = sign(m1, N, d)\n",
    "s2 = sing(m2, N, d)\n",
    "\n",
    "#s = sign(m1 * m2, N, d) = s1 * s2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "\"Regular signatures\"\n",
    "\n",
    "- signer (someone who has a private key needst to learn a meesage that he is about to sign)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "\"Blind signatures\"\n",
    "\n",
    "- signer (does not know what he is about to sign)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "327 520\n"
     ]
    }
   ],
   "source": [
    "s = sign(m, N, d)\n",
    "\n",
    "vrfy(m, s, N, e)\n",
    "print(m, s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [],
   "source": [
    "def blindSgn1(m, e, N):\n",
    "    # generate blinding factor:\n",
    "    r = randomZnElement(N)\n",
    "    return m * (r ** e % N) % N,  r\n",
    "    \n",
    "def blindSign2(s, e, N, r):\n",
    "    rinv = modinv(r, N)\n",
    "    return s * rinv  % N "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "78 481\n",
      "662\n",
      "327 520\n"
     ]
    }
   ],
   "source": [
    "s1, r = blindSgn1(m, e, N)\n",
    "s2 = sign(s1, N, d)\n",
    "s = blindSign2(s2, e, N, r)\n",
    "print(s1, r)\n",
    "print(s2)\n",
    "print(m, s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vrfy(m, s, N, e)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decSec(c, N, d, e):\n",
    "    r = randomZnElement(N)\n",
    "    mp = dec((c * (r ** e % N)) % N, N, d)\n",
    "    rinv = modinv(r, N)\n",
    "    return (mp * rinv) % N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "327 474 60\n"
     ]
    }
   ],
   "source": [
    "c = enc(m, N, e)\n",
    "d = dec(c, N, d)\n",
    "print(m, c, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "327 474 240\n"
     ]
    }
   ],
   "source": [
    "c = enc(m, N, e)\n",
    "d = decSec(c, N, d, e)\n",
    "print(m, c, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1688993, 2040139)"
      ]
     },
     "execution_count": 105,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "N, e, d, p, q = GenRSA(\"11111111111111111111\")\n",
    "d, N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 757197, -230939)"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m = random.randint(2, N)\n",
    "egcd(m, N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "831786\n"
     ]
    }
   ],
   "source": [
    "y = enc(m, N, e)\n",
    "print(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "622226 622226 True\n"
     ]
    }
   ],
   "source": [
    "x = dec(y, N, d)\n",
    "print(x, m, x == m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1688993 21 110011100010110100001\n"
     ]
    }
   ],
   "source": [
    "d_bin = \"{0:b}\".format(d)\n",
    "print(d, len(d_bin), d_bin)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2609737 22 1001111101001001001001\n"
     ]
    }
   ],
   "source": [
    "NN, ee, dd, pp, qq = GenRSA(\"11111111111111111111\")\n",
    "dd_bin = \"{0:b}\".format(dd)\n",
    "print(dd, len(dd_bin), dd_bin)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [],
   "source": [
    "def fast_pow(c, N, d):\n",
    "    d_bin = \"{0:b}\".format(d)\n",
    "    d_len = len(d_bin)\n",
    "    reductions = 0\n",
    "    h = 0\n",
    "    x = c\n",
    "    for j in range(1, d_len):\n",
    "        x, r = mod_reduce(x ** 2, N)\n",
    "        reductions = reductions + r\n",
    "        if d_bin[j] == \"1\":\n",
    "            x, r = mod_reduce(x * c, N)\n",
    "            reductions = reductions + r\n",
    "            #print(\"A\")\n",
    "            h = h + 1\n",
    "    return x, h, reductions\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [],
   "source": [
    "def mod_reduce(a, b):\n",
    "    r = 0\n",
    "    if a >= b:\n",
    "        a = a % b\n",
    "        r = 1\n",
    "        #print(\"\\tB\")\n",
    "    return a, r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [],
   "source": [
    "y = random.randint(2, N)\n",
    "x, h, r = fast_pow(y, N, d)\n",
    "h, r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. y: $ y^3 < N$ ----> if $d[1] == 0/1$ --> no reduction in the first round of the for loop\n",
    "2. z: $ z^2 < N < z^3$ ---> $d[i] == 1$ --> ther IS a reduction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(9, 27)"
      ]
     },
     "execution_count": 174,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y = random.randint(2, math.floor(N ** (1/3)))\n",
    "x, h, r = fast_pow(y, N, d)\n",
    "h, r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(9, 28)"
      ]
     },
     "execution_count": 175,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z = random.randint(math.floor(N ** (1/3)), math.floor(N ** (1/2)))\n",
    "x, h, r = fast_pow(z, N, d)\n",
    "h, r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10, 29)"
      ]
     },
     "execution_count": 176,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "yy = random.randint(2, math.floor(NN ** (1/3)))\n",
    "xx, hh, rr = fast_pow(yy, NN, dd)\n",
    "hh, rr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10, 30)"
      ]
     },
     "execution_count": 177,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "zz = random.randint(math.floor(NN ** (1/3)), math.floor(NN ** (1/2)))\n",
    "xx, hh, rr = fast_pow(zz, NN, dd)\n",
    "hh, rr"
   ]
  },
  {
   "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": 4
}