python/notebooks/ECDSA.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "e9b83408",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import hashlib"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "0254bfb3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# y^2 = x^3 + a*x + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "48638cc0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def add_points(P, Q, p):\n",
    "    x1, y1 = P\n",
    "    x2, y2 = Q\n",
    "    \n",
    "    if x1 == x2 and y1 == y2:\n",
    "        beta = (3*x1*x2 + a) * pow(2*y1, -1, p)\n",
    "    else:\n",
    "        beta = (y2 - y1) * pow(x2 - x1, -1, p)\n",
    "    \n",
    "    x3 = (beta*beta - x1 - x2) % p\n",
    "    y3 = (beta * (x1 - x3) - y1) % p\n",
    "    \n",
    "    is_on_curve((x3, y3), p)\n",
    "        \n",
    "    return x3, y3\n",
    "\n",
    "def is_on_curve(P, p):\n",
    "    x, y = P\n",
    "    assert (y*y) % p == ( pow(x, 3, p) + a*x + b ) % p\n",
    "    \n",
    "def apply_double_and_add_method(G, k, p):\n",
    "    target_point = G\n",
    "    \n",
    "    k_binary = bin(k)[2:] #0b1111111001\n",
    "    \n",
    "    for i in range(1, len(k_binary)):\n",
    "        current_bit = k_binary[i: i+1]\n",
    "        \n",
    "        # doubling - always\n",
    "        target_point = add_points(target_point, target_point, p)\n",
    "        \n",
    "        if current_bit == \"1\":\n",
    "            target_point = add_points(target_point, G, p)\n",
    "    \n",
    "    is_on_curve(target_point, p)\n",
    "    \n",
    "    return target_point"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "06aca653",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Secp256k1\n",
    "a = 0; b = 7\n",
    "G = (55066263022277343669578718895168534326250603453777594175500187360389116729240, \n",
    "     32670510020758816978083085130507043184471273380659243275938904335757337482424)\n",
    "\n",
    "p = pow(2, 256) - pow(2, 32) - pow(2, 9) - pow(2, 8) - pow(2, 7) - pow(2, 6) - pow(2, 4) - pow(2, 0)\n",
    "n = 115792089237316195423570985008687907852837564279074904382605163141518161494337"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "565de55b",
   "metadata": {},
   "outputs": [],
   "source": [
    "is_on_curve(G, p)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd0db79f",
   "metadata": {},
   "source": [
    "# Alice generates her private and public key pair"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "b7c79f82",
   "metadata": {},
   "outputs": [],
   "source": [
    "# private key of Alice\n",
    "d = random.getrandbits(256)\n",
    "\n",
    "# public key of Alice\n",
    "Q = apply_double_and_add_method(G = G, k = d, p = p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "232ff1e9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13433848042164743573906504080612824839915133641008164720264532415569497568864"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "403eea53",
   "metadata": {},
   "outputs": [],
   "source": [
    "# random_key = random.getrandbits(256)\n",
    "random_point = apply_double_and_add_method(G = G, k = random_key, p = p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "8657b41a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2549423989004030740645076493356421339477309545835940582037060479260904522953"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random_key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "58a3e6da",
   "metadata": {},
   "outputs": [],
   "source": [
    "# message = b\"ECC beats RSA\"\n",
    "message = b\"ECC beats Diffie-Hellman, too!\"\n",
    "hash_hex = hashlib.sha1(message).hexdigest()\n",
    "hash_int = int(hash_hex, 16)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "31351b55",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "531204124611006148816545464087066627965678629689"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hash_int"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c195cab",
   "metadata": {},
   "source": [
    "# Sign"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "c349a76e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# (r, s)\n",
    "r = ( random_point[0] ) % n\n",
    "s = ( ( hash_int + r * d ) * pow(random_key, -1, n) ) % n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "4b826714",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "76058233759865599401027122649904720385258380809806134291104208040832864904366"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "dd2f4f9f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8856213573513779368811935123774923867490066008725770383186210144604547226738"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78e583fb",
   "metadata": {},
   "source": [
    "# Verification"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c14a8962",
   "metadata": {},
   "outputs": [],
   "source": [
    "w = pow(s, -1, n)\n",
    "u1 = apply_double_and_add_method(G = G, k = ( hash_int * w ) % n, p = p)\n",
    "u2 = apply_double_and_add_method(G = Q, k = ( r * w ) % n, p = p)\n",
    "\n",
    "# u1 + u2\n",
    "checkpoint = add_points(P = u1, Q = u2, p = p)\n",
    "\n",
    "assert checkpoint[0] == r"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6d85ae7",
   "metadata": {},
   "source": [
    "# Attacking\n",
    "\n",
    "If 2 messages were signed with same random key, an attacker can extract sender's private key!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bcb32f98",
   "metadata": {},
   "outputs": [],
   "source": [
    "# s1 = ( h1 + r * d ) * random_key ^ -1\n",
    "# s2 = ( h2 + r * d ) * random_key ^ -1\n",
    "# s1 - s2 = ( h1 + r * d ) * random_key ^ -1 - ( h2 + r * d ) * random_key ^ -1\n",
    "# s1 - s2 = random_key ^ -1 * (h1 + r * d - h2 - r * d )\n",
    "# s1 - s2 =  random_key ^ -1 * (h1 - h2)\n",
    "# (s1 - s2) / (h1 - h2) = random_key ^ -1\n",
    "# (h1 - h2) / (s1 - s2) = random_key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "165da141",
   "metadata": {},
   "outputs": [],
   "source": [
    "s1 = 8044708637677890244949153424877160784554741168781389939176486503430395752522\n",
    "h1 = 320026739459778556085970613903841025917693204146\n",
    "\n",
    "s2 = 8856213573513779368811935123774923867490066008725770383186210144604547226738\n",
    "h2 = 531204124611006148816545464087066627965678629689"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "cc222647",
   "metadata": {},
   "outputs": [],
   "source": [
    "random_key_prime = ( ( (h1 - h2) % n ) * pow(s1 - s2, -1, n) ) % n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "39ab430d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2549423989004030740645076493356421339477309545835940582037060479260904522953"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random_key_prime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "d7ebcef3",
   "metadata": {},
   "outputs": [],
   "source": [
    "assert random_key == random_key_prime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "940f75a3",
   "metadata": {},
   "outputs": [],
   "source": [
    "random_point_prime = apply_double_and_add_method(G = G, k = random_key_prime, p = p)\n",
    "r_prime = random_point_prime[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "83ce26ee",
   "metadata": {},
   "outputs": [],
   "source": [
    "assert r_prime == r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "afeaac82",
   "metadata": {},
   "outputs": [],
   "source": [
    "# s1 = ( h1 + r * d ) * random_key ^ -1\n",
    "# s1 * random_key = h1 + r * d\n",
    "# s1 * random_key - h1 = r * d\n",
    "# (s1 * random_key - h1) / r = d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "6aa860c9",
   "metadata": {},
   "outputs": [],
   "source": [
    "d_prime = ( (s1 * random_key_prime - h1) * pow(r, -1, n) ) % n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "1fc87b87",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13433848042164743573906504080612824839915133641008164720264532415569497568864"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d_prime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "5bde09bf",
   "metadata": {},
   "outputs": [],
   "source": [
    "assert d_prime == d"
   ]
  }
 ],
 "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": 5
}