BitcoinEllipticCurveCryptography.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1>Elliptic Curve Cryptography</h1>\n",
    "<p>\n",
    "Elliptic curve equation: <br>\n",
    "y^2 = x^3 + ax + b <br>\n",
    "where a,b are such that the discriminant is nonzero: <br>\n",
    "-16(4a^3 + 27b^2) != 0\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "<h2> Plotting Elliptic Curve</h2>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "92eefc2b63a1450e927aeec68465492e"
      }
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "<function __main__.elliptic_curve>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from ipywidgets import interact\n",
    "\n",
    "def elliptic_curve(a: int, b: int):\n",
    "    y, x = np.ogrid[-5:5:100j, -5:5:100j]\n",
    "    plt.contour(x.ravel(), y.ravel(), pow(y, 2) - pow(x, 3) - x * a - b, [0])\n",
    "    plt.grid()\n",
    "    plt.show()\n",
    "\n",
    "interact(elliptic_curve, a=(0,10), b=(0,10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "<h2> Elliptic Curve Characteristics</h2>\n",
    "<p>\n",
    "<ul>\n",
    "<li> A line intersecting elliptic curve at two points will also intersect it at third point except when the line is verticle or it is a tangent.</li>\n",
    "<li> Characteristics of point on elliptic curve:</li>\n",
    "<ul>\n",
    "<li> P + 0 = 0 + P = P for all P ∈ E </li>\n",
    "<li> P + (−P) = 0 for all P ∈ E </li>\n",
    "<li> P + (Q + R) = (P + Q) + R for all P, Q, R ∈ E </li>\n",
    "<li> P + Q = Q + P for all P, Q ∈ E </li>\n",
    "</ul>\n",
    "<li> Point Adding </li>\n",
    "<ul>\n",
    "<li> P + Q + R = 0 for all P, Q, R ∈ E and for all P, Q, R ∈ L</li>\n",
    "</ul>\n",
    "<li> Point Doubling </li>\n",
    "<ul>\n",
    "<li> P is tangent on E i.e. P = Q </li>\n",
    "<li> 2P + R = 0 for all P, Q, R ∈ E\n",
    "</ul>\n",
    "<li> Characteristics of a line </li>\n",
    "<ul>\n",
    "<li> Line (L) : y = λx + ν </li>\n",
    "<li> Slope λ: <br>\n",
    "P1 = (x1, y1) and P2 = (x2, y2)<br>\n",
    "λ = (y2-y1)/(x2-x1)<br>\n",
    "</li>\n",
    "</ul>\n",
    "<li> Calculating slope for points on Elliptic curve </li>\n",
    "<ul>\n",
    "<li> For P1 != P2 </li>\n",
    "λ = (y2-y1)/(x2-x1)                           ---------------- (4) <br>\n",
    "<li> For P1 = P2 </li>\n",
    "y^2 = x^3 + ax + b <br>\n",
    "Differentiating both sides: <br>\n",
    "=> d(y^2) = d(x^3 + ax + b) <br>\n",
    "=> 2ydy = (3x^2 + a)dx <br>\n",
    "=> λ = dy/dx = (3x^2 + a)/2y                   ---------------- (3)\n",
    "</ul>\n",
    "<li> Deriving Formula for point Adding i.e. P1 != P2 </li>\n",
    "E : y^2 = x^3 + Ax + B and L : y = λx + ν <br>\n",
    "By substituting y from L: <br>\n",
    "=> (λx + ν)^2 = x^3 + Ax + B <br>\n",
    "=> x^3 + Ax + B − (λx + ν)^2 = 0                                 ----------------- (1) <br>\n",
    "Since x is on elliptic curve as well as line it is either x1, x2, or x3 <br>\n",
    "=> x - x1 = 0 or x - x2 = 0 or x - x3 = 0 where x1, x2, x3, x ∈ E and L <br>\n",
    "=> (x - x1)(x - x2)(x - x3) = 0  where x1, x2, x3, x ∈ E and L   ------------------ (2) <br>\n",
    "Equating (1) and (2) <br>\n",
    "=> x^3 + Ax + B − (λx + ν)^2 = (x - x1)(x - x2)(x - x3) where x1, x2, x3, x ∈ E and L <br>\n",
    "=> x^3 + Ax + B − (λ^2*x^2 + 2νλx + ν^2) = x^3 - (x1 + x2 + x3)x^2 + ... <br>\n",
    "Matching multipiers of x^2 only <br> \n",
    "=> λ^2*x^2 = (x1 + x2 + x3)x^2 <br>\n",
    "=> λ^2 = x1 + x2 + x3 <br>\n",
    "=> x3 = λ^2 - x1 - x2                           ------------------ (5) <br>\n",
    "Using slope formula: λ = (y2-y1)/(x2-x1) <br>\n",
    "=> λ = (y1-y3)/(x1-x3) <br>\n",
    "Since R = (x3, -y3) <br>\n",
    "λ = (y1+yr)/(x1-xr) <br>\n",
    "=> λ (x1 - xr) = (y1+yr) <br>\n",
    "=> yr = λ (x1 - xr) - y1              -----------------------(6) <br>\n",
    "From (5): <br>\n",
    "xr = λ^2 - x1 - x2                   -----------------------(7) <br>\n",
    "We have (4), (6) and (7) to perform point adding  <br>\n",
    "<li> Deriving Formula for point Doubling i.e. P1 = P2 </li>\n",
    "From (3) <br>\n",
    "λ = (3x^2 + a)/2y <br>\n",
    "From (7) i.e. xr = λ^2 - x1 - x2 <br>\n",
    "=> xr = λ^2 - 2x1            ------------- (8) <br>\n",
    "From (6) <br>\n",
    "yr = λ (x1 - xr) - y1 <br>\n",
    "We have (3), (8) and (6) to perform point doubling\n",
    "</ul>\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/add-points.png\",width=400,height=400>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "<h2> Scalar Multiplication with a Point </h2>\n",
    "<p>\n",
    "To calculate mP:<br>\n",
    "m = m0 + m1\\*2^1 + m2\\*2^2 + · · · + mr\\*2^r where m0 , . . . , mr ∈ {0, 1}<br>\n",
    "mP = m0\\*P + m1\\*P\\*2 + m2\\*P\\*2^2 + · · · + mr\\*P\\*2^r where 2^k\\*P requires k doublings<br>\n",
    "</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def point_mul(p, m):\n",
    "    n = p\n",
    "    q = None\n",
    "\n",
    "    for i in range(256):\n",
    "        if m & (1 << i):\n",
    "            if q is None:\n",
    "                q = n\n",
    "            else:\n",
    "                q = point_add(q, n)\n",
    "\n",
    "        n = point_add(n, n)\n",
    "\n",
    "    return q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2> Elliptic curve in finite field </h2>\n",
    "<p>\n",
    "Elliptic curve E is reduced by modulo prime P.<br>\n",
    "Finite field created by modulo prime P is denoted by Ƒp <br>\n",
    "=> Ě: y^2 = x^3 + Ăx + Ḃ where Ă,Ḃ ∈ Ƒp\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Point adding in Finite field Elliptic Curve </h3>\n",
    "<p>\n",
    "From (4)<br>\n",
    "λ = (yq-yp)/(xq-xp) % P<br>\n",
    "To obtain λ we need to find multiplicative-inverse of (xq-xp) in finite field<br>\n",
    "=> (yq-yp) \\* Multiplicate-Inverse(xq-xp) % P<br>\n",
    "########### <br>\n",
    "Multiplicative inverse i of a number N in finite field is calculated by :<br>\n",
    "N * i % P = 1 <br>\n",
    "since N^(P-1) % P = 1 <br>\n",
    "=> i = N^(P-2) <br>\n",
    "=> (1/N) % P = N^(P-2) % P <br>\n",
    "########## <br>\n",
    "=> ((yq-yp) \\* ((xq-xp)^(P - 2) % P)) % P<br>\n",
    "From (7)<br>\n",
    "xr = (λ^2 - xp - xq) % P <br>\n",
    "From (6)<br>\n",
    "yr = (λ (xp - xr) - yp) % P"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Point doubling in Finite field Elliptic Curve </h3>\n",
    "<p>\n",
    "From (3) <br>\n",
    "λ = (3xp^2 + a)/2yp <br>\n",
    "=> λ = (3xp^2 + a) \\* pow(2*yp % P, P - 2, P) % P <br>\n",
    "From (8) <br>\n",
    "xr = (λ^2 - 2xp) % P  <br>\n",
    "From (6) <br>\n",
    "yr = (λ (xp - xr) - yp) % P\n",
    "</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def point_add(p, q):\n",
    "    global a # a = 0 incase of bitcoin\n",
    "    xp, yp = p\n",
    "    xq, yq = q\n",
    "\n",
    "    # point doubling \n",
    "    if p == q:\n",
    "        l = pow(2 * yp % P, P - 2, P) * (3 * xp * xp + a) % P\n",
    "    # point adding\n",
    "    else:\n",
    "        l = pow(xq - xp, P - 2, P) * (yq - yp) % P\n",
    "\n",
    "    xr = (l ** 2 - xp - xq) % P\n",
    "    yr = (l * xp - l * xr - yp) % P\n",
    "\n",
    "    return xr, yr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1> Bitcoin Elliptical Curve Cryptography </h1>\n",
    "<p> Bitcoin uses sec256k1 Elliptical Curve.<br>\n",
    "Elliptic curve domain parameters over Ƒp are a sextuple: T = (p, a, b, G, n, h)<br>\n",
    "Where: <br>\n",
    "<ul>\n",
    "<li> p is Modulo Prime</li>\n",
    "<li> G is point on E(Ƒp)</li>\n",
    "<li> n is the order of the basepoint G. It is the number of points the basepoint generates under repeated addition:<br>\n",
    "nG = Identity Point (O). Identity Point O is sush that O + G = G. </li>\n",
    "<li> h is the cofactor of basepoint G. It is the order of the entire group (number of points on the curve) divided by the order of basepoint G. </li>\n",
    "</ul>\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2> Constants </h2>\n",
    "<p> The elliptic curve domain parameters over Ƒp associated with a Koblitz curve secp256k1 are\n",
    "specified by the sextuple T = (p, a, b, G, n, h) where the finite field Ƒp is defined by </p>\n",
    "<ul>\n",
    "<li> \n",
    "p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE\n",
    "FFFFFC2F <br>\n",
    "  = 2^256 − 2^32 − 2^9 − 2^8 − 2^7 − 2^6 − 2^4 − 1 \n",
    "</li>\n",
    "<li>\n",
    "The curve E: y^2 = x^3 + ax + b over Ƒp is defined by:\n",
    "a = 0 <br>\n",
    "b = 7 <br>\n",
    "=> Curve E: y^2 = x^3 + 7 over Ƒp\n",
    "</li>\n",
    "<li>\n",
    "The base point G in compressed form is:<br>\n",
    "G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798\n",
    "</li>\n",
    "<li>\n",
    "The base point G in uncompressed form is:<br>\n",
    "G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8\n",
    "</li>\n",
    "<li>\n",
    "The order n of G and the cofactor are:<br>\n",
    "n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141<br>\n",
    "h = 1\n",
    "</li>\n",
    "</ul>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import binascii\n",
    "\n",
    "# Bitcoin Secp256k1 constants [\n",
    "# generator point\n",
    "G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,\n",
    "     0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)\n",
    "\n",
    "# field prime\n",
    "P = 2 ** 256 - 2 ** 32 - 2 ** 9 - 2 ** 8 - 2 ** 7 - 2 ** 6 - 2 ** 4 - 1\n",
    "\n",
    "# order\n",
    "N = (1 << 256) - 0x14551231950B75FC4402DA1732FC9BEBF\n",
    "\n",
    "a = 0\n",
    "b = 7"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2> Key Generation </h2>\n",
    "<p> K = k \\* G where G is generator point, k is Private Key(a scalar), K is Public Key ∈ Ƒp </p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "4a3c25a9bbcd462c9ab7192210bcc88f"
      }
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import ipywidgets as widgets\n",
    "from IPython.display import display \n",
    "import binascii\n",
    "\n",
    "def privkey2pubkey(k: int):\n",
    "    global G\n",
    "    K = point_mul(G, k)\n",
    "    return K\n",
    "\n",
    "privkey = widgets.Text(description = 'Private Key')\n",
    "privkey"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "04 fcd4e9e28c13690ecff0c74633626be73c261f376b6e112ec82ad691b17c13dd 7908b8ec3209477496405fc0c51585df9d43fcf2c637e5586777768f39827d0b\n"
     ]
    }
   ],
   "source": [
    "pubkey = privkey2pubkey(int(privkey.value, 16))\n",
    "print('04 %x %x' % (pubkey[0], pubkey[1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "<h2> Message Signing </h2>\n",
    "<p> Steps to get Signature </p>\n",
    "<ul>\n",
    "<li> Calculate e=dSHA256(m), where dSHA256 is Double SHA-256 Hash function </li>\n",
    "<li> z is left most bit of e </li>\n",
    "<li> Select random number k from [1,n-1] ----------------- (1) </li>\n",
    "<li> (x, y) = k \\* G </li>\n",
    "<li> Calculate r=x mod n. If r=0, go back to (1) </li>\n",
    "<li> Calculate s=(k^(-1) \\* (z+r \\* privkey)) mod n. If s=0, go back to step 3 </li>\n",
    "<li> The signature is the pair (r,s) </li>\n",
    "</ul>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2> Signature Verification </h2>\n",
    "<p> Steps to verify Signature </p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2> Compressing/Uncompressing Point on Elliptic Curve secp256k1 </h2>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Compressing Point </h3>\n",
    "<p>\n",
    "For a given x0 there are two values of y i.e. y0, -y0 <br>\n",
    "In finite field Ƒp: <br>\n",
    "The two values of y are y0 and P - y0 <br>\n",
    "This gives us equation: y1 = P - y0 <br>\n",
    "Since P is odd in secp256k1 for any given x: y is either odd or even. <br>\n",
    "So y is removed by adding prefix denoting whether y is odd or even. <br>\n",
    "0x02 prefix denote y is even and 0x03 prefix denote y is odd. <br>\n",
    "0x04 prefix denote point is uncompressed.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "6e81e321819442e68344276458ce1050"
      }
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import ipywidgets as widgets\n",
    "from IPython.display import display \n",
    "import binascii\n",
    "\n",
    "def compressPubkey(pubkey: bytes):\n",
    "    if pubkey[0:1] == b'\\x04':\n",
    "        x_b = pubkey[1:33]\n",
    "        y_b = pubkey[33:65]\n",
    "        if (y_b[31] & 0x01) == 0: # even\n",
    "                compressed_pubkey = b'\\x02' + x_b\n",
    "        else:\n",
    "                compressed_pubkey = b'\\x03' + x_b\n",
    "    elif pubkey[0:1] == b'\\x02' or pubkey[0:1] == b'\\x03':\n",
    "        compressed_pubkey = pubkey\n",
    "    else:\n",
    "        raise ValueError('Invalid Elliptic Curve Point prefix %s' % pubkey[0])\n",
    "    return compressed_pubkey\n",
    "\n",
    "pubkey_s = widgets.Text(description = 'Public Key')\n",
    "pubkey_s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0250863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352\n"
     ]
    }
   ],
   "source": [
    "compressed_pubkey = compressPubkey(binascii.unhexlify(pubkey_s.value))\n",
    "compressed_pubkey_s = bytes.decode(binascii.hexlify(compressed_pubkey))\n",
    "print(compressed_pubkey_s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Uncompressing Point </h3>\n",
    "<p>\n",
    "Curve E: y^2 = x^3 + 7 over Ƒp <br>\n",
    "and P % 4 = 3 <br>\n",
    "=> y % p = y^(2*(p + 1)/4) % p <br>\n",
    "</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "e5e6ade26d2e4d989461d337f05fe47d"
      }
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import ipywidgets as widgets\n",
    "from IPython.display import display \n",
    "import binascii\n",
    "\n",
    "# field prime\n",
    "P = 2 ** 256 - 2 ** 32 - 2 ** 9 - 2 ** 8 - 2 ** 7 - 2 ** 6 - 2 ** 4 - 1\n",
    "\n",
    "def uncompressPubkey(x_b: bytes):\n",
    "        prefix = x_b[0:1]\n",
    "        x_b = x_b[1:33]\n",
    "        x = int.from_bytes(x_b, byteorder='big')\n",
    "\n",
    "        y_square = (pow(x, 3, P)  + 7) % P\n",
    "        y_square_square_root = pow(y_square, ((P+1) >> 2), P)\n",
    "        if (prefix == b\"\\x02\" and y_square_square_root & 1) or (prefix == b\"\\x03\" and not y_square_square_root & 1):\n",
    "            y = (-y_square_square_root) % P\n",
    "        else:\n",
    "            y = y_square_square_root\n",
    "\n",
    "        y_b = y.to_bytes(32, 'big')\n",
    "        full_pubkey_b = b''.join([b'\\x04', x_b, y_b])\n",
    "        return full_pubkey_b\n",
    "    \n",
    "pubkey_s = widgets.Text(description = 'Public Key')\n",
    "pubkey_s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0450863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b23522cd470243453a299fa9e77237716103abc11a1df38855ed6f2ee187e9c582ba6\n"
     ]
    }
   ],
   "source": [
    "uncompressed_pubkey = uncompressPubkey(binascii.unhexlify(pubkey_s.value))\n",
    "uncompressed_pubkey_s = bytes.decode(binascii.hexlify(uncompressed_pubkey))\n",
    "print(uncompressed_pubkey_s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.6.1"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}