{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "from hashlib import sha1, sha256\n",
    "from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse\n",
    "from ecdsa import ellipticcurve\n",
    "from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key\n",
    "from random import randint"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Prerequisites"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- ecdsa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task**\n",
    "- Exploit the fact that 2 signatures corresponding to 2 different messages were crafted using the same nonce $k$\n",
    "\n",
    "We know \n",
    "- the order of the subgroup generated by $G$: $q$\n",
    "- messages: $m_1, m_2$ and their hashes $h_1, h_2$\n",
    "- the signatures were generated using the same $k$\n",
    "- signatures: $(r, s_1), (r, s_2)$ <= $r$ is the same since we use the same $k$ => $Q_1 = Q_2 = kG$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\n",
    "\\begin{equation}\n",
    "s_1 \\equiv k^{-1}(h_1 + dr) \\ mod \\ q \\\\\n",
    "s_2 \\equiv k^{-1}(h_2 + dr) \\ mod \\ q\n",
    "\\end{equation}$ \n",
    "\n",
    "Substract $s_2$ from $s_1$\n",
    "- $s_1 - s_2 \\equiv k^{-1}(h_1 + dr) - k^{-1}(h_2 + dr) \\equiv k^{-1}(h_1 - h_2) \\ mod \\ q =>  k \\equiv (h_1 - h_2)(s_1 - s_2)^{-1} \\ mod \\ q$\n",
    "\n",
    "Therefore we can calculate $d$\n",
    "- $d \\equiv (sk - h)r^{-1} \\ mod \\ q$\n",
    " \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "110293943109482154156062517946490981556599973730885811037950153262390807421596\n"
     ]
    }
   ],
   "source": [
    "#generate the parameters\n",
    "G = generator_256\n",
    "q = G.order()\n",
    "print(is_prime(q))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "#generate the public and private key\n",
    "d = randint(1, q-1)\n",
    "pubkey = Public_key(G, d*G)\n",
    "privkey = Private_key(pubkey, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "#hash the messages\n",
    "m1 = b'secret_message'\n",
    "m2 = b'another_one'\n",
    "h1 = bytes_to_long(sha256(m1).digest())\n",
    "h2 = bytes_to_long(sha256(m2).digest())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "#random k\n",
    "k = randint(1, q-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "sign1 = privkey.sign(h1, k)\n",
    "sign2 = privkey.sign(h2, k)\n",
    "\n",
    "s1, r1 = sign1.s, sign1.r\n",
    "s2, r2 = sign2.s, sign2.r\n",
    "print(r1 == r2) #check if the r's are equal\n",
    "\n",
    "r = r1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "k_decr = ((h1 - h2) * inverse((s1 - s2), q)) % q\n",
    "print(k_decr == k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "d_decr = ((s1 * k - h1) * inverse(r, q)) % q\n",
    "print(d_decr == d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Resources"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- https://github.com/ashutosh1206/Crypton/tree/master/Digital-Signatures/Elliptic-Curve-DSA/Attack-k-reuse\n",
    "- https://crypto.stackexchange.com/questions/64167/ecdsa-with-common-nonce\n",
    "- PS3, bitcoin wallet hacks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.1",
   "language": "sage",
   "name": "sagemath"
  },
  "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}